Newsgroup: it.comp.sicurezza.crittografia
Titolo: Fortuna: degno erede di Yarrow?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Quando, tempo fa, ho letto l'annuncio, da parte delle nuove versioni di
FreeBSD e di Linux, di rimuovere /dev/random e sovrascriverlo con
/dev/urandom mi sono un po' scandalizzato.
Mi sono detto "ma come! quindi non ci sarà più modo per sapere se
contiene entropia 'vera' o meno?".
Poi ho letto che in realtà il cambio era motivato dall'uso di Yarrow
come PRNG e, dopo aver letto la descrizione tecnica di Yarrow, mi sono
convinto che questo cambiamento era sensato: Yarrow è sì un PRNG (e
quindi il suo output contiene ben meno entropia dei bit che produce), ma
dato che sfrutta la crittografia assicura contemporaneamente che i dati
prodotti siano indistinguibili da "dati veramente casuali" a meno di
rompere l'algoritmo crittografico stesso.
Questa idea, molto nuova ma d'altro canto molto semplice da capire, mi
ha convinto abbastanza in fretta.
Oggi, leggendo l'ultimo libro di Schneier ("Pratical Cryptography" che,
peraltro, consiglio vivamente a tutti, raramente ho visto un libro di
crittografia scritto in modo così chiaro e scorrevole) leggo della
proposta di Scheier e Ferguson (i due autori del libro) di un nuovo PRNG
chiamato "Fortuna" (come la dea romana del caso, non come la parola
italiana contraria alla iella) che è la naturale evoluzione di Yarrow.
Ho letto molte critiche (negative) di quel libro, che usavano circa
questo argomento: come può Schneier dire per mezzo libro di non usare
cose nuove e poi proporre, come PRNG, un *suo* PRNG così nuovo che non è
ancora neanche stato pubblicato su internet?
Beh, secondo me può, per il seguente motivo: un PRNG nato per risolvere
tutti i problemi che gli esistenti PRNG *già hanno* non può essere poi
tantio peggiore di questi.
E anche se un giorno gli trovassero problemi "nuovi" e diventasse quindi
insicuro sarebbe, fino a quel giorno, sicuramente più sicuro degil
"altri" PRNG che problemi conosciuti li hanno già in questo momento 0=)
Tornando comunque a "Fortuna", l'idea di base è questa: rimuovere il
componente più "complicato" e "meno affidabile" di Yarrow.
Questa componente era lo stimatore di entropia: difatti "mixare"
l'entropia ricevuta dall'esterno con il "seed" in proporzioni troppo
piccole permette all'attaccante (dando per scontato che abbia già
compromesso la segretezza del seed) di tenersi "aggiornato" sul nuovo
seed facendo solo poche prove (2^n dove n è il numero di bit di entropia
"mixati" del seed per ogni volta).
Dato che si cnosidera "sicuro" ogni valore di n >= 128, si poneva il
problema di "stimare" quanta entropia fosse presente nell'accumulatore
all'ingresso per PRNG, prima di mixarla nel seed del generatore (e
quindi ripristinare la segretezza del seed stesso, anche se fosse stato
in passato compromesso).
Ma è impossibile fare uno stimatore ottimo, perché non importa quanta
entropia contenga il dato "secondo il PRNG", ma conta solo quanta ne
contiene "secondo l'attaccante" (se l'attccante conosce buona parte
delle sorgenti di entropia, l'entropia stimata è molto superiore a
quella 'reale' negli occhi dell'attaccante).
"Fortuna" risolve questo problema alla radice eliminando lo stimatore.
Come fare, quindi, a sapere quando "mixare" i dati in ingresso?
L'idea 'geniale' sta proprio qua: la coda di ingresso nno è più una
sola, ma ci sono 32 code in ingresso.
La coda 0 viene "mixata" a ogni reseed.
La coda 1 viene "mixata" ogni 2 reseed.
La coda 2 viene "mixata" ogni 4 reseed.
La coda i viene "mixata" ogni 2^i reseed.
I dati ricevuti in ingresso vengono dati ni pasto ogni volta a una coda
diversa, secondo un algoritmo di round-robin (il primo dato alla prima
coda, il secondo alla seconda, il terzo alla terza...).
In questo modo, pur restando ingnota la quantità di entropia "relativa
all'attaccante" presente nelle varie code, è ovvio che la coda 1
contiene in media "il doppio" di entropia della coda 0, la coda 2 ancora
il doppio, e così via.
Quindi se i dati ricevuti in ingresso sono totalmente ignoti
all'attacante basterà un reseed qualunque per riportare ilseed in una
condizione di "sicurezza".
Se l'attaccante conoscerà metà dei dati che il PRNG usa per raccogliere
entropia, sarà a un reseed su due che il PRNG tornerà sicuro.
Se l'attaccante ne conoscerà il 99% questo capiterà ogni 128 reseed.
Questo design, come si nota, permette di assicurare un ritorno alla
segretezza pur non sapendo nulla sulla quantità di entropia che ogni
coda ha accumulato.
Il resto del PRNG è in realtà piuttosto simile a Yarrow, ovviamente usa
primitive crittografiche per evitare di "far ricavare" dati del seed a
partire dall'output pseudocasuale (a cui l'attaccante può ovviamente
accedere, non essendo segreto).
Per le "sorgenti di entropia", quale usare?
Come per Yarrow la risposta è: tutte quelle che hanno la speranza di
contenerne, anche poca, tanto il design del sistema fa in modo che una
sorgente che "non ha nulla da dire" (o meglio completamente prevedibile
dall'attaccante) non infici assolutamente il sistema, ma semplicemente
non gli aggiunga niente.
Quindi ogni sorgente, benché non ottima, è da utilizzare: nel caso
peggiore non fa niente, nel caso migliore aggiunge qualcosa.
Come per Yarrow l'agguinta di "dati" dalle sorgenti è molto "leggero" e
quindi moltissime parti del kernel possono chiamare dare il proprio
contributo "al volo", anche se fanno parte di interrupt che hanno
bisogno di essere processati in fretta.
Quindi, per rispondere alla dmoanda del subject, la mia risposta è:
sì, per mio modesto parere sì.
Questo non toglie, ovviamente, che quando giungerà il 'parere' dei veri
esperti crittografici il loro sarà da tenere *molto* più di conto del
mio. ;)
- --
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /
http://www.megatokyo.it
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (Cygwin)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iEYEARECAAYFAj/Vo+oACgkQaJiCLMjyUvtknACfT1Hs0oogGU+9qRkCC0mWiQ3F
/zYAoM6hHTlBNzD6CfgZPUJ4pR00bhaM
=cqLb
-----END PGP SIGNATURE-----

  [X.509 available]  ,''`.
Linux Reg. User #263663/NEW Machine: #216144 (Debian Sarge/SID) : :' :
On the Web: 
http://www.quagliata.eu.org
 - My GPG Key:0x5539D8E4 `. `'
On ICQ: 48618109 - On Jabber: 
qu...@jabber.org/@jabber.linux.it
   `-


| Prerequisiti richiesti? (A parte l'inglese, da quanto
| ho capito non e` ancora stato tradotto, ma non fa nulla).
Qua viene il bello: ovviamente qualche conoscenza precedente può solo
aiutare, ma i requisiti strettamente richiesti sono praticamente ZERO.
Perfino nella parte DH e RSA spiega da solo tutta la matematica
necessaria a partire da livello "matematica delle superiori di un
americano" (che è diversa dalla nostra =P)
Vero, a volte dà per scontate alcune cose che scontate non sono, ma non
è un libro per matematici e secondo me dare per scontato (senza
dimostrarlo), ad esempio, che la somma di moduli è il modulo della
somma... come dire, "va bene così".
Il libro non dà solo Fortuna come "consiglio innovativo" ma spiega anche
come mai le funzioni di hash delle famiglie MD e SHA sono "fallate" e
come "risolvere" buona parte dei loro problemi applicandole due volte.
Difatti Fortuna usa l'hash SHAd-256 = SHA-256(SHA-256(msg)).
BTW: sto implementando Fortuna (e tutte le sue componenti) in Java puro,
nella mia libreria lapint.
- --
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /
http://www.megatokyo.it
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (Cygwin)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iEYEARECAAYFAj/W0fEACgkQaJiCLMjyUvstEgCePV/nkxK7WccgNMx6swbdh4wG
09wAnRtj56Joj8byz0Fu7memO4uhbTwP
=t5Ss
-----END PGP SIGNATURE-----

 nella mia libreria lapint.
:)))
Nel CVS non c'e` nulla ancora, o sbaglio?



la classe SHA256 è nuova nuova, e la classe Double, se richiamata come
~  hash = new it.lapo.hash.Double(new it.lapo.hash.SHA2());
fa proprio lo SHAd-256 =)
- --
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /
http://www.megatokyo.it
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (Cygwin)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iEYEARECAAYFAj/XNLQACgkQaJiCLMjyUvtKsgCgjMt0eqxyga8YCPQVzZrtSSWF
4NYAoI/QKOuYopYrxkXQMHzHe/N2M6VK
=Nf06
-----END PGP SIGNATURE-----


(snip)
Si`... Questo l'avevo notato, ma ero alla ricerca di qualche
cosa dal nome `Fortuna', `fPRNG', `ngYarrow', etc... :)



| Si`... Questo l'avevo notato, ma ero alla ricerca di qualche
| cosa dal nome `Fortuna', `fPRNG', `ngYarrow', etc... :)
Per implementare Fortuna mi servono prima SHAd-256 (fatto e testato),
Rijndael (appena finito, ora lo testo contro i testvector) e la modalità
CTR (appena finita, dovrò inventarmi io qualche test).
Diciamo che con un po' di fortuna domani notte implemento Fortuna. 0=)
- --
L a p o   L u c h i n i
l a p o @ l a p o . i t
w w w . l a p o . i t /
http://www.megatokyo.it
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (Cygwin)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iEYEARECAAYFAj/XscUACgkQaJiCLMjyUvvY5ACdGG50C2M24+4XUEgki8sjAz42
aIwAn3d8LpfMqfybbq/G+shdCTVhko20
=1TPa
-----END PGP SIGNATURE-----

 Diciamo che con un po' di fortuna domani notte implemento Fortuna. 0=)
LOL. :)
