Newsgroup: it.comp.os.linux.sys
Titolo: Diversi tipi di md5

Dunque, ho sempre "salvato" le password in un database calcolando l'hash
md5, per evitare di lasciarle in chiaro.
Oggi mi è capitato di giocare un po' con cups ed il suo file degli
"utenti" chiamato passwd.md5 che contiene, oltre ovviamente al nome
utente, anche il gruppo e la password. Ora, dal nome penso che la
password sia anch'essa in realtà l'hash della password.
Tuttavia, per curiosità, sono andato a confrontare i due hash calcolati
a partire da una stringa identica. L'hash md5 di PHP e quello invece "di
cups" sono diversi.
Non essendo un grande esperto in materia chiedo a voi Illuminati: com'è
possibile? C'è un tranello? O forse ho erroneamente sempre creduto che
esistesse solo "un tipo" di hash md5? O forse è PHP/CUPS che fanno
qualcosa alla stringa prima di calcolare l'hash?
Enrico


No. Si puó usare una string di 'salt' per alterare l'output del hash.
La procedura consiste in:
-creare la pass (e.g. 'miapassword')
-sommare la salt string (e.g. 'miasaltstring')
-concatenarle: 'miapasswordmiasaltstring'
-passare quello a md5().
Poi, ogni volta che un utente si collega, si usa nuovamente la
concatenazione per fare il confronto col hash.
È quello che si fa normalmente ad esempio nel framework cakephp.
Ovviamente, conviene che la salt sia 'complessa'.
--
Saludos
Adriano

 qualcosa alla stringa prima di calcolare l'hash?
Due spiegazioni possono essere:
a) in uno dei due hash viene aggiunto il carattere \n;
   lo verifichi per esempio confrontando i due hash con l'output dei
   comandi:
   # echo "password" | md5sum
   # echo -n "password" | md5sum
b) uno dei due è un hash "salted"
   un'ipotetica funzione di calcolo di un hash salted potrebbe essere:
   $hash = ( md5 ( $Password . $salt ) . $salt )
-- 
Flavio Visentin
Scientists have finally discovered what's wrong with the female brain:
On the left side, there is nothing right, and on the right side, there
is nothing left.

    comandi:
Che dovrebbero uscire diversi, ma comunque uno dei due dovrebbe essere
uguale a quello che ho nel db.
Invece ho 3 hash diversi...
Mi sa che è un fatto di "salt"... cercherò nel sorgente...
Enrico

 echo $USER:$GROUP:$DIGEST
A chi potesse servire, anche in futuro ;-)
PS: la mia soluzione temporanea era basata su una patch che troncava
l'inserimento della password dal programma e la prendeva da riga di
comando. Ora mi sono accorto però che se ragionavo prima di editare
forse quelle quattro istruzioni mi avrebbero salvato dai segfault :-D
Enrico

 qualcosa alla stringa prima di calcolare l'hash?
neanch'io sono un grande esperto, ma mi pare proprio che debbano essere
diversi, altrimenti md5 non sarebbe più un hash crittografico.
questi 2 utenti hanno la password uguale:
user1:$1$P7gy9uUw$Z2QOOy5w8TTmPhQ2McayZ/:14082:0:99999:7:::
user2:$1$8z2N853a$kQh7qLTc/W4CwsHWN9lHl/:14082:0:99999:7:::

 writes:
EB> Non essendo un grande esperto in materia chiedo a voi Illuminati:
EB> com'è possibile? C'è un tranello?
Il tranello si chiama "salt" + "key strenghtening", tipo:
key = md5hash( "password" . "salt" ); // applicazione del salt
for (i=0, i < N, i++)     // key strenghtening
    key = md5hash( key );
Basta  che il  "salt" usato,  o il  numero N  di iterazioni,  o entrambi
cambino tra un programma e  l'altro o, meglio, da una libreria all'altra
(il salt  cambia anche all'interno  dello stesso programma  per evitare,
per quanto  possibile, che password  uguali generino hash uguali)  e gli
hash risultanti sono diversi.
Saluti,
Luca Polo.
-- 
Luca...@gest.unipd.it
 --- 
http://www.gest.unipd.it/~jake
----------------------------------------------------------
One Ping to rule them all. One Ping to find them.
One Ping to bring down them all.
And in the darkness crash them.         [The Lord of the Pings]

 diversi, altrimenti md5 non sarebbe più un hash crittografico.
Negativo, MD5 è una funzione di hash ONE-WAY, che ritorna una stringa di
lunghezza fissa _sempre uguale_ a parità di input. MD5 hash diversi
significano stringhe in input diverse, eventualmente ottenute mediante
qualche meccanismo di salting. All'opposto, due input diversi che generano
lo stesso hash generano una collisione, la quale rende l'algoritmo di hash
insicuro e assolutamente da non utilizzare in ambienti mission-critical. Se
non sbaglio qualcuno ha generato una collisione per MD5, il cui uso è qundi
sconsigliato a favore di algoritmi più sicuri, come SHA1.
-- 
g4b0, linux user n. 369000
http://gabo.homelinux.com

g4b0 ha scritto:
 > e assolutamente da non utilizzare in ambienti mission-critical.
[OT on]
L'uso casalingo può essere considerato mission-critical? :-P
[OT off]
Google ha confermato che qualcuno ha generato collisioni con md5, 
tuttavia per l'uso che ce ne faccio non è che sia necessaria tutta 
questa segretezza ;-)
Enrico

 sconsigliato a favore di algoritmi più sicuri, come SHA1.
Non siamo così catastrofisti.
E' stato scoperto un modo per ridurre significativamente la quantità di
iterazioni necessarie per generare due hash collidenti. Da qui a dire che
Md5 è attualmente insicuro ce ne passa.
Diverso sarebbe se fosse stato trovato il modo per ridurre le iterazioni per
trovare una collisione di hash dato un input arbitrario, ma questo ancora,
per fortuna, non è.


 qundi sconsigliato a favore di algoritmi più sicuri, come SHA1.
ormai da anni anche sha1 non è considerato immune.
quindi le password shadow che utilizzano md5 userebbero un meccanismo di key
strengthening? perché la stessa password ritorna 2 hash completamente
diversi.

 perché la stessa password ritorna 2 hash completamente diversi.
Probabilmente usano lo username o lo userid come salt.
Bye.

 Probabilmente usano lo username o lo userid come salt.
era credibile, ma non è così.

 per fortuna, non è.
Oggi in macchina mi è venuta una riflessione forse banale ma che mi ha
lasciato pensare. Premetto che non sono un esperto di algoritmi di
hashing e compagnia, anzi direi che li ho sempre visti da lontano.
Ma se un algoritmo come l'md5 o l'sha1, che ha una lunghezza fissa con
un certo numero di simboli possibili, le combinazioni non sono
"limitate"? Ovvero, non si possono sempre generare collisioni?
Perché il numero di permutazioni (si dice così no?) non è "limitato"?
(ovvero, se ci sono x possibili tali che x è uno dei simboli,
moltiplicato (o elevato a potenza? o qualsiasi operazione matematica) il
numero di "posti" (lunghezza dell'hash), questo è un numero finito).
Potenzialmente io potrei calcolare l'hash di qualsiasi cosa.
Intanto vedo di capire, almeno a grandi linee, come funziona l'md5 (o
comunque un algoritmo di hash), perché credo di avere informazioni un
po' sbagliate.
Enrico

 era credibile, ma non è così.
In shadow trovi stringhe aventi la seguente forma:
$1$seed$hash
Il seed è quindi proprio lì...
Puoi leggere il sorgente del modulo perl PasswdMD5.pm
http://search.cpan.org/src/LUISMUNOZ/Crypt-PasswdMD5-1.3/PasswdMD5.pm
e testare con un semplice script che tutto torna
#!/usr/bin/perl
use Crypt::PasswdMD5;
chomp(my $pass= <STDIN>);
chomp(my $seed= <STDIN>);
$hashed= unix_md5_crypt($pass, $seed);
print "$hashed\n";

 "limitate"? Ovvero, non si possono sempre generare collisioni?
Assolutamente sì.

 Assolutamente sì.
E quindi non sarebbe meglio generare un hash di lunghezza variabile,
dipendente dalla stringa in input?
Però così rischi che l'attaccante sappia a priori quanto è lunga la
stringa di input, così può restringere il campo di parecchio...
uhm... non è proprio il mio campo :-D
Enrico

 diversi, altrimenti md5 non sarebbe più un hash crittografico.
Hai le idee decisamente confuse. L'importante è che la funzione di hash sia
one-way, weak collision resistance e strong collision resistance
-- 
http://img169.imageshack.us/img169/1054/medioevowb0.jpg

 po' sbagliate.
Non ho ben capito cosa intendevi dire, ma lo schema classico è quello di
dividere il messaggio in blocchi e dare ogni blocco in pasto ad una
funzione di crittazione che prende in input quel preciso blocco del
messaggio e l'output "crittografato" del blocco precedente (con
l'eccezione, ovviamente, del primo blocco).
L'MD5 crea un output di 128bit e ci sono delle debolezze note mentre l'SHA
che utilizza 160 bit è ritenuto sicuro (nel caso esistono anche versioni
con più bit).
-- 
http://img169.imageshack.us/img169/1054/medioevowb0.jpg

 dipendente dalla stringa in input?
No. Ma anche per una questione storica, considerando che l'hash nasce come
metodo per verificare la correttezza di un messaggio ricevuto, è importante
che in ricezione questo non venga confuso con la parte informativa: è
necessaria una struttura ben precisa (e una firma di lunghezza fissa) per
determinare quale è il messaggio e quale l'output dell'hash.
-- 
http://img169.imageshack.us/img169/1054/medioevowb0.jpg

 "limitate"? Ovvero, non si possono sempre generare collisioni?
Collisioni ce ne sono infinite proprio perché il dominio della funzione è
infinito mentre il codominio è finito.
Se prendi una qualsiasi macchina linux e calcoli l'hash md5 di tutti i files
ivi contenuti (con md5sum) vedrai che al 99% troverai diverse collisioni.
La cosa importante però è che tali collisioni non sono "prevedibili", ovvero
dato un file X qualsiasi non è attualmente possibile generare un file Y che
abbia lo stesso hash se non usando brute force...


 uhm... non è proprio il mio campo :-D
No, decisamente no.


 print "$hashed\n";
ok, il salt viene generato automaticamente.

 come metodo per verificare la correttezza di un messaggio ricevuto, è
Non proprio.
L'hash nasce come metodo per distribuire dei dati in un insieme in modo 
piu` uniforme possibile.
Questo per avere il minor numero possibile di elementi nella stessa 
posizione dell'insieme.
Solo in seguito, vista questa sua caratteristica di distribuzione dei 
risultati, e` stato usato per il check dei file e per la "crittazione" di 
password, perche` una modifica anche minima nel parametro di input genera 
in output un risultato (una posizione) diversa.
Nessuno usera` mai md5 come funzione di hashing per una hashtable (se non 
per usi mooooolto particolari), perche` restituisce numeri troppo grandi 
per essere usati come indici di un array (che andrebbe a occupare diversi 
GB di memoria).
Bye.

 è ritenuto sicuro (nel caso esistono anche versioni con più bit).
Nessuna funzione di hashing e` ritenuta una funzione sicura di 
crittazione, perche` non e` una funzione di crittazione.
E` solo piu` difficile trovare collisioni.
Bye.

 "limitate"? Ovvero, non si possono sempre generare collisioni?
Una buona funzione hash produce delle chiavi uniformemente distribuite.
Quindi la probabilita' che, con una funzione di hash perfetto ad N bit due
sequenze di dati diverse producano lo stesso hash e' 1/2^N. Per valori alti
di N, questa probabilita' e' cosi' basso che si puo' escludere l'ipotesi che
siano due dati diversi con lo stesso hash (ovvero, una password diversa che
viene hash-ata allo stesso modo).
-- 
Per rispondermi, sostituisci a nomecognome il mio nome e cognome
To reply me, substitute nomecognome with my real name and surname
http://bitsandchaos.wordpress.com

 ivi contenuti (con md5sum) vedrai che al 99% troverai diverse collisioni.
Cioe' il numero di file che hai sul tuo computer e' nell'ordine di 2^128.
Per curiosita', che file system usi?


 dipendente dalla stringa in input?
Supponiamo che tu abbia una funzione di hash ad N bit, quindi 2^N
combinazioni possibili.
Funzioni di hash piu' piccole sarebbero quelle ad 1,2,...,N-1 bit, che hanno
un numero di combinazioni pari a 2,4,2^(N-1).
Somma(2,4,2^(N-1))=2^N - 1 - 1 = circa 2^N
quindi, avere tutte queste funzioni hash piu' piccole raddoppierebbe
solamente lo spazio dei valori della funzione hash, cosa che puoi ottenere
molto piu' semplicemente aggiungendo un bit e calcolando quindi hash ad N+1 
bit.
Inoltre, questa famiglia di funzioni hash sarebbe molto difficile da
definire (non e' banale definire una buona funzione hash, anzi e' un compito
estremamente faticoso) e comunque dovrebbe esistere un criterio che spieghi 
quale funzione usare per hash-are un certo input, e l'attaccante potrebbe 
usare lo stesso criterio per selezionare la specifica funzione hash su cui
attaccare, e sulle funzioni hash piu' piccole sarebbe molto piu' facile
trovare l'input che ha prodotto un certo hash.
Inoltre, come ti hanno detto, ci sono questioni sul formato dei messaggi che
vanno considerate. 
