Geburtstagsangriff
aus Wikipedia, der freien Enzyklopädie
Ein Geburtstagsangriff ist eine Methode, für eine gegebene Hash-Funktion verschiedene Dokumente mit gleichem Hashwert zu finden. Der Name wurde gewählt, da es sich um eine Anwendung des Geburtstagsproblems handelt.
Der naive Brute-Force-Angriff auf eine Hash-Funktion besteht darin, zu einem gegebenen Text einen anderen Text zu finden, der den gleichen Hashwert hat. Bei einem Hashwert von 40 Bit sind dafür etwa eine Billion Versuche nötig.
In vielen Missbrauchsszenarien können aber beide Texte variiert werden. Dabei handelt es sich dann um einen Geburtstagsangriff, und die nötige Zahl an Variationen ist nur noch etwas größer als die Quadratwurzel der benötigten Anzahl beim naiven Angriff, also für einen 40-Bit-Hash etwas über eine Million Versuche.
[Bearbeiten] Vorgehensweise
Erstelle Variationen von „guten“ Texten durch zum Beispiel Festlegen von veränderlichen Inhalten, die dem Betrachter nicht auffallen. Werden beispielsweise 32 Positionen festlegt, die jeweils auf zwei Arten ausgeführt werden können, so ergeben sich 232 (etwa 4.000.000.000) verschiedene Dokumente. Danach wird eine große Variation von „bösen“ Texten erstellt. Der Angreifer vergleicht nun beide Mengen und hofft, auf je ein Dokument mit dem gleichen Hashwert zu treffen.
Um dem Erfolg eines Geburtstagsangriffs entgegenzuwirken, muss die Länge des Hashwertes hinreichend groß gewählt werden, so dass Überschneidungen auch mit diesem Verfahren sehr unwahrscheinlich werden. Für elektronische Unterschriften etwa sind derzeit 160 Bit gebräuchlich.
Eine weitere Möglichkeit, dem Geburtstagsangriff entgegenzuwirken, ist die Veränderung des Dokumentes vor der Unterschrift. Damit kann die „Vorbereitung“ der Texte ausgeschlossen werden.
[Bearbeiten] Beispiel für die Anwendung
Elektronische Unterschriften beziehen sich auf den Hashwert der unterzeichneten Dokumente, nicht auf den tatsächlichen Inhalt.
Der Angreifer erzeugt also zunächst zwei verschiedene Verträge: Einen „guten“ Vertrag mit günstigen Konditionen für das Opfer und einen „schlechten“ Vertrag mit günstigen Konditionen für den Angreifer. Durch geringfügige Veränderungen (etwa das Einfügen von Leerzeichen) werden dabei beide Verträge so lange variiert, bis sie den gleichen Hashwert haben, ohne dass sich ihr jeweiliger Inhalt ändert.
Dann wird dem Opfer der „gute“ Vertrag zur elektronischen Unterschrift vorgelegt. Die erstellte Signatur bezieht sich auf den gemeinsamen Hashwert der beiden Verträge, kann also auch missbräuchlich für den „schlechten“ Vertrag verwendet werden.
Der Unterzeichner kann dieser Attacke entgegen wirken, indem er vor dem Unterschreiben ebenfalls irrelevante Änderungen durchführt, also beispielsweise ein zusätzliches Leerzeichen einfügt.
Diese Gegenmaßnahme funktioniert natürlich nur, wenn der Vertrag nicht bereits unterzeichnet ist und nur noch gegengezeichnet werden muss. Anderenfalls wäre es besser, den Hash-Algorithmus mit einem Zufallswert (seed) zu starten und als Unterschrift sowohl seed als auch Hashwert zu verwenden. Leider unterstützen übliche digitale Signaturverfahren diese Modifikation nicht.
Bei gebräuchlichen Hash-Funktionen wie SHA-1 ist jedoch die Wahrscheinlichkeit für eine zufällig auftretende Übereinstimmung bzw. Kollision der Hashwerte (p = 
) der beiden Vertragsversionen praktisch zu vernachlässigen. Eine solche Kollision kann im Grunde nur autreten, wenn, wie oben beschrieben, eine Manipulation vorliegt. Der Angreifer kann die Kollision damit nicht wirklich als Beweis verwenden, da das Auftreten dieser Kollision ihn als Betrüger entlarvt.
