Fortuna (PRNG) - Fortuna (PRNG)
Fortuna er en kryptografisk sikker pseudosluttnummergenerator (PRNG) utviklet av Bruce Schneier og Niels Ferguson og utgitt i 2003. Den er oppkalt etter Fortuna , den romerske tilfeldighetsgudinnen. FreeBSD bruker Fortuna for /dev /random og /dev /urandom er symbolsk knyttet til det siden FreeBSD 11. Apple -operativsystemer har byttet til Fortuna siden 1. kvartal 2020.
Design
Fortuna er en familie av sikre PRNG -er; Designet etterlater noen valg for implementatorer. Den består av følgende stykker:
- Selve generatoren, som en gang seedet vil produsere en ubestemt mengde pseudo-tilfeldige data.
- Den entropi akkumulator, som samler genuint tilfeldig data fra ulike kilder og bruker den til å reseed generatoren når nok ny tilfeldig har kommet.
- Frøfilen, som lagrer nok tilstand til at datamaskinen kan begynne å generere tilfeldige tall så snart den har startet.
Generator
Generatoren er basert på en hvilken som helst god blokk . Praktisk kryptografi antyder AES , slange eller tofisk . Den grunnleggende ideen er å kjøre krypteringen i tellermodus , og kryptere suksessive verdier for en inkrementerteller.
Med en 128-biters blokkering vil dette gi statistisk identifiserbare avvik fra tilfeldighet; for eksempel vil generere 2 64 virkelig tilfeldige 128-biters blokker i gjennomsnitt produsere omtrent ett par identiske blokker, men det er ingen gjentatte blokker i det hele tatt blant de første 2 128 produsert av en 128-biters chiffer i tellermodus. Derfor endres nøkkelen med jevne mellomrom: det genereres ikke mer enn 1 MiB data (2 16 128-biters blokker) uten en nøkkelendring. Boken påpeker at blokkchiffer med en 256-biters (eller større) blokkstørrelse, som ikke likte stor popularitet den gangen, ikke har dette statistiske problemet.
Nøkkelen endres også etter hver dataforespørsel (hvor liten som helst), slik at et fremtidig nøkkelkompromiss ikke bringer tidligere generatorutganger i fare. Denne egenskapen blir noen ganger beskrevet som "Hurtignettsletting" eller Videresend hemmelighold .
Entropi -akkumulator
Entropi -akkumulatoren er designet for å være motstandsdyktig mot "injeksjon" -angrep, uten å trenge sofistikerte (og uunngåelig upålitelige) estimatorer av entropi. Det er flere "bassenger" av entropi; hver entropikilde fordeler sin påståtte entropi jevnt over bassengene; og (her er det sentralt begrep) på den n- te reseeding av generatoren, basseng k brukes bare hvis n er et multiplum av 2 k . Dermed brukes k th bassenget bare 1/2 k av tiden. Pooler med høyere nummer, med andre ord, (1) bidrar til reseedings sjeldnere, men (2) samler en større mengde entropi mellom reseedings. Reseeding utføres ved å hasche de spesifiserte entropi-bassengene i blokkkrypteringsnøkkelen ved å bruke to iterasjoner av SHA-256 .
Såing
Med mindre en angriper er i stand til å kontrollere alle kildene til påstått entropi som strømmer inn i systemet (i så fall kan ingen algoritme redde det fra kompromisser), vil det være noen k som k th -bassenget samler nok entropi mellom reseedings som en reseeding med det bassenget sikrer sikkerhet. Og det bassenget vil bli brukt med et intervall som er proporsjonalt med mengden entropi det er snakk om. Derfor vil systemet alltid komme seg etter et injeksjonsangrep, og tiden det tar å gjøre det er høyst en konstant faktor større enn den teoretiske tiden det kan ta hvis vi var i stand til å identifisere hvilke kilder til entropi som var korrupte og hvilke ikke.
Denne konklusjonen er avhengig av at det er nok bassenger. Fortuna bruker 32 bassenger, og begrenser reseeding til å skje maksimalt 10 ganger per sekund. Det ville ta omtrent 13 år å gå tom for bassenger, noe Ferguson og Schneier anser lenge nok for praktiske formål. Flere paranoide implementatorer, eller de som krever generering av tilfeldige data med en kolossal hastighet og tilsvarende hyppig tilbakesending, kan bruke et større antall bassenger.
Alternativer
Fortuna skiller seg hovedsakelig fra den tidligere Yarrow -algoritmefamilien til Schneier, Kelsey og Ferguson mest i håndteringen av entropiakkumulatoren. Yarrow krevde at hver entropikilde skulle ledsages av en mekanisme for å estimere den faktiske leverte entropien, og brukte bare to bassenger; og den foreslåtte utførelsen (kalt Yarrow-160 ) brukte SHA-1 i stedet for iterert SHA-256 .
Analyse
En analyse og en foreslått forbedring av Fortuna ble gjort i 2014.
Se også
Referanser
Generell
- Niels Ferguson og Bruce Schneier, Practical Cryptography , utgitt av Wiley i 2003. ISBN 0-471-22357-3 .
- John Viega, "Practical Random Number Generation in Software", acsac, s. 129, 19. årlige konferanse for datasikkerhet (ACSAC '03), 2003
Eksterne linker
- Ferguson, Niels ; Schneier, Bruce ; Kohno, Tadayoshi (2010). "Kapittel 9: Generering av tilfeldighet" (PDF) . Kryptografiteknikk: Designprinsipper og praktiske applikasjoner . Wiley Publishing, Inc. ISBN 978-0-470-47424-2.
- "Javascript Crypto Library" . inkluderer en Javascript -implementering av Fortuna PRNG .
- Cooke, Jean-Luc (2005). "jlcookes forklaring på og forbedringer på /dev /random" . Patch som legger til en implementering av Fortuna i Linux -kjernen .
- Litzenberger, Dwayne (2013-10-20). "Fortuna -implementering i Python, en del av Python Cryptography Toolkit" .
- "Hvordan spise din entropi og ha den også - Optimale gjenopprettingsstrategier for kompromitterte RNG -er" . 2014-03-14.
- "Fortuna -implementering i C ++ 14" . Inkluderer eksempelserver, entropikilder og kommandolinjeklient . 2015-06-01.