Fortuna (PRNG)

L'algoritmo Fortuna è un generatore di numeri pseudo-casuali crittograficamente sicuro progettato da Bruce Schneier e Niels Ferguson. Prende il nome da Fortuna, la dea del caso nella mitologia romana.

Descrizione

L'algoritmo Fortuna, che più precisamente è da intendersi come una "famiglia" di PRNG dato che permette agli implementatori di modificare alcuni parametri, è composto dalle seguenti parti:

• il generatore stesso che, una volta avviato con un "seed" (un valore iniziale), produrrà una quantità indefinita di dati pseudo-casuali;
• l'accumulutatore di entropia, che raccoglie dati casuali da varie fonti (tastiera, mouse, ecc.) e li usa, quando sono stati salvati in numero sufficiente, per rinnovare il seed del generatore;
• il file del seed, che memorizza un certo quantitativo di dati casuali usati dal PRNG per inizializzare il generatore all'avvio del computer.

Il generatore

Il generatore è basato su un cifrario a blocchi che operi in modalità CTR per cifrare i valori di un contatore che viene incrementato. Nel libro Crittografia pratica gli autori suggeriscono di utilizzarne uno fra l'AES, il Serpent ed il Twofish. Generando blocchi casuali di 128 bit, la probabilità che un blocco si ripeta 2 volte è di 1 su 2⁶⁵. Nonostante ciò la chiave viene cambiata dopo la generazione di 1 MiB e dopo ogni richiesta di dati così che se anche una chiave viene violata ciò non compromette la sicurezza dei dati precedentemente generati.

L'accumulatore di entropia

L'accumulatore di entropia è progettato per resistere ad attacchi di tipo "injection", ossia manipolare le fonti usate per raccogliere entropia ed analizzare i dati che il sistema fornisce in base a quelli raccolti. I dati raccolti vengono memorizzati in 32 "pool" di entropia: ogni fonte di entropia distribuisce i propri dati su più pool. Per rigenerare il seed per l'nsima volta, vengono usati i dati raccolti da un certo pool k solo se 2^k divide n. In questa maniera il pool k è usato solo 1/2^k delle volte. Con questo sistema i pool con indice più grande vengono usati per rigenerare il seed con una frequenza inferiore rispetto a quelli con indice più piccolo: grazie a ciò i primi raccolgono così molta più entropia dei secondi. Il seed viene rigenerato mediante una funzione crittografica di hash (SHA-256) che agisce sul contenuto del pool selezionato e poi usando il risultato come nuova chiave del cifrario a blocchi.

A meno che un attaccante non sia capace di controllare tutte le fonti di entropia infiltrandosi nel sistema (caso in cui nessun algoritmo può preservare la sicurezza del PRNG) ci saranno delle k per cui il pool ksimo avrà raccolto abbastanza entropia tra due operazioni di aggiornamento del seed da garantire un livello minimo di sicurezza; inoltre, tale pool sarà utilizzato con un intervallo proporzionale al quantitativo di entropia in questione, permettendo così al sistema di recuperare lo stato di sicurezza nel caso di un attacco di tipo "injection". Tutto questo dipende da quanti pool si hanno: Fortuna ne usa 32 e richiede che la generazione di un nuovo seed avvenga almeno 10 volte al secondo. Per usare tutti i dati di tutti i pool Schneier e Ferguson hanno calcolato che il sistema impieghi circa 13 anni, un tempo accettabile per gli utilizzi del PRNG. Se è richiesto un livello di sicurezza ancora superiore, è possibile aumentare il numero di pool utilizzati dall'algoritmo.

Fortuna differisce da Yarrow, un altro PRNG di Schneier, Kelsey e Ferguson, principalmente nel modo in cui viene gestito l'accumulatore di entropia: Yarrow usava solo 2 pool e prevedeva un meccanismo di stima dell'entropia raccolta; inoltre utilizzava come funzione di hash l'algoritmo SHA-1, meno sicuro rispetto all'SHA-256.

Bibliografia

• Bruce Schneier, Niels Ferguson, Crittografia pratica, Apogeo, ISBN 88-503-2168-6.

Collegamenti esterni

• JavaScript Crypto Library, libreria crittografic in JavaScript che include una implementazione del PRNG Fortuna (licenza AGPL)
• Patch per aggiungere Fortuna al kernel Linux, su jlcooke.ca.
• (EN) Fortuna in C++, su citadelsoftware.ca. URL consultato il 26 settembre 2014 (archiviato dall'url originale il 3 novembre 2012).