LEX (chiffer)

LEX (LEX-128, LEX-192, LEX-256) är ett strömchiffer utvecklat av Alex Biryukov . Chifferet deltog i eSTREAM- tävlingen och nådde steg 3, men valdes inte desto mindre till den slutliga portföljen [1] .

Introduktion

Namnet på chiffer LEX kommer från den engelska termen . Läckavdrag . En del blockchiffer tas som grund och tanken är att mata ut delar av blockchifferets interna tillstånd vid vissa omgångar till output gamma för strömkryptering (möjligen efter att ha tillämpat någon filtreringsfunktion). En sådan metod kan tillämpas på vilket blockchiffer som helst, men i varje fall krävs noggrann övervägande om vilka delar av det interna tillståndet som ska hämtas och med vilken frekvens. Det beror främst på den runda funktionen hos blockchifferet och den runda nyckelgenereringsalgoritmen som den använder.

Beskrivning

Det ursprungliga LEX-chifferet använder AES i Output Feedback (OFB)-läge : i varje omgång extraheras 4 specifika bytes från tillståndsmatrisen. Versioner LEX-128, LEX-192 och LEX-256 skiljer sig åt i längden på nyckeln som används vid kryptering : 128, 192 respektive 256 bitar. Skillnaden med AES är att kryptoanalytikern aldrig ser hela 128-bitars chiffertext , utan bara delar av det mellanliggande tillståndet.

För det första är någon initialiseringsvektor (IV) AES-krypterad med nyckeln K för att få S = AES k (IV). Därefter krypteras S upprepade gånger i OFB-moden, och vid denna tidpunkt extraheras 32 bitar från tillståndsmatrisen i varje omgång (se fig. 1). Efter 500 krypteringar väljs ytterligare en nyckel K och arbetet fortsätter.

En viktig del av chifferet är att bestämma vilka bytes som ska extraheras från det mellanliggande tillståndet och vid vilken frekvens. Författaren till chifferet föreslår att extrahera bytes i varje udda omgång och bytes i varje jämn (se fig. 2). Byteordningen är inte viktig för säkerheten, men viktig för krypteringshastigheten. Ovanstående byteordning låter dig extrahera dem från det aktuella tillståndet i bara 4 steg med hjälp av formeln: $B_{1}=(b_{0,0},b_{0,2},b_{2,0},b_{2,2})$ $B_{2}=(b_{0,1},b_{0,3},b_{2,1},b_{2,3})$

{\begin{aligned}out32&=\left(\left(t_{0}\&0xFF00FF\right)<<8\right)\oplus \left(t_{2}\&0xFF00FF\right),\\\ end{aligned}}

där to och t2 är noll- och andraraderna i mellantillståndsmatrisen .

Valet av dessa bytepositioner motiveras av följande: båda sätter och är invarianta under ShiftRows- operationen som används i AES (den första raden förskjuts inte, den tredje förskjuts med två positioner). Genom att använda olika uppsättningar på udda och jämna omgångar säkerställs att ingångs- och utgångsbyte på två intilliggande omgångar inte bara kopplas samman med SubBytes- och MixColumns-operationerna . Således kommer angriparen att tvingas analysera två på varandra följande omgångar av kryptering. Två omgångar ger fullständig spridning i chifferns statistik, vilket begränsar angriparens förmåga att använda dividera och erövra . $B_1$ $B_{2}$

Det sista steget är modulo 2-tillägg av klartextutgångens gamma.

Kryptanalys LEX

Period för utdatasekvensen

För strömchiffer är den mest intressanta frågan perioden för den resulterande sekvensen i gamma . Eftersom LEX använder AES, kommer utdatasekvensen (gamma) att loopa när sekvensen av chiffertexter som genereras av AES loopar. Om AES genererade en sekvens som inte kan särskiljas från slumpmässig för en nyckel, så skulle längden på sekvensen vara . $O(2^{128})$

Om utgångsströmmen är en slumpmässig permutation av ett 128-bitars block, kan den kännas igen som icke-slumpmässig efter detektering av frånvaron av 128-bitars kollisioner i en ström av 264 utgångsblock. I fallet med LEX, eftersom endast delar av det interna tillståndet för AES används i varje omgång, är mappningen av det interna tillståndet till utgången inte en-till-en och följaktligen kommer sådana kollisioner att inträffa.

Tidsminnesattacker

För att ett strömchiffer ska vara resistent mot avvägningsattacker med tidsminne måste följande villkor uppfyllas . Detta säkerställer att attackens komplexitet är jämförbar med den för brute force. Initieringsvektorn kan vara öppen, men då måste den vara helt slumpmässig för att undvika en kompromiss-omsynkroniseringsattack [2] . I fallet med LEX- bitar, där Block är tillståndet för klartextblocket vid tidpunkten för kryptering. Det interna tillståndet motsvarar paret i början och under kryptering. Alltså räcker lite för att förneka möjligheten till en attack. $|K|=|IV|=|Stat|/2$ $|K|=|IV|=|Blockera|=128$ $(K,IV)$ $(block, nyckel)$ $|K|+|IV|=|K|+|S|=256$

Algebraiska attacker

Denna typ av attack är ännu inte helt klarlagd och kan vara mycket kraftfull. Möjligheten av dess tillämpning på LEX bör noggrant studeras. Det förväntas att byte av nyckel efter 500 krypteringar kommer att undvika sådana attacker. Med inriktning på en viss nyckel kan kryptoanalytikern bara få 500 block av utdatagamma; och efter att ha ersatt nyckeln kommer ekvationssystemet som sammanställts av honom att bli föråldrat.

Prestanda

För en arbetscykel producerar AES 128 bitar av chiffertext för alla nyckelalternativ (128, 192, 256 bitar), medan LEX byggd på AES ger 32 * N r (där N r är antalet rundor för en given nyckellängd ) chiffertextbitar. Således förväntas LEX överträffa AES med cirka 2,5x, 3x respektive 3,5x för 128, 192 och 256 bitars nycklar. Dessutom är fördelen med chifferet att färdiga implementeringar av det använda blockchifferet kan användas, vilket minskar utvecklingstid och kostnader.

Se även

Anteckningar

↑ CiteSeerX - Krypteringsanalys av Stream Cipher LEX . Hämtad 30 november 2011. Arkiverad från originalet 25 april 2018. (obestämd)
↑ J. Hong och P. Sarkar, "Rediscovery of time memory tradeoffs," 2005. http://eprint.iacr.org/2005/090 Arkiverad 1 juni 2014 på Wayback Machine

Länkar

[1] En ny 128-bitars Key Stream Cipher LEX
[2] En ny attack mot LEX Stream Chiffer
[3] Algebraisk kryptoanalys av en småskalig version av Stream Cipher LEX