XOR und Strings

[TroaX]

Moin moin,

ich bräuchte einmal einen kleinen Denkanstoß. Und zwar geht es um folgendes. ICh bin gerade dabei, PBKDF2 in Purebasic zu schreiben. Ich hatte zwar schon eine Version fertig (siehe hier http://forums.purebasic.com/german/view ... p?p=332608 letzter Beitrag). Allerdings ist es nicht 1 zu 1 das selbe. Denn es fehlt noch das XOR bei jeder Iteration. Da ich aber eben 2 Strings mit Hash habe, dessen einzelne Zeichen einen Hex-Wert darstellen (in meinem Beispiel über SHA3 512 Bit), kann ich ja nicht direkt mit dem XOR-Operator arbeiten. PHP interessiert das ja dank typenlosigkeit die Bohne. Aber Purebasic will das verständlicher Weise nicht.

Ich habe schon die Suchfunktion genutzt. Aber da habe ich auch nichts passendes gefunden. Entweder habe ich es versehentlich übersehen oder ich habe vor lauter Code die Lösung nicht gefunden. Ich benötige mal bitte einen Denkanstoß.

Vielen Dank

[NicTheQuick]

Wenn das quasi Hexstrings sind, dann kommst du nicht darum herum diese intern zu konvertieren, zu XOren und wieder zurück zu konvertieren.
Vielleicht so:

Code: Alles auswählen

Procedure.s XOrHexString(a.s, b.s)
	Protected *a.Character = @a, *b.Character = @b
	Protected x.i
	
	If Len(a) <> Len(b)
		ProcedureReturn ""
	EndIf
	
	While *a\c
		*a\c - '0' - Bool(*a\c >= 'A') * ('A' - '0' - 10) - Bool(*a\c >= 'a') * ('a' - 'A')
		*b\c - '0' - Bool(*b\c >= 'A') * ('A' - '0' - 10) - Bool(*b\c >= 'a') * ('a' - 'A')
		*a\c ! *b\c
		*a\c + '0' + Bool(*a\c > 9) * ('a' - '0' - 10)
		
		*a + SizeOf(Character)
		*b + SizeOf(CHaracter)
	Wend
	
	ProcedureReturn a
EndProcedure

Debug XOrHexString("aA3", "aa5")

[Kiffi]

wäre das so nicht etwas einfacher?

Code: Alles auswählen

Debug Val("$aA3") ! Val("$aa5")

Grüße ... Peter

[NicTheQuick]

Nicht, wenn die Strings 64 Zeichen haben.
Aber natürlich könnte man den String in 8-Zeichen-Blöcke zerlegen, Val() darauf anwenden, dann jeweils zwei Longs XORen, und wieder zurück rechnen.
Also so?

Code: Alles auswählen

Procedure.s XOrHexString(a.s, b.s)
	Protected *a.Character = @a, *b.Character = @b
	Protected x.i
	
	If Len(a) <> Len(b)
		ProcedureReturn ""
	EndIf
	
	While *a\c
		*a\c - '0' - Bool(*a\c >= 'A') * ('A' - '0' - 10) - Bool(*a\c >= 'a') * ('a' - 'A')
		*b\c - '0' - Bool(*b\c >= 'A') * ('A' - '0' - 10) - Bool(*b\c >= 'a') * ('a' - 'A')
		*a\c ! *b\c
		*a\c + '0' + Bool(*a\c > 9) * ('a' - '0' - 10)
		
		*a + SizeOf(Character)
		*b + SizeOf(CHaracter)
	Wend
	
	ProcedureReturn a
EndProcedure

Procedure.s XOrHexString2(a.s, b.s)
	Protected i.i = 1, size.i = Len(a), result.s = ""
	
	If size <> Len(b)
		ProcedureReturn ""
	EndIf
	
	While size >= 8
		result + RSet(Hex(Val("$" + Mid(a, i, 8)) ! Val("$" + Mid(b, i, 8)), #PB_Long), 8, "0")
		i + 8
		size - 8
	Wend
	
	While size
		result + Hex(Val("$" + Mid(a, i, 1)) ! Val("$" + Mid(b, i, 1)), #PB_Long)
		i + 1
		size - 1
	Wend
	
	ProcedureReturn result
	
EndProcedure

Debug XOrHexString("123456789", "abcdef019")
Debug XOrHexString2("123456789", "abcdef019")

Kommt mir nur reichlich lahm vor, aber hab auch keine Lust es zu testen.

[TroaX]

Die erste Lösung von NicTheQuick kommt mir da am performantesten vor. Aber ich müsste es einfach mal benchen. Wie im anderen Thread zu sehen kommen die Zeiten ja im Vergleich zur PHP-Implementierung hin, da PHP selbst ja kaum rechnet und die meisten Funktionen ja in den PHP-Libs nativ impelementiert wurden. Aber eine differenz zwischen nativ uns interpretiert ist zu sehen und war zu erwarten.

Wenn aber jetzt das XOR am Ende die Performence wieder zerreißt, dann muss ich mir etwas anderes einfallen lassen. Es sollte ja imemrhin Effektiv bleiben. Ein Hex-Datentyp wäre doch mal was für PB. DAnn wäre das vielleicht nicht so extrem

[NicTheQuick]

Eigentlich ist bei sowas wie PBKDF2 die Geschwindigkeit doch egal. Ist doch gut, wenn es langsam ist, dann kann man es auch nur langsam bruteforcen.

[TroaX]

Eigentlich ist bei sowas wie PBKDF2 die Geschwindigkeit doch egal. Ist doch gut, wenn es langsam ist, dann kann man es auch nur langsam bruteforcen.

Ne eben nicht. Wenn PHP bei jedem Durchgang das selbe Ergebnis liefert wie PB, dabei aber schneller wäre, würde sich zum Bruteforcen PHP besser eignen. Genauso wäre es, wenn jemand das gleich Ergebnis mit Assembler nochmals schneller hinbekommt. Es geht bei dem Algo ja darum, das Bruteforcen zu verlangsamen. Wenn ich aber jetzt die Anzahl an Iterationen verringere, weil sonst die Anwendung zu lahm werden würde, würde ich doch den Effekt von PBKDF2 doch wieder schwächer. Oder habe ich da einen Denkfehler?

[NicTheQuick]

Klar, wenn du den Hash eh schon hast, nimmt man eh eine fette NVidia-Karte mit 2880 Cores und bruteforced parallel. Aber wenn man nur über ein Webinterface ran kommt und nicht direkt an die DB, dann ist es egal.

Aber du hast natürlich recht, dass ein effizienter Algorithmus immer besser ist.

[TroaX]

ACH DU HEILIGE SCHEIßE!!!

Das geht garnicht!!!

Ich habe den Code nur um deine erste XOR-Prozedur erweitert. Schau dir mal die Zeiten an. Das ist nun wirklich zu extrem. Der komplette Benchmark hat fast 26 Minuten gedauert. Ohne XOR dauert das ganze nur 2 1/3 Minuten. Das ist in etwa der Faktor 11!

Code: Alles auswählen

Bench with 10 Peppers
1 Iterations in 0 ms | Comparing is 1 | Comparing in 1 ms
2 Iterations in 0 ms | Comparing is 1 | Comparing in 0 ms
4 Iterations in 0 ms | Comparing is 1 | Comparing in 1 ms
8 Iterations in 1 ms | Comparing is 1 | Comparing in 2 ms
16 Iterations in 1 ms | Comparing is 1 | Comparing in 5 ms
32 Iterations in 1 ms | Comparing is 1 | Comparing in 7 ms
64 Iterations in 2 ms | Comparing is 1 | Comparing in 18 ms
128 Iterations in 5 ms | Comparing is 1 | Comparing in 16 ms
256 Iterations in 8 ms | Comparing is 1 | Comparing in 64 ms
512 Iterations in 16 ms | Comparing is 1 | Comparing in 96 ms
1024 Iterations in 32 ms | Comparing is 1 | Comparing in 255 ms
2048 Iterations in 64 ms | Comparing is 1 | Comparing in 638 ms
4096 Iterations in 127 ms | Comparing is 1 | Comparing in 1020 ms
8192 Iterations in 255 ms | Comparing is 1 | Comparing in 2294 ms

Bench with 100 Peppers
1 Iterations in 0 ms | Comparing is 1 | Comparing in 7 ms
2 Iterations in 0 ms | Comparing is 1 | Comparing in 10 ms
4 Iterations in 0 ms | Comparing is 1 | Comparing in 5 ms
8 Iterations in 1 ms | Comparing is 1 | Comparing in 7 ms
16 Iterations in 0 ms | Comparing is 1 | Comparing in 33 ms
32 Iterations in 1 ms | Comparing is 1 | Comparing in 61 ms
64 Iterations in 2 ms | Comparing is 1 | Comparing in 99 ms
128 Iterations in 4 ms | Comparing is 1 | Comparing in 406 ms
256 Iterations in 8 ms | Comparing is 1 | Comparing in 776 ms
512 Iterations in 16 ms | Comparing is 1 | Comparing in 1356 ms
1024 Iterations in 32 ms | Comparing is 1 | Comparing in 3126 ms
2048 Iterations in 64 ms | Comparing is 1 | Comparing in 702 ms
4096 Iterations in 127 ms | Comparing is 1 | Comparing in 11982 ms
8192 Iterations in 255 ms | Comparing is 1 | Comparing in 7648 ms

Bench with 1000 Peppers
1 Iterations in 0 ms | Comparing is 1 | Comparing in 33 ms
2 Iterations in 0 ms | Comparing is 1 | Comparing in 95 ms
4 Iterations in 0 ms | Comparing is 1 | Comparing in 54 ms
8 Iterations in 1 ms | Comparing is 1 | Comparing in 185 ms
16 Iterations in 1 ms | Comparing is 1 | Comparing in 474 ms
32 Iterations in 1 ms | Comparing is 1 | Comparing in 52 ms
64 Iterations in 2 ms | Comparing is 1 | Comparing in 10 ms
128 Iterations in 4 ms | Comparing is 1 | Comparing in 157 ms
256 Iterations in 8 ms | Comparing is 1 | Comparing in 1759 ms
512 Iterations in 16 ms | Comparing is 1 | Comparing in 5762 ms
1024 Iterations in 32 ms | Comparing is 1 | Comparing in 22509 ms
2048 Iterations in 63 ms | Comparing is 1 | Comparing in 61583 ms
4096 Iterations in 128 ms | Comparing is 1 | Comparing in 108746 ms
8192 Iterations in 255 ms | Comparing is 1 | Comparing in 212362 ms

Bench without Pepperlist (static)
1 Iterations in 0 ms | Comparing is 1 | Comparing in 0 ms
2 Iterations in 0 ms | Comparing is 1 | Comparing in 0 ms
4 Iterations in 0 ms | Comparing is 1 | Comparing in 0 ms
8 Iterations in 0 ms | Comparing is 1 | Comparing in 1 ms
16 Iterations in 0 ms | Comparing is 1 | Comparing in 1 ms
32 Iterations in 1 ms | Comparing is 1 | Comparing in 1 ms
64 Iterations in 2 ms | Comparing is 1 | Comparing in 2 ms
128 Iterations in 4 ms | Comparing is 1 | Comparing in 4 ms
256 Iterations in 8 ms | Comparing is 1 | Comparing in 9 ms
512 Iterations in 16 ms | Comparing is 1 | Comparing in 16 ms
1024 Iterations in 32 ms | Comparing is 1 | Comparing in 32 ms
2048 Iterations in 63 ms | Comparing is 1 | Comparing in 64 ms
4096 Iterations in 128 ms | Comparing is 1 | Comparing in 127 ms
8192 Iterations in 255 ms | Comparing is 1 | Comparing in 255 ms
16384 Iterations in 510 ms | Comparing is 1 | Comparing in 509 ms
32768 Iterations in 1020 ms | Comparing is 1 | Comparing in 1020 ms
65536 Iterations in 2038 ms | Comparing is 1 | Comparing in 2040 ms
131072 Iterations in 4078 ms | Comparing is 1 | Comparing in 4081 ms
262144 Iterations in 8158 ms | Comparing is 1 | Comparing in 8159 ms
524288 Iterations in 16313 ms | Comparing is 1 | Comparing in 16322 ms

Bench without Pepperlist and Compare
1 Iterations in 0 ms
2 Iterations in 0 ms
4 Iterations in 0 ms
8 Iterations in 1 ms
16 Iterations in 0 ms
32 Iterations in 1 ms
64 Iterations in 2 ms
128 Iterations in 4 ms
256 Iterations in 8 ms
512 Iterations in 15 ms
1024 Iterations in 31 ms
2048 Iterations in 64 ms
4096 Iterations in 128 ms
8192 Iterations in 255 ms
16384 Iterations in 510 ms
32768 Iterations in 1019 ms
65536 Iterations in 2039 ms
131072 Iterations in 4077 ms
262144 Iterations in 8156 ms
524288 Iterations in 16317 ms
1048576 Iterations in 32630 ms
2097152 Iterations in 65280 ms
4194304 Iterations in 130559 ms
8388608 Iterations in 261237 ms
16777216 Iterations in 523382 ms

Benchtime: 1556960 ms

[Nino]

Und wenn Du die Strings mit den Hex-Werten zunächst in den Speicher pokest, und dann XOR auf den Speicherbereichen durchführst (im Zweifelsfall mit ASM-Code)?