[e-privacy] (fwd) trovate collisioni complete in MD5, SHA-0 e altri hash

[futureworlds]

-- forwarded message --
Newsgroups: it.comp.sicurezza.crittografia
Subject: trovate collisioni complete in MD5, SHA-0 e altri hash
Date: Tue, 28 Sep 2004 03:03:12 +0200

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Il 17 agosto 2004 Xiaoyun Wang, Dengguo Feng, Xuejia Lai e Hongbo Yu
hanno rilasciato un articolo [1] che annuncia la scoperta di un nuovo
metodo di attacco per trovare collisioni, applicabile a molti degli
algoritmi attualmente in uso (quelli basati sulla forma generale
proposta da MD4).
L'articolo è avallato da collisioni complete per MD4, MD5 (vedi sotto),
HAVAL-128 e RIPEMD, ottenute in "poche ore" anziché gli svariati mesi
che un moderno super-computer impiegherebbe (motivo per cui il sito
MD5CRK [2] aveva iniziato un progetto distribuito per tentare l'attacco,
progetto ora fermato proprio da questo attacco, ben più efficiente del
"birthday attack" utilizzato da MD5CRK).
Altro attacco ha avuto esito positivo anche su SHA-0, da notarsi che è
un attacco di complessità 2^40, ben inferiore a quella ideale di 2^80 e
di molto inferiore ai precedenti attacchi già noti su SHA-0.

Cosa cambia questo per l'utente comune? E per i crittografi?

L'utente comune non ha motivo di fuggire in preda al panico, almeno
nell'immediato: i più furbi già da tempo utilizzavano hash di dimensione
maggiore dei soli 128 bit di MD5 (oggi usato sopratutto come controllo
sui download dei file), sopratutto SHA-1 e ancora niente ha minacciato
in modo "diretto" SHA-1, che per ora resta da considerarsi "sicuro",
come commentato dal NIST stesso [3] (l'attacco a SHA-0 non deve troppo
spaventare: dopo tutto SHA-1 è nato proprio perché la debolezza di SHA-0
era nota):
"The results presented so far on SHA-1 do not call its security into
question. However, due to advances in technology, NIST plans to phase
out of SHA-1 in favor of the larger and stronger hash functions
(SHA-224, SHA-256, SHA-384 and SHA-512) by 2010."

Ma come sempre la scoperta di un metodo "nuovo" suggerisce ai
crittografi nuovi "standard minimi" a cui un nuovo algoritmo deve
resistere per essere considerato sicuro e quindi, benché SHA-1 resti
finora inattaccato e i suoi fratelli maggiori (SHA-256, SHA-512) siano a
maggior ragione ancora utilizzabili con tranquillità è altamente
consigliato che venga pensato un algoritmo di hash completamente
"rinnovato" e basato su idee nuove, come consigliato ad esempio da Bruce
Schneier nell'ultimo numero della sua newsletter Crypto-Gram [4]:
"Most of the hash functions we have, and all the ones in widespread use,
are based on the general principles of MD4. Clearly we've learned a lot
about hash functions in the past decade, and I think we can start
applying that knowledge to create something even more secure.
Better to do it now, when there's no reason to panic, than years from
now, when there might be. "

Ecco allegata una delle due collisioni elencate per MD5:
$ od -t x1 MD5.1
0000000 d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c
0000020 2f ca b5 87 12 46 7e ab 40 04 58 3e b8 fb 7f 89
0000040 55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 71 41 5a
0000060 08 51 25 e8 f7 cd c9 9f d9 1d bd f2 80 37 3c 5b
0000100 96 0b 1d d1 dc 41 7b 9c e4 d8 97 f4 5a 65 55 d5
0000120 35 73 9a c7 f0 eb fd 0c 30 29 f1 66 d1 09 b1 8f
0000140 75 27 7f 79 30 d5 5c eb 22 e8 ad ba 79 cc 15 5c
0000160 ed 74 cb dd 5f c5 d3 6d b1 9b 0a d8 35 cc a7 e3
$ od -t x1 MD5.2 (ho evidenziato le differenze con <>)
0000000 d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c
0000020 2f ca b5<07>12 46 7e ab 40 04 58 3e b8 fb 7f 89
0000040 55 ad 34 06 09 f4 b3 02 83 e4 88 83 25<f1>41 5a
0000060 08 51 25 e8 f7 cd c9 9f d9 1d bd<72>80 37 3c 5b
0000100 96 0b 1d d1 dc 41 7b 9c e4 d8 97 f4 5a 65 55 d5
0000120 35 73 9a<47>f0 eb fd 0c 30 29 f1 66 d1 09 b1 8f
0000140 75 27 7f 79 30 d5 5c eb 22 e8 ad ba 79<4c>15 5c
0000160 ed 74 cb dd 5f c5 d3 6d b1 9b 0a<58>35 cc a7 e3
$ md5sum MD5.*
a4c0d35c95a63a805915367dcfe6b751 MD5.1
a4c0d35c95a63a805915367dcfe6b751 MD5.2

Per chi non avesse voglia di mettere mano ad un editor esadecimale i
file già pronti da testare si possono trovare sul sito [5].
Da notarsi anche, come giustamente ricorda l'autore della pagina [5],
che allungando entrambi i file con un un medesimo contenuto l'hash resta
uguale tra i due file (il noto "length extension attack" degli hash
incrementali).

Link:
[1] http://eprint.iacr.org/2004/199.pdf
[2] http://www.md5crk.com/
[3] http://csrc.nist.gov/hash_standards_comments.pdf
[4] http://www.schneier.com/crypto-gram-0409.html#3
[5] http://www.tcs.hut.fi/~mjos/md5/

un Lapo che spera che il NIST si muova un bel po' prima del nuovo
decennio, come invece annunciato nel documento [3]... AES ha richiesto
solo 3 anni, ne abbiamo ancora più di 5...

- --
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.4 (Cygwin)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iEYEARECAAYFAkFYuFAACgkQaJiCLMjyUvs4UACg5Wr2eOmnqhMVydL9nbk90peJ
/I8AoOWt9D8nEWBt5rzFcwY8hZxK6ocR
=dF0/
-----END PGP SIGNATURE-----
-- end of forwarded message --