Obilí (šifra) - Grain (cipher)

Obilí je proudová šifra předložen eSTREAM v roce 2004 Martin Hell, Thomas Johansson a Willi Meier. Byl vybrán do finálního portfolia eSTREAM pro profil 2 projektem eSTREAM. Obilí je určeno především pro omezený hardware prostředí. Přijímá 80-bit klíč a 64-bit IV. Specifikace nedoporučují maximální délku výstupu na pár (klíč, iv). V šifře byla identifikována a napravena řada potenciálních slabin Obilí 128a což je nyní doporučená šifra pro hardwarová prostředí poskytující 128bitové zabezpečení i autentizaci.

Popis

160bitový vnitřní stav obilí se skládá z 80bitového posuvný registr lineární zpětné vazby (LFSR) a 80-bit nelineární zpětnovazební posuvný registr (NLFSR). Grain aktualizuje jeden bit LFSR a jeden bit stavu NLFSR pro každý bit ciphertext uvolněný funkcí nelineárního filtru. 80bitový NLFSR je aktualizován nelineární logickou funkcí 5 na 1 a 1bitovým lineárním vstupem vybraným z LFSR. Nelineární funkce 5: 1 bere jako vstup 5 bitů stavu NLFSR. 80bitový LFSR je aktualizován lineární funkcí 6: 1. Během operací klíčování je výstup šifry dodatečně přiváděn zpět jako lineární vstupy do aktualizačních funkcí NLFSR i LFSR.

V původním podání Grain verze 0.0 Grain je jeden bit 80bitového NLFSR a čtyři bity 80bitového LFSR dodávány nelineární logické funkci 5: 1 (která je vybrána tak, aby byla vyvážená, korelační imunní vůči prvního řádu a má algebraický stupeň 3) a výstup je lineárně kombinován s 1 bitem 80bitového NLFSR a uvolněn jako výstup.

V aktualizované verzi Grain verze 1.0 je jeden bit 80bitového NLFSR a čtyři bity 80bitového LFSR dodávány (mírně revidované) nelineární logické funkci 5 na 1 a výstup je lineárně kombinován s 7 bitů 80bitového NLFSR a uvolněno jako výstup.

Pro inicializaci šifry se 80bitový klíč načte přímo do 80bitového NLFSR a 64bitový IV se načte do nízkých 64bitů LFSR a zbývajících 16 vysokých bitů LFSR se naplní jedničkami. Šifra je zapečetěna na 160 nábojů, kde 160 bitů keystream generované jsou lineárně zpětnou vazbou jak do aktualizačních funkcí LFSR, tak NLFSR. Šifra během procesu inicializace nevydává žádný výstup klíčového proudu.

Autoři Grain diskutují o úplných rychlostech difúze procesu inicializace Grain ve specifikacích Grain verze 1.0: „U inicializace se dvěma různými IV, lišícími se pouze o jeden bit, by se měla pravděpodobnost, že bit posuvného registru pro obě inicializace je stejný, blížit 0,5 . Simulace ukazují, že toho je dosaženo po 160 stopování. “

Výkon

Šifra je navržena tak, aby umožňovala paralelně provádět až 16 kol, což umožňuje rychlejší implementace za cenu většího využití hardwaru.

Bezpečnostní

Velikost klíče je 80 bitů a velikost IV je určena jako 64 bitů. Autoři tvrdí, že šifra je navržena tak, že by neměl být možný žádný útok rychleji než vyčerpávající vyhledávání klíčů, a proto by nejlepší útok měl vyžadovat výpočetní složitost ne výrazně nižší než 280.

V původní specifikaci Grain verze 0.0[1] autoři tvrdí: „Grain poskytuje vyšší zabezpečení než několik dalších dobře známých šifer určených pro použití v hardwarových aplikacích. Známé příklady těchto šifer jsou E0 použito v Bluetooth a A5 / 1 použito v GSM. Ukázalo se, že tyto šifry mají velmi malou hardwarovou implementaci a jsou velmi nejisté. Ve srovnání s E0 a A5 / 1 „Grain poskytuje vyšší zabezpečení při zachování malé hardwarové složitosti.“

Autoři citují útok proti E0 [2] vyžadující složitost 240 a 235 snímků (snímek je dlouhý 2745 bitů). Původní šifra Grain verze 0.0 byla přerušena útokem na obnovu klíče[3] což vyžadovalo složitost 243 výpočty a 238 bitů keystream k určení 80bitového klíče.

V revidovaných specifikacích Grain verze 1.0[4] šifra má mírně přepracovanou výstupní funkci a zpětnovazební funkce NLFSR obdržela menší změnu. Specifikace tvrdí: „Funkce filtru je poměrně malá, má pouze 5 proměnných a nelinearitu 12. To je však částečně kompenzováno skutečností, že jeden ze vstupů je převzat z NLFSR. Vstupní bit z NLFSR bude záviset nelineárně [sic ] na ostatních bitech ve stavu, jak z LFSR, tak z NLFSR. Funkce malého filtru je také kompenzována lineárním přidáním 7 bitů [sic ] z NLFSR na vhodných pozicích k vytvoření výstupní funkce. "

Od října 2006 nejsou známy žádné útoky na obnovu klíčů lepší než útok hrubou silou proti Grain verze 1.0.

Útok souvisejícím s klíčem však v září 2006 zveřejnil Ozgul Kucuk v příspěvku „Slide Resynchronization Attack on the Initialization of Grain 1.0“.[5] Článek tvrdí: „najdeme související klíče a počáteční hodnoty proudové šifry Grain 1.0. Pro jakýkoli pár (K, IV) existuje související pár (K ', IV') s pravděpodobností 1/22, který generuje 1bitový posunutý klíčový proud Ačkoli to ještě nevede k efektivnímu útoku na obnovu klíče, znamená to slabost v inicializaci, kterou lze překonat [sic ] s trochou úsilí. “

Reference

  1. ^ Martin Hell, Thomas Johansson, Willi Meier (2005-04-29). „Obilí - proudová šifra pro omezená prostředí“ (PDF ). eSTREAM. Citovat deník vyžaduje | deník = (Pomoc)CS1 maint: více jmen: seznam autorů (odkaz)
  2. ^ Yi Lu, http://lasecwww.epfl.ch/~vaudenay/ (2004). „Kryptoanalýza dvouúrovňového generátoru Bluetooth Keystream E0“ (PDF ). Pokroky v kryptologii - Asiacrypt 2004, LNCS sv. 3329, str. 483-499, Springer, 2004. Citovat deník vyžaduje | deník = (Pomoc)
  3. ^ Côme Berbain, Henri Gilbert, Alexander Maximov (02.01.2006). „Kryptanalýza obilí“ (PDF ). eSTREAM. Citovat deník vyžaduje | deník = (Pomoc)CS1 maint: více jmen: seznam autorů (odkaz)
  4. ^ Martin Hell, Thomas Johansson, Willi Meier (2006). „Obilí - proudová šifra pro omezená prostředí“ (PDF ). eSTREAM. Citovat deník vyžaduje | deník = (Pomoc)CS1 maint: více jmen: seznam autorů (odkaz)
  5. ^ Ozgul Kucuk (2006-07-16). „Slide Resynchronization Attack on the Initialization of Grain 1.0“ (PS ). eSTREAM. Citovat deník vyžaduje | deník = (Pomoc)

externí odkazy