Fortuna algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. augusztus 26-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A Fortuna a kriptográfiailag biztonságos pszeudo-véletlenszám-generátorok családja . Az algoritmust Bruce Schneier és Niels Ferguson fejlesztette ki, és először a Practical Cryptography [1] című könyvükben írták le . A szerzők szerint az algoritmust a könyvön való munka közben hozták létre, és ez jelentős fejlesztés Yarrow algoritmusához képest .

Algoritmus szerkezete

A Fortuna rendszer három részből áll:

Maga a generátor , amelyet egy rögzített hosszúságú maggal inicializálnak, és tetszőleges számú pszeudo-véletlen bitet állítanak elő .
Egy entrópiagyűjtő , amely véletlenszerű adatokat gyűjt különböző forrásokból, és megváltoztatja a generátor magját, amikor elegendő entrópia halmozódott fel.
Kezdőfájl-kezelő rendszer , amely lehetővé teszi, hogy a számítógép újraindítása után azonnal pszeudo-véletlen számokat generáljon.

Generátor

Bármilyen biztonságos blokk-rejtjel használható generátorként (a "Practical Cryptography" könyv olyan rejtjeleket kínál, mint az AES (Rijndael) , a Serpent és a Twofish számláló módban . Más szóval, válaszul minden felhasználó/alkalmazás kérésére a generátor pszeudo-véletlen adatokat állít elő az egymást követő természetes számok (számlálóértékek) titkosításával. Ebben az esetben a magot használjuk kezdeti kulcsként, és minden kérés után a kulcs frissítésre kerül: az algoritmus 256 bit pszeudo-véletlen adatot generál a régi kulcs felhasználásával, és a kapott értéket használja új kulcsként. Ez azért történik, hogy a támadó ne tudja megtudni a generátor korábbi állapotait, még akkor sem, ha a következő kérés után tudja az aktuális állapotot. Ezenkívül a blokk titkosítás számláló módban nem ismétlődő 16 bájtos blokkokat állít elő 2128 periódussal , míg az ilyen sorozathosszúságú valódi véletlenszerű adatoknál valószínűleg ugyanazok a blokkértékek fordulnak elő. Ezért egy pszeudo-véletlen sorozat statisztikai tulajdonságainak javítása érdekében az egy kérésre válaszul visszaküldhető adatok maximális mérete 220 bájtra korlátozódik (ilyen szekvenciahossz mellett az azonos blokkok megtalálásának valószínűsége egy valóban véletlenszerű áramlás körülbelül 2 -97 ).

Entrópia akkumulátor

Az akkumulátor valóban véletlenszerű adatokat gyűjt külső entrópiaforrásokból , és egyenletesen osztja el 32 készlet között .

Az entrópia forrásai

Bármilyen előre nem látható adatforrást külső entrópiaforrásként használnak, például az egérmozgásokat, a billentyűleütési időt, a merevlemez- válaszokat , a hangkártya zaját stb. Ebben az esetben csak a legkisebb jelentőségű adatbájtokat kell venni, megközelítőleg egyenletesen elosztva (a jelentős bájtokat könnyen megjósolhatja a támadó).

Medencék

Minden entrópiaforrás egyenletesen és ciklikusan osztja el az eseményeket 32 készlet között . Egy esemény hozzáadása a készlethez azt jelenti , hogy összefűzi azt a készletben lévő karakterlánccal. Amikor a készlet tartalma elég nagy lesz, a generátor magja (vagyis a titkosítási kulcs ) frissítésre kerül egy vagy több készlet tartalmának kivonatolásával úgy, hogy a készlet minden frissítésben részt vesz, a készlet minden második frissítésben, a medence minden negyedik frissítésben és így tovább. Így minden egyes következő készlet ritkábban kerül felhasználásra, mint az előző, és nagyobb számú entrópiát sikerül felhalmoznia. Ez lehetővé teszi az olyan támadások automatikus visszaverését, amelyekben a támadó információval rendelkezik egyes entrópiaforrásokról – előbb-utóbb olyan kulcsfrissítés történik, amely több entrópiát használ, mint amennyit a kriptoanalizátor meg tud jósolni. Ugyanakkor kimutatható, hogy a rendszer támadás utáni automatikus helyreállításának ideje legfeljebb 64-szer haladja meg a lehetséges minimumot (ez utóbbi általában csak akkor igaz, ha a rendszer elegendő számú készlettel rendelkezik Ennek a feltételnek a teljesítéséhez a Fortuna megköveteli, hogy egyetlen frissítés se legyen másodpercenként 10-nél többször: ha lenne egy 33. készlet, adott frissítési sebesség mellett, akkor az első alkalommal legkorábban 13 évvel a frissítés kezdete után kerülne felhasználásra. algoritmus). $P_0, P_1,\ldots,P_{31}$ $P_0$ $P_0$ $P_1$ $P_2$

Seed File

Az alapfájl tartalmazza a Fortuna inicializálása során a generátornak átadott magot. Lehetővé teszi a generátor számára, hogy pszeudo-véletlen adatokat állítson elő, mielőtt elegendő entrópia halmozódna fel a rendszerben. A fájl indításkor beolvasásra kerül, majd a tartalma azonnal frissül. Amint az entrópia érkezik, a fájl időszakonként felülíródik (a szerzők azt javasolják, hogy 10 percenként készítsenek új kezdőfájlt, de figyelembe kell venni az adott alkalmazást és a rendszer entrópiagyűjtésének sebességét is).

Különbségek a Yarrow-tól

A fő különbség Fortuna és Yarrow között az entrópia-akkumulátor működésének eltérő megközelítése - Yarrow-nak mechanizmusokra volt szüksége az entrópia mennyiségének becsléséhez, és csak két medencét használt.

Kritika

Egyes kutatók kétségeiket fejezik ki ennek az algoritmusnak a célszerűségével kapcsolatban az entrópia túl gazdaságos felhasználása, és ennek eredményeként a rövid távú kompromisszum bizonyos valószínűsége miatt [2] .

Megvalósítások

Fortuna implementációja C++ nyelven
A Fortuna Python implementációja ( Python Cryptography Toolkit)
Fortuna támogatási javítás a Linux kernelhez
A Fortuna Javascript implementációja ( Javascript Crypto Library)

Lásd még

Jegyzetek

↑ Niels Ferguson, Bruce Schneier. Gyakorlati kriptográfia = gyakorlati kriptográfia. - Williams, 2005. - 416 p. — ISBN 5-8459-0733-0 .
↑ Viega János. Gyakorlati véletlenszám-generálás a szoftverekben // 19. éves számítógép-biztonsági alkalmazások konferencia. - 2003. - 129. o.