MD5 Hasher optimieren | 0xf Level 20

Du kannst die Dauer schon deutlich verkürzen, wenn du praktisch einen Baum aufbaust. Beispielliste:

A
B
C

-> Du gehst gerade hin und vergleichst *nacheinander* A+A,A+B,A+C, B+A, B+B, B+C, C+A, C+B, C+C.

Gehen wir von einer Sekunde pro Operation aus sind das [Anzahl Wörter]*[Anzahl Wörter_2] also in dem Beispiel 3*3 = 9 Sekunden. In der von dir geposteten Liste sind 68848 Wörter. Du kannst in Mathemathik auch eine 5 haben, um zu wissen, dass du auf die Weise nur sehr sehr sehr langsam (4740047104 Sekunden) an dein Ziel kommen würdest. Eine Möglichkeit, das ganze sinnvoll zu beschleunigen wäre das ganze in einen Baum zu zerlegen. Oder anders: Du legst dein Script und die Wordlist in einen seperaten Ordner - glaub mir, den brauchst du. Dein Script müsste im Grunde etwa so arbeiten wie ein Mergesort:

Indem du die Liste aufteilst, wird die Last auf einem Prozess verringert. Da AutoIt nicht Multithreading-Fähig ist, bedeutet dies, dass du damit in diesem Fall ein Multithreading erschaffen könntest.

Schritt 1: Unterscheide in deinem Script, ob du mit Parametern gestartet wurdest, oder ohne.
-> Ohne Parameter: Du bist der Chef, du gibst die Anweisungen weiter.
-> Mit Parameter: Du bist prinzipiell der Arbeiter; du hast einen Arbeitsauftrag.

Chef:
Schritt 2:
-> Zerlege die Wörterliste in kleinere Häppchen - z.B. nur 10 Worte in einer Teilliste. Dadurch würden demnach die Wordlisten_1 bis _6885 entstehen.
-> Starte dich selbst für jede Wordlist einmal, und übergebe jedes Mal eine andere Teilliste.

Schritt 3:
-> Du bist fertig und kannst nach Hause fahren. (=Exit)

Arbeiter:
Schritt 2:
-> Lies die Wordlist.txt (die ungekürzte!) und deine eigene Wordliste (die als Parameter übergeben wurde) jeweils in ein Array.

Schritt 3:
-> Vergleiche, ob eines deiner Wörter, kombiniert mit einem der Wörter der Wörterliste den Hash ergibt.

Schritt 4:
-> Hast du ein Ergebnis, gib das Ergebnis in einem anderen Prozess (z.B. Notepad) aus und beende alle Arbeiter.

Bei diesem Vorgehen wird die benötigte Zeit - leider bloß in der Theorie - durch die Anzahl der Prozesse bis maximal zur Anzahl der Wörter in der Liste verkürzt:

[Anzahl der Wörter]*[Anzahl der Wörter]/[Anzahl der Prozesse] also bestenfalls: 68848*68848/68848 = 68848 Operationen/Prozess

Der Rest hängt bloß davon ab, wie viele Operationen dein PC in einer Sekunde schafft... meiner findet bei diesem Vorgehen ein Ergebnis in weniger als 30 Sekunden, was durchaus akzeptabel sein sollte. Also: Ja es ist möglich mit AutoIt. Ist es den Aufwand wert? Eigentlich nicht. Warum ich dir keinen Code hingeworfen habe? Weil es Rätsel sind und es so klingt als wolltest du diese selbst erledigen.

Beste Grüße
Bio

Edit: Am Beispiel von oben noch mal:

Deine Vorgehensweise:

P1: A+A, A+B, A+C, B+A, B+B, B+C, C+A, C+B, C+C

Meine Vorgehensweise:

P1: A+A, A+B, A+C

P2: B+A, B+B, B+C
P3: C+A, C+B, C+C

Beide Vorgehensweisen vergleichen das Selbe. Bloß arbeitet der eine deutlich effizienter, da er die Ressourcen des Gerätes intensiver ausnutzt.

Wenn das 1. Wort ($j Schleife) gleich dem 2. ($i Schleife) ist brauchst du nicht zu hashen.

autoBert: Ist nicht gesagt.

Das Rätsel schließt die Möglichkeit von zwei Mal dem gleichen Wort nicht aus. Und einen ganz anderen Hash ergibt es ja sowieso.

Für mich sind 2 Wörter 2 verschiedene Wörter und nicht 2 mal das gleiche Wort.

Multithreading bzw. im Falle von Autoit Multiprocessing ist sicher die effektivste Optimierungsmassnahme, da die Aufgabe primär CPU limitiert ist und nur so eine 100% Auslastung aller CPU Kerne erreicht werden kann, zumindestens wenn man keinen Single Core Prozessor besitzt.

Allerdings hat der Lösungsansatz von Bioshade noch eine sehr große Schwäche. Die große ungekürzte Wortliste wird von jedem Arbeiterprozess erneut eingelesen. Das wäre aber garnicht nötig wenn man etwas geschickter an die Aufgabe ran geht.

Ich würde das Script von Trojan nutzen, und lediglich die Hashberechnung auslagern.
Die Schleife startet dann den Arbeiterprozess mit den Parametern "gesuchter Hash" und den beiden zu hashenden Worten.
In der Schleife sollte außerdem natürlich eine Bremse eingebaut werden, damit nicht innerhlab von wenigen ms tausende Prozesse gestartet werden.
Stattdessen merkt man sich in einem Array die PIDs der gestarteten Prozesse und legt eine Maximalanzahl der parelellen Hashing Prozesse fest.
Mit processexists wird bei Erreichen des Limits solange geprüft ob die Prozesse noch laufen bis wieder ein Slot frei wird, dann wird der nächste Hashprozess angeworfen, also eine Warteschlange.
Zusätzlich liefern die Hashprozesse eine Rückgabe an das Hauptprogramm (entweder Hash passt für Wort A+B oder Hash passt nicht). Für Interprozesskommunikation gibt es ja jedemenge Möglichkeiten.
Wenn einer der Prozesse erfolgreich war wird die Warteschlange geleert und die Schleife abgebrochen.

So spart man sich das zeitintensive tausenfache Einlesen und Splitten der großen Wortliste in den Arbeiterprozessen.

Zusätzlich kann man dann natürlich noch Autoberts Vorschlag aufgreifen. Angenommen ein Wort kann beliebig oft und mehrmals in der Wortliste vorkommen und grundsätzlich ist es erlaubt, dass zweimal das selbe Wort kombiniert wird, dann macht es evtl. Sinn die Wortliste zuvor auf Mehrfachvorkommen zu prüfen, zu bereinigen und maximal (sofern vom Rätsel überhaupt erlaubt) einmal eine Doppelprüfung pro Mehrfachwort durchführen. Wenn die Wortliste wirklich viele Mehrfachvorkommen enthält kann das die Menge der Hashberechnungen sehr stark reduzieren.

EDIT:

Um den Overhead durch die enorme Anzahl an Prozessaufrufen, Cryptstartup/shutdown, Verwaltung Warteschlange zu minimieren kann man auch den Ansatz von Bioshade nutzen und anstatt einem Wortpaar gleich mehrere Wortpaare sammeln und erst dann an einen Workerprozess übergeben.

Ein worker Aufruf könnte dann z.B. so ausschaun:

worker.exe "gesuchter hash" "$wort[$j]" "$wort[$i],$wort[$i+1],...,$wort[$i+99]"

also beispielhaft 100 Hashberechnungen pro Prozess.

Zitat von Bioshade

meiner findet bei diesem Vorgehen ein Ergebnis in weniger als 30 Sekunden,

Das ist echt erstaunlich.
Im Worst-Case sind es ja dennoch 4.740.047.104 md5-Berechnungen.
Meine Mühle benötigt für eine md5-Berechnung per AutoIt ca. 0.05ms.
Wenn man z.b. 16 Kerne zur Verfügung hat und den Prozessor damit komplett auslasten kann würde es damit immer noch fast 5 Stunden benötigen.

Mir ist daher nicht klar wie du es geschafft hast, das in weniger als 30s zu schaffen.
Geht eigentlich fast nur wenn das zweite Wort ziemlich weit am Anfang der Liste stand und damit ein Quasi-Best-Case eingetreten wäre.

Respekt wenn das so klappt bei dir.
Btw.: Wie ist die Wortkombination von folgendem Hash?: 276b1b9dd4d554b3a2f4fd6cbb6253ac

Zitat von Bioshade

Bei diesem Vorgehen wird die benötigte Zeit - leider bloß in der Theorie - durch die Anzahl der Prozesse bis maximal zur Anzahl der Wörter in der Liste verkürzt:

Wenn die Prozesse am Anschlag arbeiten (und das tun sie hier) bringt es nichts mehr Prozesse zu erzeugen als CPU-Cores (inklusive HT-Cores) zur Verfügung stehen.
Auf einer 8-Kern CPU werden hier 68000 parallele Prozesse nicht schneller arbeiten als 8 - eher noch langsamer.

Die Aufgabenstellung sieht für mich auch eher danach aus, dass man auf Algorithmenebene optimieren soll.
So könnte man z.B. bei der md5-Berechnung anfangen.
Wenn man den hash berechnet beginnt man die Berechnung blockweise von vorn.
da man immer zwei Wörter aneinander hängt ist der Anfang 68.000x der selbe. Dieses Zwischenergebnis brauch man also nicht immer neu berechnen.
In AutoIt macht diese Optimierung des md5-Algorithmus aber keinen wirklichen Sinn, da es in nativen AutoIt immer langsamer sein wird als die Crypt-API.

Meine Umsetzung liegt im Anhang.
Ich bekomme damit zwar auch den Prozessor zu 100% ausgelastet aber von 30s bin ich noch meilenweit entfernt.

Zitat von AspirinJunkie

Meine Umsetzung liegt im Anhang.
Ich bekomme damit zwar auch den Prozessor zu 100% ausgelastet aber von 30s bin ich noch meilenweit entfernt.

Entweder stützt sich dein System auf eine ganz andere Struktur die bei mir nicht gegeben ist, oder aber in dem Script in dem Archiv ist ein Fehler - bei mir geht die Auslastung einmalig auf 10% hoch, anschließend (nach etwa 1.5 Sekunden) werden alle (hier am Platz 4 logische Prozessoren) 4 Childprozesse geschlossen, ohne das eine Lösung erfolgt ist. Es sind bloß 4 leere txt-Dateien erstellt worden.

Gerne teste ich dies zu Hause noch einmal, dort werde ich allerdings die Zeile "#NoTrayIcon" ergänzen, weil es dort bei den 8 physikalischen Kernen zu 16 logischen Kernen (Hyper-Threading) und somit zu 32 Threads kommt - und 33x das Icon des Programms in der Tray zu haben stelle ich mir doch unglaublich nervig vor. Gerne messe ich dir dann auch die Zeit für deinen Hash dort oben und wie lange eine einzelne MD5-Berechnung auf meiner Maschine dauert.

Zitat von AspirinJunkie

Auf einer 8-Kern CPU werden hier 68000 parallele Prozesse nicht schneller arbeiten als 8 - eher noch langsamer.

Das ist nicht korrekt. Jeder Kern hat 2 Threads. Mittels Hyper-Threading wird die Anzahl der logischen Kerne verdoppelt. Bedeutet im Endeffekt, dass der CPU bei den 68000 Prozessen mit HTT stolze 32 Prozesse gleichzeitig bearbeiten kann dann die prozessorspezifische Idle-Time eintritt und schließlich die nächsten 32 Prozesse angeht. Ohne HTT wären es analog hierzu 16 Prozesse.

misterspeed:
Das Erstellen von über 4.624.000.000 Prozessen braucht in der Summe länger, als die Liste ~ 68.000 mal einzulesen. Klar relativiert sich das Ganze, wenn du größere Teilel der Wortliste übergibst, aber ich bin mir nicht sicher, ob dies wirklich einen Geschwindigkeitsvorteil darstellt (Wortliste einmalig in eine Array lesen, Werte des Arrays an Worker übergeben, dort als CMDLine-Array abgreifen, ...), wenn man beispielsweise eine SSD verwendet. Das werde ich wohl zu Hause mal nachmessen - Ergebnisse folgen.

Das sollte so funktionieren.
Kann man auch schnell testen, wenn man eine Kombi ziemlich weit am Anfang auswählt (Der Best-Case des Algorithmus).

Ich würde allerdings die Blockgröße der jeweils abzuarbeitenden Wörter vergrößern.
Ansonsten werden andauernd Prozesse beendet und neue gestartet.
In meinem Skript z.B. siehst du das andere Extrem: Nur genauso viele Prozesse wie es Kerne gibt und diese laufen parallel von Anfang bis Ende durch.
Das hat dann Nachteile wenn die Prozesse unterschiedlich lange benötigen.
Deswegen wäre dein Ansatz schonmal nicht schlecht - nur halt mit bisschen mehr Daten damit nicht soviel für die Prozesserstellung draufgeht.

Zitat von Bioshade

Das ist nicht korrekt. Jeder Kern hat 2 Threads. Mittels Hyper-Threading

Ich hab dort der Einfachheit halber nicht zwischen logischen und physischen Kernen unterschieden da es am Sachverhalt nichts ändert.
68000 parallele Prozesse bleiben Quatsch.

Zitat von Bioshade

weil es dort bei den 8 physikalischen Kernen zu 16 logischen Kernen (Hyper-Threading) und somit zu 32 Threads kommt

Warum sollte es zu 32 Threads kommen?
Es werden dann 16 Prozesse erzeugt (keine Threads...). Mehr würde ja auch keinen Sinn machen.
Aus 8 physischen Kernen werden durch HT 16 logische Kerne.
Heißt mit 16 parallelen Prozessen ist die CPU am Anschlag.
Zwar kann man gerne auch 32 starten - an der Performance wird sich aber nichts wirklich verbessern.

Zitat von Bioshade

Entweder stützt sich dein System auf eine ganz andere Struktur die bei mir nicht gegeben ist, oder aber in dem Script in dem Archiv ist ein Fehler - bei mir geht die Auslastung einmalig auf 10% hoch, anschließend (nach etwa 1.5 Sekunden) werden alle (hier am Platz 4 logische Prozessoren) 4 Childprozesse geschlossen, ohne das eine Lösung erfolgt ist. Es sind bloß 4 leere txt-Dateien erstellt worden.

Wichtig ist, dass alle vorherigen Prozesse davon gekillt werden. Auch die wordlist.txt muss mit im Verzeichnis liegen.
Hab es auf nem i3 und nem Xeon X5675 getestet - beides x64. Hat geklappt.
Hab im Skript aber nicht alle möglichen Fehler abgefangen, besonders im Hinblick auf den shared-memory ist da noch bisschen was offen.
Im Anhang nochmal die kompilierte Version.

Hab es mit deinem Skript getestet (aal und aahs) und bekomme die richtige Lösung.

Darum vergleichst du Paket 1 auch gegen die komplette Liste, nicht nur gegen das Paket...

Paket 1 vergleichst du demnach gegen A B C D E F G H I ... statt nur gegen das Paket selbst.

Ich hab mich nochmal rangesetzt und das Skript oben noch ein bisschen optimiert.
Ich konnte die Hashberechnung jetzt so gestalten, dass erst der der Hash für das erste Wort berechnet wird und dieses Zwischenergebnis für alle Kombinationen dieses Wortes wiederverwendet werden kann.
So vermeidet man die unnötige Mehrfachberechnung.
Das führt dazu, dass die Hashberechnung im Skript nun etwa doppelt so schnell arbeitet als der Einsatz von _Crypt_HashData().

Hab auch mal einen Löser für Python geschrieben:

# -*- coding: utf-8 -*-


import hashlib
from math import floor
from multiprocessing import cpu_count
from concurrent import futures
from numba import autojit
import ctypes
 
N_THREADS = cpu_count()


with open("wordlist.txt") as f:
	a_Words = [x.strip('\n') for x in f.readlines()]


s_MD5_Result = "12333e700e2870758bc7f5203fc6c23d"


@autojit
def _checkArea(searchrange):
	start, end = searchrange

	for word1 in a_Words[start:end]:	
		hasher = hashlib.md5(word1)

		for word2 in a_Words:
			h2 = hasher.copy()
			h2.update(word2)
			if h2.hexdigest() == s_MD5_Result:
				ctypes.windll.user32.MessageBoxA(0, word1 +"\t" + word2, "Fertig", 0)
				return (word1, word2)


	return False


# teilt einen Bereich in n gleichgroße Teile
def chunks(l, n):
	size = len(l)
	blocksize = int(size/n)
	for i in xrange(0, size, blocksize):
		yield i, i+blocksize-1


if __name__ == "__main__":
	with futures.ProcessPoolExecutor(max_workers=N_THREADS) as executor:
		for ret in executor.map(_checkArea, chunks(a_Words, N_THREADS)):
			pass

Der arbeitet natürlich deutlich flotter als die AutoIt-Variante.
Selbst den Worst-Case schafft er auf meinem i3 in 30 Minuten.

Von den angegebenen 30s von bioshade ist aber auch das noch meilenweit entfernt.

@Bioshade
Noch keine 30s Zeit für ne kurze Hashlösung gefunden?

hi AspirinJunkie

ich hab dein neues script (exe) grad getestet,
und bei mir hat es 15-20 sec gedauert, bis die msgbox mit "aal und aahs" kam.
der rechner ist ein amd a6 4 kerne, also kein "besonders" schneller.

// alles klar

Ja die Kombination "aal" und "aahs" ist quasi der Best-Case.
Die beiden Wörter stehen ganz am Anfang einer Liste die der Prozess abarbeiten muss.
Deshalb ist das so schnell.
Steht das erste Wort weit am Ende einer Wortliste eines Prozesses dauert es deutlich länger.

AspirinJunkie:

Die bedeutendere Frage ist, ob ich diese Zeit für dich erübrigen würde. Und diese Frage beantworte ich schlicht mit einem nein. Gerne kannst du dich weiter mit der Funktionsweise von CPUs befassen, da es dir hier offensichtlich noch an Grundlagen fehlt - siehe oben. DeFakto hat dein Script gestern - auch in kompilierter Form - nicht auf dem i5 hier am Arbeitsplatz funktioniert - auch nicht an dem i7 5390K der bei mir verbaut ist. Meinst Du, dass ich dich mehr oder weniger respektiere, bloß weil Du in einem Forum, in dem die Ränge nicht demokratisch bestimmt werden, einen Sonderrang hast und Dich mit Dingen wie shared Memory auszukennen scheinst? Da glaubst Du falsch.

Ich behaupte: AutoIt ist dermaßen lahm, dass das von jedem CPU automatisierte "herumswappen" zwischen den Prozessen durch den Prozessor deutlich schneller ist, als die Schleife in AutoIt abzuarbeiten. Und ja: Der Prozessor schafft das. Ja, der Prozess selbst würde dadurch ausgebremst werden, wenn er wieder die Aufmerksamkeit des Threads benötigt, bevor der CPU mit seiner Rotation einmal durch gekommen ist. Das passiert allerdings sehr sehr sehr selten, da wir hier bereits im Nanosekundenbereich sind. Alleine zum durchlaufen eines einzelnen Elements in der For-Schleife - und das ohne dort irgendwas zu berechnen - benötigt AutoIt bereits 0.00000001 Sekunden - 0.00001 ms bzw. 0.01 µs. Oder: 10 ns.

Preisfrage Nummer 1: Was ist ein Thread? Wann wird er genutzt, Wie wird er genutzt?
Preisfrage Nummer 2: Prozential gesehen -> Wie viel Zeit blockiert ein Prozess einen Thread?
Preisfrage Nummer 3: Wie viel Zeit verbringt der Prozessor damit die Rechnung des Prozesses durchzuführen?
Preisfrage Nummer 4: Wie viele Prozesse kann der Prozessor demnach bearbeiten, bevor er anfängt die Prozesse auszubremsen?

Wenn Du diese Fragen recherchiert hast verstehst Du, warum deine Aussagen nicht korrekt sind.

Ok. weiß zwar nicht woher Tonfall weg vom sachlichen hin zum persönlichen auf einmal kommt aber auf sowas gehe ich dann grundsätzlich nicht mehr ein.

Eines aber noch: Oben hast du berichtet die Aufgabe in AutoIt innerhalb von 30s gelöst zu haben.
Bisher hast du aber weder einen Nachweis geliefert noch entsprechenden Code präsentiert der sicherlich sehr viele interessieren würde.
Auch wenn du momentan lieber über andere Sachen schreibst - würdest du das noch nachholen?

Zitat von Bioshade

AspirinJunkie:

Die bedeutendere Frage ist, ob ich diese Zeit für dich erübrigen würde. Und diese Frage beantworte ich schlicht mit einem nein.

Du warst doch derjenige der gestern großspurig verkündet hat, das man es mit deinem Vorgehen in 30 Sekunden auf deinem PC schaffen kann:

Zitat von Bioshade

Der Rest hängt bloß davon ab, wie viele Operationen dein PC in einer Sekunde schafft... meiner findet bei diesem Vorgehen ein Ergebnis in weniger als 30 Sekunden, was durchaus akzeptabel sein sollte. Also: Ja es ist möglich mit AutoIt.

Dann sollstest du auch den Beweis antreten in dem du den geforderten Hash (notfalls per PN an Aspirin Junkie) postest.