ISAAC

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 18 september 2018; kontroller kräver 2 redigeringar .

ISAAC (Indirection, Shift, Accumulate, Add and Count) är en pseudo-slumptalsgenerator , utvecklad 1996 av Robert J. Jenkins Jr., som en utveckling av IA- och IBAA-algoritmerna utvecklade av honom. Denna generator är klassificerad som en krypto-resistent pseudoslumptalsgenerator , även om ett fullständigt och noggrant bevis inte har utförts.

Skapande historia

Den amerikanske programmeraren Robert John Jenkins Jr. gick till Berkeley 1993 för att ta en doktorsexamen i teoretisk datavetenskap , efter examen från Carnegie Mellon University 1989 och fyra år vid Oracle . Trots att studier vid Berkeley var ett seriöst test för Jenkins - han var tvungen att sluta efter ett år - var det här han började sitt arbete med studier av pseudo-slumptalsgeneratorer som en del av Manuel Blums kurs i kryptografi . I juli 1993 började Jenkins experimentera med pseudoslumptal för Intel 486-processorerna, och i april 1994 hade ISAAC utvecklats. Det är sant att artikeln som beskriver hans arbete publicerades bara två år senare, i februari 1996. [ett]

ISAAC:s föregångare

RC4

RC4 [2] [3] krypteringsalgoritmen består av två steg: generering av en pseudo-slumpmässig bitsekvens och bit-för-bit summeringsmodulo två av denna klartextsekvens .

I skedet av generering av en pseudo-slumpmässig sekvens spelar n en viktig roll - storleken på S-boxen , datamatrisen, som faktiskt bestämmer det interna tillståndet för RC4 . Följande variabler används också i RC4: i och j är iteratorer som löper genom värden, en array Key of length length , där nyckeln lagras på ett speciellt sätt, och en array S (aka S-block). Utdata: array z är en pseudo-slumpmässig sekvens . $2^{n}$

Betrakta algoritmen med n = 8 som exempel . Först fylls S -matrisen med siffror från 0 till , Key -matrisen fylls med en sekvens av n-bitars ord. Om längden på tangenten är mindre än längden på S, upprepas sekvensen tills dess längd är lika med . Då fungerar algoritmen så här: $2^{n}-1$ $2^{n}$

i = 0; j = 0; medan i < 256 //256 = 2^n j = (j + S[i] + Tangent[i mod längd]) mod 256; byt S[i] och S[j]; i++;

Efter detta steg - initialiseringssteget - följer steget för den faktiska genereringen av den pseudo-slumpmässiga sekvensen:

i = 0; j = 0; medan jag <256 j = (j + S[i]) mod 256; byt S[i] och S[j]; z[i] = S[(S[i] + S[j]) mod 256]; i++;

Utdata är en sekvens med längden n, med hjälp av vilken klartexten sedan krypteras.

IA

IA (Indirection, Addition) är en algoritm som utvecklades av Jenkins så att den kan uppfylla följande krav [4] :

omöjligheten att erhålla ett internt tillstånd från tillgängliga resultat;
lätt att komma ihåg kod;
högsta möjliga hastighet;

Indata för IA-algoritmen: array S , bestående av element från 0 till , slumpmässigt fördelade över arrayen, iteratorer i och j . Utdatamatrisen z är resultatet av algoritmen. Dessutom måste värdena på cellerna i arrayen - det vill säga längden på orden - vara större än biten, Jenkins i sitt arbete tar K = 32 bitar - detta är längden på ordet som används i alla algoritmer som beskrivs här. $2^{n}$ $2^{n}-1$ $2*n$

IBAA

IBAA (Indirection, Barrelshift, Accumulate and Add) är en algoritm skapad av Jenkins baserad på IA. Författaren anser att IBAA har följande fördelar utöver de fördelar som redan finns tillgängliga för IA [5] :

Kryptografisk säkerhet
Inga förskjutningar bör detekteras över hela cykelns längd.
Korta cykler borde vara otroligt sällsynta.

Till skillnad från RC4 och IA är IBAA baserad på cykliska förskjutningar av bitdata åt vänster. IBAA-implementeringen använder samma uppsättning variabler som IA, med den enda skillnaden att ackumulatorerna a och b läggs till , såväl som barrelshift-funktionen , en funktion som utför det cykliska skiftet som nämns ovan.

barrel(j) - skiftar cykliskt alla bitar i en matris med 32 bitar åt vänster med 19 bitar. Det kan också ges av formeln , där $(j<<19)\oplus (j>>13)$

$\ plus$ - bitvis XOR

Operationen >> betyder här aritmetisk förskjutning till höger .

ISAAC

Beskrivning

ISAAC (Indirection, Shift, Accumulate, Add and Count) är en pseudo-slumptalsalgoritm, vars princip är svårare att komma ihåg än principerna för IA och IBAA, men den har ett antal fördelar jämfört med dem [6] . När han designade ISAAC presenterades följande lista med krav för honom:

kryptografisk styrka ;
omöjligheten att erhålla ett internt tillstånd från tillgängliga resultat;
brist på korta cykler;
frånvaron av några trender i fördelningen av bitar genom cykeln;
ordnade stater måste snabbt bli kaotiska.

Till skillnad från de flesta pseudo-slumptalsgeneratorer, som är baserade på strömchiffer , är ISAAC utformad utan användning av linjära återkopplingsskiftregister.

Det genomsnittliga antalet maskininstruktioner som krävs för att få ett 32-bitars värde är 18,75. 64-bitarsversionen av ISAAC (ISAAC-64) kräver 19 instruktioner för att få ett 64-bitarsvärde.

Operationsalgoritm

Precis som i de tidigare algoritmerna har ISAAC en array S som definierar systemets interna tillstånd, även den består av element slumpmässigt placerade i arrayen från 0 till en längd av K bitar, en iterator i och tre variabler a , b och c , ansvarig för de tidigare generatortillstånden , är utdatamatrisen z samma längd som S. Men förutom dessa variabler introduceras även variabler här , som bestämmer värdet på funktionen som beror på båda iteratorerna: $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\equiv 1{\text{ mod 4}}\\a<<p_{2},&{\text{if }}i\equiv 2{\text{ mod 4}}\\a>>p_{3},&{\text{if }}i\equiv 3{\text{ mod 4}}\end{cases}}$ .

I sin artikel föreslår Jenkins . $p_{0}=13,p_{1}=6,p_{2}=2,p_{3}=16$

Generatordriftsschemat i ett godtyckligt steg för n = 8, K = 32 är som följer:

c = c + 1; b = b + c; i = 0; medan jag <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++;

Kryptanalys av ISAAC

På sin personliga hemsida tillkännagav författaren till ISAAC en tävling för att hacka generatorn - den första som kan ange numret som används som frö ( engelsk frö) för att generera de första 2560 värdena som utfärdas av generatorn kommer att få en $ 1000 pris från Jenkins. Men hittills har ingen klarat av denna uppgift. ISAAC har dock beaktats i ett antal kryptoanalytikers skrifter.

Pudovkinas attack

År 2001 publicerades en artikel [7] där Marina Pudovkina beskrev en attack baserad på klartexter , med vilken du kan hitta generatorns initiala tillstånd från ett litet segment av utdata, och även gav en korrekt uppskattning av komplexiteten i en sådan attack. Genom att använda algoritmen som beskrivs i artikeln lyckades Pudovkina minska komplexiteten i hackning till , medan komplexiteten i uttömmande sökning [8] . Enligt hennes beräkningar, för , komplexiteten av sprickbildning genom uttömmande sökning är , medan du använder Pudovkina-algoritmen, kan detta antal reduceras till . En sådan komplexitet är dock fortfarande för stor för att kalla ISAAC för en sårbar pseudo-slumptalsgenerator, sammanfattar kryptoanalytikern i sin artikel. $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}$

Jean-Philippe Aumassons analys

I sitt dokument från 2006 [9] beskriver Omasson fyra uppsättningar av "svaga" initiala tillstånd som kan skära varandra. Svaga tillstånd är de tillstånd för vilka några av elementen är slumpmässiga, och de återstående elementen är lika med samma värde. Om är det initiala tillståndet kan det definieras med hjälp av relationen: , then definieras som , mängden definieras som , medan den specificeras enligt följande: . Författaren övervägde ISAAC-algoritmen med samma värden som anges ovan (dvs. n = 8, K = 32) och beräknade antalet svaga tillstånd för var och en av uppsättningarna. För detta nummer var tillstånd, för - tillstånd, för- , men är en delmängd av . Närvaron av sådana tillstånd betyder ännu inte att ISAAC lätt kan hackas, men de är potentiella svagheter i algoritmen, så Omasson föreslog en modifierad version av ISAAC - ISAAC + [10] . ${\displaystyle W_{1},W_{2},W_{3},W_{4))$ $\alfa$ $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$ $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}$ $W_{4}$ $2^{32}$ ${\displaystyle W_{3))$ $W_2$

ISAAC+

Inmatningen vid något steg är densamma som i ISAAC, siffrorna a , b och c , arrayen S , sammansatt av 256 32-bitars ord, utmatningen är en array z med samma dimension som S . I funktionsbeskrivningen används istället för logiska bitskift >> och <<, cykliska >>> och <<<, det vill säga funktionen används $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\equiv 1{\text{ mod 4}}\\a<<<p_{2},&{\text{if }}i\equiv 2 {\text{ mod 4}}\\a>>>p_{3},&{\text{if }}i\equiv 3{\text{ mod 4}}\end{cases}}$

S [i] och z[i] initieras vid varje steg har också förändrats - i båda fallen används bitvis XOR. Det vill säga istället för

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

ISAAC+ använder:

S[i] = a ⊕ b + S[x>>>2 mod 256]; z[i] = x + a ⊕ S[S[i]>>>10 mod 256]; Attack av Paul-Pranil. Kritik

Samma 2006 publicerade Paul och Praenil en artikel [11] där de studerade en särskiljande attack på några strömmande RC4-liknande generatorer, inklusive IA och ISAAC . I sitt arbete visar de att komplexiteten i att bryta ISAAC bara är [12] . Omasson ignorerade inte denna attack [13] och påpekade den felaktiga initieringen av algoritmen av Paul och Prenil, på grund av vilken det blev möjligt att minska komplexiteten i att bryta den så mycket. $T\approx 2^{17}$

Applikation

Många ISAAC-implementeringar är tillräckligt snabba och tillförlitliga för att denna pseudo-slumptalsgenerator har blivit ganska vanlig. ISAAC används till exempel i Unix-verktyget shred (Unix) [14] för att kryptera omskriven data. Den ISAAC-baserade slumptalsgeneratorn är implementerad i ett av de vanligaste matematiska Java-biblioteken, Apache Commons Math [15] .

Anteckningar

↑ Kort självbiografi av Robert Jenkins . burtleburtle.net. Hämtad 25 november 2016. Arkiverad från originalet 9 augusti 2016. (obestämd)
↑ Schneier B., 2002 , sid. 236.
↑ Paul G., Sabemoy M., 2001 , sid. 16-19.
↑ Jenkins R.J., 1996 , sid. 41, 42-43.
↑ Jenkins R.J., 1996 , sid. 41, 43-45.
↑ Jenkins R.J., 1996 , sid. 41, 46-49.
↑ Pudovkina M.A., 2001 .
↑ Pudovkina M.A., 2001 , sid. 9.
↑ Omasson J.F., 2006 .
↑ Omasson J.F., 2006 , sid. 5.
↑ Paul S., Preneel B., 2006 .
↑ Paul S., Preneel B., 2006 , sid. 9-10.
↑ Omasson J.F., 2006 , sid. 6.
↑ GNU coreutils git . Hämtad 3 december 2016. Arkiverad från originalet 21 september 2019. (obestämd)
↑ Apache Common Math docs . Hämtad 3 december 2016. Arkiverad från originalet 22 april 2017. (obestämd)

Litteratur

Schneier B. RC4 // Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M . : Triumf, 2002. - S. 236. - 816 sid. - ISBN 5-89392-055-4 .
Paul G., Sabamoy M. RC4 Stream Chiffer // RC4 Stream Chiffer och dess varianter = RC4 Stream Chiffer och dess varianter. - Boca Raton: CRC Press, 2001. - S. 16-19. — 285 sid.
Jenkins R.J. ISAAC // Lecture Notes in Computer Science. - Fast Software Encryption, 1996. - Vol. 1039 . - S. 41-49 .
Pudovkina M. A. En känd klartextattack på ISAAC-nyckelströmsgeneratorn (eng.) . — IACR ePrint Archive, 2001.
Paul S., Pranil B. On the (o)security of stream ciphers based on arrays and modular addition (engelska) // Advances in Cryptology - Asiacrypt 2006. - Asiacrypt, 2006.
Omasson J.F. På pseudo-slumpgeneratorn ISAAC . — IACR ePrint Archive, 2006.

Länkar

Officiell webbplats för ISAAC-projektet
Math::Random::ISAAC - Perl-implementering av algoritmen
http://guilload.com/pyisaac/ - implementering av algoritmen i Python
https://rosettacode.org/wiki/The_ISAAC_Cipher - implementering av algoritmen i 19 olika programmeringsspråk