Kollisionsangriffe gegen Hash-Funktionen Auswirkungen und Stand der Entwicklung

Ordnungsmerkmale

erschienen in: <kes> 2005^#5, Seite 58

Zusammenfassung: Nachdem sich auf dem Gebiet der Hash-Funktionen etliche Jahre relativ wenig ereignet hat, sind in den letzten beiden Jahren eine ganze Reihe wissenschaftlicher Publikationen über Angriffe gegen Hash-Funktionen und ihre Auswirkungen erschienen. Im Hinblick auf die Sicherheit elektronischer Signaturen haben insbesondere Aussagen zur Sicherheit des SHA-1 für Verunsicherung gesorgt.

Zusammenfassung: Von Dr. Georg Illies und Priv.-Doz. Dr. Werner Schindler, BSI

Eine Hash-Funktion h ordnet einem Bitstring beliebiger Länge einen Bitstring fester Länge zu. Oder formal ausgedrückt: h ist eine Abbildung {0,1}* → {0,1}ⁿ. Dabei bezeichnet h(M) den Hash-Wert zum Bitstring M, und n gibt dessen Länge an. Einige Beispiele sind MD5 (n = 128), SHA-1 und RIPEMD-160 (jeweils n = 160), die Hash-Funktionen-Familie SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512; mit n = 224, 256, 384, 512), WHIRLPOOL (n = 512). Ebenso wie SHA-1 wurde die relativ neue Hash-Funktionen-Familie SHA-2 vom US-amerikanischen National Institute of Standards and Technology (NIST) standardisiert.

Hash-Werte sind Prüfsummen, wobei Änderungen am Eingabe-String M zu Änderungen des Hash-Werts h(M) führen sollen. Das erinnert an die ISBN-Nummer im Buchhandel, die (unabsichtlich) fehlerhaft eingegebene Ziffern oder "Zifferndreher" erkennen soll. Neben unabsichtlichen Veränderungen sollen Hash-Funktionen jedoch auch vorsätzliche Manipulationen aufdecken. Genauer gesagt, sollte eine gute Hash-Funktion die folgenden Eigenschaften erfüllen:

Einwegeigenschaft

Es existiert kein praktisch durchführbares Verfahren, das zu vorgegebenem Hash-Wert y ∈ {0,1}ⁿ ein Urbild x ∈ {0,1}* liefert, das heißt einen String findet, für den h(x) = y gilt.

Kollisionsresistenz

Es existiert kein praktisch durchführbares Verfahren, Kollisionen von h zu finden, das heißt zwei verschiedene Bitstrings x,x' ∈ {0,1}* mit identischem (ansonsten aber beliebigem) Hash-Wert anzugeben.

Second-Preimage-Eigenschaft

Die Kollisionsresistenz impliziert die Second-Preimage-Eigenschaft: Es existiert kein praktisch durchführbares Verfahren, das zu einem vorgegebenen Eingabe-String x einen weiteren Eingabe-String x' ≠ x liefert, für den h(x) = h(x') gilt.

Um keine Missverständnisse aufkommen zu lassen: Es gibt unendlich viele Eingabe-Strings, aber nur endlich viele verschiedene Hash-Werte. Daher existieren selbstverständlich Werte x, x' und y, die obige Gleichungen erfüllen. Darum geht es hier aber nicht: Entscheidend ist, dass man keinen Algorithmus angeben kann, mit dem die Suche nach derartigen Strings praktisch bewältigt werden kann.

Ein simples Durchprobieren zufällig gewählter Eingabe-Strings erfordert im Durchschnitt einen Aufwand von 2ⁿ Hash-Wert-Berechnungen, um zu vorgegebenem y ein Urbild x mit h(x) = y oder zu vorgegebenem Eingabe-String x einen weiteren Eingabe-String x' ≠ x zu finden, für den h(x) = h(x') gilt. Haben wir damit nicht einen Algorithmus gefunden, dessen Existenz wir ausschließen wollten? Nein, das ist nicht der Fall, weil die Zahl 2ⁿ bei gängigen Hash-Funktionen gigantisch groß ist: Für MD5 ist das 2¹²⁸, für SHA-1 und RIPEMD-160 jeweils 2¹⁶⁰, während bei den übrigen aufgeführten Beispielen sogar n ≥ 224 ist.

Aus dem so genannten Geburtstagsparadoxon folgt, dass der Aufwand für eine Kollisionssuche durch das Ausprobieren zufällig gewählter Eingabe-Strings lediglich einen Aufwand von etwa 2^(n/2) Operationen erfordert. In der Praxis ist es wesentlich schwieriger, die Kollisionsresistenz zu gewährleisten als die Einwegeigenschaft oder Second-Preimage-Eigenschaft. Da ohnehin deutlich weniger Operationen benötigt werden, sind Verbesserungen von Kollisionsangriffen normalerweise wesentlich beunruhigender als Verbesserungen von Angriffen gegen die Einweg- oder Second-Preimage-Eigenschaft.

Sichere Signaturen erfordern sichere Hash-Funktionen

Bei allen in der Praxis verwendeten Signaturverfahren wird nicht die Nachricht M selbst, sondern ihr Hash-Wert h(M) signiert. Der Signierer berechnet mit seinem geheimen Schlüssel sk eine Signatur {Sig}_{sk}(h(M)), die mit Kenntnis des öffentlichen Schlüssels pk verifiziert werden kann. Die Second-Preimage-Eigenschaft ist unbedingt notwendig, da ein Angreifer ansonsten die signierte Nachricht durch eine andere ersetzen könnte, die denselben Hash-Wert und damit auch dieselbe Signatur besitzt (man beachte, dass hierfür nicht die Kenntnis des Signaturschlüssels erforderlich wäre!). Die Kollisionsresistenz verhindert das folgende, speziellere Missbrauchsszenario: Ein Angreifer konstruiert zwei unterschiedliche Nachrichten M und M' mit h(M) = h(M') und bringt jemanden dazu, M zu signieren. Damit hätte er gleichzeitig eine gültige Signatur seines Opfers für M', deren Inhalt für den Angreifer womöglich "günstiger" als M ist.

Ein Angreifer kann die Fähigkeit, Kollisionen zu erzeugen, nur für neu zu erstellende Signaturen verwenden, während die Sicherheit früher geleisteter Signaturen durch Kollisionsangriffe nicht gefährdet ist. Entscheidend ist, ob die Kollisionsfreiheit zum Zeitpunkt gegeben war, als die Signatur erstellt wurde. Dagegen muss die Second-Preimage-Eigenschaft während der gesamten Gültigkeitsdauer einer Signatur erfüllt sein.

Merkle-Damgard-Konstruktion

Alle gängigen Hash-Funktionen folgen einem von Merkle und Damgard vorgeschlagenem Konstruktionsschema. "Kern" dieses Konstrukts ist eine (für die jeweilige Hash-Funktion spezifische) so genannte Kompressionsfunktion f:{0,1}^m × {0,1}ⁿ → {0,1}ⁿ . Die Kompressionsfunktion f könnte beispielsweise aus einer eingehend untersuchten, geeigneten Blockchiffre abgeleitet werden. Allerdings liefe dies einer ganz wesentlichen Anforderung an Hash-Funktionen entgegen: Hash-Funktionen sollen nämlich effizient, das heißt mit relativ geringem Aufwand, berechenbar sein. Die Kompressionsfunktion wird daher bei den praxisrelevanten Hash-Funktionen durch die Hintereinanderausführung vieler, sehr effizient implementierbarer Funktionen (Schritte) realisiert. Beispielsweise besteht die MD5-Kompressionsfunktion aus 64, die Kompressionsfunktion bei SHA-1 aus 80 Schritten. Jeder einzelne Schritt ist so konstruiert, dass er auf einer üblichen Prozessorarchitektur mit 32-Bit-Registern innerhalb weniger Prozessortakte ausführbar ist.

Die Sicherheit einer Merkle-Damgard-Hash-funktion h (z. B. MD5 oder SHA-1) kann man aus Eigenschaften ihrer Kompressionsfunktion f ableiten. Allerdings gilt auch das Umgekehrte: So lassen sich erfolgreiche Angriffe gegen die Kompressionsfunktion normalerweise schnell auf Angriffe gegen die gesamte Hash-Funktion ausweiten.

Außerdem besitzt die Merkle-Damgard-Konstruktion eine weitere Eigenschaft, die inzwischen immer kritischer gesehen wird (Multikollisionen, theoretische Angriffe gegen die Einwegeigenschaft; vgl. [5,7]): Aus einer einzigen Kollision kann man durch simples Verlängern beliebig viele weitere Kollisionen zu erzeugen. Genauer gesagt: Sind a und a' Bitstrings gleicher Länge, die ein Vielfaches der Eingabeblocklänge m ist, und gilt h(a) = h(a'), so gilt auch h(a||b) = h(a'||b) für jeden String b.

"Chinesische Angriffe"

Im Zusammenhang mit digitalen Signaturen, die hohen Sicherheitsanforderungen genügen sollen, ist die von NIST standardisierte Hash-Funktion SHA-1 im internationalen Umfeld am weitesten verbreitet. Für andere Anwendungen spielt auch MD5 noch eine wichtige Rolle.

Für MD5 ist es chinesischen Kryptologen um Xiaoyun Wang gelungen, einen ganz bestimmten 1024-Bit-Differenzenvektor c und eine Liste hinreichender Bedingungen an bestimmte Registerbits (Zwischenergebnisse) mit der folgenden Eigenschaft anzugeben: Erfüllen zwei Strings x,x' ∈ {0,1}¹⁰²⁴ die Differenzenbedingung c = x − x' (32-Bit-wortweise Differenzenbildung) sowie bestimmte Registerbitbedingungen, so folgt MD5(x) = MD5(x'), das heißt x und x' liefern eine MD5-Kollision. Die meisten dieser Bedingungen an die Registerbits lassen sich vorab durch eine geschickte Wahl von x erfüllen.

Ob die übrigen Bedingungen erfüllt sind, stellt sich erst später, das heißt während der Berechnung der beiden Hash-Werte, heraus. Durchschnittlich erfordert dies keinen höheren Aufwand als die Berechnung von 2³⁹ MD5-Hash-Werten [9], um einen geeigneten Bitstring x zu finden. Das ist deutlich effizienter als die erwähnte Geburtstagsattacke, welche etwa 2⁶⁴ Hash-Wert-Berechnungen erfordert. Es sei an dieser Stelle erwähnt, dass die chinesische Forschergruppe auch Kollisionen zu anderen Hash-Funktionen (MD5, HAVAL, RIPEMD, aber nicht RIPEMD-160) erzeugen konnte, welche aber wie MD5 schon etliche Jahre als unsicher gelten und insbesondere im Zusammenhang mit digitalen Signaturen.

Ein analoges Vorgehen wie beim MD5 würde nach [10] beim SHA-1 etwa 2⁶⁹ Hash-Wert-Berechnungen erfordern. Dies stellt zweifellos eine erhebliche Verbesserung gegenüber einer Geburtstagsattacke (ca. 2⁸⁰ Hash-Wert-Berechnungen) dar. Allerdings sind auch 2⁶⁹ Hash-Wert-Berechnungen noch eine enorme Anzahl. Zudem ist diese Aussage zumindest vorerst unter einem gewissen Vorbehalt zu sehen: Im Gegensatz zu den MD5-Kollisionen existieren keine SHA-1-Kollisionen, sondern die genannte Komplexität basiert auf theoretischen Überlegungen, in die heuristische Bedingungen eingehen (z. B. die stochastische Unabhängigkeit der Registerbitbedingungen). Außerdem hat sich bei der Analyse der entsprechenden Bedingungen für den MD5 gezeigt, dass die in [9] angegebene Liste der hinreichenden Bedingungen nicht ganz vollständig ist. Vergleichbare Ungenauigkeiten in der erst kürzlich erschienenen Arbeit [10] könnten unter Umständen Korrekturen in der Abschätzung des Aufwands erforderlich machen. Unabhängig davon stellt aber [10] auf jeden Fall einen erheblichen kryptographischen Fortschritt bei der Kollisionssuche für den SHA-1 dar. Mitte August ließen Wang et al. verlautbaren, dass gar 2⁶³ SHA-1-Operationen genügten (Crypto 2005, Rump-Session); nähere Informationen liegen hierzu indes zurzeit noch nicht vor.

Folgen von Kollisionen

Für die eingangs beschriebenen Angriffe auf Signaturen werden im Normalfall semantisch sinnvolle Kollisionen benötigt, deren Generierung grundsätzlich schwieriger ist als die Generierung abstrakter Kollisionen. In [8] und [6] wurde allerdings gezeigt, wie man aus abstrakten Hash-Kollisionen Kollisionen gültiger X.509-Zertifikate konstruieren kann. Diese Konstruktion stellt allerdings – unabhängig von der verwendeten Hash-Funktion – zumindest im Umfeld der qualifizierten elektronischen Signatur keine konkrete Gefahr dar.

Die bereits erwähnte Verlängerungseigenschaft von Kollisionen einer Merkle-Damgard-Hash-funktion erleichtert unter anderem auch die Konstruktion syntaktisch und semantisch sinnvoller Kollisionen für spezielle Dokumentdateiformate. In [3,4] wurden PostScript-, PDF-, TIFF- und MS-Word-Dateien untersucht. Allerdings kann ein Sachverständiger dort eine "verdächtige Konstruktion" erkennen – zumindest wenn er den "Trick" kennt –, selbst wenn nur noch eine der beiden Kollisionsdateien vorliegt.

Für MD5 wurden in [3,4,6,8] konkrete Beispiele konstruiert. Das Vorgehen lässt sich beinahe wörtlich auf andere Hash-Funktionen übertragen, bei denen die Kollisionsfreiheit (für beliebige Initialisierungsvektoren – IVs) nicht mehr gewährleistet ist. Trotz der Einschränkungen, die die praktische Durchführung derartiger Betrügereien betreffen, unterstreichen diese Überlegungen, dass die Anforderung der Kollisionsresistenz in keiner Weise abgeschwächt werden sollte.

Muss der MD5 nun aus allen kryptographischen Anwendungen verschwinden? Der MD5 spielt bei digitalen Signaturen, die hohen Sicherheitsanforderungen genügen sollen, schon lange keine Rolle mehr. Daneben wird MD5 aber auch bei anderen kryptographischen Anwendungen eingesetzt. Sofern die Kollisionsfreiheit hierfür nicht erforderlich ist, ist dagegen derzeit nichts einzuwenden.

Konsequenzen für den Algorithmenkatalog

Die Bundesnetzagentur (BNetzA, früher RegTP) als zuständige Behörde veröffentlicht seit 1998 nach den Angaben des BSI und unter Beteiligung von Experten aus Wirtschaft und Wissenschaft im Bundesanzeiger jährlich eine Übersicht über Algorithmen und Parameter, die mindestens für den Zeitraum von sechs Jahren für qualifizierte elektronische Signaturen gemäß Signaturgesetz (SigG) als geeignet anzusehen sind (sog. Algorithmenkatalog). Als geeignet wurden beziehungsweise werden die Hash-Funktionen RIPEMD-160, SHA-1 und die SHA-2-Familie angesehen, während beispielsweise MD5 zu keiner Zeit empfohlen wurde.

Der Algorithmenkatalog 2005 [1] erklärt SHA-1 und RIPEMD-160 als bis Ende 2010 geeignet. Das NIST plant, den SHA-1 zu diesem Termin auslaufen zu lassen. Angesichts der neuen Erkenntnisse zum SHA-1 erscheint es nun notwendig, erneut darüber nachzudenken, bis zu welchem Zeitpunkt von der Eignung von SHA-1 und RIPEMD-160 ausgegangen werden kann.

Darüber wird bei der diesjährigen Expertenanhörung der BNetzA zum Algorithmenkatalog 2006 zu befinden sein, welche voraussichtlich im November 2005 stattfinden wird. Dabei werden sicher auch Erkenntnisse und Entwicklungen des von der NIST initiierten Cryptograhic Hash Workshops (2005-10-31/11-01) einfließen. Dieser Workshop könnte auch im Hinblick auf Alternativkandidaten zur SHA-2-Familie neue Erkenntnisse bringen.

zurück zum Inhalt
© SecuMedia-Verlags-GmbH, 55205 Ingelheim (DE),
<kes> 2005^#5, Seite 58