Trivium (chiffer)

Triviums struktur

Trivium är ett synkront strömchiffer designat för att tillhandahålla en flexibel kompromiss mellan hastighet och grindantal i hårdvara, och någorlunda effektiv mjukvaruimplementering.

Trivium skickades till Profile II (hårdvara) för eSTREAM -tävlingen av dess författare, Christophe De Cannière och Bart Preneel , och har valts ut som en del av portföljen för lågarea hårdvaruchiffer (Profil 2) av eSTREAM-projektet. Den är inte patenterad och har specificerats som en internationell standard enligt ISO/IEC 29192-3.

Den genererar upp till 2 ⁶⁴ bitars utdata från en 80-bitars nyckel och en 80-bitars IV . Det är den enklaste eSTREAM-deltagaren; medan den visar ett anmärkningsvärt motstånd mot kryptoanalys för sin enkelhet och prestanda, låter de senaste attackerna säkerhetsmarginalen se ganska smal ut.

Beskrivning

Triviums 288-bitars interna tillstånd består av tre skiftregister av olika längd. Vid varje omgång skiftas en bit in i vart och ett av de tre skiftregistren med användning av en icke-linjär kombination av uttag från det och ett annat register; en bit av output produceras. För att initiera chiffret skrivs nyckeln och IV in i två av skiftregistren, med de återstående bitarna som börjar i ett fast mönster; chiffertillståndet uppdateras sedan 4 × 288 = 1152 gånger, så att varje bit i det interna tillståndet beror på varje bit av nyckeln och av IV på ett komplext olinjärt sätt.

Inga tappningar visas på de första 65 bitarna i varje skiftregister, så varje ny tillståndsbit används inte förrän minst 65 omgångar efter att den har genererats. Detta är nyckeln till Triviums mjukvaruprestanda och flexibilitet i hårdvara.

Specifikation

Trivium kan specificeras mycket kortfattat med hjälp av tre rekursiva ekvationer. Varje variabel är ett element av GF (2); de kan representeras som bitar , där "+" är XOR och "•" är OCH .

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 = bi _{−69 −87} + b _{i −84} + b _{i −83} • b _{i −82} + c _{i _}

₀ Utmatningsbitarna r ... r _{2 ⁶⁴ −1} genereras sedan av

r _i = c _{i −66} + c _{i −111} + a _{i −66} + a _{i −93} + b _{i −69} + b _{i −84}

₀₀ Givet en 80-bitars nyckel k ... k ₇₉ och en l -bit IV v ... v _{l −1} (där 0 ≤ l < 80), initieras Trivium enligt följande:

₀ ( a ₋₁₂₄₅ ... a ₋₁₁₅₃ ) = (0, 0 ... 0, k ... k ₇₉ )
₀ ( b ₋₁₂₃₆ ... b ₋₁₁₅₃ ) = (0, 0 ... 0, v ... v _{l −1} )
( c ₋₁₂₆₃ ... c ₋₁₁₅₃ ) = (1, 1, 1, 0, 0 ... 0)

De stora negativa indexen på initialvärdena speglar de 1152 steg som måste ske innan utdata produceras.

För att mappa en ström av bitar r till en ström av byte R använder vi LSb-första mappningen R _i = Σ _{j =0, ..., 7} 2 ^j r _{8 i +j} .

Prestanda

En enkel hårdvaruimplementering av Trivium skulle använda 3488 logiska grindar och producera en bit per klockcykel. Men eftersom varje tillståndsbit inte används under minst 64 omgångar kan 64 tillståndsbitar genereras parallellt till en något högre hårdvarukostnad på 5504 grindar. Olika avvägningar mellan hastighet och yta är också möjliga.

Samma egenskap tillåter en effektiv bitslice-implementering i programvara; prestandatestning av eSTREAM ger bulkkrypteringshastigheter på cirka 4 cykler/byte på vissa x86 -plattformar, vilket kan jämföras med de 19 cyklerna/byte för AES -referensimplementeringen på samma plattform.

säkerhet

[Trivium] designades som en övning för att utforska hur långt ett strömchiffer kan förenklas utan att offra dess säkerhet, hastighet eller flexibilitet. Även om enkla design är mer benägna att vara sårbara för enkla, och möjligen förödande, attacker (vilket är anledningen till att vi starkt avråder från användningen av Trivium i detta skede), inspirerar de verkligen mer förtroende än komplexa system, om de överlever en lång period av offentlighet granskning trots sin enkelhet.

Från och med april 2015 är inga kryptoanalytiska attacker bättre än brute-force attacker kända, men flera attacker kommer nära. Kubattacken kräver 2 ⁶⁸ steg för att bryta en variant av Trivium där antalet initialiseringsomgångar reduceras till 799. Tidigare har andra författare spekulerat i att dessa tekniker kan leda till ett avbrott för 1100 initialiseringsomgångar, eller "kanske till och med det ursprungliga chiffer" . Detta bygger på en attack på grund av Michael Vielhaber som bryter 576 initialiseringsrundor i endast 2 ^12,3 steg.

En annan attack återställer det interna tillståndet (och därmed nyckeln) för det fullständiga chifferet i cirka 2 ^89,5 steg (där varje steg är ungefär kostnaden för en enda rättegång i uttömmande sökning). Reducerade varianter av Trivium som använder samma designprinciper har brutits med en ekvationslösningsteknik. Dessa attacker förbättras jämfört med den välkända tid-rymd-avvägningsattacken på strömchiffer, som med Triviums 288-bitars interna tillstånd skulle ta 2 ¹⁴⁴ steg, och visar att en variant på Trivium som inte gjorde någon förändring förutom att öka nyckellängden utöver 80 bitar på uppdrag av eSTREAM Profile 2 skulle inte vara säkert. Med en optimerad lösningsstrategi är det ytterligare möjligt att reducera komplexiteten för tillståndsåterställning till 2 ¹³² steg.

En detaljerad motivering av utformningen av Trivium ges i en artikel "A Stream Cipher Construction Inspired by Block Cipher Design Principles".

externa länkar