ISAAC

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é 18. září 2018; kontroly vyžadují 2 úpravy .

ISAAC (Indirection, Shift, Accumulate, Add and Count) je generátor pseudonáhodných čísel vyvinutý v roce 1996 Robertem J. Jenkinsem Jr. jako vývoj jím vyvinutých algoritmů IA a IBAA. Tento generátor je klasifikován jako generátor pseudonáhodných čísel odolný vůči kryptoměnám , ačkoli nebyl proveden úplný a přísný důkaz.

Historie vytvoření

Americký programátor Robert John Jenkins Jr. po absolvování Carnegie Mellon University v roce 1989 a čtyřech letech na Oracle odešel v roce 1993 do Berkeley , aby získal doktorát v teoretické informatice . Navzdory skutečnosti, že studium na Berkeley bylo pro Jenkinse vážnou zkouškou – musel ji po roce opustit – právě zde začal pracovat na studiu generátorů pseudonáhodných čísel v rámci kurzu Manuela Bluma o kryptografii . . V červenci 1993 začal Jenkins experimentovat s pseudonáhodnými čísly pro procesory Intel 486 a do dubna 1994 byl vyvinut ISAAC. Pravda, článek popisující jeho práci vyšel až o dva roky později, v únoru 1996. [jeden]

Předchůdci ISAAC

RC4

Šifrovací algoritmus RC4 [2] [3] se skládá ze dvou kroků: generování pseudonáhodné bitové sekvence a sčítání bit po bitu modulo dva této sekvence otevřeného textu .

Ve fázi generování pseudonáhodné sekvence hraje důležitou roli n - velikost S-boxu , datového pole, které vlastně určuje vnitřní stav RC4 . V RC4 jsou také použity následující proměnné: i a j jsou iterátory procházející hodnotami, pole Key of length length , ve kterém je klíč uložen speciálním způsobem, a pole S (aka S-blok). Výstupní data: pole z je pseudonáhodná sekvence . $2^{n}$

Zvažte algoritmus používající n = 8 jako příklad . Nejprve je pole S vyplněno čísly od 0 do , pole Key je vyplněno posloupností n-bitových slov. Pokud je délka klíče menší než délka S, pak se sekvence opakuje, dokud není její délka rovna . Pak algoritmus funguje takto: $2^{n}-1$ $2^{n}$

i = 0; j = 0; zatímco i < 256 //256 = 2^n j = (j + S[i] + Key[i délka modu]) mod 256; swap S[i] a S[j]; i++;

Po této fázi - inicializační fázi - následuje fáze vlastního generování pseudonáhodné sekvence:

i = 0; j = 0; zatímco já < 256 j = (j + S[i]) mod 256; swap S[i] a S[j]; z[i] = S[(S[i] + S[j]) mod 256]; i++;

Výstupem je posloupnost délky n, s jejíž pomocí se pak zašifruje otevřený text.

IA

IA (Indirection, Addition) je algoritmus, který vyvinul Jenkins tak, aby mohl splňovat následující požadavky [4] :

nemožnost získat vnitřní stav z dostupných výstupních výsledků;
snadno zapamatovatelný kód;
nejvyšší možná rychlost;

Vstupní data algoritmu IA: pole S , sestávající z prvků od 0 do , náhodně rozmístěných po poli, iterátory i a j . Výstupní datové pole z je výsledkem algoritmu. Také hodnoty buněk v poli - tedy délka slov - musí být větší než bit, Jenkins ve své práci zabírá K = 32 bitů - to je délka slova, která se používá v všechny zde popsané algoritmy. $2^{n}$ $2^{n}-1$ $2*n$

IBAA

IBAA (Indirection, Barrelshift, Accumulate and Add) je algoritmus vytvořený Jenkinsem založený na IA. Autor se domnívá, že IBAA má kromě již dostupných výhod pro IA následující výhody [5] :

Kryptografické zabezpečení
Po celé délce cyklu by neměly být detekovány žádné odchylky.
Krátké cykly by měly být neuvěřitelně vzácné.

Na rozdíl od RC4 a IA je IBAA založen na cyklických posunech bitových dat doleva. Implementace IBAA používá stejnou množinu proměnných jako IA, jen s tím rozdílem, že jsou přidány akumulátory a a b , stejně jako funkce barrelshift , funkce, která provádí výše zmíněný cyklický posun.

barel(j) - cyklicky posouvá všechny bity v poli 32 bitů doleva o 19 bitů. Může být také dán vzorcem , kde $(j<<19)\oplus (j>>13)$

$\oplus$ - bitový XOR

Operace >> zde znamená aritmetický posun doprava .

ISAAC

Popis

ISAAC (Indirection, Shift, Accumulate, Add and Count) je algoritmus pseudonáhodných čísel, jehož princip je hůře zapamatovatelný než principy IA a IBAA, má však oproti nim řadu výhod [6] . Při navrhování ISAAC mu byl předložen následující seznam požadavků:

šifrovací síla ;
nemožnost získat vnitřní stav z dostupných výstupních výsledků;
nedostatek krátkých cyklů;
nepřítomnost jakýchkoli trendů v distribuci bitů v průběhu cyklu;
uspořádané státy se musí rychle stát chaotickými.

Na rozdíl od většiny generátorů pseudonáhodných čísel, které jsou založeny na proudových šifrách , je ISAAC navržen bez použití posuvných registrů s lineární zpětnou vazbou.

Průměrný počet strojových instrukcí potřebných k získání 32bitové hodnoty je 18,75. 64bitová verze ISAAC (ISAAC-64) vyžaduje 19 instrukcí k získání jedné 64bitové hodnoty.

Operační algoritmus

Stejně jako v předchozích algoritmech má ISAAC pole S , které definuje vnitřní stav systému, sestávající také z prvků náhodně umístěných v poli od 0 do délky K bitů, iterátoru i a tří proměnných a , b a c , odpovědné za předchozí stavy generátoru, má výstupní datové pole z stejnou délku jako S . Kromě těchto proměnných jsou zde však představeny i proměnné , které určují hodnotu funkce, která závisí na obou iterátorech: $2^{n}$ $2^{n}-1$ ${\displaystyle p_{0},p_{1},p_{2},p_{3))$

$f(a,i)={\begin{cases}a<<p_{0},&{\text{if }}i\equiv 0{\text{ mod 4}}\\a>>p_ {1},&{\text{if }}i\ekviv 1{\text{ mod 4}}\\a<<p_{2},&{\text{if }}i\ekviv 2{\text{ mod 4}}\\a>>p_{3},&{\text{if }}i\equiv 3{\text{ mod 4}}\end{cases}}$ .

Jenkins ve svém článku navrhuje . $p_{0}=13,p_{1}=6,p_{2}=2,p_{3}=16$

Schéma činnosti generátoru v libovolném kroku pro n = 8, K = 32 je následující:

c = c + 1; b = b + c; i = 0; zatímco já < 255 x = S[i]; a = f(a,i) + S[i + 128 mod 256]; S[i] = a + b + S[x>>2 mod 256]; z[i] = x + S[S[i]>>10 mod 256]; b = z[i]; i++;

Kryptoanalýza od ISAAC

Na svém osobním webu autor ISAAC vyhlásil soutěž o hacknutí generátoru - ten, kdo jako první dokáže specifikovat číslo použité jako seed ( anglicky seed) pro vygenerování prvních 2560 hodnot vydaných generátorem, obdrží 1 000 $ cena od Jenkinse. S tímto úkolem se však zatím nikdo nedokázal vyrovnat. Nicméně ISAAC byl zvažován ve spisech řady kryptoanalytiků.

Pudovkinův útok

V roce 2001 vyšel článek [7] , ve kterém Marina Pudovkina popsala útok založený na prostých textech , pomocí kterého můžete z malého segmentu výstupních dat zjistit počáteční stav generátoru a také poskytla přesný odhad složitost takového útoku. Pomocí algoritmu popsaného v článku se Pudovkině podařilo snížit složitost hackování na , zatímco složitost vyčerpávajícího vyhledávání [8] . Podle jejích výpočtů je pro , složitost crackování vyčerpávajícím hledáním , při použití Pudovkina algoritmu by toto číslo mohlo být sníženo na . Taková složitost je však stále příliš velká na to, abychom ISAAC označili za zranitelný generátor pseudonáhodných čísel, shrnuje kryptoanalytik ve svém článku. $T_{met}=2^{(2n+\theta _{2})(m-1)}(K-2n-\theta _{2}){\frac {2}{3}}m$ $T_{br}=2^{Km-1}$ $m=256,n=8,K=32,p_{\theta }=13,p_{1}=6,p_{2}=2,p_{3}=16,\theta _{1} =\theta _{2}=2$ $T_{br}=5,91*10^{2446}$ $T_{met}=4,67*10^{1240}$

Analýza Jean-Philippe Aumasson

Omasson ve svém článku z roku 2006 [9] popisuje čtyři sady „slabých“ počátečních stavů , které se mohou vzájemně prolínat. Slabé stavy jsou stavy, pro které jsou některé prvky náhodné a zbývající prvky mají stejnou hodnotu. Jestliže je počáteční stav, pak jej lze definovat pomocí vztahu: , then je definováno jako , množina je definována jako , while je zadáno následovně: . Autor zvážil algoritmus ISAAC se stejnými hodnotami uvedenými výše (tj. n = 8, K = 32) a vypočítal počet slabých stavů pro každou ze sad. Pro toto číslo bylo států, pro - uvádí, pro - , ale je podmnožinou . Přítomnost takových stavů ještě neznamená, že ISAAC lze snadno hacknout, ale jsou potenciálními slabinami algoritmu, proto Omasson navrhl upravenou verzi ISAAC - ISAAC+ [10] . ${\displaystyle W_{1},W_{2},W_{3},W_{4))$ $\alpha$ $W_{1}$ ${\displaystyle \alpha \in W_{1}\Longleftrightarrow \alpha _{0}=\alpha _{1))$ $W_2$ $\alpha \in W_{2}\Longleftrightarrow \exists N\in \{2,...,256\},\exists X\in \{0,...,2^{32}-1 \},\alpha _{0}=X,\{0<i<256,\alpha _{i}=X\}=N-1$ ${\displaystyle W_{3))$ $\alpha \in W_{3}\Longleftrightarrow \exists N\in \{2,...,256\},\exists X\in \{0,...,2^{32}-1 \},\forall i\in \{0,...,N-1\},\alpha _{i}=X$ ${\displaystyle W_{4))$ $\alpha \in W_{4}\Longleftrightarrow \exists X\in \{0,...,2^{32}-1\},\forall i\in \{0,...,255 \},\alpha _{i}=X$ $W_{1}$ $2^{8160}$ $W_2$ $2^{8167.99}$ ${\displaystyle W_{4))$ $2^{32}$ ${\displaystyle W_{3))$ $W_2$

ISAAC+

Vstup je v určitém kroku stejný jako v ISAAC, čísla a , b a c , pole S , složené z 256 32bitových slov, výstup je pole z stejné dimenze jako S . V popisu funkce jsou místo logických bitových posunů >> a << použity cyklické >>> a <<<, tedy funkce $f(a,i)$

$f'(a,i)={\begin{cases}a<<<p_{0},&{\text{if }}i\equiv 0{\text{ mod 4}}\\a> >>p_{1},&{\text{if }}i\ekviv 1{\text{ mod 4}}\\a<<<p_{2},&{\text{if }}i\ekviv 2 {\text{ mod 4}}\\a>>>p_{3},&{\text{if }}i\equiv 3{\text{ mod 4}}\end{cases}}$

Změnil se také způsob, jakým jsou S[i] a z[i] v každém kroku iniciovány – v obou případech se používá bitový XOR. Tedy místo toho

S[i] = a + b + S[x>>2 mod 256]; z[i] = x + S[S[i]>>10 mod 256];

ISAAC+ používá:

S[i] = a ⊕ b + S[x>>>2 mod 256]; z[i] = x + a ⊕ S[S[i]>>>10 mod 256]; Útok Paula-Pranila. Kritika

Ve stejném roce 2006 Paul a Praenil publikovali článek [11] , ve kterém studovali charakteristický útok na některé streamingové generátory podobné RC4, včetně IA a ISAAC . Ve své práci ukazují, že složitost prolomení ISAAC je pouze [12] . Omasson tento útok neignoroval [13] a poukázal na chybnou iniciaci algoritmu Paulem a Prenilem, díky čemuž bylo možné tolik snížit složitost jeho prolomení. $T\cca 2^{17}$

Aplikace

Mnoho implementací ISAAC je dostatečně rychlých a spolehlivých, aby se tento generátor pseudonáhodných čísel stal zcela běžným. ISAAC se používá například v unixové utilitě shred (Unix) [14] pro šifrování přepsaných dat. Generátor náhodných čísel založený na ISAAC je implementován v jedné z nejběžnějších Java matematických knihoven, Apache Commons Math [15] .

Poznámky

↑ Stručná autobiografie Roberta Jenkinse . burtleburtle.net. Získáno 25. listopadu 2016. Archivováno z originálu 9. srpna 2016. (neurčitý)
↑ Schneier B., 2002 , s. 236.
↑ Paul G., Sabemoy M., 2001 , s. 16-19.
↑ Jenkins R.J., 1996 , s. 41, 42-43.
↑ Jenkins R.J., 1996 , s. 41, 43-45.
↑ Jenkins R.J., 1996 , s. 41, 46-49.
↑ Pudovkina M.A., 2001 .
↑ Pudovkina M.A., 2001 , str. 9.
↑ Omasson J.F., 2006 .
↑ Omasson J.F., 2006 , s. 5.
↑ Paul S., Preneel B., 2006 .
↑ Paul S., Preneel B., 2006 , s. 9-10.
↑ Omasson J.F., 2006 , s. 6.
↑ GNU coreutils git . Získáno 3. prosince 2016. Archivováno z originálu dne 21. září 2019. (neurčitý)
↑ Apache Common Math docs . Získáno 3. prosince 2016. Archivováno z originálu dne 22. dubna 2017. (neurčitý)

Literatura

Schneier B. RC4 // Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumf, 2002. - S. 236. - 816 s. - ISBN 5-89392-055-4 .
Paul G., Sabamoy M. Streamová šifra RC4 // Streamová šifra RC4 a její varianty = Streamová šifra RC4 a její varianty. - Boca Raton: CRC Press, 2001. - S. 16-19. — 285 str.
Jenkins R.J. ISAAC // Poznámky k přednáškám z informatiky. - Rychlé softwarové šifrování, 1996. - Sv. 1039 . - str. 41-49 .
Pudovkina M. A. Známý útok v otevřeném textu na generátor keystreamu ISAAC (eng.) . — Archiv ePrint IACR, 2001.
Paul S., Pranil B. O (ne)bezpečnosti proudových šifer založených na polích a modulárním sčítání (anglicky) // Advances in Cryptology - Asiacrypt 2006. - Asiacrypt, 2006.
Omasson J.F. O pseudonáhodném generátoru ISAAC . — Archiv ePrint IACR, 2006.

Odkazy

Oficiální stránky projektu ISAAC
Matematika:: Náhodný:: ISAAC - Perl implementace algoritmu
http://guilload.com/pyisaac/ - implementace algoritmu v Pythonu
https://rosettacode.org/wiki/The_ISAAC_Cipher - implementace algoritmu v 19 různých programovacích jazycích