Trivium (šifra) - Trivium (cipher)

Struktura trivia

Trivium je synchronní proudová šifra navržen tak, aby poskytoval flexibilní kompromis mezi rychlostí a počet bran v hardwaru a přiměřeně efektivní implementaci softwaru.

Trivium bylo odesláno do profilu II (hardware) eSTREAM soutěž jeho autorů, Christophe De Cannière a Bart Preneel, a byl vybrán jako součást portfolia pro nízkoplošné hardwarové šifry (profil 2) projektem eSTREAM. Není patentován a byl specifikován jako mezinárodní norma podle ISO / IEC 29192-3.^[1]

Generuje až 2⁶⁴ bity výstupu z 80 bitů klíč a 80-bit IV. Je to nejjednodušší účastník eSTREAMu; i když vykazuje pozoruhodnou odolnost vůči dešifrování pro svou jednoduchost a výkon, nedávné útoky nechávají bezpečnostní rezervu vypadat poněkud štíhle.

Popis

288bitový vnitřní stav Trivium se skládá ze tří posuvné registry různých délek. V každém kole se bit posune do každého ze tří posuvných registrů pomocí nelineární kombinace odboček z tohoto a jednoho dalšího registru; vyprodukuje se jeden bit výstupu. Pro inicializaci šifry jsou klíč a IV zapsány do dvou posuvných registrů, přičemž zbývající bity začínají pevným vzorem; stav šifry je poté aktualizován 4 × 288 = 1152krát, takže každý bit vnitřního stavu závisí na každém bitu klíče a IV komplexním nelineárním způsobem.

Na prvních 65 bitech každého posuvného registru se neobjeví žádná klepnutí, takže každý nový stavový bit se nepoužívá, dokud se nevygeneruje alespoň 65 kol. To je klíč k výkonu a flexibilitě softwaru Trivium v ​​hardwaru.

Specifikace

Trivium lze specifikovat velmi stručně pomocí tří rekurzivních rovnic.^[2] Každá proměnná je prvkem GF (2); mohou být reprezentovány jako bity, přičemž „+“ je XOR a „•“ bytí A.

• A_i = C_i−66 + C_i−111 + C_i−110 • C_i−109 + A_i−69
• b_i = A_i−66 + A_i−93 + A_i−92 • A_i−91 + b_i−78
• C_i = b_i−69 + b_i−84 + b_i−83 • b_i−82 + C_i−87

Výstupní bity r₀ ... r_2⁶⁴−1 jsou pak generovány

• r_i = C_i−66 + C_i−111 + A_i−66 + A_i−93 + b_i−69 + b_i−84

Vzhledem k 80bitovému klíči k₀ ... k₇₉ a l-bit IV proti₀ ... proti_l−1 (kde 0 ≤ l ≤ 80), Trivium se inicializuje takto:

• (A₋₁₂₄₅ ... A₋₁₁₅₃) = (0, 0 ... 0, k₀ ... k₇₉)
• (b₋₁₂₃₆ ... b₋₁₁₅₃) = (0, 0 ... 0, proti₀ ... proti_l−1)
• (C₋₁₂₆₃ ... C₋₁₁₅₃) = (1, 1, 1, 0, 0 ... 0)

Velké záporné indexy na počátečních hodnotách odrážejí 1152 kroků, které je nutné provést před vytvořením výstupu.

Mapovat proud bitů r do proudu bajtů R, používáme mapování little-endian R_i = Σ_{j=0 ... 7} 2^j r_{8i+ j}.

Výkon

Pro přímou hardwarovou implementaci Trivium by bylo použito 3488 logické brány a vyprodukovat jeden bit za taktovací cyklus. Protože se však každý stavový bit nepoužívá po dobu nejméně 64 kol, lze 64 bitů stavu generovat paralelně při mírně vyšších nákladech na hardware o 5504 bran. Rovněž jsou možné různé kompromisy mezi rychlostí a oblastí.

Stejná vlastnost umožňuje efektivní implementaci bitslice v softwaru; testování výkonu do eSTREAM dát hromadné rychlosti šifrování kolem 4 cykly / bajt na některých x86 platformy, které se dobře srovnává s 19 cykly / bajty AES referenční implementace na stejné platformě.

Bezpečnostní

[Trivium] bylo navrženo jako cvičení při zkoumání toho, jak daleko lze proudovou šifru zjednodušit, aniž by byla obětována její bezpečnost, rychlost nebo flexibilita. I když je pravděpodobné, že jednoduché návrhy budou náchylné k jednoduchým a možná i zničujícím útokům (což je důvod, proč v této fázi důrazně nedoporučujeme používat Trivium), určitě vzbudí větší důvěru než složitá schémata, pokud přežijí dlouhé období veřejného života kontrola navzdory jejich jednoduchosti.^[3]

Od dubna 2015^{[Aktualizace]}, žádné kryptoanalytické útoky lepší než útok hrubou silou jsou známy, ale několik útoků se blíží. The krychlový útok vyžaduje 2⁶⁸ kroky k rozbití varianty Trivium, kde je počet inicializačních kol snížen na 799.^[4] Dříve jiní autoři spekulují, že tyto techniky by mohly vést k přerušení 1100 inicializačních kol, nebo „možná i původní šifře“.^[5] Toto navazuje na útok způsobený Michaelem Vielhaberem, který rozbije 576 inicializačních kol pouze za 2^12.3 kroky.^[6][7]

Další útok obnoví vnitřní stav (a tedy klíč) plné šifry kolem 2^89.5 kroky (kde každý krok představuje zhruba cenu jednoho pokusu při vyčerpávajícím hledání).^[8] Redukované varianty trivia využívající stejné konstrukční principy byly rozbity technikou řešení rovnic.^[9] Tyto útoky vylepšují známý časoprostorový kompromisní útok na šifry streamů, který by s 288bitovým interním stavem Trivium trval 2¹⁴⁴ kroky a ukazují, že varianta na Trivium, která neprovedla žádnou změnu kromě zvýšení délky klíče nad 80 bitů nařízených eSTREAM Profil 2, by nebyla bezpečná. Pomocí optimalizované strategie řešení je dále možné snížit složitost obnovy stavu na 2¹³² kroky.^[10]

Podrobné odůvodnění návrhu Trivia je uvedeno v.^[11]

Reference

externí odkazy

• Stránka eSTREAM na Trivium
• Implementace eSTREAM