MD5 Länge einfügen als 64 Bit?

[Apollonius]

Ähem - irgendwie stehst du mit Endianness in letzter Zeit auf Kriegsfuß. Windows ist Little-Endian. Der Mensch ist von Natur aus Big Endian nach Konvention auf Big Endian gepolt. Daher stellen Format, IntToStr und co. auch alle Zahlen als Big Endian dar. Alles andere wäre vollkommen absurd.

[himitsu]

ich glaub du hast Recht ,

hab's geändert

[fortuneNext]

Hey
Super, ihr habt mir in Riesenschritten weitergeholfen!

Von der reinen Logik her habe ich den Algorithmus denke ich nun einigermaßen verstanden.
Die Umsetzung jedoch funktioniert noch nicht so wirklich:
Ich habe mir mal himitsus freundlich bereitgestellten Code genauer angesehen. Dabei ist mir aufgefallen, dass die Vorbereitung wesentlich eleganter aussieht. Aktuell bin ich soweit, dass ich zwar einen Hash erzeugen kann, der jedoch nicht grade nach MD5 aussieht (aus "test" kommt "$6320DC97 D66ACA76 A4A1F2AD D851C940"). Könnte es also an der Vorbereitung liegen?

Delphi-Quellcode:

  textlength := length(text) * 8;
  textlengthbin := IntToBin(textlength);
  text := text + '1';
  while ((length(text) * 8) mod 512) <> 448 do
    text := text + '0';
  while (length(textlengthbin) * 8) mod 512 <> 64 do
    textlengthbin := '0' + textlengthbin;
  text := text + textlengthbin;

Ist die genauso funktionstüchtig, wie ich es mir gedacht habe?
Text ist die eingehende Message (string), textlengthbin ein string.
(Es ist mir klar, dass ich das ganze *8 auch auslassen könnte und direkt mit den richtigen zahlen rechnen könnte, das ist bloß zum besseren Verständnis da Ich meine eher das anhängen der Binärfolge.)

Vielleicht liegt die Fehlerquelle auch woanders. Die Zuweisung von w ist mir auch sehr ins Auge gesprungen:
Pointer(w) := PAnsiChar(message); Diese Zeile verstehe ich leider nicht. Wie kommen denn da 32-Bit-Blöcke heraus?
Bei mir siehen die Blockunterteilungen so aus:

Delphi-Quellcode:

  for x := 1 to (length(text) * 8) div 512 do
  begin
    block := copy(text, 512 div 8, 512 div 8);
    for i := 0 to 15 do
      w[i] := StrToInt(copy(block, (i + 1) * (32 div 8), 32 div 8));

{...}

Dabei ist block ein String, in welchen die 512-Bit-Blöcke geladen werden sollen.
{...} ist der restliche Code - also Zuweisung von a,b,c,d und die Hauptschleife.
Für die Ausgabe habe ich vorläufig erstmal die oben stehende Lösung genutzt (danke auch nochmal dafür ), damit ich erstmal überhaupt einen Hash herausbekomme, um zu sehen, ob es der Richtige ist - ich werde mir aber auch noch einmal eine eigene Lösung erarbeiten
Nunja, jedenfalls finde ich den Fehler nicht wirklich, wahrscheinlich ein Denkfehler meinerseits.
Danke!


PS: Ganz am Rande... ich habe logische Operatoren vorher nicht sonderlich oft auf Integer angewendet - was AND und OR bewirken, ließ sich recht schnell erschließen, aber was bewirkt denn NOT, sodass aus einer 4 eine -5 wird?

[himitsu]

Zitat von fortuneNext:

Könnte es also an der Vorbereitung liegen?

Delphi-Quellcode:

  textlength := length(text) * 8;
  textlengthbin := IntToBin(textlength);
  text := text + '1';
  while ((length(text) * 8) mod 512) <> 448 do
    text := text + '0';
  while (length(textlengthbin) * 8) mod 512 <> 64 do
    textlengthbin := '0' + textlengthbin;
  text := text + textlengthbin;

jupp, in dem Beispiel ist ja von 0 und 1 als Bit die Rede, wenn man das ganze jetzt auf ganze Bytes hochrechnet, dann muß man hier indireckt einen Schritt vorziehen.

eine 1 anhängen und danach gleich noch 7 mal eine 0 ergibt binär ein Byte mit b10000000, was hexadezimal der $80 entspricht, also dem Char #128 bzw. #$80.
und danach kann man dann weiterhin soviele 0 in 8-er-Grüppchen anhängen, bis die 448 erreicht ist.
also b00000000 = $00 = #0

Ord('0') und Ord('1') entsprechen aber nicht der binären 0 und 1

'0' = #48 <> #$00
'1' = #49 <> #$80


Vielleicht liegt die Fehlerquelle auch woanders. Die Zuweisung von w ist mir auch sehr ins Auge gesprungen:
Pointer(w) := PAnsiChar(message); Diese Zeile verstehe ich leider nicht. Wie kommen denn da 32-Bit-Blöcke heraus?

Im Grunde hab ich mir da nur das kopieren gesparrt.
Wenn du dir die Definition von w (bei mir) ansiehst, wirst du die einzelnen 32-Bit-Blöcke erkennen.
Da w bei mir ein Pointer ist, konnte ich diesen einfach auf den Anfang des Strings legen, somit also seine 32-Bit-Blöcke geneu über die Daten des Strings legen.

OK, ich hätte w auch als "eigenständige" Variable definieren können und dann je 512 Bit (16 * 32 Bit = 64 Byte) vom String da reinkkopieren müssen.
(hab aber statt zu die Daten in w reinzukopieren nur das w über die Daten verschoben)

Zitat von fortuneNext:

Bei mir siehen die Blockunterteilungen so aus:

Delphi-Quellcode:

  for x := 1 to (length(text) * 8) div 512 do
  begin
    block := copy(text, x * (512 div 8) + 1, 512 div 8);
    for i := 0 to 15 do
      w[i] := StrToInt(copy(block, (i + 1) * (32 div 8), 32 div 8));

{...}

Hier hattest du noch einen Fehler.
du mußt den String binär ansehn, also die Bits direkt in w[i] kopieren und nicht umwandeln (StrToInt).

Delphi-Quellcode:

for x := 1 to (length(text) * 8) div 512 do
begin
  block := copy(text, x * (512 div 8) + 1, 512 div 8);
  for i := 0 to 15 do
    w[i] := LongWord(Ord(block[(i * (32 div 8)) + 1]))
        or (LongWord(Ord(block[(i * (32 div 8)) + 2])) shl 8)
        or (LongWord(Ord(block[(i * (32 div 8)) + 3])) shl 16)
        or (LongWord(Ord(block[(i * (32 div 8)) + 4])) shl 24);

man könnte jetzt auch einfach sich 4 Zeichen nehmen und diese direkt in einen LongWord casten

Delphi-Quellcode:

for x := 1 to (length(text) * 8) div 512 do
begin
  block := copy(text, 512 div 8, 512 div 8);
  for i := 0 to 15 do
    w[i] := PLongWord(@block[(i * (32 div 8)) + 1])^;

und du hattest vergessen das x in die Verarbeitung mit einzurechnen ... mit x * (512 div 8) + 1 wird auf den Anfang des aktuellen Blocks verwiesen.

Zitat von fortuneNext:

Für die Ausgabe habe ich vorläufig erstmal die oben stehende Lösung genutzt (danke auch nochmal dafür ), damit ich erstmal überhaupt einen Hash herausbekomme, um zu sehen, ob es der Richtige ist - ich werde mir aber auch noch einmal eine eigene Lösung erarbeiten

bin auch gespannt, was bei dir dann mal rauskommt ... schließlich gibt es ja mehrere Wege das ganze in Delphi umzusetzen.

Zitat von fortuneNext:

PS: Ganz am Rande... ich habe logische Operatoren vorher nicht sonderlich oft auf Integer angewendet - was AND und OR bewirken, ließ sich recht schnell erschließen, aber was bewirkt denn NOT, sodass aus einer 4 eine -5 wird?

AND, OR, NOT, XOR und SHL bzw. SHR verarbeiten ja erstmal direkt die einzelnen Bits der einzelnen Werte.
NOT kehrt dabei dir Bits einfach um. (aus b1101000 wird also b0010111)

Warum da aus einer 4 eine -5 wird, liegt an der Interpretation dieser Bits.
Bei einem Integer werden die Bits nach dem Zweierkomplement ausgewertet.


PS: die x-Schleife von dir ist eigentlich optimaler
for x := 1 to (length(text) * 8) div 512 do ich hatte die Verarbeitung immer auf den Stringanfang gelegt und nach jedem Durchgang den eben verarbeiteten Stringteil rausgelöscht.
wenn ich da (ähnlich wie bei dir) die Verarbeitung verschieben würde und die "langsame" Stringverarbeitung (das Löschen) stattdessen wegließe, dann wäre es natürlich schneller ... aber da ich in Wiki's Code keine Schleifenvariable (wie dein x) vorfand, hatte ich es so gelöst (ohne Variable und dafür mit Löschen).


[add]
Hab mein Beispiel mal so umgestllt, daß jetzt nicht mehr gelöscht wird und stattdessen eine Variable wie dein x (hab'se i2 genannt) verwendet wird.

Außerdem gibt's eine Version wo weiterhin w als Pointer-Array über die Daten geschoben wird
und dann noch 'ne Version, wo w als eigentsändiges Array existiert und die Daten da reinkopiet werden.

[fortuneNext]

Super, vielen Dank für die sehr detaillierte Beschreibung das hat mir ein ganzes Stück weitergeholfen. Ich glaube, langsam verstehe ich das mit dem Binären System dadrin und mit der Bit-Byte-Umrechnung. Irgendwo muss aber trotzdem noch ein Fehler sein...

Ich poste einfach mal den gesamten Code, wie er aktuell aussieht.
Dabei entspricht Int64ToBinLength fast deiner UInt64ToLELength-Funktion.
Die aktuellen Fehlersymptome:

Der erste Block des hashs lautet immer "$77777777".
Bei der 2. Verschlüsselung - und das erstaunt mich sehr - verändern sich der 2. und 3. Block. Der Hash ist folglich auch falsch

Delphi-Quellcode:

function TMD5.Crypt(text: string):string;
var
  r: array[0..63] of longword;
  k: array[0..63] of longword;
  i, x, y: longword;
  a, b, c, d: longword;
  h0, h1, h2, h3: longword;
  textlength: int64;
  block: string;
  w: array[0..15] of longword;
  f, g: longword;
  temp: longword;
begin
  r[0] := 7;
  r[1] := 12;
  r[2] := 17;
  r[3] := 22;
  r[4] := 7;
  r[5] := 12;
  r[6] := 17;
  r[7] := 22;
  r[8] := 7;
  r[9] := 12;
  r[10] := 17;
  r[11] := 22;
  r[12] := 7;
  r[13] := 12;
  r[14] := 17;
  r[15] := 22;

  r[16] := 5;
  r[17] := 9;
  r[18] := 14;
  r[19] := 20;
  r[20] := 5;
  r[21] := 9;
  r[22] := 14;
  r[23] := 20;
  r[24] := 5;
  r[25] := 9;
  r[26] := 14;
  r[27] := 20;
  r[28] := 5;
  r[29] := 9;
  r[30] := 14;
  r[31] := 20;

  r[32] := 4;
  r[33] := 11;
  r[34] := 16;
  r[35] := 23;   
  r[36] := 4;
  r[37] := 11;
  r[38] := 16;
  r[39] := 23;
  r[40] := 4;
  r[41] := 11;
  r[42] := 16;
  r[43] := 23;  
  r[44] := 4;
  r[45] := 11;
  r[46] := 16;
  r[47] := 23;

  r[48] := 6;
  r[49] := 10;
  r[50] := 15;
  r[51] := 21;
  r[52] := 6;
  r[53] := 10;
  r[54] := 15;
  r[55] := 21;
  r[56] := 6;
  r[57] := 10;
  r[58] := 15;
  r[59] := 21;
  r[60] := 6;
  r[61] := 10;
  r[62] := 15;
  r[63] := 21;

  for i := 0 to 63 do
  begin
    k[i] := floor(abs(sin(i + 1) * power(2, 32)));
  end;

  h0 := $67452301;
  h1 := $EFCDAB89;
  h2 := $98BADCFE;
  h3 := $10325476;

  textlength := length(text) * 8;
  text := text + #$80;
  while ((length(text) * 8) mod 512) <> 448 do
    text := text + #$00;
  text := text + Int64ToBinLength(textlength);

  for x := 1 to (length(text) * 8) div 512 do
  begin
    block := copy(text, (512 div 8) * x, 512 div 8);
    for i := 0 to 15 do
      move(block[i * 32 + 1], w, 32);

    a := h0;
    b := h1;
    c := h2;
    d := h3;

    for i := 0 to 63 do
    begin
      if (0 <= i) and (i <= 15) then
      begin
        f := (b and c) or ((not b) and d);
        g := i;
      end
      else if (16 <= i) and (i <= 31) then
      begin
        f := (b and d) or (c and (not d));
        g := (5*i + 1) mod 16;
      end
      else if (32 <= i) and (i <= 47) then
      begin
        f := b xor c xor d;
        g := (3*i + 5) mod 16;
      end
      else if (48 <= i) and (i <= 63) then
      begin
        f := c xor (b or (not d));
        g := (7*i) mod 16;
      end;

      temp := d;
      c := b;
      b := ((a + f + k[i] + w[g]) shl (r[i])) or ((a + f + k[i] + w[g]) shr (32 - (r[i]))) + b;
      a := temp;
    end;

    h0 := h0 + a;
    h1 := h1 + b;
    h2 := h2 + c;
    h3 := h3 + d;

  end;

  Result := Format('$%.2x%.2x%.2x%.2x %.2x%.2x%.2x%.2x %.2x%.2x%.2x%.2x %.2x%.2x%.2x%.2x',
      [h0 shr 0 and $ff, h0 shr 8 and $ff, h0 shr 16 and $ff, h0 shr 24 and $ff,
       h1 shr 0 and $ff, h1 shr 8 and $ff, h1 shr 16 and $ff, h1 shr 24 and $ff,
       h2 shr 0 and $ff, h2 shr 8 and $ff, h2 shr 16 and $ff, h2 shr 24 and $ff,
       h3 shr 0 and $ff, h3 shr 8 and $ff, h3 shr 16 and $ff, h3 shr 24 and $ff]);

end;

Am meisten verwirrt mich, dass bei der 2. Verschlüsselung ein anderer Hash herauskommt. Eigentlich müsste ja eine komplett neue Runde erzeugt werden, da kanns doch nicht sein, dass etwas anderes herauskommt. Zumal ab dem 2. Versuch alle gleich sind...

[gammatester]

Ist zwar alles ziemlich undurchsichtig, aber dies ergibt mit Sicherheit keinen Sinn:

Delphi-Quellcode:

    for i := 0 to 15 do
      move(block[i * 32 + 1], w, 32);

Bist Du sicher, daß
 k[i] := floor(abs(sin(i + 1) * power(2, 32))); die richtigen Werte liefert? Warum nicht die Konstanten einsetzen?

Gammatester

[fortuneNext]

Zitat von gammatester:

Ist zwar alles ziemlich undurchsichtig, aber dies ergibt mit Sicherheit keinen Sinn:

Delphi-Quellcode:

    for i := 0 to 15 do
      move(block[i * 32 + 1], w, 32);

Wieso nicht?
Block ist doch 512 Bit groß. Wenn ich den jetzt in 16 32-Bit-Blöcke aufteilen will, muss ich 16x32 Bits nach w bringen. Wie auch himitsu schrieb, oder?

Zitat von himitsu:

OK, ich hätte w auch als "eigenständige" Variable definieren können und dann je 512 Bit (16 * 32 Bit = 64 Byte) vom String da reinkkopieren müssen.
(hab aber statt zu die Daten in w reinzukopieren nur das w über die Daten verschoben)

[gammatester]

Zitat von fortuneNext:

Zitat von gammatester:

Ist zwar alles ziemlich undurchsichtig, aber dies ergibt mit Sicherheit keinen Sinn:

Delphi-Quellcode:

    for i := 0 to 15 do
      move(block[i * 32 + 1], w, 32);

Wieso nicht?
Block ist doch 512 Bit groß. Wenn ich den jetzt in 16 32-Bit-Blöcke aufteilen will, muss ich 16x32 Bits nach w bringen. Wie auch himitsu schrieb, oder?

Weil die ersten 15 move-Aktionen im Nirvana verschwinden. Da kannst Du gleich einmaligmove(block[15 * 32 + 1], w, 32); hinschreiben.

Wahrscheinlich ist allerdings, daß Du w auch irgendwie mit i indizieren willst.

Gammatester

[himitsu]

konnte jetzt nicht testen, ob's so geht, aber einige Fehler hab ich schonmal gefunden.

deine Zeilen auskommentiert, dann 'ne kleine Beschreibung dazu und darunter direkt den Fehler behoben

Delphi-Quellcode:

function TMD5.Crypt(text: string):string;
var
  r: array[0..63] of longword;
  k: array[0..63] of longword;
  i, x, y: longword;
  a, b, c, d: longword;
  h0, h1, h2, h3: longword;
  textlength: int64;
  block: string;
  w: array[0..15] of longword;
  f, g: longword;
  temp: longword;
begin
  r[0] := 7;
  r[1] := 12;
  r[2] := 17;
  r[3] := 22;
  r[4] := 7;
  r[5] := 12;
  r[6] := 17;
  r[7] := 22;
  r[8] := 7;
  r[9] := 12;
  r[10] := 17;
  r[11] := 22;
  r[12] := 7;
  r[13] := 12;
  r[14] := 17;
  r[15] := 22;

  r[16] := 5;
  r[17] := 9;
  r[18] := 14;
  r[19] := 20;
  r[20] := 5;
  r[21] := 9;
  r[22] := 14;
  r[23] := 20;
  r[24] := 5;
  r[25] := 9;
  r[26] := 14;
  r[27] := 20;
  r[28] := 5;
  r[29] := 9;
  r[30] := 14;
  r[31] := 20;

  r[32] := 4;
  r[33] := 11;
  r[34] := 16;
  r[35] := 23;
  r[36] := 4;
  r[37] := 11;
  r[38] := 16;
  r[39] := 23;
  r[40] := 4;
  r[41] := 11;
  r[42] := 16;
  r[43] := 23;
  r[44] := 4;
  r[45] := 11;
  r[46] := 16;
  r[47] := 23;

  r[48] := 6;
  r[49] := 10;
  r[50] := 15;
  r[51] := 21;
  r[52] := 6;
  r[53] := 10;
  r[54] := 15;
  r[55] := 21;
  r[56] := 6;
  r[57] := 10;
  r[58] := 15;
  r[59] := 21;
  r[60] := 6;
  r[61] := 10;
  r[62] := 15;
  r[63] := 21;

  for i := 0 to 63 do
  begin
    k[i] := floor(abs(sin(i + 1) * power(2, 32)));
  end;

  h0 := $67452301;
  h1 := $EFCDAB89;
  h2 := $98BADCFE;
  h3 := $10325476;

  textlength := length(text) * 8;
  text := text + #$80;
  while ((length(text) * 8) mod 512) <> 448 do
    text := text + #$00;
  text := text + Int64ToBinLength(textlength);

  for x := 1 to (length(text) * 8) div 512 do
  begin
    //block := copy(text, (512 div 8) * x, 512 div 8);
    ///   (512 div 8) * x        für  x = 1 {startwert}
    ///   (512 div 8) * 1 = 64   müßte aber 1 sein {1 = erstes Zeichen im String}
    block := copy(text, (512 div 8) * (x - 1) + 1, 512 div 8);
    ///for i := 0 to 15 do
    ///  //move(block[i * 32 + 1], w, 32);
    ///  move(block[i * (32 div 8) + 1], w[i], (32 div 8));   // du willtest doch wohl alles in 
    ///oder gleich                                            // die EINZELNEN w[i] reinkoppieren
    move(block[1], w, 512 div 8);                             // und die 32 waren wohl noch Bits

    a := h0;
    b := h1;
    c := h2;
    d := h3;

    for i := 0 to 63 do
    begin
      if (0 <= i) and (i <= 15) then
      begin
        f := (b and c) or ((not b) and d);
        g := i;
      end
      else if (16 <= i) and (i <= 31) then
      begin
        f := (b and d) or (c and (not d));
        g := (5*i + 1) mod 16;
      end
      else if (32 <= i) and (i <= 47) then
      begin
        f := b xor c xor d;
        g := (3*i + 5) mod 16;
      end
      else if (48 <= i) and (i <= 63) then
      begin
        f := c xor (b or (not d));
        g := (7*i) mod 16;
      end;

      temp := d;
      d := c;  // dieze Zeile hattest'e vergessen
      c := b;
      // die lange Formel stimmt ^^
      b := ((a + f + k[i] + w[g]) shl (r[i])) or ((a + f + k[i] + w[g]) shr (32 - r[i])) + b;
      a := temp;
    end;

    h0 := h0 + a;
    h1 := h1 + b;
    h2 := h2 + c;
    h3 := h3 + d;

  end;

  Result := Format('$%.2x%.2x%.2x%.2x %.2x%.2x%.2x%.2x %.2x%.2x%.2x%.2x %.2x%.2x%.2x%.2x',
      [h0 shr 0 and $ff, h0 shr 8 and $ff, h0 shr 16 and $ff, h0 shr 24 and $ff,
       h1 shr 0 and $ff, h1 shr 8 and $ff, h1 shr 16 and $ff, h1 shr 24 and $ff,
       h2 shr 0 and $ff, h2 shr 8 and $ff, h2 shr 16 and $ff, h2 shr 24 and $ff,
       h3 shr 0 and $ff, h3 shr 8 and $ff, h3 shr 16 and $ff, h3 shr 24 and $ff]);

end;

[fortuneNext]

Hey,
danke vielmals

Zitat:

d := c; // dieze Zeile hattest'e vergessen

Manchmal sind die Fehler erstaunlich einfach

Zitat:

Delphi-Quellcode:

    ///for i := 0 to 15 do
    ///  //move(block[i * 32 + 1], w, 32);
    ///  move(block[i * (32 div 8) + 1], w[i], (32 div 8));   // du willtest doch wohl alles in
    ///oder gleich                                            // die EINZELNEN w[i] reinkoppieren
    move(block[1], w, 512 div 8);                             // und die 32 waren wohl noch Bits

Ich kannte move vorher nicht ;-D Und in der Hilfe hab ich mich scheinbar einfach verlesen, ich dachte, es kopiert direkt die Bits

Mit deiner Hilfe kam nun das erste Mal der richtige Hash raus

Einen Ansatz zur Lösung der Berechnung des Hashs am Ende hab ich auch schon.

Delphi-Quellcode:

  for i := 1 to length(DecToBin(h0) + DecToBin(h1) + DecToBin(h2) + DecToBin(h3)) div 8 do
    Result := lowerCase(Result + IntToHex(StrToInt(copy(DecToBin(h0) + DecToBin(h1) + DecToBin(h2) + DecToBin(h3), 8 * (i - 1) + 1, 8)), 2));

Kommt nicht das richtige Ergebnis raus.

So ganz hab ichs auch noch nicht mit diesen Endians (evtl. reicht mein informatisches Wissen einfach dafür noch nicht aus). Soweit ich das verstanden habe, muss ich irgendetwas drehen. Der Endhash wird damit sicherlich nicht gemeint sein, doch auch das Drehen des Binärstrings oder der einzelnen 8-Bit-Blöcke hat nicht zum Erfolg geführt.
Was mir weiterhin aufgefallen ist: Bei meinem Ansatz ist das Endergebniss viel zu lang. Jeder Block hat ohnehin 80 Bit (10 zeichen), das ist ja soweit noch richtig. Aber bei deinem bisherigen Ansatz wird es ja bloß um bis zu 24 gedreht und damit kommen auch nur 32 Bit heraus, wodurch sich dann der korrekte 128-Bit-Hash auch erklärt - bei mir kommen jedoch die vollen 80-Bit-Blöcke heraus. Warum ließt du weniger aus den Blöcken aus - davon steht in Wikipedia doch nichts?
Und eine Frage hätte ich noch zu deinem Code:

Zitat:

h0 shr 0 and $ff

Und zwar speziell auf das "and $ff" bezogen. Meiner Logik nach müsste das doch vollkommen sinnfrei sein, oder nicht?

$ff
11111111
and
10010110
10010110

Das verändert doch nichts an den Bits, egal, welche Zeichen man nimmt?
Beim Weglassen kommt jedoch etwas Anderes heraus.

Vielen Dank dass ihr soviel Geduld mit mir habt Ich denke, ich lerne dabei eine ganze Menge

fortuneNext