MD5 Algorithmus - Wo ist mein Fehler?

[B3ta]

Hallo zusammen,

Für ein Schulprojekt arbeite ich momentan daran, den MD5 Algorithmus in Delphi zu "rekonstruieren" orientiert habe ich mich dabei hauptsächlich an dem Pseudocode der zu dem Algorithmus auf Wikipedia zu finden ist (Link)
Ich habe das jetzt meines erachtens nach ziemlich genau so wie dort im Pseudo Code in Delphi rekonstruiert, und das Programm startet auch ohne mir irgendeinen Fehler auszugeben.

Allerdings ist das Ergebnis, das mein Algorithmus mir ausgibt ein anderes als es eigentlich sein sollte. So bekomme ich zum Bespiel für einen leeren String nicht wie erwartet den hash-Code: "d41d8cd98f00b204e9800998ecf8427e" Sondern bei mir: "ed41a20e3a99f08c0a329113c39ee592"
Ich bin meinen Quelltext jetzt auch schon etliche male durchgegangen und habe nach potentiellen Fehlern gesucht, habe aber bisher keine gefunden. Deshalb frage ich hier um Rat, ob vielleicht von euch irgendjemand den Fehler entdeckt.

Hier mein Code:

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, Math;

type
  TForm1 = class(TForm)
    Label1: TLabel;
    Button1: TButton;
    Edit1: TEdit;
    Button2: TButton;
    procedure Button1Click(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var KlarText: AnsiString;
    a0,b0,c0,d0: LongWord;
    K: Array[0..63] of LongWord;
    Form1: TForm1;
const s: Array[0..63] of LongWord =  (7,12,17,22, 7,12,17,22, 7,12,17,22, 7,12,17,22,
                                      5,9,14,20, 5,9,14,20, 5,9,14,20, 5,9,14,20,
                                      4,11,16,23, 4,11,16,23, 4,11,16,23, 4,11,16,23,
                                      6,10,15,21, 6,10,15,21, 6,10,15,21, 6,10,15,21);


implementation

{$R *.dfm}

{-----------------------------------------------------------------------------}
function F1(x,y,z:LongWord):LongWord;
begin
  Result:= (x and y) or ((not x) and z);
end;

function F2(x,y,z:LongWord):LongWord;
begin
  Result:= (x and z) or (y and (not z));
end;

function F3(x,y,z:LongWord):LongWord;
begin
  Result:= x xor y xor z;
end;

function F4(x,y,z:LongWord):LongWord;
begin
  Result:= y xor (x or (not z));
end;

procedure PrepareText;
var l,j: Int64;
var i: integer;
begin
  l:= Length(KlarText)*8;
  KlarText:= Klartext+ Chr(128);
  repeat
    KlarText:= KlarText+Chr(0);
  until Length(KlarText) mod 64 = 56;

  for i:= 0 to 7 do begin
    j:= l;
    //ShowMessage(IntToStr(j));
    j:= j shl (i*8);
    //ShowMessage(IntToStr(j));
    j:= j shr 56;
    KlarText:= KlarText+Chr(j);
  end;

  {for i:=1 to Length(Klartext) do begin
    ShowMessage('Buchstabe an Stelle ' + IntToStr(i) + ':' + Klartext[i]);
  end;}

end;

procedure HashMD5;
var A,B,C,D,temp,RotWert,FWert: LongWord;
var M: array[0..15] of LongWord;
var TempText,Hash: AnsiString;
var parts,i,j,g: integer;     //Anzahl der 512 bit Stücke im KlarText
begin

  //Variablen auf Standard setzen:
  a0:= StrToInt('$67452301');
  b0:= StrToInt('$EFCDAB89');
  c0:= StrToInt('$98BADCFE');
  d0:= StrToInt('$10325476');

  PrepareText;

  parts:= Length(KlarText) div 64;

  for i:=1 to parts do begin
    TempText:= Copy(KlarText, ((i-1)*64+1), 64);
    for j:= 0 to 15 do begin
      M[j]:=  ( ((Ord(TempText[1])) shl 24) or ((Ord(TempText[2])) shl 16) or
              ((Ord(TempText[3])) shl 8) or (Ord(TempText[4])) );
      Delete(TempText, 1, 4);
    end;

    A:=a0;
    B:=b0;
    C:=c0;
    D:=d0;

    for j:=0 to 63 do begin
      Case j of
        0..15: begin
          g:= i;
          FWert:= F1(B,C,D);
          temp:= D;
          D:= C;
          C:= B;
          RotWert:=   (((A+FWert+K[i]+M[g]) shl s[i])
                      or ((A+FWert+K[i]+M[g]) shr (32-s[i])));
          B:= B+RotWert;
          A:= temp;
        end;

        16..31: begin
          g:= (5*i +1) mod 16;
          FWert:= F2(B,C,D);
          temp:= D;
          D:= C;
          C:= B;
          RotWert:=   (((A+FWert+K[i]+M[g]) shl s[i])
                      or ((A+FWert+K[i]+M[g]) shr (32-s[i])));
          B:= B+RotWert;
          A:= temp;
        end;

        32..47: begin
          g:= (3*i +5) mod 16;
          FWert:= F3(B,C,D);
          temp:= D;
          D:= C;
          C:= B;
          RotWert:=   (((A+FWert+K[i]+M[g]) shl s[i])
                      or ((A+FWert+K[i]+M[g]) shr (32-s[i])));
          B:= B+RotWert;
          A:= temp;
        end;

        48..63: begin
          g:= (7*i) mod 16;
          FWert:= F4(B,C,D);
          temp:= D;
          D:= C;
          C:= B;
          RotWert:=   (((A+FWert+K[i]+M[g]) shl s[i])
                      or ((A+FWert+K[i]+M[g]) shr (32-s[i])));
          B:= B+RotWert;
          A:= temp;
        end;
      end;
    end;
    a0:= a0+A;
    b0:= b0+B;
    c0:= c0+C;
    d0:= d0+D;
  end;


  Hash:= IntToHex(a0,8)+ IntToHex(b0,8)+IntToHex(c0,8)+IntToHex(d0,8);
  Form1.Label1.Caption:= Hash;

end;

{-----------------------------------------------------------------------------}
procedure TForm1.Button1Click(Sender: TObject);
begin
  KlarText:= Edit1.Text;
  HashMD5;
end;

procedure TForm1.FormCreate(Sender: TObject);
var i:integer;
begin
  for i:=0 to 63 do begin
    K[i]:= floor(abs(sin(i+1))* Power(2,32));
  end;
end;

end.

Vielen Dank im vorraus und ich hoffe jemand kann mir helfen.

Lg B3ta

[gammatester]

Dir fehlt das finale Padding/Compression. In Sourcecodes oft MD5_Final genannt (such mal danach).

[B3ta]

Hallo gammatester,

Ich habe jetzt etwas gegoogled und habe zu dem besagtem md5_final nicht wirklich etwas (zumindest für mich verständliches) gefunden. Weder Quelltext noch irgendeine theoreitsche erklärung.

Was genau soll denn in diesem finalen padding geschehen? Kannst du das vielleicht kurz erläutern?

Lg B3ta

[Klaus01]

Hallo,

in der md5.pas ist MD5Final mit drin.

Grüße
Klaus

[himitsu]

Wenn man den Code nicht in Init, Update und Final aufteilt, sondern nur eine Calc-Methode hat, dann gibt es das Final natürlich nicht einzeln.
Dann kann man allerdings auch nur alles auf einmal haschen und nicht Init > Update > Update > ... > Final machen, um stückchenweise zu rechnen.

Grundsätzlich gibt es aber eine Initialisierung (Einrichtug der Startwerte), am Ende eine Finalisierung (abschließende Umformung der errechneten Werte) und zwischendrin die einrechnung der zu haschenden Daten (Bytes).
Auf geteilt oder eben alles zusammen, aber vorhanden muß der Code dennoch sein

[gammatester]

Zitat von B3ta:

Ich habe jetzt etwas gegoogled und habe zu dem besagtem md5_final nicht wirklich etwas (zumindest für mich verständliches) gefunden. Weder Quelltext noch irgendeine theoreitsche erklärung.

Was genau soll denn in diesem finalen padding geschehen? Kannst du das vielleicht kurz erläutern

Sie Dir mal den Wiki-Artikel. Das Padding dient dazu, die Textlänge auf ein Vielfaches von 512 Bit zu bringen:

Zitat:

Zuerst wird eine Eins an die Ausgangsnachricht angehängt. Danach wird die Ausgangsnachricht mit Nullen so aufgefüllt, dass ihre Länge 64 Bits davon entfernt ist, durch 512 teilbar zu sein. Nun wird eine 64-Bit-Zahl, die die Länge der Ausgangsnachricht codiert, angehängt. Die Nachrichtenlänge ist jetzt durch 512 teilbar.

Im Pseudocode ist das der Teil // Vorbereitung der Nachricht 'message':

In der theoretischen Beschreibung vom MD5 wird dieses Padding und das Einfügen der 64-Bit-Textlänge am Anfang gemacht. In der Praxis arbeiten fast alle Implementationen mit der Möglichkeit auch Messages zu hashen, deren Länge bei Start von MD5 nocj nicht bekannt ist (Stichwort Online-Verarbeitung). Wenn die komplette Nachricht verarbeitet ist, werden die 'Vorbereitungsschritte' in einem MD5_Final am Schluß gemacht und der Digest/Fingerabdruck berechnet.

Wie auch immer: Dieses Padding und Anhängen der Länge fehlen bei Dir.

[B3ta]

Hallo Gammatester,

Ich muss dich hier berichtigen: Dieses Vorbereiten des Textes habe ich in meiner Version drin. Das entspricht meiner Prozedur "PrepareText"
Auch wenn die Art und Weise wie ich es bei mir löse vielleicht etwas ungewöhnlich ist. Wenn ich das richtig verstanden habe macht sie genau das was sie soll.
Oder habe ich da vielleicht was falsch gemacht?

Lg B3ta

[B3ta]

Hallo nochmal an alle,

Kann mir denn niemand sagen, wo mein Fehler liegt? Wenn ich euch richtig verstanden habe, dann müsste das Padding doch bei mir der Prozedur "PrepareText" entsprechen, oder nicht?

Lg B3ta

[gammatester]

Ich vermute, daß es nicht nur ein Fehler ist. Leider ist Dein Code ziemlich verwirrend: Angefangen mit der Tatsache, daß mal wieder Strings für Bytearrays misbraucht werden.

Mir ist auf jedenfall noch aufgefallen, daß die Shiftkonstanten s[i] und die Rundenkonstanten K[i] natürlich nicht mit der Blocknummer des Textes indiziert werden sondern mit dem Rundenindex pro Block (also Deinem j)! Wiki verwendet übrigens i für den Rundenindex, warum weichst Du davon ab und nimmst i für die 512-Bit-Blockindex der Nachricht? Wahrscheinlich sind die Bufferbytes dann auch falsch indiziert (also g wohl via j berechnen), wobei diese g-Konstruktion ziemlich undurchsichtig ist.

Ein schneller Hack zeigt, daß dies allerdings nicht der einzige Fehler ist. Wenn Du wirklich das Rad mit nach diesem Pseudocode neu-erfinden willst, empfehle ich Dir die angesprochenen Änderungen zumachen und dann schrittweise mit einer bekannt-richtigen MD5-Implementation zu vergleichen.

[B3ta]

Hallo gammatester,

Danke nochmal für die Antwort!

Ja, wie schon gesagt ist meine Variante, hier weiterhin einen String zu nutzen wohl weder die effizienteste noch beste Variante, allerdings für mich der verständlichste Weg das darzustellen - Ich bin halt nur Amateur

Und du hattest auch Recht, mit dem Index. Da habe ich nicht richtig nachgedacht und meine Indizes anders bezeichnet und dann aber stumpf das "i" aus dem Pseudo-Code abgeschrieben :s

Allerdings hast du Recht damit, dass es nicht nur daran gelegen hat. Zwar komme ich jetzt auf ein anderes Ergebnis als vorher, jedoch immer noch nicht auf mein erwartetes Ergebnis.
Das mit dem vergleichen eines funktionierenden Algorithmus gestaltet sich für mich als schwierig, da ich zB bei dem hier etwas früher gepostetem Beispiel zum MD5 nicht so recht durchsehe und verstehe, wann jetzt genau was passiert.

Aber ich werde mir noch 'ne Lösung einfallen lassen.

Lg B3ta