Cryptography Reference
In-Depth Information
Nachrichten durchprobiert, dann erzeugt er quasi zufällige Hashwerte. In dem obigen Beispiel
gibt es 2 160 unterschiedliche Hashwerte. Dass eine gewählte Nachricht auf einen bestimmten
Hashwert fällt, hat die Wahrscheinlichkeit 2 -160 , falls sich die Nachrichten gleichmäßig auf die
2 160 Hashwerte verteilen.
Bei den kollisionsresistenten Hashfunktionen wird noch unterschieden zwischen schwach
kollisionsresistenten und stark kollisionsresistenten Hashfunktionen.
Definition: Bei schwach kollisionsresistenten Hashfunktionen ist es praktisch nicht durch-
führbar, zu einem gegebenen Hashwert h(m) eine andere Nachricht m* mit dem gleichen
Hashwert h(m*) = h(m) zu finden.
Definition: Bei stark kollisionsresistenten Hashfunktionen ist es praktisch nicht durchführ-
bar, zwei Nachrichten m 1 und m 2 mit dem gleichen Hashwert h(m 1 ) = h(m 2 ) zu finden.
Die beiden Arten von Hashfunktionen unterscheiden sich insbesondere durch die Art des Ang-
riffs, gegenüber dem sie resistent sein sollen. Im Fall von schwach kollisionsresistenten Hash-
funktionen sind die Nachricht m und ihr Hashwert h(m) festgelegt. Im Fall von stark kollisi-
onsresistenten Hashfunktionen hat der Angreifer völlige Freiheit in der Auswahl der beiden
Nachrichten m 1 und m 2 . Die Arten der Angriffe werden im Folgenden diskutiert.
3.1.2 Angriffe auf Hash-Funktionen
Die hier diskutierten Angriffe sind Brut-Force-Angriffe, bei denen Kollisionsversuche ohne
Kenntnis der speziellen Eigenschaften der Hashfunktionen durchgeführt werden und die damit
auf jede Hashfunktion anwendbar sind. Bei speziellen Hashfunktionen kann der Aufwand für
einen Angriff geringer sein als bei einem Brut-Force-Angriff. In diesem Fall ist dann zu ent-
scheiden, ob die Kollisionsresistenz einer speziellen Hashfunktion noch ausreicht.
3.1.2.1 Angriff auf schwache Kollisionsresistenz
Es wird angenommen, dass die Hashwerte eine Länge von n Bit haben. Die Nachrichten dür-
fen beliebig lang sein. Es wird weiter angenommen, dass es sich um gute Hashfunktionen
handelt, d.h. die Hashwerte der Nachrichten verteilen sich gleichmäßig und quasi-zufällig auf
alle 2 n möglichen Hashwerte.
Bei schwacher Kollisionsresistenz ist eine Nachricht m mit ihrem Hashwert h(m) vorgegeben.
Ein Angreifer wählt Nachrichten m* aus und prüft, ob er eine Kollision mit h(m*) = h(m)
gefunden hat. Die Wahrscheinlichkeit, dass bei einem Versuch eine Kollision mit h(m) auftritt,
ist 2 -n . Bei jedem Versuch ergibt sich ein Erwartungswert von 2 -n Kollisionen. Die Erwar-
tungswerte der Kollisionen können bei unabhängigen Versuchen addiert werden. Bei 2 n Ver-
suchen ist der Erwartungswert für Kollisionen E K = 2 n ·2 -n = 1. Das heißt, bei 2 n Versuchen tritt
im Mittel eine Kollision auf.
n
&
Zahl der Versuche für im Mittel E
1 Kollision
2
K
(3.1-1)
n
bei Wahrscheinlichkeit von 2
für eine Kollision je Versuch
Search WWH ::




Custom Search