Králičí

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 12. listopadu 2018; kontroly vyžadují 6 úprav .

Králík je vysokorychlostní proudová šifra poprvé představená [1] v únoru 2003 na 10. FSE Symposium. V květnu 2005 byl přihlášen do soutěže eStream , jejímž cílem bylo vytvořit evropské standardy pro systémy šifrování streamů.

Rabbit vyvinuli Martin Boesgaard , Mette Vesterager , Thomas Pedersen , Jesper Christiansen a Ove Scavenius .

Králík používá 128bitový klíč a 64bitový inicializační vektor. Šifra byla navržena pro použití v softwaru jako vysoká rychlost šifrování. Zároveň by rychlost šifrování mohla dosáhnout 3,7 cyklů na bajt ( CPB ) pro procesor Pentium 3 a 10,5 cyklů na bajt pro ARM7. Šifra se však také ukázala jako rychlá a kompaktní při implementaci do hardwaru.

Hlavní součástí šifry je generátor bitového toku , který zašifruje 128 bitů zprávy na iteraci. Výhoda šifry je v důkladném promíchání jejích vnitřních stavů mezi dvěma po sobě jdoucími iteracemi. Funkce míchání je zcela založena na aritmetických operacích dostupných na moderních procesorech, tj . k implementaci šifry nejsou potřeba substituční S-boxy a vyhledávací tabulky.

Autoři šifry poskytli úplnou sadu datových listů na domovské stránce Cryptico [2] . Šifra je také popsána v RFC 4503 . Cryptico vlastnil patent na šifru a po mnoho let komerční využití šifry vyžadovalo licenci. Dne 6. října 2008 však bylo povoleno bezplatně používat šifru k jakémukoli účelu [3] .

Králík a eStream [4]

Soutěž eStream

Proudové šifry projektu eSTREAM se skládají ze dvou profilů. Profil 1 obsahuje softwarově orientované šifry a Profil 2 zahrnuje hardwarově orientované šifry.

Nejlepší šifry projektu:

Profil 1	Profil 2
HC-128	F-FCSR-H v2
Králičí	Zrno v1
Salsa 20/12	MICKEY v2
Sosemanuk	Trivium

Profil 1 obsahuje symetrické proudové šifry s dobrou softwarovou implementací. Tak dobré, že by měly překonat blokový symetrický šifrovací algoritmus AES v režimech generování gama. Hlavním požadavkem na tento profil bylo poskytnout úroveň zabezpečení 128 bitů.

Přednosti a nedostatky králičí šifry

Králík je jedním z nejstarších návrhů projektu eSTREAM. Tato proudová šifra nebyla podrobena žádným úpravám ani dodatkům. Jeho specifikace se od roku 2003 do současnosti nezměnila. Šifra přežila všechny tři fáze projektu a v žádné z nich nebyla vystavena kryptoanalytickým útokům. Tento algoritmus je mimo jiné velmi dobře implementován na nových procesorech rodiny Intel. Jako nevýhodu můžete vidět skutečnost, že šifra Rabbit poskytuje úroveň zabezpečení pouze 128 bitů.

Výsledky závěrečného hlasování projektu eSTREAM pro Profil 1.

Profil 1	brýle
Králičí	2,80
Salsa20	2,80
Sosemanuk	1.20
HC-128	0,60
NLS v2	-0,60
LEXv2	−1,20
CryptoMT v3	−1,40
Drak	−1,60

Algoritmus

Vnitřní stav proudové šifry obsahuje 513 bitů. 512 z nich je rozděleno do osmi 32bitových stavových proměnných a osmi 32bitových čítačů , kde je stavová proměnná subsystému během iterace a je odpovídající čítač proměnných. 513. bit je přenosový bit , který musí být uložen mezi iteracemi. Tento bit je inicializován na nulu. Při inicializaci závisí na klíči 8 stavových proměnných a 8 čítačů. $x_{{j,i}}$ $c_{{j,i}}$ $x_{{j,i}}$ $j$ $i$ $c_{{j,i}}$ ${\displaystyle \phi _{7,i))$

Diagram nastavení stavu

Algoritmus se inicializuje rozšířením 128bitového klíče na 8 stavových proměnných a 8 čítačů, takže mezi klíčem, proměnnými počátečního stavu a počátečními čítači existuje vzájemná shoda jedna ku jedné . Klíč je rozdělen do 8 podklíčů: , , … , , stavové proměnné a čítače se inicializují pomocí podklíčů $x_{{j,0}}$ $c_{{j,0}}$ $K^{[127..0]}$ $k_{0}^{[15..0]}$ $k_{1}^{[31..16]}$ $k_{7}^{[127..112]}$

x_{j,0}={\begin{cases}k_{(j+1\mod 8)}\diamant k_{j},&{\text{pro sudý))\ j,\\k_{ (j+5\mod 8)}\diamant k_{(j+4\mod 8)},&{\text{for odd}}\ j,\\\end{cases}}

c_{j,0}={\begin{cases}k_{(j+4\mod 8)}\diamant k_{(j+5\mod 8)},&{\text{pro sudý)) \ j,\\k_{j}\diamant k_{(j+1\mod 8)},&{\text{for odd}}\ j,\\\end{cases}}

kde je operace zřetězení. $\diamant$

Systém se spustí 4krát podle funkce dalšího stavu definované níže, aby se snížila korelace mezi bity klíče a bity vnitřních stavových proměnných. Na konci se počítadla znovu inicializují následovně:

{\displaystyle c_{j,4}=c_{j,4}\oplus x_{(j+4mod8),4))

aby se zabránilo obnovení klíče invertováním systému počítadel.

Funkce dalšího stavu

x_{{0,i+1}}=g_{{0,i}}+(g_{{7,i}}\lll 16)+(g_{{6,i}}\lll 16)

x_{{1,i+1}}=g_{{1,i}}+(g_{{0,i}}\lll 8)+g_{{7,i}}

x_{{2,i+1}}=g_{{2,i}}+(g_{{1,i}}\lll 16)+(g_{{0,i}}\lll 16)

x_{{3,i+1}}=g_{{3,i}}+(g_{{2,i}}\lll 8)+g_{{1,i}}

x_{{4,i+1}}=g_{{4,i}}+(g_{{3,i}}\lll 16)+(g_{{2,i}}\lll 16)

x_{{5,i+1}}=g_{{5,i}}+(g_{{4,i}}\lll 8)+g_{{3,i}}

x_{{6,i+1}}=g_{{6,i}}+(g_{{5,i}}\lll 16)+(g_{{4,i}}\lll 16)

x_{{7,i+1}}=g_{{7,i}}+(g_{{6,i}}\lll 8)+g_{{5,i}}

g_{j,i}=\jméno operátora {LSW} ((x_{j,i}+c_{j,i})^{2})\oplus \jméno operátora {MSW} ((x_{j,i }+c_{j,i})^{2})

Zde jsou všechny doplňky modulo 2 32 . Funkce a vracejí dolní a horní čtyři bajty 64bitového čísla , - cyklický posun doleva. $\operatorname {LSW} (x)$ $\operatorname {MSW} (x)$ $X$ $\já budu$

Počítací systém

Rovnice, které specifikují změnu v systému čítačů:

c_{{0,i+1}}=c_{{0,i}}+a_{0}+\phi _{{7,i}}\mod 2^{{32}}

c_{{1,i+1}}=c_{{1,i}}+a_{1}+\phi _{{0,i+1}}\mod 2^{{32}}

c_{{2,i+1}}=c_{{2,i}}+a_{2}+\phi _{{1,i+1}}\mod 2^{{32}}

c_{{3,i+1}}=c_{{3,i}}+a_{3}+\phi _{{2,i+1}}\mod 2^{{32}}

{\displaystyle c_{4,i+1}=c_{4,i}+a_{4}+\phi _{3,i+1}\mod 2^{32))

c_{{5,i+1}}=c_{{5,i}}+a_{5}+\phi _{{4,i+1}}\mod 2^{{32}}

c_{{6,i+1}}=c_{{6,i}}+a_{6}+\phi _{{5,i+1}}\mod 2^{{32}}

c_{{7,i+1}}=c_{{7,i}}+a_{7}+\phi _{{6,i+1}}\mod 2^{{32}}

kde počet bitů přenosu je dán $\phi _{j,i+1}$

\phi _{j,i+1}={\begin{cases}1,&{\text{if))\ c_{0,i}+a_{0}+\phi _{7,i }\geqslant 2^{32}\wedge j=0,\\1,&{\text{if))\ c_{j,i}+a_{j}+\phi _{j-1,i+1 }\geqslant 2^{32}\wedge j>0,\\0,&{\text{jinak}}.\end{cases}}

Konstanty jsou také definovány jako $aj}$

a_{0}={\mathtt {0x4D34D34D)),\quad a_{1}={\mathtt {0xD34D34D3)),

a_{2}={\mathtt {0x34D34D34)),\quad a_{3}={\mathtt {0x4D34D34D)),

a_{4}={\mathtt {0xD34D34D3)),\quad a_{5}={\mathtt {0x34D34D34)),

a_{6}={\mathtt {0x4D34D34D)),\quad a_{7}={\mathtt {0xD34D34D3)).

Schéma extrakce

Po každé iteraci je generováno 128 výstupních bitů pomocí následujících vzorců:

s_{i}^{{[15..0]}}=x_{{0,i}}^{{[15..0]}}\oplus x_{{5,i}}^{{[31 ..16]}}

s_{i}^{{[31..16]}}=x_{{0,i}}^{{[31..16]}}\oplus x_{{3,i}}^{{[15 ..0]}}

s_{i}^{{[47..32]}}=x_{{2,i}}^{{[15..0]}}\oplus x_{{7,i}}^{{[31 ..16]}}

s_{i}^{{[63..48]}}=x_{{2,i}}^{{[31..16]}}\oplus x_{{5,i}}^{{[15 ..0]}}

s_{i}^{{[79..64]}}=x_{{4,i}}^{{[15..0]}}\oplus x_{{1,i}}^{{[31 ..16]}}

s_{i}^{{[95..80]}}=x_{{4,i}}^{{[31..16]}}\oplus x_{{7,i}}^{{[15 ..0]}}

s_{i}^{{[111..96]}}=x_{{6,i}}^{{[15..0]}}\oplus x_{{3,i}}^{{[31 ..16]}}

s_{i}^{{[127..112]}}=x_{{6,i}}^{{[31..16]}}\oplus x_{{1,i}}^{{[15 ..0]}}

kde je 128bitový blok toku šifrování v iteraci. $s_{i}$ $i$

Schéma šifrování a dešifrování

Operace XOR se provádí mezi extrahovanými bity a textem/šifrovaným textem pro šifrování/dešifrování.

c_{i}=p_{i}\oplus s_{i},

p_{i}=c_{i}\oplus s_{i},

kde a označují tý blok šifrovaného textu a textu. $c_{i}$ $p_{i}$ $i$

Vlastnosti schématu nastavení klíče

Instalaci klíče lze rozdělit do tří fází: rozšíření klíče, iterační systém, úprava čítače.

Stupeň rozšíření klíče zaručuje vzájemnou shodu mezi klíčem stavu a klíčem čítače, což zabraňuje tomu, aby klíče byly nadbytečné. Také přiděluje klíčové bity optimálním způsobem pro iterace.
Iterační systém zajišťuje, že po jedné iteraci funkce dalšího stavu ovlivní každý bit klíče všech osm stavových proměnných. Také zajišťuje, že po druhé iteraci funkce dalšího stavu ovlivní všechny klíčové bity všechny stavové bity s pravděpodobností 0,5. Kvůli spolehlivosti šifrování se iterace provádí čtyřikrát.
I když jsou čítače známé útočníkovi, úprava čítače značně komplikuje obnovu klíče invertováním systémového čítače, protože bude vyžadovat informace o stavových proměnných a také poruší vztah jedna ku jedné mezi klíčem. a počítadlo.

Zabezpečení

Králík poskytuje 128bitovou ochranu proti útočníkům, jejichž cílem je jediný unikátní klíč. Pokud dojde k útoku na několik klíčů najednou a nezáleží na tom, který z nich je prolomený, pak se zabezpečení sníží na 96 bitů [5] .

Útoky na funkci zřízení klíče

Jakmile je klíč nastaven, bity čítače a stavu jsou přísně a velmi nelineárně závislé na bitech klíče. To znesnadňuje prolomení útoků na hádání částečného klíče, i když bity čítače byly známy po úpravě čítače. Znalost počítadel samozřejmě usnadňuje další typy hacků.

Kolizní útok

Králičí šifra používá nejednoznačné mapování, různé klíče mohou potenciálně vést ke stejnému gamutu. Tento problém se v podstatě scvrkává na otázku, zda různé klíče vedou ke stejným hodnotám čítačů, protože různé hodnoty čítačů téměř jistě povedou k různým generacím gama. Všimněte si, že systém rozšíření a iterace klíčů byl navržen tak, aby každý klíč vedl k jedinečným hodnotám čítačů. Úprava počítadla však může mít za následek stejné hodnoty počítadla pro dva různé klíče. Za předpokladu, že po čtyřech počátečních iteracích je vnitřní stav v podstatě náhodný a nekoreluje se systémem čítače, je pravděpodobnost kolizí dána „narozeninovým paradoxem“, tedy pro všechny klíče se očekává jedna kolize v 256- počítadlo bitů $2^{128}$ [ specifikovat ] . Kolize čítačového systému by tedy v praxi neměla způsobovat problémy.

Související klíčový útok

Útok je založen na využití vlastností symetrie v dalším stavu a funkcích nastavení klíčů. Uvažujme například dva klíče a související vztahem pro všechny . To vede ke vztahu a . Nyní zvažte, kdy a jsou stejný klíč. Pokud je podmínka splněna, pak by si další stavová funkce zachovala vlastnost symetrie. Ale lze snadno zkontrolovat, že konstanty jsou zvoleny tak, aby . Funkce dalšího stavu tedy není citlivá na související útok klíče. $K$ ${\tilde K}$ $K^{{[i]}}={\tilde K}^{{[i+2]}}$ $i$ $x_{{j,0}}={\tilda x}_{{j+2,0}}$ $c_{{j,0}}={\tilda c}_{{j+2,0}}$ $K$ ${\tilde K}$ $a_{{j,0}}={\tilda a}_{{j+2,0}}$ $aj}$ $a_{{j,0}}\neq {\tilde a}_{{j+2,0}}$

Částečný Key Guess Attack

Hádej a ověř útok

Takový útok by byl možný, pokud by výstupní bity mohly být predikovány pomocí malé sady vnitřních stavových bitů. Útočník musí uhodnout vhodnou část stavových proměnných, předpovědět výstupní bity a porovnat je s přímo pozorovanými bity na výstupu, aby si ověřil, že jeho odhad je správný. Útočník musí uhodnout alespoň 2*12 vstupních bajtů pro různé g-funkce, aby je mohl otestovat proti jednomu bajtu. To je ekvivalentní uhodnutí 192 bitů, což je těžší než zkoušet všechny klíče.

Útok hádej a urči

Podstatou této metody je, že musíte uhodnout několik neznámých proměnných šifry a pomocí nich odvodit zbývající neznámé. Poté se systém několikrát spustí a výstup se porovná se skutečným výstupem šifry, aby se ověřil předpoklad. Útočník se pokusí znovu vytvořit 512 bitů vnitřního stavu, tj. pozoruje 4 po sobě jdoucí 128bitová data na výstupu šifry a provede následující:

Rozděluje 32bitový čítač a 32bitovou stavovou proměnnou na 8bitové proměnné.
Píše systém rovnic, které modelují změnu čítačů a stavových proměnných, a výstupní data. Výsledkem je 160 rovnic a 160 neznámých.
Vyřeší tento systém tím, že uhodne co nejvíce neznámých.

Účinnost tohoto přístupu závisí na počtu uhodnutých proměnných. Toto číslo je zespodu ohraničeno 8bitovým subsystémem s nejmenším počtem vstupních proměnných. Pokud budeme čítače ignorovat, každý bajt funkce dalšího stavu závisí na 12 vstupních bytech. Pokud vezmete v úvahu čítače, každý bajt na výstupu subsystému již závisí na 24 vstupních bytech. Útočník tedy musí uhodnout více než 128 bitů, čímž útok znemožní.

Algebraické útoky

Algebraicky normální tvar (ANF) g-funkce

Daná booleovská funkce , ANF je reprezentace jako mnohorozměrný polynom (to je součet monomials od vstupních proměnných). Velký počet monočlenů a jejich dobrá distribuce energie jsou důležitými vlastnostmi nelineárních bloků v šifře. $f:(0,1)^{n}\rightarrow (0,1)$ $F$

Pro náhodnou booleovskou funkci ve 32 proměnných je průměrný počet monočlenů , a průměrný počet monočlenů, které zahrnují všechny dané proměnné, je . Pokud vezmeme v úvahu 32 náhodně vybraných funkcí, pak průměrný počet monočlenů, které nejsou v žádné z 32 funkcí, je 1 a odpovídající rozptyl je také 1. $2^{{31}}$ $2^{30}$

Pro g-funkci v králičí šifře má ANF pro 32 booleovských dílčích funkcí alespoň mocninu 30. Počet monočlenů se mění od do , kde pro náhodnou funkci by měl být . Rozdělení monočlenů jako funkce stupně je znázorněno na obrázku. V ideálním případě by hlavní část měla být mezi tečkovanými čarami, které ukazují odchylky od průměru ideální náhodné funkce. Některé booleovské funkce se výrazně liší od výsledků pro náhodnou funkci, nicméně všechny mají velký počet monočlenů vysokého stupně. $2^{{24.5}}$ $2^{{30,9}}$ $2^{{31}}$

Kromě toho byla zkoumána částečná koincidence 32 funkcí. Celkový počet monočlenů, které se vyskytují jednou, je , zatímco počet monočlenů, které se nevyskytují vůbec, je . Ve srovnání s náhodnou funkcí se jedná o poměrně velké odchylky. Tyto informace mohou být užitečné pro budoucí analýzu šifry. $2^{{26.03}}$ $2^{{26.2}}$

Algebraicky normální forma (ANF) pro úplnou šifru

Je prakticky nemožné vypočítat ANF pro všechny bity na výstupu pro úplnou šifru. Ale snížení velikosti klíče ze 128 bitů na 32 bitů umožňuje naučit se 32 booleovských výstupních funkcí jako funkce 32 bitového klíče.

U zkrácené verze králičí šifry byla funkce nastavení zkoumána pro různý počet iterací. ANF se určuje po 0, 1, 2, 3, 4 iteracích a jedné další iteraci ve schématu extrakce. Pro iterace 0+1 byl počet monočlenů přibližně 2^31, jak se očekávalo u náhodné funkce. Ale po dvou iteracích se výsledek stabilizoval. To znamená, že již nedochází ke kolísání výkonu. Počet chybějících polynomů je 0, 1, 2, 3, 1 v iteracích (0+1), ..., (4+1). Je zřejmé, že tato data odpovídají výsledkům pro náhodné funkce.

Korelační útoky

Lineární aproximace

Lineární útok zahrnuje nalezení nejlepší lineární aproximace mezi bity na vstupu funkce dalšího stavu a bity na výstupu extrakčního obvodu. K tomu použijte Walsh-Hadamardovu transformaci za předpokladu, že všechna vstupní data jsou lineárně nezávislá. Bylo zjištěno, že nejlepší lineární korelace má korelační koeficient řádu , který implikuje generování výstupu z iterací pro srovnání s náhodnou funkcí. $2^{{-57,8}}$ $2^{{114}}$

Aproximace druhého řádu

Odříznutí ANF pro g-funkci členů nad druhým řádem výrazně zlepšuje aproximaci za správných podmínek.

Označte aproximací druhého řádu ANF pro . Podle experimentálních výsledků je korelační koeficient mezi a menší než a korelační koeficient mezi a je přibližně roven . To znamená, že některé členy vyššího stupně jsou odříznuty, když je modulo 2 přidáno ke dvěma sousedním bitům. Na základě těchto dat dává šifra s druhým řádem aproximace přinejlepším korelační koeficient řádu . Tato hodnota korelačního koeficientu je pro útok nedostatečná. Pokud vezmeme v úvahu i čítače, pak je rozbor mnohem složitější. https://vk.com/tibber $f^{{[j]}}$ $g^{{[j]}}$ $F$ $G$ $2^{{-9,5}}$ $f^{{[j]}}\oplus f^{{[j+1]}}$ $g^{{[j]}}\oplus g^{{[j+1]}}$ $2^{{-2,72}}$ $2^{{-26.4}}$

Poznámky

↑ M. Boesgaard, M. Vesterager, T. Pedersen, J. Christiansen, O. Scavenius. Králík: Vysoce výkonná proudová šifra. Proč. FSE 2003. Springer LNCS 2887, pp. 307-329 ( PDF )
↑ M. Boesgaard, T. Pedersen, M. Vesterager, E. Zenner. The Rabbit Stream Cipher - Design a bezpečnostní analýza. Proč. SASC 2004. ( PDF Archivováno 17. května 2011 na Wayback Machine )
↑ Phorum :: ECRYPT fórum :: Králík se stává veřejnou doménou . Získáno 18. prosince 2010. Archivováno z originálu 30. června 2009. (neurčitý)
↑ Portfolio eSTREAM Steve Babbage, Christophe De Canni`ere, Anne Canteaut, Carlos Cid, Henri Gilbert, Thomas Johansson, Matthew Parker, Bart Preneel, Vincent Rijmen a Matthew Robshaw6 ( PDF archivováno 13. srpna 2012 na Wayback Machine )
↑ Christophe De Cannière, Joseph Lano a Bart Preneel , „Comments on the Rediscovery of Time Memory Data Tradeoffs“, 2005. ( PDF archivováno 6. července 2015 na Wayback Machine )

Odkazy

Domovská stránka Cryptico Archivováno 28. ledna 2011 na Wayback Machine
Rabbit RFC Archivováno 24. května 2011 na Wayback Machine
Stránka eSTREAM na Rabbit Archivováno 17. srpna 2010 na Wayback Machine
Srovnávací analýza šifer projektu eSTREAM

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) nafukovací ryba Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsob ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher