LEX (šifra)

LEX (LEX-128, LEX-192, LEX-256) je proudová šifra vyvinutá Alexem Biryukovem . Šifra se zúčastnila soutěže eSTREAM a dostala se do fáze 3, ale přesto nebyla vybrána do finálního portfolia [1] .

Úvod

Název šifry LEX pochází z anglického výrazu . Extrakce úniku . Nějaká bloková šifra je brána jako základ a myšlenkou je vydávat části vnitřního stavu blokové šifry v určitých kolech na výstupní gama pro šifrování proudu (případně po aplikaci nějaké filtrační funkce). Takovou metodu lze aplikovat na libovolnou blokovou šifru, ale v každém případě je potřeba pečlivě zvážit, které části vnitřního stavu načíst a na jaké frekvenci. Závisí to hlavně na zaokrouhlovací funkci blokové šifry a algoritmu generování zaokrouhleného klíče, který používá.

Popis

Původní šifra LEX používá AES v režimu Output Feedback (OFB) : v každém kole jsou ze stavové matice extrahovány 4 specifické bajty . Verze LEX-128, LEX-192 a LEX-256 se liší délkou klíče použitého při šifrování : 128, 192 a 256 bitů. Rozdíl oproti AES je v tom, že kryptoanalytik nikdy nevidí celý 128bitový šifrovaný text , ale pouze části přechodného stavu.

Nejprve je nějaký inicializační vektor (IV) AES zašifrován klíčem K, aby se získalo S = AES k (IV). Dále je S opakovaně zašifrováno v režimu OFB a v tomto okamžiku je ze stavové matice v každém kole extrahováno 32 bitů (viz obr. 1). Po 500 šifrováních se zvolí další klíč K a práce pokračuje.

Klíčovou součástí šifry je rozhodnutí, které bajty extrahovat z mezistavu a na jaké frekvenci. Autor šifry navrhuje extrahovat bajty v každém lichém kole a bajty v každém sudém (viz obr. 2). Pořadí bajtů není důležité pro bezpečnost, ale důležité pro rychlost šifrování. Výše uvedené pořadí bajtů vám umožňuje extrahovat je z aktuálního stavu v pouhých 4 krocích pomocí vzorce: $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),\\\ konec{aligned}}

kde to a t2 jsou nula a druhá řada v matici mezilehlého stavu, v daném pořadí.

Volba těchto pozic bajtů je motivována následujícím: obě sady a jsou invariantní pod operací ShiftRows používanou v AES (první řádek není posunut, třetí je posunut o dvě pozice). Použití různých sad na lichá a sudá kola zajišťuje, že vstupní a výstupní bajty ve dvou sousedních kolech nejsou spojeny pouze operacemi SubBytes a MixColumns . Útočník tak bude nucen analyzovat dvě po sobě jdoucí kola šifrování. Dvě kola poskytují úplné rozptýlení ve statistikách šifry, což omezuje útočníkovu schopnost používat rozděl a panuj . $B_1$ $B_{2}$

Posledním krokem je modulo 2 přidání gama výstupu v otevřeném textu.

Kryptoanalýza LEX

Období výstupní sekvence

U proudových šifer je nejzajímavější otázka periody výsledné sekvence v gama . Protože LEX používá AES, výstupní sekvence (gama) se bude opakovat, když sekvence šifrových textů generovaných AES smyčkou. Pokud by AES vygeneroval sekvenci nerozlišitelnou od náhodné pro jeden klíč, pak by délka sekvence byla . $O(2^{128})$

Pokud je výstupní proud náhodnou permutací 128bitového bloku, může být rozpoznán jako nenáhodný po zjištění nepřítomnosti 128bitových kolizí v proudu 264 výstupních bloků. V případě LEX, protože se v každém kole používají pouze části vnitřního stavu AES, není mapování vnitřního stavu na výstup individuální, a proto k takovým kolizím dojde.

Útoky na časovou paměť

Aby byla proudová šifra odolná vůči útokům typu time-memory trade-off , musí být splněny následující podmínky . To zajišťuje, že složitost útoku je srovnatelná s brutální silou. Inicializační vektor může být otevřený, ale pak musí být zcela náhodný, aby nedocházelo k útoku typu tradeoff-resynchronization [2] . V případě bitů LEX, kde Block je stav bloku otevřeného textu v době šifrování. Vnitřní stav odpovídá páru na začátku a během šifrování. K negaci možnosti útoku tedy stačí kousek. $|K|=|IV|=|Stát|/2$ $|K|=|IV|=|Blokovat|=128$ $(K,IV)$ $(blok, klíč)$ $|K|+|IV|=|K|+|S|=256$

Algebraické útoky

Tento typ útoku ještě není plně objasněn a může být velmi silný. Možnost jeho aplikace na LEX by měla být pečlivě prostudována. Očekává se, že změna klíče po 500 šifrováních zabrání takovým útokům. Zacílením na konkrétní klíč může kryptoanalytik získat pouze 500 bloků výstupního gama; a po výměně klíče jím sestavený systém rovnic zastará.

Výkon

Pro cyklus práce vytváří AES 128 bitů šifrového textu pro všechny možnosti klíče (128, 192, 256 bitů), zatímco LEX postavený na AES poskytne 32 * N r (kde N r je počet kol pro danou délku klíče ) bity šifrovaného textu. Očekává se tedy, že LEX překoná AES asi 2,5x, 3x a 3,5x v tomto pořadí pro 128, 192 a 256 bitové klíče. Výhodou šifry je navíc to, že lze použít již hotové implementace použité blokové šifry, což snižuje čas a náklady na vývoj.

Viz také

Poznámky

↑ CiteSeerX – Kryptoanalýza streamové šifry LEX . Získáno 30. listopadu 2011. Archivováno z originálu dne 25. dubna 2018. (neurčitý)
↑ J. Hong a P. Sarkar, „Rediscovery of time memory tradeoffs“, 2005. http://eprint.iacr.org/2005/090 Archivováno 1. června 2014 na Wayback Machine

Odkazy

[1] Nová 128bitová šifra Key Stream Cipher LEX
[2] Nový útok na LEX Stream Cipher
[3] Algebraická kryptoanalýza malé verze proudové šifry LEX