SHA-3, der neue Hash-Standard

Kryptographische Hash-Funktionen sind ein wichtiger Baustein bei der sicheren Kommunikation im Internet. In den letzten Jahren geriet hier einiges in Bewegung. Die lange Zeit eingesetzten Verfahren MD5 und SHA-1 waren sich plötzlich nicht mehr so sicher wie ursprünglich gedacht. So nutzte der Virus Flame, der im Mai diesen Jahres auf zahlreichen Rechnern im nahen Osten entdeckt wurde, die Schwäche von MD5, um sich über den Update-Service von Windows zu installieren.

Infolge der kryptographischen Durchbrüche entschied die US-Standardisierungsbehörde NIST (National Institute for Standards and Technology), einen Wettbewerb [1] zur Entwicklung eines neuen Hash-Standards ins Leben zu rufen. Vor wenigen Wochen wurde der Sieger gekürt: Der Algorithmus Keccak [2] , entwickelt von einem belgischen Team von Wissenschaftlern. Es ist der zweite Wettbewerb dieser Art: Bereits der symmetrische Verschlüsselungsstandard AES, der heute in fast allen kryptographischen Anwendungen zu finden ist, wurde mithilfe eines ähnlichen Wettbewerbs 2003 verabschiedet.

Fingerabdruck

Doch worum geht es bei kryptographischen Hash-Funktionen eigentlich? Kryptographische Hash-Funktionen bilden eine beliebige Eingabe, etwa eine Datei, auf eine Ausgabe fester Länge ab. Die Ausgabe wird in der Regel als sogenannte Hexadezimalzahl angegeben. Der MD5-Hash des Wortes "Hallo" beträgt etwa d1bf93299de1b68e6d382c893bf1215f. Um als sicher zu gelten, muss eine kryptographische Hash-Funktion zwei Bedingungen erfüllen:

• Nicht umkehrbar: Es soll extrem schwierig sein, bei einem gegebenen Hash eine Eingabe zu finden, die diesen Hash als Ausgabe produziert.
• Kollisionsresistenz: Es soll extrem schwierig sein, zwei Eingaben zu finden, die dieselbe Ausgabe produzieren.

Kryptographische Hash-Funktionen werden zu vielen Zwecken eingesetzt. Der wichtigste sind digitale Signaturen. Signaturverfahren wie RSA werden dabei nicht über die gesamte Eingabe gebildet, sondern nur über den Hash einer Eingabe. Doch auch an vielen anderen Stellen finden Hash-Funktionen Anwendung. Sichere Protokolle wie SSL/TLS sind komplexe Konstruktionen, die Hash-Funktionen als Bausteine für unterschiedliche Zwecke einsetzen.

MD5 gebrochen, SHA-1 gefährdet

Im Jahr 2004 gelang es einem Team um die chinesische Wissenschaftlerin Xiaoyun Wang erstmals, eine praktische Kollision der MD5-Funktion zu zeigen und zwei Eingabedateien zu produzieren, die denselben MD5-Hash besitzen. Doch Warnsignale gab es schon lange: Bereits 1996 warnte der inzwischen verstorbene Bochumer Professor Hans Dobbertin vor Schwächen in MD5.

Die chinesischen Forscher beließen es jedoch nicht beim Angriff auf MD5: Im Jahr 2005 verbesserte Wangs Team bekannte Angriffe gegen den bis dahin als sicher geltenden Standard SHA-1 mehrmals. Zwar blieben diese theoretisch – bis heute konnte noch niemand eine reale Kollision vorführen – doch klar war: Auch SHA-1 konnte mittelfristig nicht mehr als sicher gelten.

Übrig blieben die bis dahin kaum genutzten Hash-Funktionen der SHA-2-Familie mit den Namen SHA-224, SHA-256, SHA-284 und SHA-512. Doch selbst hier schwante manchen Kryptographen Unheil: Denn die Methoden, die bei SHA-2 genutzt werden, unterscheiden sich nur geringfügig von denen in MD5 und SHA-1.

Die US-Behörde NIST kündigte daraufhin an, einen neuen Hash-Standard entwickeln zu wollen. Dafür wurde ein Wettbewerb ausgerufen: Weltweit sollten die besten Kryptografen Vorschläge für den neuen Standard einreichen. Diese wurden auf mehreren Konferenzen diskutiert und auf mögliche Schwächen abgeklopft. Neben den nahe liegenden Gründen war auch der Ruf lautgeworden, generell dem Thema mehr Aufmerksamkeit zu widmen. Kryptografische Hash-Funktionen seien bislang von der Forschung vernachlässigt worden.

64 Vorschläge [3] wurden eingereicht, die sich dann in mehreren Runden zunächst auf 15 und dann auf 5 Finalisten reduzierten. Den Kandidaten, die es in Runde zwei schafften, war es danach erlaubt, kleine Verbesserungen an ihren Algorithmen vorzunehmen, um auf mögliche Kritikpunkte zu reagieren.