MD5 Hash bilden und abgleichen

[PrinceMaisle]

Hallo,

ich suche nach einer Lösung die Ausführungszeit zu beschleunigen oder die Performance aus meiner Schleife zu erhöhen. Folgendes Szenario:

Eine Datei mit Wörtern wird ausgelesen. Alle Wörter werden miteinander kombiniert und ein md5 Hash gebildet. Dieser wird mit einem festen md5 abgeglichen. Ein Treffer soll das ganze beenden und die beiden Wörter anzeigen, welche für den Treffer benötigt wurden.

$baselist = file("baselist.txt");
for($word1=0;$word1 < count($baselist); $word1++){
    for($word2=0;$word2 < count($baselist); $word2++){
        $result = md5($baselist[$word1].$baselist[$word2]);
        if($result == '7d5e051c603636bbd8b45c9d59ba0ff4') {
            echo "Treffer<br>";
            echo $baselist[$word1]."-".$baselist[$word2];
            
            exit;
        }
         echo $baselist[$word1]."-".$baselist[$word2];
    }
}

Je mehr Wörter in der Basisdatei vorhanden sind, umso länger braucht es jedoch. Da ich keinen Teffer erreichen kann, wenn so etwa 68.000 Wörter in der Datei vorhanden sind, bricht das Script wohl irgendwann ab. Wie bekomme ich das schneller abgearbeitet?

[MudGuard]

Hi,

ich suche nach einer Lösung die Ausführungszeit zu beschleunigen oder die Performance aus meiner Schleife zu erhöhen. Folgendes Szenario:

Eine Datei mit Wörtern wird ausgelesen. Alle Wörter werden miteinander kombiniert und ein md5 Hash gebildet. Dieser wird mit einem festen md5 abgeglichen. Ein Treffer soll das ganze beenden und die beiden Wörter anzeigen, welche für den Treffer benötigt wurden.

Einmalig für alle Kombinationen den Hash berechnen und die Zuordnung speichern.

Aber das willst Du vermutlich nicht …

for($word1=0;$word1 < count($baselist); $word1++){
    for($word2=0;$word2 < count($baselist); $word2++){

Mikro-Optimierung: den Wert count($basisliste) einmalig ermitteln, nicht bei jedem Schleifendurchlauf (wenn sich die Liste ändern würde, wäre ne for-Schleife vermutlich eh nicht das richtige).

Ansonsten: schnellere Hardware, mehr Speicher …

cu,
Andreas a/k/a MudGuard

[PrinceMaisle]

Hi,

Einmalig für alle Kombinationen den Hash berechnen und die Zuordnung speichern.

Aber das willst Du vermutlich nicht …

Eigentlich nicht, aber jetzt wo du es sagst, käme ich zumindest auf diesem Weg zu meinem Treffer. Das ist der Weg.

Mikro-Optimierung: den Wert count($basisliste) einmalig ermitteln, nicht bei jedem Schleifendurchlauf (wenn sich die Liste ändern würde, wäre ne for-Schleife vermutlich eh nicht das richtige).

Stimmt, jedes bisschen zählt, nicht nur bei der Energie.

Ansonsten: schnellere Hardware, mehr Speicher …

Ja, Tim Allen wäre auf jeden Fall dabei, aber ich versuche mehr Power immer erst als letzte Lösung

[Rolf B]

Hallo PrinceMaisle,

Eigentlich nicht, aber jetzt wo du es sagst, käme ich zumindest auf diesem Weg zu meinem Treffer. Das ist der Weg.

Ist es denn so, dass Du diese Nummer für mehr als einen Hash laufen lassen musst? Die Vorausberechnung lohnt sich nur dann.

Du musst auch bedenken, dass bei 68000 Wörtern die bescheidene Anzahl von 4624000000 Hashes zu speichern ist (in Worten: Viereinhalb Milliarden). Pro Hash sind das 32 Bytes, wenn Du die Hex-Form wählst, oder 16 Bytes, wenn Du die Binärform verwendest. Wir reden also von 74 oder 148 Gigabytes an Nettodaten. Hinzu kommen ggf. noch 6 Bytes pro Eintrag, um zwei Wortnummern dabei zu speichern (muss man nicht tun, man kann auch aus der Fundposition in der Liste die Wortnummern rückrechnen).

Das ist ein ziemliches Datenmonster.

Was nicht funktioniert, ist, zunächst aus den Einzelwörtern die Hashes zu bestimmen und diese zu speichern. Der MD5 Algorithmus ist nicht so simpel, dass man aus MD5(wort1) und MD5(wort2) auf einfache Weise den MD5 Hash von (wort1+wort2) bestimmen könnte.

Rolf

[PrinceMaisle]

Du musst auch bedenken, dass bei 68000 Wörtern die bescheidene Anzahl von 4624000000 Hashes zu speichern ist (in Worten: Viereinhalb Milliarden). Pro Hash sind das 32 Bytes, wenn Du die Hex-Form wählst, oder 16 Bytes, wenn Du die Binärform verwendest. Wir reden also von 74 oder 148 Gigabytes an Nettodaten. Hinzu kommen ggf. noch 6 Bytes pro Eintrag, um zwei Wortnummern dabei zu speichern (muss man nicht tun, man kann auch aus der Fundposition in der Liste die Wortnummern rückrechnen).

Das ist ein ziemliches Datenmonster.

Ahhhhhhhhhhh. Quantenrechner nötig. Irgendwie vergeht mir grade die Lust daran. Hab ich wohl ziemlich unterschätzt. Danke fürs Abholen. Bin gut in der Realität angekommen. Werde das mal lassen. Das übersteigt einfach meine Möglichkeiten.

[Rolf B]

Hallo PrinceMaisle,

ein kartesisches Produkt einer Tabelle mit sich selbst wächst nun mal quadratisch mit der Anzahl der Einträge in der Tabelle.

Es scheint, als wolltest Du im brute force Verfahren irgendeine Kombination von zwei Wörtern erraten, von denen Du nur den Hash kennst.

Ich sehe da ebenfalls keinen Optimierungsansatz außer

• flottere Hardware
• Aufteilen der Aufgabe auf N Prozesse, von denen jeder 1/N der Wörter mit der kompletten Wörterliste kombiniert. Das steuerst Du über die Start- und Endwerte einer der beiden Schleifen. Bei 100 Wörtern und 5 Prozessen würde bspw. die äußere Schleife im Prozess 1 von 0-19 laufen, im Prozess 2 von 20-29, ... im Prozess 5 von 80-99.

count($baselist) in eine Variable zu legen bringt minimal etwas, diese Funktion zählt nicht wirklich sondern fragt ein internes Attribut des Array-Objekts ab.

FALLS die Kombination eines Wortes mit sich selbst außer Frage steht, könntest Du vor dem Bilden des Hashes noch prüfen, ob $wort1 != $wort2 ist und Dir das Hashen ersparen.

Aber Du kommst mit all dem nicht drumherum, dass der Vorgang quadratische Komplexität hat.

Das Script bricht aber nur dann ab, wenn es auf einem Webserver läuft. Führst Du es lokal auf deinem eigenen PC aus, gibt es keine Laufzeitbegrenzung (oder Du kannst sie in der php.ini entfernen).

Wenn Du auf einen Webserver angewiesen bist, kannst Du Zeitscheiben bilden, analog zu der "N Prozesse" Idee. Du übergibst dem Script per Parameter, welchen Ausschnitt der Wortliste die äußere Schleife abfahren soll. Wenn Du 100000 Wörter hast und die äußere Schleife pro Durchlauf immer nur 20 Wörter packt, na gut, dann rufst Du das Ding halt 5000 mal mit entsprechenden Parametern auf. Je nach Power des Webservers musst Du noch dafür sorgen, dass nicht zu viele Aufrufe parallel erfolgen.

Auf einem Web bei einem Shared Hoster würde ich das aber lassen, denn der dürfte Dir dann recht zügig die Leistung drosseln oder Dich rausschmeißen.

Es ist aber kein Problem, ein Kommandozeilen-PHP auf einem Windows- oder Linux PC zum Laufen zu bringen. Auf einem Raspi sollte man das aber nicht probieren - nicht weil der kein PHP lernen könnte, sondern weil der für den Job zu lahm ist.

Rolf

[PrinceMaisle]

Hallo PrinceMaisle,

ein kartesisches Produkt einer Tabelle mit sich selbst wächst nun mal quadratisch mit der Anzahl der Einträge in der Tabelle.

Merke ich auch gerade. Mit 5000 Wörtern bekomme ich 25 Mio. Ergebnisse. Hochgerechnet auf die 68.000 Wörter kommen da am Ende 350 Mio. Ergebnisse.

Es scheint, als wolltest Du im brute force Verfahren irgendeine Kombination von zwei Wörtern erraten, von denen Du nur den Hash kennst.

Ja. Genau so ist es. Aber nicht, weil ich mich in Sony hacken will.

Bisschen Knobeln auf 0xf.at

Ich sehe da ebenfalls keinen Optimierungsansatz außer

• flottere Hardware
• Aufteilen der Aufgabe auf N Prozesse, von denen jeder 1/N der Wörter mit der kompletten Wörterliste kombiniert. Das steuerst Du über die Start- und Endwerte einer der beiden Schleifen. Bei 100 Wörtern und 5 Prozessen würde bspw. die äußere Schleife im Prozess 1 von 0-19 laufen, im Prozess 2 von 20-29, ... im Prozess 5 von 80-99.

Ich merke schon, mal eben ist eine solche "Operation" nicht gemacht. Und einen Grund muss es ja geben, wieso Hardware immer besser werden muss. Aber immerhin hab ich nun ein paar Ansätze.

[Rolf B]

Hallo PrinceMaisle,

https://0xf.at/play/20

Damn. Wieso musstest Du das tun?

Looking for Thinking Cap

Hab mich erstmal mit Nr. 13 aufgewärmt 😉

Rolf

[Rolf B]

Hallo PrinceMaisle,

Level 20 solved!

Ich habe im Prinzip deinen Algorithmus verwendet, aber das Script parametriert, so dass ich ein Intervall für die äußere Schleife vorgeben kann. Damit kann ich die Aufgabe nach Belieben partitionieren.

Ich habe einen Ryzen 5 mit 6 Kernen und Hyperthreading, d.h. ich habe 12 Prozesse gestartet, mit je 6000 Wörtern. Der letzte war dann etwas unterbeschäftigt... Jeder Teilprozess lief 102s. Weniger Prozesse führen zu längerer Gesamtlaufzeit.

102 Sekunden ist für einen Webserver natürlich zu viel, da muss man dann auf 2000 Wörter heruntergehen oder noch weniger, je nach Serverperformance.

Wichtig ist: file() liefert Dir das Zeilenendezeichen mit, bevor Du die Suchschleife startest, musst Du also erstmal über die Wörtertabelle laufen und sie trimmen.

Du schaffst das!

Rolf

[tk]

Moin,

Wichtig ist: file() liefert Dir das Zeilenendezeichen mit, bevor Du die Suchschleife startest, musst Du also erstmal über die Wörtertabelle laufen und sie trimmen.

… oder FILE_IGNORE_NEW_LINES als zweiten Parameter für file() verwenden.

Gruß
Tobias

[Rolf B]

Hallo tk,

ups 😉 - PHP ist nunmal nicht meine Muttersprache.

Aber immerhin hab ich die Levels 1-21 von 0xf.at durch und deutlich unter par gelöst. Die übrigen sehen so aus, als bräuchte ich dafür eeetwas mehr Ausgeschlafenheit...

Rolf

[PrinceMailse]

Hallo PrinceMaisle,

https://0xf.at/play/20

Damn. Wieso musstest Du das tun?

Ich hatte ja keine Ahnung. Dachte ich bin der einzige "dummy" der die Finger von Knobelaufgaben einfach nicht lassen kann 😂

[MudGuard]

Hi,

count($baselist) in eine Variable zu legen bringt minimal etwas, diese Funktion zählt nicht wirklich sondern fragt ein internes Attribut des Array-Objekts ab.

Darum schrieb ich ja auch Mikrooptimierung. Gespart wird aber der Aufruf an sich (inkl. Stack Space anlegen usw.). Ist nicht viel, aber doch etwas. Und bei 68K² =~ 4,6 Milliarden Aufrufen kommt dann doch in Summe was zusammen.

cu,
Andreas a/k/a MudGuard

[Der Martin]

Hallo,

count($baselist) in eine Variable zu legen bringt minimal etwas, diese Funktion zählt nicht wirklich sondern fragt ein internes Attribut des Array-Objekts ab.

Darum schrieb ich ja auch Mikrooptimierung. Gespart wird aber der Aufruf an sich (inkl. Stack Space anlegen usw.). Ist nicht viel, aber doch etwas.

korrekt, aber ...

Und bei 68K² =~ 4,6 Milliarden Aufrufen kommt dann doch in Summe was zusammen.

... macht es in der Praxis einen Unterschied, ob das Script 215 Tage läuft oder nur 213?

Einen schönen Tag noch
 Martin

[Raketenwilli]

Wenn schon optimieren dann:

#1.:
define ( 'BIN', hex2bin( '7d5e051c603636bbd8b45c9d59ba0ff4' ) );
foreach ( $baselist as $w1 ) {
     foreach ( $baselist as $w2 ) {
         #2.:
         if ( BIN === md5( $w1 . $w2, true ) ) {
             echo "$w1 $w2";
             exit;
         }
     }
}

Gezeigte Optimierungen:

1. Der Job, aus dem binärem Ergebnis von md5() noch die hexadezimale Präsentation zu erstellen, kostet Zeit. Also einmalig die vorliegende hexadezimale Präsentation des Hashes in eine binäre umwandeln und nur die binäre Form des Hashes ermitteln.

2. Der typstrenge Vergleich versucht nicht noch eine Gleichheit via Umwandlung des Inhalts vorzunehmen.

Nicht gezeigt:

Dann sollte man das ganze auf so viele Jobs aufteilen, wie man Prozessorkerne (oder Threads, falls man die im BIOS nicht abstellt, was bei der Aufgabe aber angemessen wäre) - hat. Dazu wäre wäre für jeden Job eine partielle Wortliste zu erzeugen, die in den foreach-Schleifen aber mit der vollständigen Liste kombiniert wird.

Ferner sollten bei einem Treffer dann alle übrigen Jobs abgebrochen werden. Da PHP-Skripte die eigene PID kennen müsste diese dazu in eine Datei weggeschrieben werden und nach dem echo via Systembefehl (kill, pkill e.t.c. ) die Prozesse beendet werden.

Was mir noch einfällt: Eigentlich sieht das aus wie ein Job für Grafikkarte. Wer macht sowas in PHP?

[Rolf B]

Hallo Raketenwilli,

Wer macht sowas in PHP?

Ich 😉

Und in unter 2 Minuten Rechenzeit auf einem normalen modernen Hobel ist das wohl akzepabel.

Ich habe mir deine Optimierungsvorschläge mal angeschaut. Zum testen habe ich mein PHP Script bei Wort 65000 starten lassen, der Treffer ist bei 67504. Die Parallelscripte habe ich weggelassen. Damit ergeben sich Testlaufzeiten von etwas über 10s.

• md5 mit false aufrufen und hex via == vergleichen: 14,3s
• md5 mit false aufrufen und hex via === vergleichen: 13,1s
• md5 mit true aufrufen und binär via == vergleichen: 12,9s
• md5 mit true aufrufen und binär via === vergleichen: 12,3s

Da ist also Potenzial für ca 14% Laufzeitersparnis.

Die Abfrage auf erfolgreichere Parallelprozesse habe ich so gelöst, dass der Finder eine "found.txt" schreibt und die übrigen abbrechen, sobald sie diese Datei finden. Das tun sie nicht in jedem Durchlauf für Wort 1, sondern nur alle 200 Worte, sonst verliert man gleich wieder anderthalb Prozent (also fast nix 😉).

Was deutlich Wirkung hat, ist die PHP Version. Mit PHP 7.4 dauert die Nummer fast 2s länger, und ein historisches PHP 5.6, das ich hier noch im Museum habe, brauchte doppelt so lange. Der opcache.jit bringt ebenfalls ca 2s Laufzeitgewinn.

Was eher nichts bringt, ist foreach statt for($j=0; ...) als Schleifensteuerung. Ich hatte zuerst for ($j=0; ...) drin und habe es auf foreach umgestellt, das war unterhalb der Messschwelle.

Wirkung hat auch der Einsatz von SPLFixedArray. Es ist ein paar Prozent langsamer 😉. Ich müsste jetzt noch schauen, wie sich die Sache unter C# mit .net verhält, glaube aber, dass es nicht viel sein kann. Die Implementierung der MD5 Funktion dürfte der kritische Pfad sein.

Rolf

[Raketenwilli]

Ich habe die originale Wortliste genommen und auf 10.000 Array-Einträge verkürzt. Letztes Wort ist dann 'bevy'. Nach dem (doppelt) suche ich auch:

<?php 

### Vorbereitung
/*
$baselist = array_slice( file( 'wordlist.txt', FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES ) , 0 , 10000 );
echo count($baselist) . ' Elemente,' .PHP_EOL;
file_put_contents( 'array.serialized', serialize( $baselist ) );
exit;
#*/

$baselist = unserialize( file_get_contents( 'array.serialized' ) );

define ( 'BIN', md5( 'bevybevy', true ) );
foreach ( $baselist as $w1 ) {
     foreach ( $baselist as $w2 ) {
         #2.:
         if ( BIN === md5( $w1 . $w2, true ) ) {
             echo "$w1 $w2";
             exit;
         }
     }
}

Auf dem „Raspberry Pi 4 Model B Rev 1.5“ mit 8GB, frisiert auf 1,8 GHz:

~/tmp$ time php test.php 
bevy bevy
real	0m49,090s
user	0m48,805s
sys	0m0,105s

Für 100.000.000 (100 Mio) mal „Hash bauen und vergleichen“ ist das gar nicht schlecht. Mit der hexadezimalen Ausgabe von md5() und den nicht typstrengen Vergleichen ( == statt === ) ist das bei mir sogar 10 Sekunden langsamer.

PHP-Version ist 8.2.