[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

No Subject



Thomas Roessler <roessler@guug.de>:

> [...] Hash-Wert [...]  Die dabei verwendete Abbildung ist so
> konstruiert, daß das Urbild eines gegebenen Wertes rechnerisch
> schwer[1] zu bestimmen ist, und daß es rechnerisch schwer ist, zwei
> Texte zu finden, die zum gleichen Hash-Wert führen.

> [1] Rechnerisch schwer heißt dabei, daß der zur Ausführung der
> betreffenden Operationen nötige Aufwand in nichtpolynomialer Weise
                                  ^^^^^^^    ^^^^^^^^^^^^^^^
> in der Länge der betrachteten Daten steigt; [...]

Diese Darstellung ist sachlich falsch. Das Suchen von SHS-Urbildern
oder -Kollisionen der Länge N ist in O(N) Schritten machbar [*].
Berücksichtigt man noch, dass SHS nur für Eingaben unter 2^64 Bits
definiert ist, kommt man sogar auf O(1).

            [*]  (unter ein paar Annahmen über die Surjektivität der
                 Kompressionsfunktion B^160 x B^512 ---> B^160 bei
                 teilweise vorgegebenen Eingabewerten)



Begriffe wie "nichtpolynomialer Aufwand" sind (hier) der falsche
Ansatz (schließlich sind SHS und die anderen üblichen Hash-Algorithmen
hinsichtlich der Länge des Hash-Wertes nicht skalierbar); man muss den
Aufwand konkret betrachten. Zum Beispiel so:

"Rechnerisch schwer" heißt: Um die Aufgabe mit einer "nicht
vernachlässigbaren Wahrscheinlichkeit" lösen zu können, muss man
"unvorstellbar viele" einfache Einzelschritte durchführen.
(Als erlaubte Einzelschritte kann man die logischen Basisfunktionen
auf Bits annehmen, oder auch ALU-Operationen auf "handelsüblichen"
Registergrößen. Beim verfügbaren Speicher braucht man dabei nicht zu
geizen, sondern kann so viele Register wie Schritte zulassen; damit
hat man serielle und parallele Implementierungen erfasst.)

Die dabei verwendeten Einzelbegriffe sind noch zu klären: Welche
Wahrscheinlichkeit ist noch "vernachlässigbar"? Welche Anzahl von
Einzelschritten ist nicht mehr "vorstellbar"? -- Wenn man hierfür
plausible Werte vorsichtig schätzt (und annimmt, dass SHS keine
rechnerischen Abkürzungen erlaubt), kann man sich überlegen, ob das
Kollisionsproblem und das Urbildproblem bei SHS tatsächlich in dem
Sinne "rechnerisch schwer" sind.


Bodo Moeller
<Bodo_Moeller@public.uni-hamburg.de>