Hallo!

Ich beschäftige mich aktuell mit einem Algorithmus, der es erforderlich macht, an einen String ein einzelnes "1" Bit anzuhängen und dann den String durch anhängen von "0" Bits auf Länge Kongruent 448, modulo 512 zu bringen. Dies soll auch geschehen, falls der String schon eine Länge von 448 Bit (modulo 512) hat.

Anschließend soll die Länge des Strings als 64 Bit Zahl an den String angehängt werden, sodass die resultierende Länge des Strings nun ein vielfaches von 512 ist. Sollte die Länge größer als 64 Bit sein, sollen nur die 64 niederwertigen Bits angehängt werden.

Würde mich freuen, wenn mir jemand sagen könnte, wie ich eine solche Methode implementieren kann.

Liebe Grüße,

Andreas

Erstmal hab ich Fragen zu deinem Problem:

1. C (char *) oder C++ (std:string) ?
Edit: Hab jetzt erst den Titel gesehen.

2. Du redest von "Bits anhängen", aber die kleinste Einheit ist ein Byte. Soll der String also eine Länge (Anzahl der Zeichen) haben, welche durch 512 einen Rest von 448 ergibt? Oder soll die Länge geteilt durch 64 einen Rest von 56 ergeben?
3. Wie zum Teufel soll die Länge eines Strings nicht mehr in einen 64 Bit unsigned integer passen? Das wären 128 Exabyte, sofern ich mich nicht verrechnet habe.

Ansonsten: Wo hängts denn? Ein string ist ein char-Array. Ein char hat 8 bit, ist also genau ein byte. In C kannst du mit char rechnen wie mit Zahlen, also sollte das doch alles kein Problem sein.

Hallo.

Danke erstmal für deine schnelle Antwort. Habe nachfolgend mal versucht deine Fragen zu beantworten.

Zitat von CPoly

C (char *) oder C++ (std:string) ?

Es ist eigentlich egal, da ich mit einem C++ std::string arbeite und so mit der Methode c_str() auf das Char Array zugreifen kann.

Zitat von CPoly

Du redest von "Bits anhängen", aber die kleinste Einheit ist ein Byte. Soll der String also eine Länge (Anzahl der Zeichen) haben, welche durch 512 einen Rest von 448 ergibt? Oder soll die Länge geteilt durch 64 einen Rest von 56 ergeben?

Genau das Problem hatte ich auch. Es sollen allerdings tatsächlich Bits angehängt werden. Nachfolgend ein kleiner Ausschnitt aus dem entsprechenden RFC.

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.

3.2 Step 2. Append Length


A 64-bit representation of b (the length of the message before the
padding bits were added) is appended to the result of the previous
step. In the unlikely event that b is greater than 2^64, then only
the low-order 64 bits of b are used. (These bits are appended as two
32-bit words and appended low-order word first in accordance with the
previous conventions.)

At this point the resulting message (after padding with bits and with
b) has a length that is an exact multiple of 512 bits. Equivalently,
this message has a length that is an exact multiple of 16 (32-bit)
words. Let M[0 ... N-1] denote the words of the resulting message,
where N is a multiple of 16.

Zitat von CPoly

Wie zum Teufel soll die Länge eines Strings nicht mehr in einen 64 Bit unsigned integer passen? Das wären 128 Exabyte, sofern ich mich nicht verrechnet habe.

Ich weiß auch, dass das eigentlich nicht vorkommen sollte, aber der Algorithmus sieht es, wie du oben sehen konntest, so vor.

Liebe Grüße,

Andreas

Hi.

Warum sagst du denn nicht gleich, das es um den MD4 Algorithmus geht?

Und wie kommst du auf String? Die Rede ist von einer Nachricht, also einer Bitfolge. Die Verarbeitung erfolgt wortweise (16Bit).

Das was der Abschnitt aus dem RFC sagt, ist lediglich, dass du die Nachricht so ausrichten mußt, dass die Länge der Nachricht am Ende ein Vielfaches von 512 ist. Das muß man aber nicht wirklich so machen. Verarbeite einfach alle Daten und zum Schluss erzeuge die Padding Daten (so muß man die Nachricht nicht doppelt lesen falls die Größe nicht durch andere Funktionen ermittelt werden kann).

Man findet mit Sicherheit auch Implementierungen von MD4 im Netz...

Gruß

Zitat von deepthroat

Warum sagst du denn nicht gleich, das es um den MD4 Algorithmus geht?

Fast richtig. Es geht um MD5.

Zitat von deepthroat

Und wie kommst du auf String? Die Rede ist von einer Nachricht, also einer Bitfolge. Die Verarbeitung erfolgt wortweise (16Bit).

Zitat von deepthroat

Das was der Abschnitt aus dem RFC sagt, ist lediglich, dass du die Nachricht so ausrichten mußt, dass die Länge der Nachricht am Ende ein Vielfaches von 512 ist. Das muß man aber nicht wirklich so machen. Verarbeite einfach alle Daten und zum Schluss erzeuge die Padding Daten (so muß man die Nachricht nicht doppelt lesen falls die Größe nicht durch andere Funktionen ermittelt werden kann).

Das kann ich leider nicht ganz nachvollziehen. Die Padding Daten müssen doch zu Anfang erzeugt werden, sodass die nachfolgenden Transformationen überhaupt ausgeführt werden können.

Zitat von deepthroat

Man findet mit Sicherheit auch Implementierungen von MD4 im Netz...

Natürlich findet man im Netz auch Implementationen in C/C++, sogar Massenweise, darunter vorallem sehr umständliche, falsche und schlecht dokumentierte. Sogar das RFC 1312 selbst enthält eine Implementierung in C. Leider komme ich um eine eigene Implementation nicht rum. Sie ist Teil eines Fach-Praktikums.

Wenn ich es nun richtig verstanden habe, muss ich meinen String in ein Byte Array umwandeln.

Code cpp:

1	unsigned char *buffer = input.c_str();

Danach kann ich nun das Anfügen und das Anpassen der Größe vornehmen. Aber wie mache ich das?

Später operiere ich dann ja auf einem Array von 64 Bytes, also 512 Bits.

Liebe Grüße,

Andreas

Zitat von Avedo

Das kann ich leider nicht ganz nachvollziehen. Die Padding Daten müssen doch zu Anfang erzeugt werden, sodass die nachfolgenden Transformationen überhaupt ausgeführt werden können.

Ich hab den MD5-Algorithmus jetzt nicht exakt im Kopf, aber soweit ich mich erinnere, muss man den String doch nur einmal durchlaufen, oder nicht? Dann reicht es doch, wenn du die Padding-Bits „on demand“ generierst, nämlich genau dann wenn du am Ende des Strings angekommen bist.

Zitat von Avedo

Wenn ich es nun richtig verstanden habe, muss ich meinen String in ein Byte Array umwandeln.

Code cpp:

1	unsigned char *buffer = input.c_str();

Danach kann ich nun das Anfügen und das Anpassen der Größe vornehmen. Aber wie mache ich das?

Musst du nicht unbedingt. Du kannst über string::append Zeichen an den String anhängen (zuerst '\x80' und dann so oft '\0' bis du bei einem Vielfachen von 56 Zeichen in der Gesamtlänge angekommen bist).

Grüße,
Matthias

Guten Abend!

Habe nochmal versucht das Programm zum Laufen zu bringen. Dabei bin ich ein ganzes Stück weiter gekommen und ich glaube nun auch einiges verstanden zu haben.

Leider geht zur Zeit irgendwo, aus mir nicht ganz erklärlichen Gründen, noch etwas in die Hose. Ich befürchte, dass noch etwas bei der Umrechnung von uint64 in einen Binär-String fehlschlägt. Der betreffende Abschnitt findet sich, zusammen mit der Anpassung der Länge des Strings, in der Methode preprocess().

Wäre super, wenn jemand mal einen Blick auf die Klasse werfen könnte. Habe das komplette Programm als *.zip-Archiv in den Anhang gepackt. Ein Minimal-Beispiel und ein Makefile zur einfacheren Kompilierung liegt ebenfalls bei.

Liebe Grüße,

Andreas

PS: Das Resultat der Ausführung des Beispiels sollte "9e107d9d372bb6826bd81d3542a419d6" sein.

Guten Morgen!

Habe gestern und heute noch etwas an meinem Programm gearbeitet und noch ein paar Fehler behoben. Leider wird immer noch nicht der richtige Hash-Code erzeugt. Woran das liegt, weiß ich leider nicht. Ich bin den Algorithmus eigentlich noch einmal Schritt für Schritt durchgegangen.

Wäre super, wenn jemand von euch noch einmal drauf schaun könnte. Die neue Version habe ich am Ende angehängt.

Liebe Grüße,

Andreas

Hallo,

ich sehe da einige potenzielle Probleme mit deiner Implementierung. Zuerst mal deine typedefs — auf einem 64-Bit-System könntest du damit Probleme kriegen. Dein uint32 hat bei mir beispielsweise 64 Bits, womit die ganze Modulo-2^32-Arithmetik den Bach runter geht. Du könntest stattdessen die Typen aus cstdint verwenden, falls vorhanden. Bei der Intialisierung von state hast du denke ich die Bytesortierung falsch rum.

Verwende am besten eine Beispielimplementierung, die die Zwischenzustände mit ausgibt, um die Fehler einzugrenzen.

Grüße,
Matthias

Guten Morgen!

Danke für deine Hilfe. Bin ein ganzes Stück weiter gekommen. Habe nun jedoch ein Problem. Lustiger Weise wird der Hash-Code von "The quick brown fox jumps over the lazy dog" korrekt erzeugt. Gebe ich jedoch eine zu verwendende Datei an oder übergebe zum Beispiel "Hallo Welt", so wird ein falscher Hash erzeugt.

Durch das Einfügen einiger Ausgaben und deren Abgleich mit der Ausgabe des von dir oben erwähnten Tools, konnte ich herausfinden, dass der Fehler bereits in der Initialisierung auftritt. Weder die Umwandlung des String ansich noch das Anhängen des einzelnen Bits, das Auffüllen mit Nullen und das Anhängen der String Länge, scheint zu funktionieren.

Es muss also im folgenden Abschnitt etwas Schief laufen.

Code cpp:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

// Get the size of the unpadded message.     uint64 inputLength = input.size() * 8;       // Append a single '1' bit, ...     input.append(1, '\x80');       // ... and then the '0' bit until the string length is congruent to 56 modulo 64.     input.append(56 - (input.size() % 64), '\0');       // Finally append the length of unpadded message as 64-bit little-endian integer to message.     char chLen[8];     chLen[7] = (unsigned char) ((inputLength >> 56) & 0xff);     chLen[6] = (unsigned char) ((inputLength >> 48) & 0xff);     chLen[5] = (unsigned char) ((inputLength >> 40) & 0xff);     chLen[4] = (unsigned char) ((inputLength >> 32) & 0xff);     chLen[3] = (unsigned char) ((inputLength >> 24) & 0xff);     chLen[2] = (unsigned char) ((inputLength >> 16) & 0xff);     chLen[1] = (unsigned char) ((inputLength >> 8) & 0xff);     chLen[0] = (unsigned char) (inputLength & 0xff);     input.append(chLen, 8);       return input;

Im Anhang habe ich auch nochmal die komplette überarbeitete Version angehängt.

Würde mich sehr freun, wenn jemand von euch noch einen Blick darauf werfen könnte.

Liebe Grüße,

Andreas

Hi.

Zitat von Avedo

Code cpp:

1 2	// ... and then the '0' bit until the string length is congruent to 56 modulo 64.     input.append(56 - (input.size() % 64), '\0');

Irgendwas kann hier nicht stimmen. Das Ergebnis von modulo 64 kann 0 bis 63 sein. 56 - 63 = -7.

Zufällig hat "The quick brown fox jumps over the lazy dog" genau die richtige Größe, so das es dann passt.

Wie schon gesagt, ist diese Vorverarbeitung unnötig. Du kopierst die Daten 3fach umher ohne wirklich etwas mit ihnen anzustellen.

Gruß

Hallo!

Danke für deine Antwort.

Zitat von deepthroat

Irgendwas kann hier nicht stimmen. Das Ergebnis von modulo 64 kann 0 bis 63 sein. 56 - 63 = -7.

Das stimmt allerdings. Habe den entsprechenden Part mal wie folgt abgeändert. Das funktioniert auch ganz gut.

Code cpp:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

// Get the size of the unpadded message.     uint64 inputLength = input.size() * 8;       // Append a single '1' bit, ...     input.append(1, '\x80');       // ... calculate the index ...     size_t index = input.size() % 64;       // ... and the padding length ...     size_t padLen = (index < 56) ? (56 - index) : (120 - index);       // ... and then the '0' bit until the string length is congruent to 56 modulo 64.     input.append(padLen, '\0');       // Finally append the length of unpadded message as 64-bit little-endian integer to message.     char chLen[8];     chLen[0] = (unsigned char) (inputLength & 0xff);     chLen[1] = (unsigned char) ((inputLength >> 8) & 0xff);     chLen[2] = (unsigned char) ((inputLength >> 16) & 0xff);     chLen[3] = (unsigned char) ((inputLength >> 24) & 0xff);     chLen[4] = (unsigned char) ((inputLength >> 32) & 0xff);     chLen[5] = (unsigned char) ((inputLength >> 40) & 0xff);     chLen[6] = (unsigned char) ((inputLength >> 48) & 0xff);     chLen[7] = (unsigned char) ((inputLength >> 56) & 0xff);     input.append(chLen, 8);       return input;

Leider bleibt noch ein letztes Problem. Irgendwie geht etwas beim setzen von '\x80' schief. Er trägt mir an dieser Stelle den falschen Wert ein. Hat dazu vielleicht noch jemand eine Idee.

Zitat von deepthroat

Wie schon gesagt, ist diese Vorverarbeitung unnötig. Du kopierst die Daten 3fach umher ohne wirklich etwas mit ihnen anzustellen.

Das mag sein, aber ich habe leider keinen blassen Schimmer, wie ich es aktuell anders lösen sollte. Zu einem Beispiel sage ich natürlich nicht nein. :-P

Liebe Grüße,

Andreas

Zitat von Avedo

Das mag sein, aber ich habe leider keinen blassen Schimmer, wie ich es aktuell anders lösen sollte. Zu einem Beispiel sage ich natürlich nicht nein. :-P

Durchlaufe den Original-String (ohne das Padding) in ganzen 64-Byte-Blöcken. Am Ende bleibt im Allgemeinen noch ein Stück <64 Byte am Ende des Strings übrig. Schreibe dieses an den Anfang von block und fülle den Rest mit dem Padding auf. Führe mit diesem Block jetzt noch eine letzte Runde durch. Du musst aber noch ein paar Fälle unterscheiden, z.B. wenn das Padding nicht mehr in den Block passt (du müsstest dann noch einen weiteren Block generieren).

\edit:

Zitat von Avedo

Leider bleibt noch ein letztes Problem. Irgendwie geht etwas beim setzen von '\x80' schief. Er trägt mir an dieser Stelle den falschen Wert ein. Hat dazu vielleicht noch jemand eine Idee.

Wie hast du das verifiziert?

Grüße,
Matthias

Zitat von Matthias Reitinger

Durchlaufe den Original-String (ohne das Padding) in ganzen 64-Byte-Blöcken. Am Ende bleibt im Allgemeinen noch ein Stück <64 Byte am Ende des Strings übrig. Schreibe dieses an den Anfang von block und fülle den Rest mit dem Padding auf. Führe mit diesem Block jetzt noch eine letzte Runde durch. Du musst aber noch ein paar Fälle unterscheiden, z.B. wenn das Padding nicht mehr in den Block passt (du müsstest dann noch einen weiteren Block generieren).

Vielen Dank für diese Erläuterungen. Werde nun erstmal versuchen meine aktuelle Version zum Laufen zu bekommen. In einer späteren Version versuche ich dann diesen Punkt zu verbessern.

Zitat von Matthias Reitinger

Wie hast du das verifiziert?

Ich habe mir einfach mal alle Blöcke ausgeben lassen. Alle werden richtig erzeugt. Allerdings tritt genau an der Stelle, an der das einzelne Bit eingefügt wird ein Fehler auf.

Ein Beispiel: Möchte ich die Nachricht "Hallo du kleine Welt. Es ist ein schoener Tag" verarbeiten, erhalte ich die folgenden Blöcke.

block[0] = 6c6c6148
block[1] = 7564206f
block[2] = 656c6b20
block[3] = 20656e69
block[4] = 746c6557
block[5] = 7345202e
block[6] = 74736920
block[7] = 6e696520
block[8] = 68637320
block[9] = 656e656f
block[10] = 61542072
block[11] = ffff8067
block[12] = 0
block[13] = 0
block[14] = 168
block[15] = 0

Aussehen sollte es aber wie folgt.

block[0] = 6c6c6148
block[1] = 7564206f
block[2] = 656c6b20
block[3] = 20656e69
block[4] = 746c6557
block[5] = 7345202e
block[6] = 74736920
block[7] = 6e696520
block[8] = 68637320
block[9] = 656e656f
block[10] = 61542072
block[11] = 00008067
block[12] = 00000000
block[13] = 00000000
block[14] = 00000168
block[15] = 00000000

Der Unterschied findet sich in Block 11, an dessen Stelle die Nachricht zu Ende ist und das Bit eingefügt wird. Dort steht bei mir ffff8067 anstatt 00008067, wie es der von dir vorgstellte MD5-Generator tut, der auch den richtigen Hash erzeugt.

Ich habe leider keine Ahnung, woran das liegen kann. Hat jemand von euch dazu eine Idee?

Liebe Grüße

Andreas

EDIT: Habe gerade noch ein paar Tests durchgeführt und es scheint generell noch ein Problem mit dem Padding zu geben. Der Rest ist in Ordnung.

Hi.

Zitat von Avedo

Der Unterschied findet sich in Block 11, an dessen Stelle die Nachricht zu Ende ist und das Bit eingefügt wird. Dort steht bei mir ffff8067 anstatt 00008067, wie es der von dir vorgstellte MD5-Generator tut, der auch den richtigen Hash erzeugt.

Ich habe leider keine Ahnung, woran das liegen kann. Hat jemand von euch dazu eine Idee?

signed / unsigned Problem.

Verwende std::basic_string<unsigned char> und füge 0x80 statt '\x80' hinzu.

Gruß