Fortuna algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 26. august 2021; verifikation kræver 1 redigering .

Fortuna er en familie af kryptografisk sikre pseudo-tilfældige talgeneratorer . Algoritmen blev udviklet af Bruce Schneier og Niels Ferguson og først beskrevet i deres bog Practical Cryptography [1] . Ifølge forfatterne blev algoritmen skabt under arbejdet med bogen og er en væsentlig forbedring af Yarrows algoritme .

Algoritmestruktur

Fortuna-systemet består af tre dele:

Selve generatoren , initialiseret med et frø af en fast længde og producerer et vilkårligt antal pseudo-tilfældige bits .
En entropiakkumulator , der indsamler tilfældige data fra forskellige kilder og ændrer generatorens frø, når der er blevet akkumuleret nok entropi .
Et frøfilstyringssystem, der giver mulighed for at generere pseudo-tilfældige tal umiddelbart efter genstart af computeren.

Generator

Enhver sikker blokchiffer kan bruges som en generator (bogen "Praktisk kryptografi" tilbyder cifre som AES (Rijndael) , Serpent og Twofish ) i tællertilstand . Med andre ord, som svar på hver bruger-/applikationsanmodning, producerer generatoren pseudo-tilfældige data ved at kryptere på hinanden følgende naturlige tal (tællerværdier). I dette tilfælde bruges frøet som den indledende nøgle, og efter hver anmodning opdateres nøglen: Algoritmen genererer 256 bit pseudo-tilfældige data ved hjælp af den gamle nøgle og bruger den resulterende værdi som den nye nøgle. Dette gøres for at angriberen ikke kan finde ud af generatorens tidligere tilstande, selvom han kender den aktuelle tilstand efter næste anmodning. Derudover producerer en blokchiffer i tællertilstand ikke-gentagende 16-byte blokke med en periode på 2128 , mens det i sande tilfældige data med sådanne sekvenslængder er sandsynligt, at de samme blokværdier forekommer. Derfor, for at forbedre de statistiske egenskaber af en pseudo-tilfældig sekvens, er den maksimale størrelse af data, der kan returneres som svar på en anmodning, begrænset til 220 bytes (med en sådan sekvenslængde er sandsynligheden for at finde identiske blokke i en virkelig tilfældig rækkefølge strøm er omkring 2 −97 ).

Entropiakkumulator

Akkumulatoren indsamler virkelig tilfældige data fra eksterne kilder til entropi og fordeler det jævnt over 32 puljer .

Kilder til entropi

Alle kilder til uforudsigelige data bruges som eksterne kilder til entropi, f.eks. musebevægelser, tastetryk, harddiskreaktioner , lydkortstøj og så videre. I dette tilfælde bør kun de mindst signifikante databytes tages, fordelt omtrent jævnt (signifikante bytes kan let forudsiges af en angriber).

Puljer

Hver entropikilde fordeler begivenheder ensartet og cyklisk på tværs af 32 puljer . Tilføjelse af en begivenhed til puljen betyder at sammenkæde den med en streng, der allerede er i puljen. Når indholdet af puljen bliver stort nok, opdateres generatorens frø (det vil sige krypteringsnøglen ) ved at hashe indholdet af en eller flere puljer, hvor puljen deltager i hver opdatering, puljen i hver anden opdatering, puljen i hver fjerde opdatering og så videre. Således bruges hver efterfølgende pulje mindre hyppigt end den foregående og formår at akkumulere et større antal entropi. Dette giver dig mulighed for automatisk at afvise angreb, hvor angriberen har information om nogle af entropikilderne - før eller siden sker der en nøgleopdatering, som bruger mere entropi, end kryptanalytikeren er i stand til at forudsige. Samtidig kan det påvises, at tiden for automatisk gendannelse af systemet efter et angreb ikke overstiger det minimum mulige med højst 64 gange (sidstnævnte er generelt kun sandt, hvis systemet har et tilstrækkeligt antal puljer ; for at opfylde denne betingelse kræver Fortuna, at ingen opdateringer er mere end 10 gange i sekundet: hvis der var en 33. pulje, med en given opdateringshastighed, ville den blive brugt for første gang tidligst 13 år efter starten af algoritme). $P_0, P_1,\ldots,P_{31}$ $P_0$ $P_0$ $P_1$ $P_2$

Seed-fil

Seed-filen indeholder det frø, der sendes til generatoren, når Fortuna initialiseres. Det giver generatoren mulighed for at producere pseudo-tilfældige data, før der er akkumuleret nok entropi i systemet. Filen læses ved opstart, hvorefter dens indhold straks opdateres. Efterhånden som entropi modtages, overskrives filen med jævne mellemrum (forfatterne anbefaler at generere en ny frøfil hvert 10. minut, men du bør også tage højde for den specifikke applikation og hastigheden af entropiindsamling i systemet).

Forskelle fra Yarrow

Den største forskel mellem Fortuna og Yarrow er en anden tilgang til driften af entropiakkumulatoren - Yarrow krævede mekanismer til at estimere mængden af entropi og brugte kun to puljer.

Kritik

Nogle forskere udtrykker tvivl om det praktiske ved at bruge denne algoritme på grund af for økonomisk brug af entropi, og som følge heraf en vis sandsynlighed for kortsigtet kompromis [2] .

Implementeringer

Implementering af Fortuna i C++
Python implementering af Fortuna ( Python Cryptography Toolkit)
Fortuna support patch til Linux-kernen
Javascript implementering af Fortuna ( Javascript Crypto Library)

Se også

Noter

↑ Nils Ferguson, Bruce Schneier. Praktisk kryptografi = Praktisk kryptografi. - Williams, 2005. - 416 s. — ISBN 5-8459-0733-0 .
↑ John Viega. Praktisk generering af tilfældige tal i software // 19. årlige konference om computersikkerhedsapplikationer. - 2003. - S. 129.