ISAAC

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2018. szeptember 18-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

Az ISAAC (Indirection, Shift, Accumulate, Add and Count) egy pszeudo-véletlen számgenerátor , amelyet 1996-ban Robert J. Jenkins Jr. fejlesztett ki az általa kifejlesztett IA és IBAA algoritmusok továbbfejlesztéseként. Ez a generátor kripto-rezisztens pszeudo-véletlenszám-generátornak minősül , bár teljes és szigorú bizonyításra nem került sor.

Létrehozási előzmények

Robert John Jenkins Jr. amerikai programozó 1993-ban Berkeley -ben szerzett Ph.D fokozatot elméleti számítástechnikából , miután 1989-ben diplomázott a Carnegie Mellon Egyetemen és négy évet az Oracle -nél . Annak ellenére, hogy a Berkeley-ben való tanulás komoly próbatétel volt Jenkins számára – egy év után abba kellett hagynia –, Manuel Blum kriptográfiai kurzusának részeként itt kezdte el a pszeudo-véletlenszám-generátorok tanulmányozását . . 1993 júliusában Jenkins kísérletezni kezdett az Intel 486 processzorok pszeudo-véletlen számokkal, és 1994 áprilisára kifejlesztették az ISAAC-ot. Igaz, a munkásságát ismertető cikk csak két évvel később, 1996 februárjában jelent meg. [egy]

Az ISAAC elődei

RC4

Az RC4 [2] [3] titkosítási algoritmus két lépésből áll: egy pszeudo-véletlen bitsorozat generálása és a bitenkénti összegzés, amely ennek az egyszerű szöveges szekvenciának a második modulja .

A pszeudo-véletlen sorozat generálásának szakaszában az n fontos szerepet játszik - az S-box mérete , az adattömb, amely valójában meghatározza az RC4 belső állapotát . Az RC4-ben a következő változók is használatosak: i és j értékeken átfutó iterátorok , hosszúságú Key tömb , amelyben a kulcs speciális módon van tárolva, és egy S tömb (más néven S-blokk). Kimeneti adatok: a z tömb egy pszeudo-véletlen sorozat . $2^{n}$

Tekintsük az n = 8 -at használó algoritmust példaként . Először az S tömböt 0 -tól ig terjedő számokkal , a Key tömböt n-bites szavak sorozatával töltjük meg. Ha a billentyű hossza kisebb, mint S, akkor a sorozatot addig ismételjük, amíg a hossza egyenlő lesz . Ezután az algoritmus a következőképpen működik: $2^{n}-1$ $2^{n}$

i = 0; j = 0; míg i < 256 //256 = 2^n j = (j + S[i] + Kulcs[i mod hossza]) mod 256; S[i] és S[j] felcserélése; i++;

Ezt a szakaszt - az inicializálási szakaszt - követően a pszeudo-véletlen sorozat tényleges generálásának szakasza következik:

i = 0; j = 0; míg én <256 j = (j + S[i]) mod 256; S[i] és S[j] felcserélése; z[i] = S[(S[i] + S[j]) mod 256]; i++;

A kimenet egy n hosszúságú szekvencia, amelynek segítségével a nyílt szöveget ezután titkosítják.

IA

Az IA (Indirection, Addition) egy algoritmus, amelyet a Jenkins fejlesztett ki, hogy megfeleljen a következő követelményeknek [4] :

a rendelkezésre álló kimeneti eredményekből belső állapot megszerzésének lehetetlensége;
könnyen megjegyezhető kód;
a lehető legnagyobb sebesség;

Az IA algoritmus bemeneti adatai: S tömb , amely 0 -tól ig terjedő elemekből áll , véletlenszerűen elosztva a tömbön, i és j iterátorok . A z kimeneti adattömb az algoritmus eredménye. Ezenkívül a tömb celláinak értékének - vagyis a szavak hosszának - nagyobbnak kell lennie, mint a bit, Jenkins munkájában K = 32 bitet vesz fel - ez a szó hossza, amelyet a az itt leírt összes algoritmust. $2^{n}$ $2^{n}-1$ $2*n$

IBAA

Az IBAA (Indirection, Barrelshift, Accumulate and Add) egy Jenkins által az IA-n alapuló algoritmus. A szerző úgy véli, hogy az IBAA a következő előnyökkel rendelkezik az IA számára már elérhető előnyök mellett [5] :

Kriptográfiai biztonság
A ciklus teljes hosszában nem szabad eltolást észlelni.
A rövid ciklusoknak hihetetlenül ritkáknak kell lenniük.

Az RC4-től és az IA-tól eltérően az IBAA a bitadatok ciklikus balra tolódásán alapul . Az IBAA megvalósítás ugyanazt a változókészletet használja, mint az IA, azzal az egyetlen különbséggel, hogy az a és b akkumulátorok hozzáadódnak , valamint a barrelshift függvény , amely a fent említett ciklikus eltolást hajtja végre.

barrel(j) – ciklikusan eltolja a 32 bites tömb összes bitjét 19 bittel balra. Megadható a képlettel is , ahol $(j<<19)\oplus (j>>13)$

$\oplus$ - bitenkénti XOR

A >> művelet itt jobbra való aritmetikai eltolást jelent .

ISAAC

Leírás

Az ISAAC (Indirection, Shift, Accumulate, Add and Count) egy pszeudo-véletlenszám-algoritmus, melynek elve nehezebben megjegyezhető, mint az IA és az IBAA elve, de számos előnye van velük szemben [6] . Az ISAAC tervezésekor a következő követelménylistát mutatták be neki:

kriptográfiai erősség ;
a rendelkezésre álló kimeneti eredményekből belső állapot megszerzésének lehetetlensége;
rövid ciklusok hiánya;
a bitek eloszlásának tendenciáinak hiánya a ciklus során;
a rendezett állapotoknak gyorsan kaotikussá kell válniuk.

A legtöbb pszeudo-véletlen számgenerátorral ellentétben, amelyek adatfolyam titkosításokon alapulnak , az ISAAC-ot lineáris visszacsatolású eltolási regiszterek használata nélkül tervezték.

A 32 bites érték eléréséhez szükséges gépi utasítások átlagos száma 18,75. Az ISAAC 64 bites verziója (ISAAC-64) 19 utasítást igényel egy 64 bites érték eléréséhez.

Műveleti algoritmus

Az előző algoritmusokhoz hasonlóan az ISAAC-nak is van egy S tömbje , amely meghatározza a rendszer belső állapotát, amely szintén a tömbben 0 -tól K bites hosszúságig véletlenszerűen elhelyezkedő elemekből, egy i iterátorból és három a , b és c változóból áll. , amely az előző generátorállapotokért felelős, a z kimeneti adattömb azonos hosszúságú S -vel . Azonban itt ezeken a változókon kívül olyan változókat is bevezetünk , amelyek meghatározzák a függvény mindkét iterátortól függő értékét: $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}}$ .

Jenkins cikkében azt javasolja . $p_{0}=13,p_{1}=6,p_{2}=2,p_{3}=16$

A generátor működési sémája tetszőleges lépésben n = 8, K = 32 esetén a következő:

c = c + 1; b = b + c; i = 0; míg én <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++;

Cryptanalysis by ISAAC

Személyes honlapján az ISAAC szerzője versenyt hirdetett a generátor feltörésére - az első, aki meg tudja adni a magként használt számot ( angol seed) , hogy létrehozza a generátor által kiadott első 2560 értéket, 1000 dollárt kap. díjat a Jenkinstől. Ezzel a feladattal azonban eddig senki sem tudott megbirkózni. Az ISAAC-ot azonban számos kriptoanalitikus is figyelembe vette.

Pudovkina támadása

2001-ben megjelent egy cikk [7] , amelyben Marina Pudovkina egy egyszerű szövegeken alapuló támadást írt le , amellyel a generátor kezdeti állapotát a kimeneti adatok egy kis szegmenséből megtalálhatja, és pontos becslést adott a egy ilyen támadás összetettsége. A cikkben leírt algoritmus segítségével Pudovkinának sikerült -ra csökkentenie a hackelés , míg a kimerítő keresés összetettségét [8] . Számításai szerint a -ra a kimerítő kereséssel történő hackelés bonyolultsága , míg a Pudovkina algoritmus használatával ez a szám -ra csökkenthető . Ez a bonyolultság azonban még mindig túl nagy ahhoz, hogy az ISAAC-ot sebezhető álvéletlenszám-generátornak nevezzük – foglalja össze cikkében a kriptoanalitikus. $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 Aumasson elemzése

2006-os cikkében [9] Omasson négy "gyenge" kezdeti állapotot ír le , amelyek keresztezhetik egymást. Gyenge állapotok azok az állapotok, amelyeknek egyes elemei véletlenszerűek, és a többi elem azonos értékkel egyenlő. Ha a kezdeti állapot, akkor a következő összefüggéssel definiálható: , akkor a következőképpen van definiálva , a halmaz definíciója: , míg a következőképpen van megadva: . A szerző az ISAAC algoritmust a fent megadott értékekkel (azaz n = 8, K = 32) vette figyelembe, és kiszámította a gyenge állapotok számát az egyes halmazokhoz. Ez a szám az állapotok, a for - states, a for - értékek voltak , de a részhalmaza . Az ilyen állapotok jelenléte még nem jelenti azt, hogy az ISAAC könnyen feltörhető, de ezek az algoritmus potenciális gyengeségei, ezért Omasson az ISAAC módosított változatát javasolta - 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$ $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}$ $W_{3}$ $W_2$

ISAAC+

A bemenet valamilyen lépésnél ugyanaz, mint az ISAAC-ban, az a , b és c számok, az S tömb , amely 256 32 bites szóból áll, a kimenet egy S -vel azonos méretű z tömb . A függvényleírásban a >> és << logikai biteltolások helyett ciklikus >>> és <<<, azaz a függvény kerül felhasználásra. $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}}$

Az S[i] és z[i] iniciálási módja is megváltozott az egyes lépésekben – mindkét esetben bitenkénti XOR-t használunk. Vagyis ahelyett

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

Az ISAAC+ a következőket használja:

S[i] = a ⊕ b + S[x>>>2 mod 256]; z[i] = x + a ⊕ S[S[i]>>>10 mod 256]; Paul-Pranil támadása. Kritika

Ugyanebben a 2006-ban Paul és Praenil publikált egy cikket [11] , amelyben egy megkülönböztető támadást tanulmányoztak néhány streaming RC4-szerű generátor, köztük az IA és az ISAAC ellen . Munkájukban megmutatják, hogy az ISAAC feltörésének bonyolultsága csak [12] . Omasson nem hagyta figyelmen kívül ezt a támadást [13] , és rámutatott az algoritmus Paul és Prenil hibás elindítására, ami miatt lehetővé vált a feltörés bonyolultságának csökkentése. $T\approx 2^{17}$

Alkalmazás

Sok ISAAC-megvalósítás elég gyors és megbízható ahhoz, hogy ez a pszeudo-véletlenszám-generátor meglehetősen általánossá vált. Az ISAAC-ot például a Unix segédprogramban (Unix) [14] használják az átírt adatok titkosításához. Az ISAAC-alapú véletlenszám-generátort az egyik legelterjedtebb Java matematikai könyvtárban, az Apache Commons Math -ban [15] valósítják meg .

Jegyzetek

↑ Robert Jenkins rövid önéletrajza . burtleburtle.net. Letöltve: 2016. november 25. Az eredetiből archiválva : 2016. augusztus 9.. (határozatlan)
↑ Schneier B., 2002 , p. 236.
↑ Paul G., Sabemoy M., 2001 , p. 16-19.
↑ Jenkins R.J., 1996 , p. 41, 42-43.
↑ Jenkins R.J., 1996 , p. 41, 43-45.
↑ Jenkins R.J., 1996 , p. 41, 46-49.
↑ Pudovkina M.A., 2001 .
↑ Pudovkina M.A., 2001 , p. 9.
↑ Omasson J.F., 2006 .
↑ Omasson J.F., 2006 , p. 5.
↑ Paul S., Preneel B., 2006 .
↑ Paul S., Preneel B., 2006 , p. 9-10.
↑ Omasson J.F., 2006 , p. 6.
↑ GNU coreutils git . Letöltve: 2016. december 3. Az eredetiből archiválva : 2019. szeptember 21.. (határozatlan)
↑ Apache Common Math docs . Letöltve: 2016. december 3. Az eredetiből archiválva : 2017. április 22.. (határozatlan)

Irodalom

Schneier B. RC4 // Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód a C.- M. -ben: Triumf, 2002. - S. 236. - 816 p. - ISBN 5-89392-055-4 .
Paul G., Sabamoy M. RC4 Stream Cipher // RC4 Stream Cipher and Its Variants = RC4 Stream Cipher and Its Variants. - Boca Raton: CRC Press, 2001. - S. 16-19. — 285 p.
Jenkins R. J. ISAAC // Számítástechnikai előadásjegyzetek. - Fast Software Encryption, 1996. - Vol. 1039 . - 41-49 . o .
Pudovkina M. A. Ismert egyszerű szöveges támadás az ISAAC kulcsfolyam-generátora ellen (eng.) . – IACR ePrint Archívum, 2001.
Paul S., Pranil B. On the (in)security of stream ciphers based on tömbök és moduláris összeadás (angol) // Advances in Cryptology - Asiacrypt 2006. - Asiacrypt, 2006.
Omasson J.F. Az ISAAC pszeudovéletlen generátorról . – IACR ePrint Archívum, 2006.

Linkek

Az ISAAC projekt hivatalos honlapja
Math::Random::ISAAC - Az algoritmus Perl implementációja
http://guilload.com/pyisaac/ - az algoritmus megvalósítása Pythonban
https://rosettacode.org/wiki/The_ISAAC_Cipher – az algoritmus megvalósítása 19 különböző programozási nyelven