[A] Der MD5 Algorithmus



  • Inhalt

    • 1 Einleitung

    • 2 Theorie

    • 2.1 Anhängen von zusätzlichen Bits

    • 2.2 Anhängen der Größe

    • 3 Umsetzung

    • 3.1 Pseudocode

    • 3.2 Implementation in C++

    • 4 Quellen

    1 Einleitung

    Dieser Artikel soll einen Einblick in den Message Digest Algorithm 5 (kurz: MD5) liefern.

    MD5 ist ein Algorithmus aus dem Jahr 1991 und wurde von Ronald L. Rivest entwickelt. Es handelt sich hierbei um ein kryptographisches Verfahren, welches aus einer beliebig großen Eingabe einen 128 Bit langen Hash generiert.
    Dabei gilt das Prinzip:
    Gleiche Eingabe -> Gleiche Ausgabe

    Desweiteren ist der MD5-Algorithmus irreversibel, d.h. man kann aus einem MD5-Hash die originalen Daten nicht wiederherstellen.
    Hauptanwendung findet der MD5-Algorithmus in der Integritätskontrolle von Dateien oder Datenpaketen.

    Beispielsweise wird auf Download-Seiten auch häufig der MD5-Hash einer Datei angegeben. Nach dem Herunterladen dieser Datei, kann man nun aus der Geladenen Datei wiederum einen MD5-Hash generieren. Stimmen diese überein, so weiß man, dass es sich um eine unveränderte Kopie des Originals handelt, als dass die Datei in Ordnung ist.

    Mittlerweile gilt der MD5-Algorithmus allerdings als unsicher, da es Chinesen gelungen ist, durch Analyse gezielt Kollisionen im Algorithmus zu finden. Diese setzen allerdings voraus, dass man sowohl das Original als auch dessen Hash kennt, um eine Kollision mit dem gleichen Hash zu finden. Somit sind als MD5-Hash gespeicherte Passwörter immer noch als relativ sicher einzustufen.

    2 Theorie

    Dieser Abschnitt wird in Worten erläutern, wie man einen MD5-Hash generiert. Es wird also nicht erklärt, auf welchen Überlegungen der MD5-Algorithmus aufgebaut ist.

    Zunächst zu den Einheiten:

    1 Bit = Die kleinste Einheit am PC, sie kann nur die Werte 1 und 0 annehmen.
    1 Byte = 8 Bit -> Durch das Hintereinanderschalten von 8 Bits erhält man einen Wertebereich von 0 bis 28-1 = 255.
    1 Word = 2 Byte (16 Bit)
    1 DWord = 4 Byte (32 Bit)
    1 QWord = 8 Byte (64 Bit)

    In der Beschreibung des MD5-Algorithmus wird überwiegend in Bits gerechnet, allerdings ist es für die spätere Implementation von Nutzen, wenn man auch die anderen Einheiten kennt, da C++ keinen Datentyp für einzelne Bits zur Verfügung stellt.

    2.1 Anhängen von zusätzlichen Bits

    Es wird von einem Paket an Daten ausgegangen, welches als Eingabe für den Algorithmus dient.
    Die kleinste Speichereinheit am PC ist ein Byte! also kann man davon ausgehen, dass diese Paket eine durch 8 teilbare Anzahl von Bits enthält.

    Die Länge/Größe des Paket erechnet sich also so:
    Länge = (Länge_in_Bytes) * 8

    An dieses Paket wird nun zunächst 1 Bit mit dem Wert 1 angehängt.
    Das Paket, welches nach Abschnitt 2.1 besteht, muss eine Länge haben, welche 64 Bits davon entfernt ist, durch 512 entfernt zu sein.
    Also kurz, die Endgröße für diesen Abschnitt hat diesen Aufbau:
    Endlänge = (n * 512) + 448

    n ist hier ein Platzhalter und kann bei kleinen Paketen auch 0 sein, dann würde das Datenpaket nur bis zu einer Größe von 448 Bits verlängert.

    Um nun zu dieser Größe zu gelangen, werden nun nach der bereits angehängten 1 so viele 0en angehängt, bis die Bedingen für die Endlänge erfüllt ist.

    2.2 Anhängen der Größe

    An das Paket, welches Abschnitt 2.1 verlassen hat, wird nun noch die ursprüngliche Länge in Bits angehängt. Diese wird in Form eines 64 Bit Wertes angehängt, was auch die seltsame Paketlänge erklärt.
    Nach Anhängen dieses Wertes ist die neue Länge des Paketes nämlich genau durch 512 teilbar.

    Achtung: In einer 64-Bit Variable kann ein maximaler Wert von 264-1 = 18.446.744.073.709.551.616 gespeichert werden.
    Das entspricht in etwa einer Paketgröße von 2.147.483.648 GB, was zur heutigen Zeit ausreichend sein sollte.
    Im Falle aber eines größeren Paketes, soll der Länge in einem 128 Bit Wert gespeichert und nur die niederwertigen 64 Bit dieses Wertes angehängt werden.
    Da dieser Fall aber recht unrealistisch ist, werde ich ihn in meiner Implementation nicht berücksichtigen.


Log in to reply