Re: Due file FRUIBILI con lo stesso hash, è possibile in teoria?
Vend
> Dunque partiamo dall'idea che in teoria è possibile creare due sequenze
> di dati con lo stesso hash (qualunque sia l'algoritmo di hashing),
> giusto? L'hash proietta una sequenza di dati teoricamente infinita, in
> un hash finito e molto piu' corto del file originale (di solito pochi
> bytes), quindi è ovvio che prima o poi capitino i doppioni; se cosi' non
> fosse avremmo inventato il compattatore piu' potente del mondo: un file
> di 100 giga si "compatta" nel suo hash di pochi byte, e poi tramite
> brute force, potenza di calcolo permettendo, si "scompatta" ricavandone
> il file originale (ragionamento solo teorico, visto che le potenze di
> calcolo necessarie sarebbero fantascientifiche).
>
> Il problema è che: anche se esistono in teoria n files tutti aventi lo
> stesso hash del nostro file originale, dubito che anche gli altri
> abbiano dei dati che significano qualcosa.
E' possibile, ed è stato dimostrato che può essere fatto anche per
falsificare i certificati digitali:
Zampino
> Cioè creare due files apparentemente "validi" con lo stesso hash.
Sì, è fattibile. Dipende anche dalla funzione di hash. MD5 soffre di
questo problema.
Cerca "MD5 collision" su un motore di ricerca.
Daniele Orlandi
>
> E' possibile modificare il file B solo in alcune parti o alla fine del
> file, in modo che l'utente che lo guarda continui a vedere il filmato B,
> magari pieno di disturbi ma comunque riconoscibile, ma che l'hash di B
> diventi uguale ad A?
Due file con lo stesso hash non devono necessariamente differire per un
numero grande di bit.
Anzi, se il tuo hash ha una lunghezza di 128 bit è garantito che ti basta
modificare 128 bit, in qualunque posizione, anche contigui, di un
*qualunque* file per ottenere un file con lo stesso hash.
Se l'algoritmo di digest è sicuro la difficoltà di trovare questi 128 bit
sarà dell'ordine di 2^128 tentativi e quindi sebbene *possibile* non è
*fattibile*.
Infilare in un file 128 bit senza che siano visibili e mantenendo corretto
il formato è di norma semplice.
PDF, JPG, AVI, MPEG-TS ad esempio possono include tag/frames non visibili
nei quali metti tutto quello che vuoi.
Ciao,
--
Daniele Orlandi つづく
Vend
> Anzi, se il tuo hash ha una lunghezza di 128 bit č garantito che ti basta
> modificare 128 bit, in qualunque posizione, anche contigui, di un
> *qualunque* file per ottenere un file con lo stesso hash.
Perchč?
Daniele Orlandi
>
>> Anzi, se il tuo hash ha una lunghezza di 128 bit è garantito che ti basta
>> modificare 128 bit, in qualunque posizione, anche contigui, di un
>> *qualunque* file per ottenere un file con lo stesso hash.
>
Mi devo correggere: i digest non necessariamente garantiscono quella
proprietà. Non garantiscono neppure di essere biiettivi quando l'input ha
dimensione uguale alla dimensione dell'hash.
D'altra parte, però, un buon algoritmo di digest deve avvicinarsi il più
possibile ad un random oracle il quale ha codominio uniformemente
distribuito (ed è perfino una funzione suriettiva quando le dimensioni del
dominio e del codominio coincidono).
Quindi, siccome la probabilità che due input diversi abbiano lo stesso hash
si deve avvicinare a 1/2^128 signfica che dati 2^128 input diversi ho una
probabilità:
(1-1/2^128)^(2^128) = 0.37 di non trovare l'hash che cerco.
Però già aggiungendo 4 bit, la P=0.37^(2^4) diventa un numero irrisorio
(1.23*10^-7).
Quindi "basta" modificare 128 + x bit in qualunque posizione scelta per
avere una buona probabilità di trovare l'hash cercato.
(Spero di non aver sbagliato i calcoli)