Newsgroup: it.comp.sicurezza.pgp
Titolo: Javascript Enrtopy Gatherer

http://www.lapo.it/JEG/
Ho finalmente finito una prima versione della mia pozza per raccolta di 
entropia in JavaScript. Ho trovato il linguaggio particolarmente scevro 
di possibilità di raccolta di vera entropia se non immessa dall'utente 
stesso... l'unica fonte "automatica" è un orrendo contatore in 
millisecondi, che leggo in automatico quando viene chiamata la funzione 
per l'aggiunta di entropia, oltre ai dati passati esplicitamente alla 
funzione stessa.
Mi farebbe piacere ricevere un commento sulla sicurezza 
dell'implementazione, non vorrei aver commesso errori grossolani, 
sopratutto nella parte che sfrutta l'hash per gestire una pozza da 512 
bit invece che da 128 bit (uso MD5 come funzione "mescolante").
BTW: la libreria in sé è tutta contenuta in 
http://www.lapo.it/JEG/JEG.js
 ed è sotto licenza LGPL
--
Lapo

 bit invece che da 128 bit (uso MD5 come funzione "mescolante").
Quando si dà un giudizio sul lavoro altrui, si rischia che l'autore del
lavoro possa sentirsi offeso. Se dovesse accadere, sappi che non era mia
intenzione.
La prima ovvia annotazione riguarda l'md5.
E` stato provato alcuni anni fa che questo hash presenta dei punti deboli
(ne avevamo parlato proprio in questo ng alcuni mesi fa).
L'sha-2 è ancora giovane e quindi non analizzato a dovere.
L'sha-1 è l'unico universalmente accettato (è anche approvato dal nist) ed è
stato ampiamente analizzato. Non c'è ragione per non utilizzarlo.
Da quanto ho capito, la sorgente d'entropia dovrebbe essere
window.crypt.random(16).
Sai *esattamente* cosa fa?
Tu scrivi "netscape-specific crypto libraries". Secondo me questo è già un
buon motivo per non utilizzarla: non è portabile e può essere modificata (da
altri, in meglio o in peggio).
Quando si usano sorgenti con scarsa entropia (come nel nostro caso)
converrebbe usare almeno qualche accorgimento di base (per aumentare la
complessità della sequenza in uscita):
1- usare un ottimo hash (come sha-1);
2- hashare almeno il doppio dei bit in uscita;
3- decimare l'uscita come si diceva nell'altro post;
4- prelevare i bit casualmente usando, per esempio, M-M;
5- non "chiudere" l'hash; cioè usi due hash: h1 e h2. Tieni sempre in
memoria h1 (non calcoli mai l'hash di h1), aggiungi l'entropia in h1, copi
h1 in h2, calcoli l'hash di h2 e lo usi per generare i bit. In altre parole,
h1 viene sempre aggiornato con la nuova entropia, con h2 calcoli l'hash dei
bit accumulati fino a quel momento.
In definitiva, per darti un commento sulla sicurezza (come chiedevi),
utilizzando una sorgente intrinsecamente povera d'entropia e tecniche di
post-processo non troppo complesse, il generatore mi sembra poco sicuro se
paragonato a quello che si potrebbe ottenere con un pc sfruttando l'hardware
di serie.
Cristiano

-----BEGIN PGP SIGNED MESSAGE-----
Cristiano wrote:
 > Quando si dà un giudizio sul lavoro altrui, si rischia che l'autore
 > del lavoro possa sentirsi offeso. Se dovesse accadere, sappi che
 > non era mia intenzione.
Non ti preoccupare, è quello che voglio.
 > La prima ovvia annotazione riguarda l'md5.
Verissimo, non so perchè non ho usato SHA-1 fin dall'inizio, ma lo
sto già cambiando =)
 > E` stato provato alcuni anni fa che questo hash presenta dei punti
 > deboli (ne avevamo parlato proprio in questo ng alcuni mesi fa).
...purtropo non lo seguivo ancora ;)
 > Da quanto ho capito, la sorgente d'entropia dovrebbe essere
 > window.crypt.random(16).
No, non proprio.
è solo "una delle"... il problema è che di sorgenti "automatiche" in
js ce ne sono poche e quando quella è disponibile -qualunque cosa
faccia- è facile che faccia qualcosa di meglio degli eventi del mouse
dell'utente o altre cose raccoglibili.
Comunque la funzione JEG.seed ha il principale scopo di usare i dati
ricevuti ni paraemtro, l'ora in millisecondi e quella eventuale
funzione sono buttate dentro "tanto male non possono farlo" (e in
modo da complicare un minimo la vita all'attaccante anche se l'utente
non generasse proprio nessun evento).
 > Sai *esattamente* cosa fa?
 > Tu scrivi "netscape-specific crypto libraries". Secondo me questo è
 > già un buon motivo per non utilizzarla: non è portabile e può
 > essere modificata (da altri, in meglio o in peggio).
Non è portabile e infatti non è disponibile su IE per dirne una.. ma
so cosa fa: dà accesso alla funzione randmo delle Cryptyo API di
Mozilla (o Netscape a seconda dei casi) che non mi sembra che
facciano così schifo (beh, almeno dopo la correzione di qualche anno
fa eheheh).
E comunque resta una sorgente "in più", le poche volte che c'è.
 > 1- usare un ottimo hash (come sha-1);
Al più presto..
 > 2- hashare almeno il doppio dei bit in uscita;
In che senso? Non ho posto nessun limite ai bit in ingresso...
 > 3- decimare l'uscita come si diceva nell'altro post;
Capisco decimare l'uscita di un ADC o simili, ma usando direttamente
un hash per "compattare" i bit è davvero lo stesso utile?
Quella decimazione è un rudimentale filtro passa basso e un hash che
non desse un uscita "rumore bianco" sarebbe un ben povero hash...
 > 4- prelevare i bit casualmente usando, per esempio, M-M;
 > 5- non "chiudere" l'hash; cioè usi due hash: h1 e h2. Tieni sempre
 > in memoria h1 (non calcoli mai l'hash di h1), aggiungi l'entropia
 > in h1, copi h1 in h2, calcoli l'hash di h2 e lo usi per generare i
 > bit. In altre parole, h1 viene sempre aggiornato con la nuova
 > entropia, con h2 calcoli l'hash dei bit accumulati fino a quel
 > momento.
Non ho capito bene quel che hai detto, ma fondamentalmente intendi di
dare in uscita la parte bassa (quanti bit si vuole) dell'hash del
pool e non una seppur piccola parte del pool stesso, esatto?
 > In definitiva, per darti un commento sulla sicurezza (come
 > chiedevi), utilizzando una sorgente intrinsecamente povera
 > d'entropia e tecniche di post-processo non troppo complesse,
In realtà la sorgente è "sconosciuta", visto che ha il "programma
utente" il compito di raccogliere quanti più dati possibile e
passarli, la libreria si interessa solo di "metterli assieme" e
spremerli il più possibile.
 > il generatore mi sembra poco sicuro se
 > paragonato a quello che si potrebbe ottenere con un pc sfruttando
 > l'hardware di serie.
In che senso usando hardware di serie? In javascript nno c'è accesso
alcuno all'hardware, mi basta che sia sicuro nel suo ambito non che
sia sicuro rispetto a soluzioni ovviamente più serie come un
/dev/random che può accedere agli interrupt di tutto un kernel...
 > Cristiano
Grazie per il commento, presto posterò la verisone corretta e
riveduta ;)
Forse nella next version aggiungerò pure una stima dell'entropia
presente nel pool, ma lì è sempre un casino da fare senza sapere che
dati vengon ricevuti come seed.
- --
Lapo
-----BEGIN PGP SIGNATURE-----
Version: PGP 8.0 (Build 294) Beta
iQEVAwUBPa/Tl7FBTvTQ5Fg5AQFoxgf/fONlNR4+uBtKz3E7ELtD4trmyhTPGLW5
btGciL0M57Rj4uHzxZAkZ8+p6NMUn9KWVbk/XlVw89PirLRBada6EbdnmM8lBVjg
IX0Z2sX2qxkr4GGgnMo/yL8/GeEOa66El+LIIQ/S7Bnedf+bauvmVKJXfJjsOihc
Sj5BgChA6CPLqqUtw1uMbnVRmqWyLMPdCHnNSKOM9PM5LPm/TWXvNixG5CQKNEbG
GSkEzi4EOxmUO9ODBOfkyb7lgRBPKhsrStzdYX9CnHM3/mNm2Ivvs8vwfNIRP9g+
C/ylKs57ot3AQGkopSpj6T7OsgjVbqcoAeFMR57MbyY7rzPT8AO5OQ==
=sWhF
-----END PGP SIGNATURE-----

 dati vengon ricevuti come seed.
Se ci riesci sono disposto a pagare somme cospicue! :-)
Cristiano

 Se ci riesci sono disposto a pagare somme cospicue! :-)
Perché?
Alla fine è chi dà il dato che dice quanto quel dato vale (parametro 
'entr' della JEG.seed), è praticamente impossibile fare stime "a 
posteriori"... (si possono generare sequenze pseudocasuail che reggono a 
tutti i test ma sono comunque totalmente deterministiche.. inoltre 
analizzare i dati per stimarn l'entropia ni questo modo sarebbe 
oltremodo lento)
--
Lapo

 sarebbe oltremodo lento)
Io direi "oltremodo impossibile" :-)
Purtroppo non ho proprio la più pallida idea di come stimare l'entropia dei
bit che io stesso fornisco.
Anche parlando con alcuni ricercatori che armeggiano tutto il giorno con i
generatori non siamo riusciti a venirne a capo.
Tu hai qualche idea?
Cristiano

 Tu hai qualche idea?
Dal punto di vista della libreria (a posteriori) non vedo proprio come 
fare, no... dato sopratutto che penso sia possibile creare un generatore 
pseudocasuale che passa test di casualità complessi a piacere 
(complicando il generatore a piacere, ovviamente).
--
Lapo

 Tu hai qualche idea?


 contenete una entropia di 314.15 bit esatti.
Mi potete spiegare che cosa si intende dicendo che una data quantità N di
byte contiene Nb bit di entropia?
In questo contesto per voi cosa rappresenta l'entropia? Io conosco la
definizione termodinamica ma non riesco a capire cosa sia in questo
contesto.
Ciao e Grazie
Fabio

 piacere (complicando il generatore a piacere, ovviamente).
Già. :-)
Cristiano

 contesto.
Tutta un'altra cosa :-)
Evitando una definizione matematica, ci basta sapere (per i nostri scopi)
che i bit d'entropia sono quelli realmente, assolutamente, totalmente
imprevedibili.
Per esempio, un generatore a congruenza lineare (come ogni altro generatore
deterministico) non è in grado di generare nemmeno 1 bit d'entropia, perché
sono tutti prevedibili (basandosi unicamente su ricorrenze puramente
matematiche).
Invece, un generatore basato su particolari fenomeni fisici è in grado di
generare un'elevata entropia (quasi 1 bit per ogni bit emesso) perché la sua
uscita è molto difficilmente prevedibile o totalmente imprevedibile.
In genere, se l'uscita è presa così com'è, l'entropia è molto inferiore
rispetto a quella che potrebbe generare se l'uscita fosse opportunamente
post-processata (anche con semplici filtri).
Ad esempio, i parametri di molti fenomeni fisici utilizzati per generare
numeri casuali (come quello basato sul decadimento alfa cui accennavo
l'altra volta) hanno una distribuzione a campana (o gaussiana, o normale)
per cui sarebbero totalmente inadatti a generare numeri casuali (che hanno
una distribuzione uniforme). Per ovviare a questo inconveniente, è molto
efficace il metodo di prendere almeno 6 numeri da n bit dall'uscita e
sommarli modulo 2^n; i numeri risultanti avranno un'ottima distribuzione
uniforme.
Ho fatto una breve panoramica, spero che sia stata sufficiente! :-)
Cristiano

contesto.
In realtà esiste una conenssione molto intima tra le due cose:
in fisica si chiama entropia
   H = K ln P [J/K]
il logaritmo della probabilità del sistema di essere nello stato in cui 
è (tra tutti possibili stati)
in teoria dell'informazione si chiama entropia (anche se sarebbe più 
corretto chiamarla neghentropia)
   H = - ln P [bit]
il logaritmo della probabilità su cui l'informazione ricevuta ha tolto 
ogni dubbio
Quindi quando un sistema fisico che può stare in 10 stati possibili ha 
un'indecisione di "ln 10" bit (a priori non conosco lo stato del 
sistema) può essere totalmente definito grazie a 10 bit di informazione.
Da notare che l'informazione contenuta in un messaggio è indipendente 
dalla forma, mentre la dimensione fisica del messaggio è dipendente 
ovviamente anche dalla forma.
Ad esempio il messaggio "il numero che segue 1" e il messaggio "2" hanno 
dimensioni diverse (in bit di "spazio") ma contengono la stessa wuantitò 
di informazione (che non può essere definita in modo assoluto a meno di 
definire lo spazio dentro al quale ci si muove).
BTW: proprio per questo motivo il numero pi greco, pur avendo infinite 
cifre, non contiene una quantitò infinita di informazione (esistono 
algoritmi per calcolare che occupano spazi finiti benché richiedano 
tempi infiniti).
Spesso comunque (come nei messaggi tra me e Cristiano) si parla di 
entropia sottintendendo "nuova entropia"... sotto questa ottica pi greco 
non ovvre ALCUNA informazione, in quanto è sempre uguale a sé stesso.
Leggere le cifre del pi greco non ci dice nulla di nuovo: lo conoscevamo 
già.
Invece in un generatore di numeri casuali bisogna massimizzare 
l'imprevedibilità del numero rispetto a TUTTI i numeri precedenti.
--
Lapo

 una buona stima dell'entropia, ma siamo sempre su cose approssimative.
Una stima a posteriori precisa è quasi impossibile... o è comunque 
sempre costruibile un generatore complesso a piacere che "sconfigge" il 
metodo usato facendgli credere che i numeri generati siano veramente 
casuali.
BTW: direi che con questo messaggio siamo riusciti a isolare il "kernel" 
di teoria che è diverso nelle nostre rispettive visioni e che protava a 
quell'incomprensione, ovvero che se
   A = f(B)
allora
   H(A) <= H(B), per ogni funzione f
--
Lapo

 Concordo perfettamenet con te,
[...]
Leggendo il messaggio, mi rendo conto che questa č l'unica cosa su cui siamo
d'accordo! :-)
Credo che potremmo continuare la conversazione per alcuni mesi senza mai
trovare punto d'incontro.
Direi che abbiamo detto le nostre ragioni con sufficiente chiarezza.
Vorrei solo aggiungere che mi sembra di notare che tu ragioni in modo piů
matematico e teorico, io in modo piů semplice e pratico.
Forse a uno manca un po' di pratica e all'altro un po' di matematica :-) se
ci mettiamo a scrivere insieme un generatore, viene fuori una roba da NSA!
:-)
Grazie per l'interessante conversazione. Alla prossima.
Cristiano

ci mettiamo a scrivere insieme un generatore, viene fuori una roba da NSA!
Ma la pratica, in una materia teorica, non puň prescindere dalla
teoria ;-)
(e cosa di piů teorico della teoria dell'infromazione e della teoria
dei numeri?)
Lapo
--
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 /

 java).
"non ho mai programmato in java"in questo caso non centra ,
bisognerebbe dire : 'non ho mai scritto in JavaScript'.
Spesso chi non utilizza questi linguaggi confonde l'uno con l'altro o li
accomuna,
mentre a dispetto del nome sono abbastanza distanti benche' dialoghino
perfettamente fra loro. Java e' un linguaggio di programmazione ideato dalla
Sun,
JavaScript (realizzato da Netscape ma nativamente supportato anche da IE)
invece e' un linguaggio di scripting e puo' forse essere visto come una
estensione
dell'HTML (la lingua franca del web) su cui si innesta o da cui viene
richiamato.
Scusate la pedanteria era solo per non generare idee sbagliate in chi
leggesse...
Regards,
 Mattex
--------------------------------
Inviato via 
http://usenet.libero.it