Všesměrový autentizační protokol TESLA

Autor: T. Vaněk <vanekt1(at)fel.cvut.cz>, Pracoviště: České vysoké učení technické v Praze, FEL , Téma: Bezpečnost, Vydáno dne: 30. 12. 2008

V tomto článku jsou popsány základní principy všesměrového autentizačního protokolu TESLA. V dalším dílu je na tomto protokolu demonstrována možnost simulace všesměrových protokolu pomocí modifikované BAN logiky.


TESLA - A Broadcast Authentication Protocol - Abstract:

This article describes basic properties and behaviour of the broadcast authentication protocol TESLA. This protocol can be used for one-way authentication of the messages that are sent to the multiple receivers simultaneously.


Úvod

Protokol TESLA (Time Efficient Stream Loss-tolerant Authentication) byl vyvinut za účelem autentizace všesměrového vysílání. Autentizace je u protokolu TESLA jednosměrná a jedná se o autentizaci zpráv vysílaných jedním vysílačem a přijímaných více příjemci.

Protocol TESLA vyžaduje časovou synchronizaci odesílatele a příjemce. Časová synchronizace je nutná k zabránění odchytávání a napodobování paketů. Důraz je kladen na mechanismus sloužící pro ověřování klíče vysílače. V protokolu TESLA jsou k ověřování používány takzvané jednosměrné řetězce. Jednosměrné řetězce (One-way chains – OWC) jsou řetězce výstupních hodnot z hashovací funkce. Používáme opakovaně jednu jednosměrnou hashovací funkci. Na obr. 1 je vidět, jak vysílač generuje řetězec pomocí náhodně vybraného prvku s a na něj opakovaně aplikuje jednosměrnou funkci F . Přijímač odkrývá hodnoty řetězce v opačném směru. K celému řetězci je nakonec navázán element s0, díky kterému můžeme následně zkontrolovat hodnotu každého elementu daného řetězce. Abychom dokázali, že daný element řetězce si je skutečným elementem s s indexem i, musí platit: Fi(si)=s0 . Obecně platí, že si předchází sj, jestliže je i < j . Abychom ověřili, že sj je element řetězce, pokud víme, že si je i-tý člen řetězce, musí platit: Fj-i(sj)=si. Tak prokážeme, že elementy byly použity v pořadí s0, s1, s2, ..., st-1, st.

vanek21

Obr. 1 Příklad jednosměrného řetězce

Časová synchronizace

Protokol TESLA vyžaduje, aby přijímač a vysílač byly volně časově synchronizování s maximální danou odchylkou Δ , jejíž velikost musí být známa jak přijímači tak i vysílači. Okamžitá časová odchylka δ nesmí být větší než Δ . Obrázek 2 ukazuje příklad časové synchronizace mezi vysílačem a přijímačem. Přijímač vyšle požadavek na časovou synchronizaci v čase tR . V tomto okamžiku je hodnota času na vysílací stranět1. Vysílač zpracuje dotaz a odpoví na něj v čase tS . V tento okamžik je hodnota času na přijímací straně t3. V našem případě zajímá vysílač pouze maximální časová odchylka Δ. Jakmile obdrží přijímač svůj přesný čas tr , vypočítá odchylku podle vzorce: ts <tr - tR + ts. Skutečná chyba po této synchronizaci je δ , ale protože přijímač nezná zpoždění paketu vyžadujícího časovou synchronizaci, musí předpokládat, že odchylka je Δ.

vanek22

Obr. 2 Příklad časové synchronizace mezi přijímačem a vysílačem

Doba šíření a zpracování odpovědi neovlivní hodnotu δ, protože pro přijímač je rozhodující pouze maximální (horní hranice) odchylka. Pokud vysílač zaznamená čas přijetí paketu, nebude mít doba zpracování žádný vliv, a chyba zpracování paketu se tak nepromítne do celkové odchylky δ. Protokol pro časovou synchronizaci pak může vypadat následovně:

1. Vysílač S vygeneruje pár klíčů Ks-1 (soukromý klíč) a Ks (veřejný klíč).
2. Vysílač odešle libovolným způsobem přijímači veřejný klíčKs.
3. Přijímač vybere velké náhodné a nepředvídatelné číslo tzv. nonce a odešle ho vysílači. Před vysláním první zprávy zaznamená přijímač svůj lokální čas tR .
4. Vysílač odešle přijímači zprávu S → R: { Čas vysílače ts , nonce}Ks-1. Zpráva obsahující náhodné číslo od příjemce a čas vysílače je zašifrována soukromým klíčem odesílatele.

Ověření vrácené zprávy proběhne následovně: Přijímač ověří digitální podpis přijaté zprávy a poté zkontroluje, zda je náhodné číslo stejné jako jím vygenerované. Pokud je zpráva autentická, přijímač uloží čas tS a tR . Pro výpočet horní odchylky od místního času t je použit vzorec: δ ≤ Δ = t - tR -tS. Bezpečnost časové synchronizace závisí především na nepředvídatelnosti náhodného čísla (nonce). Pokud by ho útočník dokázal předpovědět, může napodobit paket vyžadující časovou synchronizaci, vyslat tento paket vysílači a později odpovědět přijímači

Základní popis protokolu TESLA

Vysílač rozdělí čas do úseků konstantní délky. Pomocí samo-autetizačních hodnot (SElf Authentication vaLue - SEAL) vytvoří autentizační řetězec a jeho hodnoty přiřadí jednotlivým časovým úsekům. Samoautentizační hodnoty jsou takové hodnoty, které může Příjemce autentizovat bez dalších dodatečných informací. Jednosměrný řetěz je pak používán v opačném pořadí, než byl vytvořen, proto nemůže být žádná hodnota použita k určení hodnoty předcházející. Vysílač stanoví čas, kdy budou odhaleny hodnoty jednosměrných řetězců. Hodnoty jsou tedy zveřejněny až v čase odhalení.
 
Vysílač přiloží ke každému odeslanému paketu identifikační kód zprávy, označovaný jako MAC – (Message Authentication Code). MAC je pro každý paket unikátní a závisí na jeho obsahu. Každému podepsanému paketu je určen časový interval a odpovídající hodnota z jednosměrného řetězce k vypočtení MAC. Spolu s paketem je odeslána i část jednosměrného řetězce, která může být zveřejněna.
 
Paket dorazí k příjemci, který musí provést následující proceduru: Příjemce zná časový plán pro odkrývání paketů. Je-li časově synchronizován, může zjistit, zda klíč použitý pro výpočet MAC je stále platný, tzn. ověří, jestli vysílač odhalil klíče použité pro výpočet MAC. Pokud je MAC stále tajný, uloží ho příjemce do vyrovnávací paměti.
 
Každý příjemce ověřuje, je-li odhalený klíč platný. Pomocí dříve odhalených klíčů každý příjemce ověří, je-li odhalený klíč platný. Pravost MAC ověří u uloženého paketu klíčů. Pokud je všechno v pořádku, přijme paket.
 
Jednosměrné řetězce mají tu vlastnost, že pokud je nějaké hodnota ztracena, může být vypočtena pomocí následujících hodnot. To je velmi výhodné pro všesměrové vysílání, protože příjemce může ověřit pravost paketu, i když jsou některé klíče ztraceny.
 
Příprava vysílače
Vysílač rozdělí čas do intervalů o konstantní délce T. Pokud časový interval 0 bude začínat v čase T0 , časový interval 1 bude začínat v čase T1 = T0 + Ti . Každému intervalu je pak přiřazena hodnota z jednosměrného řetězce. Jeho délka je rovna N a obsahuje hodnoty K0, K0, K1, ..., KN. Tzn., že po určitém časovém úseku (ten je dán délkou N) musí být vytvořen nový řetězec. Hodnotě řetězce KN je přiřazena náhodná hodnota. Celý řetězec je poté sestaven pomocí PRF funkce f a vzorce: F(k)=fk(0) , kde F je jednosměrná funkce tvořící jednosměrný řetězec. Zbylé hodnoty řetězce jsou vypočítány podle vzorce Ki=F(Ki+1) . Jestliže známe hodnotu KN, můžeme vypočítat všechny hodnoty řetězce podle vzorce Ki=FN-1(KN).
 
Příprava přijímače
Následující podmínky platí pro každého příjemce zpráv autentizovaných pomocí protokolu TESLA. Každý příjemce musí být volně časově synchronizován s vysílačem, znát časový plán pro zveřejňování klíčů a přijmout ověřený veřejný klíč vysílače. Časová synchronizace musí proběhnout před přijetím první zprávy podepsané protokolem TESLA. Plán pro odkrývání klíčů musí příjemce obdržet jiným zabezpečeným kanálem např. přes zabezpečený komunikační kanál.
Časový plán obsahuje následující informace:

Vysílání ověřených zpráv
Každé vyslané zprávě je přiřazen MAC vypočítaný s pomocí klíče, kterým je hodnota z jednosměrného řetězce, který odpovídá danému časovému intervalu. Klíč je zveřejňován s časovou prodlevou d, tudíž zpráva vyslána v intervalu j odkrývá klíč Kj-d a může být ověřena klíčem Kj+d. Máme pouze jeden klíč pro daný časový interval a potřebujeme vypočítat MAC a klíč Kj. Aby nebyla snížena bezpečnost protokolu, je volen následující postup: Pomocí pseudonáhodné funkce f' zkonstruujeme jednosměrnou funkci OWF F':F'(k) = f'k(1). Funkce F' slouží k výpočtu MAC: K'i = F'(Ki). Obr. 3 ukazuje konstrukci jednosměrného řetězce a výpočet MAC. Chceme-li vyslat zprávu Mj , musíme vytvořit následující paket: Pj = { Mj || MAC(K'j, Mj) || Ki-d} .

vanek23

Obr. 3 Vysílání ověřených zpráv

Ověřování zpráv
Pro ověření paketů jsou klíče zveřejňovány se zpožděním d. V okamžiku zveřejnění je daný klíč k dispozici všem, tedy i útočníkovi. Postup ověřování zpráv je následující:
Vysílač vyšle paket Pj v časovém intervalu i (viz. Obr. 3). Po jeho přijetí je použit samo-autentizační klíč Ki-d , který je odkrytý v tomto paketu a použitý pro výpočet intervalu i. Příjemce díky časové synchronizaci zjistí, v jakém nejvyšším intervalu x se může vysílač nacházet. Pokud platí x < i + d ( d je prodleva mezi zveřejněním klíče, i je interval, kdy byl vyslán paket, x je nejvyšší možný interval, ve kterém se může nacházet vysílač) je paket bezpečný ( klíč pro ověření daného paketu je stále tajný – nebyl vyslán). Jelikož vysílač ještě nevyslal klíč pro ověření paketu P , musí příjemce uložit do své vyrovnávací paměti následující informace: (i,Mj,MAC(K'i,Mj) . Po uplynutí doby d a po obdržení klíče Ki příjemce ověří jeho pravost a je-li posledním zveřejněným klíčem. Jestliže se potvrdí, že Ki je posledním obdrženým klíčem k danému času, zkontroluje příjemce jeho pravost podle následujícího postupu:
K ověření pravosti je použit starší klíč Kv, kde v <j. Pro klíč Kv musí platit: Ki = Fi-v(Ki) , jestliže rovnost platí, je klíč pravý a přijímač spočítá klíč K'i, který je poté použit pro ověření paketu přijatého v intervalu i, případně paketů přijatých v předchozích intervalech. Klíče pro starší pakety mohou být odvozeny z novějších klíčů, ale opačný postup není možný (vyplývá z vlastnosti jednosměrných řetězců).

Tento příspěvek vznikl v rámci výzkumného záměru MSM6840770038.

Literatura

[1] Perrig A., Tygar J.D., Secure broadcast communication in wired and wireless networks 2002. ISBN 0-7923-7650-1
[2] RFC 4082 - Timed Efficient Stream Loss-Tolerant Authentication (TESLA): Multicast Source Authentication Transform Introduction, [on-line] , 2005, [cit. 10.6.2008], Dostupný z WWW: http://www.ietf.org/rfc/rfc4082.txt
[3] Zloch T., Všesměrové autentizační protokoly, Bakalářská práce, Katedra telekomunikační techniky, ČVUT-FEL, 2006
[5] Abadi M., Security Protocols and their Properties, In Foundations of Secure Computation (20th International Summer School on Foundations of Secure Computation, Marktoberdorf, Germany, 2000