md5 nach RFC 1321

FrEEzE2046

Dokumentation: RFC 1321

Hallo,

ich muss/soll eingene Routinen zur Bildung eines MD5-Hashes nach Ronald L. Rivest implementieren.

Dabei stellt sich mir direkt nach den ersten Zeilen eine Verständnisfrage. Und zwar betrifft es folgenden Abschnitt:

3.1 Step 1. Append Padding Bits

The message is "padded" (extended) so that its length (in bits) is
congruent to 448, modulo 512. That is, the message is extended so
that it is just 64 bits shy of being a multiple of 512 bits long.
Padding is always performed, even if the length of the message is
already congruent to 448, modulo 512.

Padding is performed as follows: a single "1" bit is appended to the
message, and then "0" bits are appended so that the length in bits of
the padded message becomes congruent to 448, modulo 512. In all, at
least one bit and at most 512 bits are appended.

1. Satz: Die Nachricht wird erweitert, sodass ihre Länge (in Bit) 448 entspricht. Was soll das modulo 512 bedeuten? 448 modulo 512 ergibt doch 448 - was soll das also?
2. Satz: Die Nachricht wurde so erweitert, dass sie genau 64 Bit davon entfernt ist ein vielfaches von 512 bits zu sein. [Leuchtet ein]
3. Satz: Die Auffüllung findet immer statt, auh wenn die Länge der Nachricht bereits 448 entspricht. Hier wieder die Frage: a) was bedeutet modulo 512 und b) das würde ja bedeuten, dass eine längere Nachricht an der Stelle 448 abgeschnitten wird. Denn meines Wissens nach führt eine Padding-Funktion (so zumindest auch meine Implementation) ein Truncate aus, wenn der übergebene Text länger ist.

Kann es vielleicht sein, dass mit der angesprochenen "message" die Ausgangsnachricht, also der Hash selbst gemeint ist? Aber auch das wäre doh Blödsinn, da der Hash 128 Bit (16 Byte) groß ist ...

Mit bitte um schnelle Hilfe. Schon mal danke an jeden der sich die Mühe macht.

volkard

Padding sorgt dafür, daß das letzte 512-Byte-Paket genau 448 Bytes groß ist.
Und Padding wird immer ausgeführt, sogar, wenn das letzte schon zufällig 448 Bytes groß war. Dann muß halt eine Eins mit 511 Nullen drangeklatscht werden.

^^ bits, nicht bytes.
im original-code sieht das so aus:

static unsigned char PADDING[64] = 
{
  0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
...
 /* Pad out to 56 mod 64.
 */
  index = (unsigned int)((context->count[0] >> 3) & 0x3f);
  padLen = (index < 56) ? (56 - index) : (120 - index);
  MD5Update (context, PADDING, padLen);
...

FrEEzE2046

Also, erst einmal vielen Dank für eure Anregungen. Ich habe das Ganze aber noch nicht richtig verstanden.

Was genau bedeutet das "letzte" 64-Byte Packet? Muss ich mir das so vorstellen, dass die übergebene Message in 64-Byte Blöcke aufgeteilt wird und sollte der letzte Block nicht "voll" sein, so wird er mit Nullen gefüllt? Ist das so richtig interpretiert?

index = (unsigned int)((context->count[0] >> 3) & 0x3f);
  padLen = (index < 56) ? (56 - index) : (120 - index);

mmmh, also das verstehe ich nicht. Was genau ist bei dir Context?
Sieht für mich folgendermaßen aus:
1. Du machst einen shr um 3 stellen, da 2^3 = 8 (Umrechnung von Bit zu Byte)
2. Vom Resultat holst du dir den Wert der unteren 63 Bit

Das würde bei 64 Byte "8" ergeben ... also weiß ich, dass 8 Byte gefüllt sind. Die Errechnung von padLen verstehe ich dann wieder nicht.

Tut mir leid, wenn ich mich etwas blöd anstelle.

C++ Forumbot

Dieser Thread wurde von Moderator/in rüdiger aus dem Forum ANSI C in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

volkard

Ich Versuch's mal.

index = (unsigned int)((context->count[0] >> 3) & 0x3f);
  padLen = (index < 56) ? (56 - index) : (120 - index);
mmmh, also das verstehe ich nicht. Was genau ist bei dir Context?
Sieht für mich folgendermaßen aus:
1. Du machst einen shr um 3 stellen, da 2^3 = 8 (Umrechnung von Bit zu Byte)
2. Vom Resultat holst du dir den Wert der unteren 63 Bit
Jup.

2. Vom Resultat holst du dir den Wert der unteren 6 Bit
Die unteren 6 Bit zu holen ist das selbe wie MOD 64 zu rechnen. Also Mod 64Byte, ist Mod 512Bit. Ganzzahlige Vielfache von 512 Bit werden weggeworfen.
Das ist der Index des letzten benutzen Bytes im letzten Block.
und dann kommt

if(index<56)//Wenn genug Platz ist, dann normal auffüllen
   padLen=56-index;
else//ansonsten ein ganzen Paket mehr nehmen und auch auffüllen
   padLen=64+56-index;

FrEEzE2046

Dann habe ich es doch richtig verstanden Das mit den 63 Bit war natürlich ein gedanklicher Mischmasch zwischen 63 (0x3f) und den 6 "Bit" ^^.

Vielen Dank, sollte sich noch ein Problem ergeben, ergänze ich diesen Thread. Die Sache mit den 64 Byte Blöcken die quasi über der Eingangsnachricht liegen, habe ich aber richtig erläutert oder?

EDIT: Wofür wurde hier das Char-Array PADDING benutzt?

FrEEzE2046 schrieb:

mmmh, also das verstehe ich nicht. Was genau ist bei dir Context?

'context' ist eine MD5_CTX struct. die funktion 'MD5Update()' braucht 'ne adresse auf die aktuelle MD5_CTX, einen pointer auf die daten und die länge der daten, dann werden soviele bytes wie die länge angibt, in den MD5-hash hineingemixt (in dem fall eben padLen von den padding-bytes).
ach ja, such mal im originalcode (der im RFC davei ist) nach 'MDString'. daran siehste auch, wie MD5 benutzt wird und welche aufgaben MD5Update,;MD5Final usw. haben.

FrEEzE2046 schrieb:

EDIT: Wofür wurde hier das Char-Array PADDING benutzt?

^^na, um die padding-bits (beginnend mit einer 1) mit anzuhängen.

FrEEzE2046

;fricky schrieb:

FrEEzE2046 schrieb:

EDIT: Wofür wurde hier das Char-Array PADDING benutzt?

^^na, um die padding-bits (beginnend mit einer 1) mit anzuhängen.

Ja, aber 128 ist doch keine Angst

EDIT: 1 meine ich^^

FrEEzE2046 schrieb:

Ja, aber 128 ist doch keine 1

es geht doch um bits. 128(als byte) hat links eine 1 und dann 7 nullen, die anderen bytes sind jeweils für die restlichen 504 null-bits da. als bit-string ist sieht das array so aus: 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

FrEEzE2046

Ich muss nochmal fragen, da eine meiner Fragen konsequent ignoriert wird

Also, in der Dokumentation ist nur die Rede davon, dass die Nachricht auf 448 Bit "erweitert" wird. Was passiert aber, wenn die Nachricht größer ist als 56 Byte? Wird dann die Nachricht auf 112 Byte erweitert?

volkard

120

hustbaer

FrEEzE2046, wie kann man nur so auf dem Schlauch stehen...

Die Nachricht wird so erweitert, dass gilt

(Länge-In-Bits(Nachricht) [i]modulo[/i] 512) == 448

Dabei wirst zuerst ein Bit mit Wert 1 angehängt, und dann (solange nötig) Bits mit dem Wert 0.

Wie du auf die Idee kommen könntest dass der Hash-Wert irgendwie mit Padding versehen werden soll... keine Ahnung. Den Hash-Wert errechnest du ja erst, und der ist immer 128 Bit -- wieso sollte man da irgendein Padding dranhängen. Und wieso auf 448 Bit?

FrEEzE2046

hustbaer schrieb:

Wie du auf die Idee kommen könntest dass der Hash-Wert irgendwie mit Padding versehen werden soll... keine Ahnung. Den Hash-Wert errechnest du ja erst, und der ist immer 128 Bit -- wieso sollte man da irgendein Padding dranhängen. Und wieso auf 448 Bit?

Komme ich überhaupt nicht. Ich habe nie gesagt, dass der Hash selbst vergrößert wird, sondern die Eingangsnachricht.

Ich hatte nur die Aussage nicht verstanden:

hustbaer schrieb:

Die Nachricht wird so erweitert, dass gilt
(Länge-In-Bits(Nachricht) [i]modulo[/i] 512) == 448

Warum ist mir jetzt auch nicht mehr klar. Ist ja eigentlich ganz einfach (56, 120, 184, 248, ...)

hustbaer

FrEEzE2046 schrieb:

hustbaer schrieb:
"Die Nachricht wird so erweitert, dass gilt
(Länge-In-Bits(Nachricht) [i]modulo[/i] 512) == 448
Warum ist mir jetzt auch nicht mehr klar.

Darauf willst du nicht wirklich eine Antwort, oder?

hustbaer schrieb:

Warum ist mir jetzt auch nicht mehr klar.

Darauf willst du nicht wirklich eine Antwort, oder?

die frage ist berechtigt. wahrscheinlich ist ohne dieses padding der output nicht 'zufällig' genug, bei bestimmten eingabedaten. warum das genau gemacht wird, steht im RFC auch nicht, musste wohl mal dem rivest 'ne mail schicken.

Tyrdal

Ihm ist nicht klar warum er es vorher nicht kapiert hat!

hustbaer

Huch!
Eine dritte Möglichkeit wie man es verstehen kann
Ja, das wird er gemeint haben.

Ich hatte es noch anders ausgelegt. Wenn man den Satz als rhetorische Frage liest, und böswillig etwas Zynismus unterstellt, bekommt er nämlich nochmal eine andere Bedeutung. Hihi. Hab ich wohl falsch interpretiert. Oops.