Keccak

aus SecuPedia, der Plattform für Sicherheits-Informationen

Anzeige
Wechseln zu: Navigation, Suche

Keccak ist eine Hash-Funktion, die im Oktober 2012 vom National Institute of Standards and Technology (NIST) als SHA-3 (SHA=Secure Hash Algorithm) Standard ausgewählt wurde [1]. Anlass für die Neuausschreibung des Standards war ein von chinesischen Kryptologen [2] 2005 als theoretische Möglichkeit veröffentlichter, aber von der Fachwelt als realistisch anerkannter Angriff auf die Hash-Funktion SHA-1. Sie war zu der Zeit am weitesten verbreitet. Der Angriff stellte aber zunächst auch die Sicherheit anderer Hash-Funktionen in Frage, darunter die des bis dahin modernsten Standards SHA-2.

Beschreibung

Hans-Joachim Knobloch (Secorvo Security Consulting, Karlsruhe) berichtete Anfang 2013 in der Fachzeitschrift kes [3]wie folgt über Geschichte und Funktionsweise des neuen Standards (gekürzte Wiedergabe):

Der Sicherheitsvorteil von Keccak ist, dass er … ein anderes Konstruktionsprinzip verfolgt als SHA-1 und SHA-2, nämlich die von den Keccak-Autoren Guido Bertoni, Joan Daemen, Michaël Peeters und Gilles Van Assche entwickelte Schwammkonstruktion (Sponge-Konstruktion) [4].

Diese Konstruktion ist resistent gegen die Verlängerungsangriffe, unter denen Merkle-Damgård-Hash-Funktionen leiden. So werden sichere schlüsselabhängige Kryptoprüfsummen effizienter möglich als mit einem „Keyed-Hash Message Authentication Code (HMAC)“-Verfahren [5], das zwei Aufrufe der Hash-Funktion erfordert. Vor allem aber besteht die berechtigte Hoffnung, dass künftige Angriffe gegen SHA-2 nicht durch weitere Verbesserung des ihnen zugrunde liegenden kryptoanalytischen Prinzips auf SHA-3 übertragbar sind. Bei den Vorgängern ist die Gefahr einer solchen Übertragung der Angriffe von SHA-0 auf SHA-1 und weiter auf SHA-2 deutlich wahrscheinlicher.

Zudem kann die Schwammkonstruktion selbst bei identischer Schwammfunktion durch Änderung von untergeordneten Parametern wie der relativen Größe der r- und c-Anteile des internen Zustands flexibel an unterschiedlichen Sicherheitsbedarf angepasst werden.

Leider ist SHA-3 nicht durchgängig performanter als SHA-2. Keccak ist besonders effizient in Hardware zu implementieren, nicht ganz so gut in Software. Eigentlich kein Wunder, wenn man bedenkt, dass seine Autoren – darunter mit Joan Daemen einer der Erfinder des AES-Gewinners Rijndael – bei den Hardware-Herstellern STMicroelectronics und NXP Semiconductors arbeiten, die beide auch Security-Chips im Portfolio haben.


Schutz gegen Angriffe

Doch während viele Anwendungen wie beispielsweise Netzwerk-Chips mit eingebauter VPN-Funktion von einer in Hardware extrem schnellen Hash-Funktion profitieren, ist es gerade diese gute Implementierbarkeit in Hardware, die auch sehr schnell Verschwörungstheoretiker auf den Plan ruft. Denn wenn SHA-3 zur Einwegverschlüsselung von Passwörtern genutzt wird, können schnelle SHA-3-Chips die Arbeit von professionellen Passwort-Knackern – zu denen mutmaßlich auch der mit dem NIST verschwägerte amerikanische Aufklärungsdienst NSA gehört – deutlich erleichtern. Allerdings kann man sich als Anwender durch das Hinzufügen eines Klartextzufallswerts zur Individualisierung jedes Passworteintrags (Salting) und eine vielfache Hintereinanderausführung der Hash-Funktion für jedes einzelne Passwort (Stretching) effektiv auch gegen noch so schnelle SHA-3-Chips schützen. Gleiches gilt auch für die bekannt gewordene 21-prozentige Optimierung beim Brechen von per SHA-1 einwegverschlüsselten Passwörtern [6] – Salting und ausreichendes Stretching machen jede Optimierung zunichte.


Funktionsweise

Keccak ist nicht als ein eindeutiger Algorithmus definiert, sondern als Algorithmenfamilie mit verschiedenen Auslegungsparametern (z. B. Wortlänge, Rundenzahl), durch deren Variation sich Tausende von mehr oder minder verschiedenen Hash-Funktionen ergeben [7].

Keccak/SHA-3 ist ein Hashalgorithmus nach der Schwammkonstruktion mit einem internen Zustand von 1600 Bit, die anfänglich alle Null sind. Der Anteil der Kapazität c an diesen 1600 Bit ist jeweils das Doppelte der Ausgabelänge. Das heißt umgekehrt, dass SHA-3 mit 224, 256, 384 und 512 Bit Ausgabelänge in der „Aufsaug“-Phase jeweils Nachrichtenhappen von 1152, 1088, 832 beziehungsweise 576 Bit auf einmal verarbeitet. Für die gleiche Nachricht braucht SHA-3 also um so länger, je größer der benötigte Hashwert ist. Am Ende der Nachricht wird der letzte Eingabeblock durch Padding mit zwei 1-Bits und dazwischen so vielen 0-Bits aufgefüllt, wie nötig sind, um auf eine glatte Blockgrenze zu kommen.


Rundenfunktion

Die Schwammfunktion f von Keccak/SHA-3 arbeitet auf diesem Zustand von 1600 Bit, die dazu als Quader aus 5x5 64-Bit-Worten arrangiert werden. f wiederum besteht aus 24 Wiederholungen (Kryptologen sprechen gerne von „Runden“) einer Rundenfunktion R, die diesen Zustandsquader verändert. Das sind mehr als doppelt so viele Runden, wie nach heutigem Kenntnisstand nötig wären, damit die besten bekannten Angriffsansätze gegen R wirkungslos werden.

Die Rundenfunktion ihrerseits setzt sich aus fünf hintereinander ausgeführten Einzelschritten zusammen, die von den Keccak-Autoren θ, ρ, π, χ und ι getauft wurden.

θ invertiert jedes einzelne Bit des Zustands abhängig von der Paritätssumme von zwei 5-Bit-Spalten aus der vorherigen und nachfolgenden 5x5-Bit-Scheibe des Zustandsquaders. So wird schon nach wenigen Runden eine gute Diffusion, das heißt ein „Verschmieren“ jedes einzelnen Ausgangsbits über den gesamten Zustandsquader erreicht.

ρ rotiert die 25 einzelnen 64-Bit-Worte des Zustandsquaders nach einem vorgegebenen Muster unterschiedlich weit zyklisch durch. Dadurch werden die Bits innerhalb einer jeden 5x5-Bit-Scheibe immer wieder neu zusammengewürfelt und die Diffusion durch θ, das ja auf diesen Bit-Scheiben operiert, weiter verbessert.

π wiederum vertauscht die 64-Bit-Worte innerhalb der 5x5-Schichtung nach einem komplexen, aber regelmäßigen Muster, das nur das innere Wort an seinem Platz belässt. Auch hierdurch wird über viele Runden hinweg die Diffusion weiter verbessert.

χ ist die nichtlineare Komponente einer jeden Runde, das heißt die Teilfunktion, bei der nicht einfach jedes Ausgabebit als XOR-Summe verschiedener Eingabebits dargestellt werden kann. Gäbe es χ nicht, wäre die ganze Schwammfunktion f als großes, aber lösbares lineares Gleichungssystem aus einzelnen Bits darstellbar und auf diesem Wege zu brechen. χ addiert zu jedem 64-Bit-Wort per XOR die „Not a AND b“-Verknüpfung der beiden folgenden Worte a und b aus der jeweiligen 5er-Zeile des Zustandsquaders.

ι schließlich addiert (wieder bitweise per XOR) zum 0., 1., 3., 7., 15., 31. und 63. Bit des 64‑Bit-Worts „links unten“ eine – für jede der 24 Runden unterschiedliche – 7-Bit-Rundenkonstante. Dieser Schritt sorgt dafür, dass eventuelle Symmetrien im Zustandsquader, die sich durch von einem Angreifer gezielt gewählte Eingabewerte ergeben könnten, schon nach wenigen Runden verschwinden. Eine der Besonderheiten von Keccak ist, dass diese Rundenkonstanten als Ausgabe eines kurzen, linear rückgekoppelten Schieberegisters definiert sind, sodass sie mit wenigen Schaltkreisen oder Prozessorbefehlen „just in time“ für jede Runde neu berechnet werden können, anstatt sie als Tabelle im Speicher zu halten.


Implementierung

Die allermeisten Anwender sollten jedoch gar nicht erst versuchen, SHA-3 selbst zu implementieren. Die Keccak-Autoren stellen optimierte Referenzimplementierungen für verschiedene Prozessorarchitekturen von 8- bis 64-Bit-CPUs und auch in der Hardware-Beschreibungssprache VHDL bereit. Bei diesen Referenzimplementierungen wurde bereits auf die Widerstandskraft gegen moderne Seitenkanalattacken, wie Timing-Analyse durch datenabhängige Sprünge oder Cache-Misses bei großen Tabellen sowie Power-Analyse geachtet.


Frage der Dringlichkeit

Anders als dies beim Start des SHA-3-Auswahlwettbewerbs im Jahr 2007 zu befürchten war, ist die Weiterentwicklung und Verfeinerung von Angriffen gegen Hash-Funktionen der Merkle-Damgård-Reihe seit einiger Zeit ins Stocken geraten. Die SHA-2-Familie von Hash-Funktionen kann nach heutiger Sicht immer noch als sicher für die kommenden Jahre gelten. Das NIST sieht daher den sehr ressourcenhungrigen SHA-3 ausdrücklich als Ergänzung zum SHA-2 für Anwendungsfelder, in denen die Vorteile von Keccak zum Tragen kommen, beispielsweise für Krypto-Chips.

Daneben ist der neue Standard eine Rückversicherung für den Fall, dass eines Tages doch ein erfolgreicher Angriff gegen SHA-2 entdeckt wird. Angesichts der Vorlaufzeit von der Inkraftsetzung eines Krypto-Standards bis zur praktischen Unterstützung durch marktgängige Produkte scheint es auch äußerst ratsam, bereits jetzt mit dem Etablieren dieser Rückversicherung zu beginnen.

Wie lange es dauert, bis eine neue Krypto-Hashfunktion tatsächlich in der Praxis genutzt werden kann, ohne Interoperabilitätsprobleme zu befürchten, zeigt sich am SHA-2: Die ersten Mitglieder der SHA-2-Familie wurden im Jahr 2002 standardisiert. Zehn Jahre später sind immer noch fast alle SSL/TLS-Serverzertifikate öffentlicher Server unter Nutzung des SHA-1 erstellt, weil manche älteren Browser- und Betriebssystem-Versionen die betreffenden Zertifikate mangels Unterstützung von SHA-2 nicht interpretieren und als ungültig ablehnen.

Da die Attacken, die zum SHA-3 Wettbewerb führten, die starke Kollisionsresistenz betreffen, sollte man sich als Anwender vergegenwärtigen, dass viele Anwendungen wie die Einwegverschlüsselung von Passwörtern und Prüfsummen bei SSL/TLS oder IPsec nicht direkt davon betroffen sind. Und selbst bei direkt betroffenen Anwendungen wie dem Ausstellen von Public-Key-Zertifikaten ist keine übertriebene Sorge angebracht: Zertifikate, die vor der Entwicklung einer erfolgreichen Attacke erstellt wurden, bleiben sicher, solange diese Attacke sich nicht auch gegen die schwache Kollisionsresistenz richtet.

Für die Sicherheit von realen Anwendungen ist daher ein möglichst zügiger Wechsel von SHA-1 auf SHA-2 (je nach Anwendung z. B. SHA-256 oder SHA-512) viel wichtiger als das Warten auf erste Implementierungen von SHA-3. Und bei der Einwegverschlüsselung von Passwörtern sollte man ohnehin auf Salting und Stretching setzen, egal welche Krypto-Hashfunktion verwendet wird.


Einzelnachweis

  1. NIST: SHA-3 Selection Announcement, 2. Okt. 2012, http://csrc.nist.gov/groups/ST/hash/sha-3/sha-3_selection_announcement.pdf
  2. Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Wu: Finding Collisions in the Full SHA-1, 1. Juni 2005, www.cryptome.org/wang_sha1_v2.zip
  3. Hans-Joachim Knobloch: „Schwamm drüber – Funktionsweise von SHA-3 (Keccak)“ in „kes – Die Zeitschrift für Informationssicherheit“ 1/2013, S. 10 ff
  4. Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche: Cryptographic Sponge Functions, Ver. 0.1, 14. Jan. 2011, http://sponge.noekeon.org/CSF-0.1.pdf
  5. Hugo Crawczyk, Mihir Bellare, Ran Canetti: RFC 2104 – HMAC: Keyed Hashing for Message Authentication, Februar 1997, www.ietf.org/rfc/rfc2104.txt
  6. Jens Steube: Exploiting a SHA1 Weakness in Password Cracking, 4. Dez. 2012, http://hashcat.net/p12/js-sha-1exp_169.pdf
  7. Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche: The Keccak reference, Ver. 3, 14. Jan. 2011, http://keccak.noekeon.org/Keccak-reference-3.0.pdf


Siehe übergeordnete Stichworte


Siehe auch



Diese Seite wurde zuletzt am 31. Januar 2017 um 14:23 Uhr von Oliver Wege geändert. Basierend auf der Arbeit von Peter Hohl.

Anzeigen