Verunsicherung um Sicherheit von Kryptoalgorithmen

Unter Kryptoexperten sorgen derzeit angebliche Schwachstellen in Kryptoalgorithmen für Verunsicherung. Grund sind die Ankündigungen zweier Forscherteams auf der diesjährigen Crypto 2004, Fehler in den Hash-Algorithmen SHA-0 und MD5 sowie eventuell sogar in SHA-1 entdeckt zu haben.

Solche Algorithmen erzeugen aus einer längeren Zeichenkette einen kurzen Hash-Wert beziehungsweise Fingerprint und werden beispielsweise bei digitalen Zertifikaten und zur Authentitätssicherung von Quellcode verwendet. Auch der PGP-Fingerprint ist ein Hash-Wert des PGP-Schlüssels. Aus dem Hash-Wert lassen sich keine Rückschlüsse auf die Originalzeichenkette ziehen. Bei dem in vielen Applikationen eingesetzten Algorithmus SHA-1 ist der Hash 160 Bit lang, bei MD5 ist er nur 128 Bit lang.

Wichtigste Anforderung an einen Hash-Algorithmus ist, im Idealfall aus unterschiedlichen Zeichenketten nicht den gleichen Hash-Wert zu erzeugen. Da Hash-Werte aber kürzer als die Eingabezeichenkette sind, käme dies einem idealem Kompressionsalgorithmus gleich. Somit gibt es, je nach verwendetem Algorithmus, eine gewisse Wahrscheinlichkeit gleicher Hash-Werte. Gleiche Werte bezeichnen Kryptologen auch als Kollision. Die Wahrscheinlichkeit dafür ist aber extrem gering. Auch das Suchen oder Erzeugen solcher Dubletten lag bislang nicht im Bereich verfügbarer Rechentechnik.

Den Ankündigungen zufolge wollen die Forscherteams aber nun Wege gefunden haben, durch angebliche Schwachstellen eine Vielzahl von Kollisionen zu berechnen. Damit wäre es unter Umständen möglich -- wenn auch noch eher theoretisch -- gültige Hash-Werte aus gefälschten Zeichenketten zu erzeugen. So wären PGP-Fingerprints bis zum Einsatz sicherer Algorithmen nicht mehr vertrauenswürdig, gleiches gilt für X.509v3-Zertifikate.

Durch das Knacken von SHA-0 soll es zudem in absehbarer Zeit möglich sein, eventuell SHA-1 zu kompromittieren. MD5 galt schon seit längerem als unsicherer im Vergleich zu SHA-1. Das MD5CRK-Projekt versuchte durch den Zusammenschluss vieler Rechner über das Internet (ähnlich SETI@Home) und das Berechnen von Kollisionen dies zu beweisen. Auch der Sourcecode einiger Open-Source-Projekte, etwa der Apache-Webserver, wird derzeit noch mit MD5-Hashes gesichert.

Allen Angriffen auf die Algorithmen zum Trotz ist es aber weiterhin sehr schwierig, zwei sinnvolle -- und nicht irgendwelche beliebigen -- Zeichenketten zu finden, die denselben Hash-Wert erzeugen. So dürfte es immensen Aufwand erfordern, in einen Sourcecode eine Backdoor derart einzubauen, dass der gleiche Hash herauskommt wie bei der Sourcecodeversion ohne Backdoor. Gleiches gilt für digitale Zertifikate und PGP-Fingerprints. Allerdings hat sich in der Vergangenheit immer wieder gezeigt, dass eine kleine Lücke schnell zu einem großen Loch aufgerissen wird. Um über die wirkliche Tragweite der Entdeckungen urteilen zu können, muss man allerdings die Kommentare der Kryptoexperten nach der Crypto 2004 abwarten.

Siehe dazu auch: (dab)

• SHA-1 Break Rumored von Edward W. Felten
• Near-Collisions of SHA-0 von Eli Biham, Rafi Chen
• Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD von Xiaoyun Wang, Dengguo Feng, Xuejia Lai und Hongbo Yu
• A real MD5 collision, Analyse von Eric Rescorla

• Harte Nüsse: Verschlüsselungsverfahren und ihre Anwendungen, Artikel aus c't 17/2003, S. 200, auf heise Security
• Durch die Hintertür: Methoden der Kryptanalyse, Artikel aus c't 22/2003, S. 204, auf heise Security