[C++] Bit-Operationen auf String

[Bgag]

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

 

[CPoly]

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.

 

[Bgag]

Hallo.

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

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.

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.

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

 

[deepthroat]

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ß

 

[Bgag]

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

Fast richtig. Es geht um MD5.

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

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.

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.

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

 

[Matthias Reitinger]

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.

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

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

 

[Bgag]

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.

 

[Bgag]

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

 

[Matthias Reitinger]

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

 

[Bgag]

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.

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