MD5
MD5 verarbeitet Blöcke der Länge 512 Bits oder 64 Bytes, so dass jede
Nachricht durch Auffüllen mit einer 1 und weiteren 0en auf diese Länge
gebracht werden muss. Da das erste angehängte Bit auf jeden Fall eine 1 ist und
die letzten 64 Bits oder 8 Bytes zur Darstellung der Länge der
Originalnachricht verwendet werden, müssen gegebenenfalls sogar mehr als 512
Bits angehängt werden.
Zu Anfang werden vier Verkettungsvariablen initialisiert:
| A := 0123456716 |
| B: = 89ABCDEF16 |
| C := FEDCBA9816 |
| D := 7654321016 |
Die Nachricht wird in n Worten zu 512 Bits zerlegt, die
als M0, M1, ..., Mn bezeichnet werden. Jedes
dieser 512-Bit-Worte wird in 16 32-Bit-Worte zerlegt, die wir hier für den
k-ten Teilblock als Mkj bezeichnen, wobei j=0..15.
Es werden vier Funktionen definiert:
| F(X,Y,Z) = (XLY)V(~XLZ), |
| G(X,Y,Z) = (XLZ)V(YL~Z), |
| H(X,Y,Z) = X xor Y xor Z, |
| I(X,Y,Z) = Y xor (X xor ~Z). |
Wenn Mkj den j-ten Teilblock des k-ten Teilworts
bezeichnet und CSLk das zyklische Schieben nach links um k Stellen
bedeutet, so erhält man die Funktionen:
| FF(a,b,c,d,Mij,s,ti) steht für a
= b + CSLs(a+F(b,c,d)+Mij+ti), |
| GF(a,b,c,d, Mij,s,ti) steht für a
= b + CSLs(a+G(b,c,d)+ Mij+ti), |
| HH(a,b,c,d, Mij,s,ti) steht für a
= b + CSLs(a+H(b,c,d)+ Mij+ti), |
| II(a,b,c,d, Mij,s,ti) steht
für a = b + CSLs(a+I(b,c,d)+ Mij+ti). |
Mit diesen Funktionen werden vier Runden mit jeweils 16 Schritten
durchgeführt, also insgesamt 64 Schritte:
| Runde 1: |
| FF(a,b,c,d, Mi0, 7, d76aa47816) |
| FF(d,a,b,c,Mi1, 12, E8C7B75616) |
| FF(c,d,a,b,Mi2, 17, 242070DB16) |
| FF(b,c,d,a,Mi3, 22, C1BDCEEE16) |
| FF(a,b,c,d, Mi4, 7, F57C0FAF16) |
| FF(d,a,b,c,Mi5, 12, 4787C62A16) |
| FF(c,d,a,b,Mi6, 17, A830461316) |
| FF(b,c,d,a,Mi7, 22, FD46950116) |
| FF(a,b,c,d, Mi8, 7, 698098D816) |
| FF(d,a,b,c,Mi9, 12, 8B44F7AF16) |
| FF(c,d,a,b,Mi10,17, FFFF5BB116) |
| FF(b,c,d,a,Mi11,22, 895CD7BE16) |
| FF(a,b,c,d, Mi12,7, 6B90112216) |
| FF(d,a,b,c,Mi13,12, FD98719316) |
| FF(c,d,a,b,Mi14,17, A679438E16) |
| FF(b,c,d,a,Mi15,22, 49B4082116) |
| Runde 2: |
| GG(a,b,c,d, Mi1, 5, F61E256216) |
| GG(d,a,b,c, Mi6, 9, C040B34016) |
| GG(c,d,a,b, Mi11,14,265E5A5116) |
| GG(b,c,d,a, Mi0, 20,E9B6C7AA16) |
| GG(a,b,c,d, Mi5, 5, D62F105D16) |
| GG(d,a,b,c, Mi10,9, 0244145316) |
| GG(c,d,a,b, Mi15,14,D8A1E68116) |
| GG(b,c,d,a, Mi4, 20,E7D3FBC816) |
| GG(a,b,c,d, Mi9, 5, 21E1CDE616) |
| GG(d,a,b,c, Mi14,9, C33707D616) |
| GG(c,d,a,b, Mi3, 14,F4D50D8716) |
| GG(b,c,d,a, Mi8, 20,455A14ED16) |
| GG(a,b,c,d, Mi12,5, A9E3E90516) |
| GG(d,a,b,c, Mi2, 9, FCEFA3F816) |
| GG(c,d,a,b, Mi7, 14,676F02D916) |
| GG(b,c,d,a, Mi12,20,8D2A4C8A16) |
| Runde 3: |
| HH(a,b,c,d, Mi5, 4, FFFA394216) |
| HH(d,a,b,c, Mi6, 11,8771F68116) |
| HH(c,d,a,b, Mi11,16,6D9D612216) |
| HH(b,c,d,a, Mi14,23,FDE5380C16) |
| HH(a,b,c,d, Mi1, 4, A4BEEA4416) |
| HH(d,a,b,c, Mi4, 11,4BDECFA916) |
| HH(c,d,a,b, Mi7, 16,F6BB4B6016) |
| HH(b,c,d,a, Mi10,23,BEBFBC7016) |
| HH(a,b,c,d, Mi13,4, 289B7EC616) |
| HH(d,a,b,c, Mi0, 11,EAA127FA16) |
| HH(c,d,a,b, Mi3, 16,D4EF308516) |
| HH(b,c,d,a, Mi6, 23,04881D0516) |
| HH(a,b,c,d, Mi9, 4, D9D4D03916) |
| HH(d,a,b,c, Mi12,11,E6DB99E516) |
| HH(c,d,a,b, Mi15,16,1FA27CF816) |
| HH(b,c,d,a, Mi2, 23,C4AC566516) |
| Runde 4: |
| II(a,b,c,d, Mi0, 6, F429224416) |
| II(d,a,b,c, Mi7, 10,432AFF9716) |
| II(c,d,a,b, Mi14,15,AB9423A716) |
| II(b,c,d,a, Mi5, 21,FC93A03916) |
| II(a,b,c,d, Mi12, 6,655B59C316) |
| II(d,a,b,c, Mi3, 10,8F0CCC9216) |
| II(c,d,a,b, Mi10,15,FFEFF47D16) |
| II(b,c,d,a, Mi1, 21,85845DD116) |
| II(a,b,c,d, Mi8, 6,6FA87E4F16) |
| II(d,a,b,c, Mi15,11,FE2CE6E016) |
| II(c,d,a,b, Mi6, 15,A301431416) |
| II(b,c,d,a, Mi13,21,4E0811A116) |
| II(a,b,c,d, Mi4, 6,F7537E8216) |
| II(d,a,b,c, Mi11,10,BD3AF23516) |
| II(c,d,a,b, Mi2, 15,2AD7D2BB16) |
| II(b,c,d,a, Mi9, 21,EB86D39116) |
Die Werte a, b, c und d werden zu den Werte von A, B, C und D addiert und mit
dem nächsten Datenblock Mi+1
fortgefahren. Die Ausgabe ist die Konkatenation der Werte in A, B, C und D, also
128 Bits.
Es gibt keine ernsthaften Sicherheitsbedenken gegen MD5, wenngleich die kurze
Länge des Digest einen Geburtstagsangriff nicht unmöglich macht. Schneier
schreibt in seinem Buch, dass er MD5 nicht einsetzt, weil es "eine
Schwachstelle in der Kompressionsfunktion" zu geben scheint, die jedoch
nach Ansicht der Autoren keine Auswirkung auf die Sicherheit der Hashfunktion
hat.
|