Fortuna-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 26. elokuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Fortuna on salausturvallisten näennäissatunnaisten lukugeneraattoreiden perhe . Algoritmin ovat kehittäneet Bruce Schneier ja Niels Ferguson , ja se kuvattiin ensimmäisen kerran kirjassaan Practical Cryptography [1] . Kirjoittajien mukaan algoritmi luotiin kirjan parissa työskennellessä, ja se on merkittävä parannus Yarrow'n algoritmiin .

Algoritmin rakenne

Fortuna-järjestelmä koostuu kolmesta osasta:

Itse generaattori , joka on alustettu kiinteän pituisella siemenellä ja tuottaa mielivaltaisen määrän näennäissatunnaisia bittejä .
Entropiaakku , joka kerää satunnaista dataa eri lähteistä ja muuttaa generaattorin siementä aina, kun entropiaa on kertynyt tarpeeksi.
Siementiedostojen hallintajärjestelmä , joka tarjoaa mahdollisuuden luoda näennäissatunnaisia numeroita heti tietokoneen uudelleenkäynnistyksen jälkeen.

Generaattori

Mitä tahansa suojattua lohkosalausta voidaan käyttää generaattorina (kirja "Practical Cryptography" tarjoaa salauksia, kuten AES (Rijndael) , Serpent ja Twofish ) laskuritilassa . Toisin sanoen, vastauksena jokaiseen käyttäjän/sovelluksen pyyntöön generaattori tuottaa näennäissatunnaista dataa salaamalla peräkkäiset luonnolliset luvut (laskuriarvot). Tässä tapauksessa siementä käytetään aloitusavaimena ja jokaisen pyynnön jälkeen avain päivitetään: algoritmi luo 256 bittiä näennäissatunnaista dataa vanhalla avaimella ja käyttää tuloksena olevaa arvoa uutena avaimena. Tämä tehdään siten, että hyökkääjä ei voi saada selville generaattorin aiempia tiloja, vaikka hän tietäisi nykyisen tilan seuraavan pyynnön jälkeen. Lisäksi laskuritilassa oleva lohkosalaus tuottaa ei-toistuvia 16-tavuisia lohkoja, joiden jakso on 2128 , kun taas todellisessa satunnaisessa datassa, jolla on tällaisia sekvenssipituuksia, samat lohkoarvot todennäköisesti esiintyvät. Siksi näennäissatunnaisen sekvenssin tilastollisten ominaisuuksien parantamiseksi yhteen pyyntöön palautettavan datan enimmäiskoko on rajoitettu 220 tavuun (tällä sekvenssin pituudella todennäköisyys löytää identtisiä lohkoja todella satunnaisessa virta on noin 2 -97 ).

Entropiaakku

Akku kerää todella satunnaista dataa ulkoisista entropialähteistä ja jakaa sen tasaisesti 32 poolille .

Entropian lähteet

Ulkoisina entropian lähteinä käytetään kaikkia arvaamattomien tietojen lähteitä, kuten hiiren liikkeitä, näppäinpainalluksia, kiintolevyn vasteita , äänikortin kohinaa ja niin edelleen. Tässä tapauksessa tulee ottaa vain vähiten merkitsevät datatavut, jaettuna suunnilleen tasaisesti (hyökkääjä voi helposti ennustaa merkittävät tavut).

Altaat

Jokainen entropialähde jakaa tapahtumat tasaisesti ja syklisesti 32 pooliin . Tapahtuman lisääminen pooliin tarkoittaa sen ketjuttamista jo poolissa olevaan merkkijonoon. Aina kun poolin sisällöstä tulee tarpeeksi suuri, generaattorin siemen (eli salausavain ) päivitetään hajauttamalla yhden tai useamman poolin sisältö siten, että pooli osallistuu jokaiseen päivitykseen, pooli joka toisessa päivityksessä, allas joka neljännessä päivityksessä ja niin edelleen. Siten jokaista seuraavaa poolia käytetään harvemmin kuin edellinen, ja se onnistuu keräämään suuremman määrän entropiaa. Tämän avulla voit automaattisesti torjua hyökkäykset, joissa hyökkääjällä on tietoa joistakin entropialähteistä - ennemmin tai myöhemmin tapahtuu avainpäivitys, joka käyttää enemmän entropiaa kuin kryptanalyytikko pystyy ennustamaan. Samalla voidaan osoittaa, että aika järjestelmän automaattiseen palautumiseen hyökkäyksen jälkeen ylittää mahdollisen minimin enintään 64 kertaa (jälkimmäinen on totta yleisesti ottaen vain, jos järjestelmässä on riittävä määrä pooleja ; tämän ehdon täyttämiseksi Fortuna edellyttää, että päivityksiä ei tehdä useammin kuin 10 kertaa sekunnissa: jos 33. pooli olisi tietyllä päivitysnopeudella, sitä käytettäisiin ensimmäisen kerran aikaisintaan 13 vuoden kuluttua päivityksen alkamisesta. algoritmi). $P_0, P_1,\ldots,P_{31}$ $P_0$ $P_0$ $P_1$ $P_2$

Siementiedosto

Siementiedosto sisältää siemen, joka on siirretty generaattorille, kun Fortuna alustetaan. Sen avulla generaattori voi tuottaa näennäissatunnaista dataa ennen kuin järjestelmään on kertynyt tarpeeksi entropiaa. Tiedosto luetaan käynnistyksen yhteydessä, minkä jälkeen sen sisältö päivitetään välittömästi. Kun entropia vastaanotetaan, tiedosto kirjoitetaan ajoittain päälle (tekijät suosittelevat uuden siementiedoston luomista 10 minuutin välein, mutta sinun tulee myös ottaa huomioon erityinen sovellus ja entropian keruun nopeus järjestelmässä).

Erot Yarrowsta

Suurin ero Fortunan ja Yarrow'n välillä on erilainen lähestymistapa entropiaakun toimintaan - Yarrow tarvitsi mekanismeja entropian määrän arvioimiseen ja käytti vain kahta poolia.

Kritiikki

Jotkut tutkijat epäilevät tämän algoritmin käytön käytännöllisyyttä entropian liian taloudellisen käytön vuoksi ja sen seurauksena jonkin verran lyhytaikaisen kompromissin todennäköisyyttä [2] .

Toteutukset

Fortunan toteutus C++:ssa
Fortunan Python-toteutus ( Python Cryptography Toolkit)
Fortuna-tukikorjaus Linux-ytimelle
Fortunan Javascript-toteutus ( Javascript Crypto Library)

Katso myös

Muistiinpanot

↑ Niels Ferguson, Bruce Schneier. Käytännön kryptografia = Käytännön kryptografia. - Williams, 2005. - 416 s. — ISBN 5-8459-0733-0 .
↑ John Viega. Käytännön satunnaislukujen luominen ohjelmistoissa // 19th Annual Computer Security Applications Conference. - 2003. - s. 129.