Hash-Funktionen unter Beschuss

Ordnungsmerkmale

erschienen in: <kes> 2005^#2, Seite 10

Rubrik: Management und Wissen

Schlagwort: Hash-Funktionen

Zusammenfassung: Seit Mitte Februar gab es mehrere alarmierende Schlagzeilen zu kryptographischen Hash-Funktionen. Wie bedeutend sind die aktuellen Entwicklungen für die Praxis?

Autor: Von Dirk Fox, Karlsruhe

Gleich mehrere Hiobsbotschaften jagten in den letzten Monaten durch die Gazetten: SHA-1 gebrochen!, MD5-Kollisionen gefunden! Man konnte den Eindruck gewinnen, der Kryptographie im Allgemeinen und digitalen Signaturen im Besonderen stehe der GAU unmittelbar bevor. Vor allem Bruce Schneiers Weblog-Eintrag vom 15. Februar "SHA-1 has been broken" hat bei Kryptologen und PKI-Nutzern weltweit einen Adrenalinstoß ausgelöst. Vier chinesische Forscher um Xiaoyun Wang hatten ein bemerkenswertes Ergebnis angekündigt: Mit einem Aufwand von 2⁶⁹ wollen sie SHA-1-Kollisionen finden können.

Kryptographische Hash-Funktionen spielen für die Sicherheit digitaler Signaturen eine entscheidende Rolle: Kann man zwei Texte finden, die denselben Hash-Wert liefern, kann man also eine so genannte Kollision konstruieren, dann sind die Signaturen dieser beiden Texte identisch: Eine elektronische Unterschrift des einen Textes ist auch für den anderen gültig und nicht als Fälschung zu erkennen.

Die zentrale Sicherheitseigenschaft einer Hash-Funktion ist daher ihre "Kollisionsresistenz": Es muss praktisch unmöglich sein, ein solches Paar zweier – nicht notwendigerweise sinnvoller – Nachrichten (Bitfolgen) zu finden, die denselben Hash-Wert besitzen. Zwar existieren grundsätzlich immer Kollisionen, da ein Hash-Wert von 16–20 Byte ja erheblich kürzer ist als der zugehörige Originaltext, aber das Auffinden auch nur einer einzigen Kollision sollte aufgrund des dafür erforderlichen Rechenaufwands praktisch undurchführbar sein.

Analog zu einem Signier- oder Chiffrieralgorithmus wird die Sicherheit einer Hash-Funktion sowohl von ihrer (kryptographischen) Stärke als auch von der Länge des Hash-Werts bestimmt. Von einem "sicheren" Algorithmus erwartet man, dass es keinen besseren Weg gibt, Kollisionen zu finden, als zufälliges Ausprobieren (Brute Force) und dass der Suchraum hinreichend groß ist, um ein solches Ausprobieren praktisch unmöglich zu machen.

Donald W. Davies und Wyn L. Price zeigten bereits 1989, dass der Aufwand für das Finden einer Kollision bei maximal 2^{(Länge des Hash-Werts in Bit)/2} Hash-Operationen liegt. Bei den gebräuchlichen Verfahren sind also maximal 2⁶⁴ bis 2⁸⁰ Hashes erforderlich, was deutlich jenseits dessen liegt, was man heute mit konzentrierter Rechenleistung in vernünftiger Zeit erreichen kann. Da – wie bei symmetrischen Chiffren – auch für Hash-Algorithmen kein Verfahren bekannt ist, um ihre kryptographische Stärke zu beweisen, gelten Funktionen so lange als sicher, bis es gelingt Schwächen aufzudecken.

Verbreitete Verfahren

Die Zahl der heute bekannten und verwendeten Hash-Funktionen ist erschreckend klein – tatsächlich sind es im Wesentlichen drei: MD5, der US-amerikanische Secure Hash Algorithm (SHA) und das europäische Verfahren RIPEMD. Schlimmer noch: Alle drei Verfahren (bzw. Hash-Familien) basieren auf demselben iterativen Prinzip und im Kern auf dem von Ronald Rivest Anfang der 90er-Jahre entwickelten Message-Digest-Algorithmus MD4.

MD5 (RFC 1321) wurde von Rivest 1991 als eine kryptographisch stärkere Variante des MD4 entwickelt; die Funktion erzeugt einen 128-Bit-Hash-Wert. Die erste Version des Secure Hash Algorithm (SHA), der bereits 160 Bit lieferte, hatte das US-amerikanische National Institute of Standards and Technology (NIST) im Mai 1993 publiziert und knapp zwei Jahre später aufgrund einer (unveröffentlichten) technischen Schwäche zum SHA-1 korrigiert; neben MD5 ist diese Version heute das verbreitetste kryptographische Hash-Verfahren.

Eine dritte Fassung des US-Standards wurde vom NIST im August 2000 als FIPS PUB 180-2 veröffentlicht. Diese Spezifikation umfasst neben SHA-1 drei weitere Varianten: SHA-256, SHA-384 und SHA-512, die Hashes entsprechender Bit-Länge produzieren. Im Rahmen einer "Change Notice" wurde Anfang 2004 noch eine 224-Bit-Version ergänzt. Diese fünf Algorithmen werden oft auch "SHA-x" genannt.

Die dritte Familie entstand im Rahmen des europäischen Réseaux IP Européens (RIPE). Der ursprüngliche Hash-Algorithmus RIPEMD wurde von Hans Dobbertin, Antoon Bosselaers und Bart Preneel 1996 zu RIPEMD-160 "aufgebohrt" und 2004 von der International Organization for Standardization in der ISO/IEC 10118-3 genormt. In der Praxis konnte sich RIPEMD allerdings bis heute nicht durchsetzen. Er wird zwar – neben den aktuellen SHA-Varianten – von der Regulierungsbehörde für Telekommunikation und Post (RegTP) für qualifizierte Signaturen empfohlen, jedoch nur in sehr wenigen Anwendungen genutzt. Wegen der prinzipiellen Ähnlichkeiten zu SHA und MD5 erscheint es zudem nicht unwahrscheinlich, dass RIPEMD von kryptoanalytischen Erfolgen hinsichtlich der beiden "Schwesterverfahren" ebenfalls betroffen wäre.

Fazit

Kryptologisch ist es zwar korrekt, SHA-1 als "gebrochen" zu bezeichnen, sobald ein besserer Angriff als Brute Force bekannt ist. Bei allem Respekt vor diesem ersten erfolgreichen kryptoanalytischen Angriff auf SHA-1, bleiben aber auch 2⁶⁹ Hash-Operationen ein Aufwand, der deutlich jenseits des Praktikablen liegt – und er liefert lediglich zwei "zufällige", keineswegs sinnvolle Zeichenfolgen, die denselben Hash besitzen.

Die Erfahrung der vergangenen Jahre lehrt jedoch, dass ein derart "angeschossener" Algorithmus schon bald tatsächlich "erlegt" sein kann: Auch für MD5 hatte man zunächst nur Kollisionen der Rundenfunktion gefunden. Kürzlich haben aber Lenstra, Wang und de Weger eine Methode publiziert, die eine Konstruktion zweier kollidierender Zertifikate in wenigen Minuten auf einem PC ermöglicht. Letztlich ist zwar auch dieser Angriff nur von eingeschränkter praktischer Relevanz, da die Konstruktion eines zweiten Zertifikats zu einem bereits vorliegenden damit nicht gelingt – bestehende MD5-gehashte Zertifikate sind also nicht gefährdet. Allerdings muss zukünftig jede weitere Verwendung des MD5 für digitale Signaturen als grob fahrlässig gewertet werden.

Und bei einem durchschlagenden Erfolg der kryptoanalytischen Anstrengungen gegenüber SHA droht dann tatsächlich ein GAU: Denn zum SHA-1 gibt es derzeit fast keine standardisierte und vor allem keine in Anwendungsstandards und Implementierungen (z. B. S/MIME) verbreitete Alternative, auch wenn die SHA-x-Versionen unter Kryptologen auf absehbare Zeit als sicher gelten.

Der einzig (zumindest temporär) wirksame Ausweg angesichts der Abhängigkeit von nur einem Konstruktionsprinzip wäre die Verwendung mehrerer mit verschiedenen Algorithmen erzeugter Hash-Werte in Zertifikaten und digitalen Signaturen. Das ist allerdings bisher in keinem Standard vorgesehen.

Mittelfristig bleibt die klare Notwendigkeit, konzertiert nach neuen Hash-Verfahren zu suchen – vielleicht in ähnlicher Weise wie bei der öffentlichen Ausschreibung des Advanced Encryption Standards (AES) im Jahre 1997, an der sich fast die gesamte weltweite Krypto-Community aktiv beteiligte.

Dirk Fox ist Geschäftsführer der Secorvo Security Consulting GmbH und Herausgeber der Fachzeitschrift Datenschutz und Datensicherheit (DuD).