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