[C++] Bit-Operationen auf String

[deepthroat]

Hi.

	// ... 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ß

 

[Bgag]

Hallo!

Danke für deine Antwort.

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.

	// 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.

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.

Liebe Grüße,

Andreas

 

[Matthias Reitinger]

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.

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:

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

 

[Bgag]

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.

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.

 

[deepthroat]

Hi.

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ß

 

[Bgag]

Hallo!

Vielen Dank für deine Hilfe, euer aller Hilfe. Habe leider nur begrenzt Daumen.

Das Programm läuft nun, auch wenn ich mich gerade noch etwas verrückt gemacht habe, da ich einen anderen Hash aus einer Datei generiert habe, als der oben gepostete MD5-Generator. Allerdings habe ich dann meinen Hash mit der Ausgabe des unter XUbuntu automatisch verfügbaren Programms md5sum verglichen und das hat das gleiche Resultat geliefert.

Das Programm unterstützt nun die Verarbeitung von Dateien unter angabe des Dateipfades, von Strings, die mit -s, Testfällen und Zeit-Tests, die mit -x und -t angegeben werden können. Die Befehle können natürlich auch wild hintereinander geschrieben werden.

Beispiele:

./md5 -x
./md5 ~/Videos/myvideo.avi
./md5 -t ~/Videos/myvideo.avi
./md5 -s "The quick brown fox jumps over the lazy dog"
./md5 -t -s "Bli Bla Blubb" ~/Videos/vid1.avi -t ~/Videos/vid2.avi -x

Das komplette Programm findet man nochmal im Anhang.

Liebe Grüße

Andreas

PS: Das Programm konnte den Hash einer 704MB großen *.avi Datei in nur 3.64 Sekunden bilden.

PSS: Komischer Weise gab es im übrigen Probleme, wenn ich Dateien mit dem C++ ifstream anstatt des C FILE-Handles gelesen habe. Welchen Grund könnte das haben?

EDIT: Er frisst zwar vieles, jedoch hat er bei großen Dateien Probleme. Woran kann das liegen.

 

[sheel]

Was sind große Dateien? >2GB?

 

[Bgag]

Nein leider nicht. Nach der Umstellung auf C-FILE Handles kann ich schon Dateien von 700 mb nicht mehr verarbeiten.

 

[Matthias Reitinger]

Kein Wunder, du liest die Dateien schließlich ohne guten Grund komplett in den Speicher ein. Du solltest eine Methode anbieten, die es erlaubt, eine Zeichenkette Stück für Stück an deine Klasse zu übergeben. Diese sollte den den Hashwert dann inkrementell berechnen.

Grüße,
Matthias

 

[Bgag]

Ich habe nun das Programm so abgeändert, dass Strings und Dateien unterschiedlich behandelt werden. Es kommt nun auch zu einer Blockweisen Verarbeitung, an deren Ende erst das Padding vorgenommen wird.

Dank dieser Änderungen funktioniert nun auch die Verarbeitung beliebig großer Dateien ohne Probleme.

Vielen Dank an alle Helfer. Die neueste Version habe ich angehängt.

Liebe Grüße

Andreas