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

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 s₀, 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 s_i je skutečným elementem s s indexem i, musí platit: Fⁱ(s_i)=s₀ . Obecně platí, že s_i předchází s_j, jestliže je i < j . Abychom ověřili, že s_j je element řetězce, pokud víme, že s_i je i-tý člen řetězce, musí platit: F^j-i(s_j)=s_i. Tak prokážeme, že elementy byly použity v pořadí s₀, s₁, s₂, ..., s_t-1, s_t.

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 t_R . V tomto okamžiku je hodnota času na vysílací stranět₁. Vysílač zpracuje dotaz a odpoví na něj v čase t_S . V tento okamžik je hodnota času na přijímací straně t₃. V našem případě zajímá vysílač pouze maximální časová odchylka Δ. Jakmile obdrží přijímač svůj přesný čas t_r , vypočítá odchylku podle vzorce: t_s <t_r - t_R + t_s. 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 Δ.

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íčů K_s^-1 (soukromý klíč) a K_s (veřejný klíč).

2. Vysílač odešle libovolným způsobem přijímači veřejný klíčK_s.

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 t_R .

4. Vysílač odešle přijímači zprávu S → R: { Čas vysílače t_s , nonce}K_s^-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 t_S a t_R . Pro výpočet horní odchylky od místního času t je použit vzorec: δ ≤ Δ = t - t_R -t_S. 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 T₀ , časový interval 1 bude začínat v čase T₁ = T₀ + T_i . 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 K₀, K₀, K₁, ..., K_N. 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 K_N je přiřazena náhodná hodnota. Celý řetězec je poté sestaven pomocí PRF funkce f a vzorce: F(k)=f_k(0) , kde F je jednosměrná funkce tvořící jednosměrný řetězec. Zbylé hodnoty řetězce jsou vypočítány podle vzorce K_i=F(K_i+1) . Jestliže známe hodnotu K_N, můžeme vypočítat všechny hodnoty řetězce podle vzorce K_i=F^N-1(K_N).
 
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:

• Trvání intervalu T_int , startovací čas T , délku intervalu i a délku jednosměrného řetězce.
  
• Prodleva mezi odkrýváním klíčů d (je dána počtem časových intervalů)
  
• Dodatek K_i> k jednosměrnému řetězci klíčů ( i < j - d , kde j je index daného intervalu).
  

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íč K_j-d a může být ověřena klíčem K_j+d. Máme pouze jeden klíč pro daný časový interval a potřebujeme vypočítat MAC a klíč K_j. 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'(K_i). Obr. 3 ukazuje konstrukci jednosměrného řetězce a výpočet MAC. Chceme-li vyslat zprávu M_j , musíme vytvořit následující paket: P_j = { M_j || MAC(K'_j, M_j) || K_i-d} .

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

Ověřování zpráv
Pro ověření paketů jsou klíče K´ 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 P_j v časovém intervalu i (viz. Obr. 3). Po jeho přijetí je použit samo-autentizační klíč K_i-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,M_j,MAC(K'_i,M_j) . Po uplynutí doby d a po obdržení klíče K_i příjemce ověří jeho pravost a je-li posledním zveřejněným klíčem. Jestliže se potvrdí, že K_i 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íč K_v, kde v <j. Pro klíč K_v musí platit: K_i = F^i-v(K_i) , 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