md5

[Secxet]

Salve.
Vorrei sapere come viene calcolato l'hash dell'md5, ho già cercato su google di capirne il funzionamento ma non sono riuscito a capirne molto, ora vorrei sapere se qualcuno di voi saprebbe spiegarmi come funziona.
Es. se ho la stringa "ab", come faccio ad ottenere il relativo hash md5, calcolandolo a mano, se qualcuno riesce a spiegarmi dettagliatamente tutti i pasaggi che vengono effetuati per ottenere l'hash, gliene sarò riconoscente.

Grazie in anticipo.

[task-]

E' un processo estremamente complicato non ti è di nessunaiuto conoscerne tutti i passaggi....

[fcorbelli]

Lo trovi facilmente su internet.
Se ti interessa a "stragrandissime linee" il messaggio originale, dopo essere stato opportunamente "allungato", viene spezzato in blocchi di 512 bit.
Ognuno di questi blocchi, a sua volta, viene suddiviso in porzioni più piccole, ad ognuna delle quali sono applicate un certo numero di funzioni logiche (composizione di AND, NOT e XOR) che "rimescolano" il contenuto.

[Secxet]

Originariamente inviato da fcorbelli

Lo trovi facilmente su internet.
Se ti interessa a "stragrandissime linee" il messaggio originale, dopo essere stato opportunamente "allungato", viene spezzato in blocchi di 512 bit.
Ognuno di questi blocchi, a sua volta, viene suddiviso in porzioni più piccole, ad ognuna delle quali sono applicate un certo numero di funzioni logiche (composizione di AND, NOT e XOR) che "rimescolano" il contenuto.

Inanzittutto grazie della risposta, credo di aver capito cosa volevi dire, ma potresti riuscire ad essere un pò più dettagliato?

Grazie ancora.

[fcorbelli]

Non mi è chiaro se vuoi l'algoritmo in pseudocodice o in codice.
Lo trovi facilmente basta che cerchi qualcosa tipo
"md5 pascal" o quello che vuoi

Ad esempio
http://pascal.sources.ru/crypt/md5asm32.htm

[Secxet]

Quello che mi servirebbe è capire il procedimento che viene fatto, partendo da una stringa in input fino ad ottenere l'hash.

[fcorbelli]

Originariamente inviato da Secxet

Quello che mi servirebbe è capire il procedimento che viene fatto, partendo da una stringa in input fino ad ottenere l'hash.

ti basta leggere il sorgente o guardare direttamente l'algoritmo, ad esempio su wikipedia
http://en.wikipedia.org/wiki/MD5#Pseudocode
e qui
http://tools.ietf.org/html/rfc1321

[Secxet]

OK, sto cercando di capire l'algoritmo, che c'è su wikipedia,
nel primo pasaggio vengono dichiarati 2 array(r, k) di lunghezza 64, mentre nel secondo pasaggio non riesco a capire cosa si sta facendo, sapresti spiegarmi cosa è?

non capisco cosa voglia dire questa istruzione ":="

Grazie.

[fcorbelli]

assegnazione

[Secxet]

Grazie, io pensavo chissà cosa volesse dire, adesso però non capisco perchè vengono assegnati proprio quei valori ad r?, hanno qualche significato particolare?

mentre nel pasaggio succesivo c'è questo:

//Use binary integer part of the sines of integers (Radians) as constants:
for i from 0 to 63
    k[i] := floor(abs(sin(i + 1)) × (2 pow 32))
end for

il ciclo credo di averlo capito, calcola il seno di (i+1), ne prende il valore assoluto, lo moltiplica per 2^32, elimina tutta la parte decimale, ed infine lo assegna ad k[i]?

Es: i:=0

sin(0 + 1)-->0,017452406437283512819418978516316
abs(0,017452406437283512819418978516316)-->0,017452406437283512819418978516316
0,017452406437283512819418978516316*2^32-->74957514,884632562639401266449305
floor(74957514,884632562639401266449305)-->74957514
k[i]:=74957514
giusto?
perchè mi viene un dubbio sul calcolo del seno, perchè nei commenti c'è scritto qualcosa a riguardo dei radianti, però non ci ho capito molto.

Grazie ancora.

ok, ora ho capito, si calcola il seno di i+1, in radianti che è 0.8414709848, prendo il valore assoluto, lo moltiplico per 2^32 ottenedo: 3614090360,2489131008, arrotondo a 0 decimali: 3614090360, lo converto in esadecimale: D76AA478, ottenedo esattamente quello che c'è nella tabella sul link di wikipedia che mi hai dato, l'unica differenza è che gli all'inizio del valore in esadecimale c'è anche 0x, che non capisco cosa voglia dire.

però non ho ancora capito perchè all'array r vengono assegnati proprio quei valori, inoltre sapresti spiegarmi cosa vuol dire la segiente roba:

//Pre-processing: adding a single 1 bit
append "1" bit to message    
/* Notice: the input bytes are considered as bit strings,
  where the first bit is the most significant bit of the byte.[37]
  In other words: the order of bits in a byte is BIG ENDIAN,
  but the order of bytes in a word is LITTLE ENDIAN */

[fcorbelli]

Originariamente inviato da Secxet

all'inizio del valore in esadecimale c'è anche 0x, che non capisco cosa voglia dire.

Proprio "esadecimale"

inoltre non ho ancora capito perchè nell'array r vengono scelti proprio quei valori.

Perchè son così.
In teoria, ma moooolto in teoria, dovrebbero irrobustire da una crittanalisi differenziale, un po' come la scelta delle funzioni fatta a suo tempo (in segreto) per DES.

Non mi è chiaro se vuoi sapere "come" si calcola l'hash o "perchè" lo si calcola così

[Secxet]

Grazie ancora, no voglio semplicemente capire come si calcola, mi potresti spiegare cosa significa il pasaggio successivo:

//Pre-processing: adding a single 1 bit
append "1" bit to message    
/* Notice: the input bytes are considered as bit strings,
  where the first bit is the most significant bit of the byte.
  In other words: the order of bits in a byte is BIG ENDIAN,
  but the order of bytes in a word is LITTLE ENDIAN */

[fcorbelli]

Originariamente inviato da Secxet

Grazie ancora, no voglio semplicemente capire come si calcola, mi potresti spiegare cosa significa il pasaggio successivo:

//Pre-processing: adding a single 1 bit
append "1" bit to message    
/* Notice: the input bytes are considered as bit strings,
  where the first bit is the most significant bit of the byte.
  In other words: the order of bits in a byte is BIG ENDIAN,
  but the order of bytes in a word is LITTLE ENDIAN */

La prima parte è il padding, ovvero allungare il messaggio fino a giungere a un multiplo di 512 byte, il che sottostà a regole precise (contiene anche la lunghezza del messaggio, se non ricordo male, è parecchio che non lo insegno più).
Riguardo invece a big e little endian, si tratta della forma di codifica delle parole, ovvero se si memorizzano prima i byte bassi o quelli alti.
E' un retaggio storico di una diatriba nata ai tempi di motorola vs intel (poi portata avanti lato powerpc e così via).

[Secxet]

Inanzittutto grazie per la risposta.

Però non credo di aver capito.
Es. se il mio mesaggio è questo:
"Cantami o diva del pelide Achille l'ira funesta" --> 47 byte
ora il messaggio è di 47 byte, quindi ora devo raggiungere una lunghezza di 64 byte, aggiungendo 17 byte?

però mi viene un dubbio 64 non è un sottomultiplo di 512?
e se il messaggio da criptare fosse più lungo di 512 byte, i byte in più vengono ignorati?
inoltre quali byte vengono aggiunti per raggiungere tale lunghezza?


ora forse ho capito:
leggendo su questo sito: http://tools.ietf.org/html/rfc1321 (step 3.1)

nella fase di padding il messaggio viene "imbottito", in modo tale che la lunghezza del massaggio si pari ad 448bit mod 512bit(in altre parole di 448 bit -- >56 byte), quindi il messaggio viene portato ad una lunghezza di 448bit, in modo tale che manchino solo 64 bit perchè il messaggio sia pari a 512 bit, l'imbottitura avviene come segue:
viene prima aggiunto il bit "1", e poi "0" bit fino a raggiungere 448 bit.

giunto?

[fcorbelli]

Sono multipli di 512 bit, non byte.
La prima fase del padding serve per arrivare all'ultimo chunk cui appendere la lunghezza del messaggio (a 64 bit), per poi avere un messaggio composto esattamente da multipli di 512 bit.

[Secxet]

Sono multipli di 512 bit, non byte.
La prima fase del padding serve per arrivare all'ultimo chunk cui appendere la lunghezza del messaggio (a 64 bit), per poi avere un messaggio composto esattamente da multipli di 512 bit.

e no sta volta non ho capito nulla, potresti spiegarti meglio

Grazie in anticipo.=)

[fcorbelli]

Originariamente inviato da Secxet

e no sta volta non ho capito nulla, potresti spiegarti meglio

Grazie in anticipo.=)

Bhè in realtà è piuttosto semplice.
I messaggi vengono elaborati a blocchi di 512 bit, e fin qui bene.
Però in coda al messaggio (inteso come flusso di bit) viene appesa la lunghezza del messaggio stesso (in binario, 64 bit).
Quindi avrai qualcosa tipo
<messaggio>.........<pad>............<ultimi 64 bit, lunghezza >
010102010101010 1...0000000[...]00000000000000000000000000111
Gli ultimi 64 bit sono la lunghezza del messaggio (* per inciso come puoi capire non riesci a calcolare hash di più di 2^64 bit di lunghezza, ma in questo caso fa lo stesso, memorizzi comunque i 64 bit della lunghezza)

In sostanza il messaggio è composto da tanti chunk da 512 bit, l'ultimo dei quali ha gli ultimi 64 riservati (=posti alla lunghezza), quindi in realtà ne ha 448 (che sono 512-64) liberi.
Se sono tutti occupati bene, altrimenti li paddi con un "1" e tanti zeri fino ad arrivare a 488, a quel punto ci metti la lunghezza del messaggio (64 bit) e ottieni l'ultimo chunk di 512.
In teoria, ma molto in teoria, questo consente-una volta decodificato il messaggio- di controllare di aver letto tanti byte quanti avrebbero dovuti essere (una sorta di "doppio controllo")

[Secxet]

non capisco perchè servono 64 bit per contenere la lunghezza del messaggio, se al massimo il messaggio può essere lungo 448bit, infatti se il messaggio fosse lungo 448 bit, trasformando 448 in binario diventa:111 000 000(9 bit), quindi basterebbere 9 bit per contenere la lunghezza del messaggio?

inotre anlizzando il passo successivo, dentro un ciclo for, c'è un and "b and c"
b = 0xefcdab89
c = 0x98badcfe

come si calcola l'and tra questi 2 valori?

Grazie in anticipo.

[Secxet]

pubblico la risposta di fcorbelli sul forum(può tornare utile ad altre persone) che non può rispondere direttamente sul forum:

----------------------------------------------------------------------------------------------------------------------
La prima risposta è relativa al fatto che sono previsti 64 bit per la lunghezza del messaggio.
Ma questo può essere lungo fino a 2^64 bit.
Se consideriamo l'hash di un file d 4gigabyte, si avranno 32 bit a zero e 32 a 1 per la lunghezza.
In altri termini la lunghezza del messaggio è quella TOTALE.

Riguardo alla funzione "and" questa opera in binario.
Si convertono quindi i valori in binario, e poi si opera la moltiplicazione ("E" logico), secondo la tabella della verità
di AND per cui il risultato è 1 se e solo se entrambi gli operandi sono 1.

Nell'esempio, per semplicità, supponiamo
b=$89
c=$fe

b (in binario) vale
10001001
mentre c
11111110

Ora si fa l'AND bit a bit (il cui risultato è 1 se entrambi sono 1)

12345678
10001001 AND
11111110
-------------
1: 1 AND 1 = 1
2: 0 AND 1 = 0
3: 0 AND 1 = 0
4: 0 AND 1 = 0
5: 1 AND 1 = 1
6: 0 AND 1 = 0
7: 0 AND 1 = 0
8: 1 AND 0 = 0
Risultato (se non mi son sbagliato)

10001000

[Secxet]

Grazie mille , ho capito.

ora però sempre riferendomi ad sito da lei linkatomi:http://en.wikipedia.org/wiki/MD5#Pseudocode, nella parte in cui ci sono 2 cicli for annidati, per quanto riguarda il ciclo più interno ho capito che va da 0 a 63, mentre quello esterno non riesco a capire quanto dura...

inoltre all'interno del ciclo più esterno è presente questa istruzione:

b := b + leftrotate((a + f + k[i] + w[g]) , r[i])

cosa vuol dire leftrotate?

Grazie.