Cryptography Reference
In-Depth Information
Bei einem Angriff auf starke Kollision ist ein Hashwert mit einer Länge von mindestens
n = 160 erforderlich. Die Anzahl der Versuche für im Mittel eine Kollision ist dann
j 1,4·2
160/2
= 1,4·2
80
.
Die Frage einer schwachen oder starken Kollisionsresistenz ist eine Frage der Anwendung und
weniger eine Eigenschaft der Hashfunktion. Bei einer digitalen Signatur auf den Hashwert
h(m) einer Nachricht m müsste ein Angreifer eine Nachricht m* genau für diesen Hashwert
finden, um der vorhandenen Signatur die konstruierte Nachricht m* zu unterschieben. Zu ei-
nem vorgegebenen Hashwert eine andere Nachricht m* zu finden entspricht einem Angriff auf
schwache Kollisionsresistenz. Eine starke Kollisionsresistenz wäre somit nicht erforderlich.
Allerdings zeigen neuere Angriffe [KES05], dass eine schwache Kollisionsresistenz im Zu-
sammenhang mit digital signierten Dokumenten, die von einem Interpreter verarbeitet werden,
nicht unbedingt ausreicht. Gefundene Kollisionen können verwendet werden, um die Bild-
schirm-Ausgabe, zum Beispiel eines Postscript-Interpreters, zu steuern. Bei gleich bleibender
digitaler Signatur wird dann, abhängig von der im elektronischen Dokument eingesetzten Kol-
lision, eine andere Ausgabe am Bildschirm angezeigt. Das interpretierte Dokument enthält
dann Anweisungen, bei dem einen Kollisions-Datum die Ausgabe bestimmter Information zu
unterdrücken, während diese Informationen bei dem anderen Datum angezeigt werden. Beide
Datensätze besitzen aber denselben Hashwert und führen somit zu einer identischen digitalen
Signatur.
3.1.2.3
Geburtstagsangriff
Der Angriff auf starke Kollisionsresistenz wird auch als
Geburtstagsangriff
bezeichnet. Die
Bezeichnung leitet sich von einem Phänomen her, das als
Geburtstags-Paradoxon
bezeichnet
wird. Eine erste Situation sei, dass ich einen Saal betrete und feststelle, ob eine andere Person
im Saal am gleichen Tag Geburtstag hat wie ich selbst. Wenn Geburtstage gleichmäßig und
zufällig über das Jahr verteilt sind, dann hat im Mittel eine von 365 anderen Personen an mei-
nem Geburtstag ebenfalls Geburtstag.
Eine zweite Situation sei, dass Personen in einem Saal zusammenkommen und diese feststel-
len, ob zwei beliebige Personen im Saal am gleichen Tag Geburtstag haben. Dafür sind deut-
lich weniger als 365 Personen erforderlich. Diese Situation entspricht genau dem Fall, dass j
zufällig ausgewählte Geburtstage „kollidieren“. Wenn wir in (3.1-3) die Zahl der Möglichkei-
ten 2
n
an Hashwerten durch die Zahl 365 der möglichen Tage im Jahr ersetzen, dann gibt
(3.1-4) die Zahl der Personen an, die zusammenkommen müssen, um im Mittel eine Geburts-
tagskollision zu haben.
j
)
1/ 2
2 365
27 bis 28
(3.1-4)
Das heißt, es müssen 27 bis 28 Personen zusammenkommen, so dass im Mittel einmal das
Ereignis „Geburtstag am gleichen Tag“ auftritt. An anderer Stelle [Bu99] wird angegeben,
dass k=23 Personen zusammenkommen müssen, so dass das Ereignis „Geburtstag am gleichen
Tag“ mit der Wahrscheinlichkeit von 1/2 auftritt. Die Zahl der Personen ist dafür plausibler-
maßen kleiner als jene nach (3.1-4). Brute-Force-Angriffe für Schlüssel, die teilweise bekannt
sind, lassen sich ganz praktisch für alle implementierten modernen symmetrischen Verfahren
in CrypTool durchführen: siehe Menü Analyse \ Symmetrische Verschlüsselung (modern).
