SHA-3

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
SHA-3 (Keccak)
Entwickler Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche
Veröffentlicht Januar 2011 (3. Version)
Abgeleitet von RadioGatún (Vorgänger)
Zertifizierung SHA-3 Standard
Länge des Hashwertes (Bit) variabel
(üblich sind: 224, 256, 384, 512)
Struktur Sponge-Konstruktion
Runden 24
(12+2ℓ, in SHA-3 ist ℓ = 6)
Beste bekannte Kryptoanalyse
second preimage attack von Daniel J. Bernstein auf 6 von 24 Runden von Keccak-512 mit 2506 Funktionsaufrufen und einer Platzkomplexität von 2176 [1]

SHA-3 ist eine kryptologische Hashfunktion der SHA-Familie, die von Guido Bertoni, Joan Daemen, Michaël Peeters und Gilles Van Assche unter dem Namen Keccak [kɛtʃak],[2] entwickelt wurde. Keccak wurde 2012 von dem US-amerikanischen NIST als Gewinner des SHA-3-Wettbewerbs bekannt gegeben[3] und wird als Alternative zu SHA-2 standardisiert.[4]

Vorgeschichte[Bearbeiten]

Im Jahr 2004 gab es mehrere Durchbrüche bei Angriffen gegen damals weit verbreitete Hash-Funktionen wie MD5 (praktische Kollisionen) und SHA-1 (theoretische Kollision mit großem Aufwand). Zwar existierte die SHA-2-Familie, gegen die es bislang keine praxisrelevanten Angriffe gibt, dennoch bestand der Bedarf nach einem neuen Standard für kryptografische Hash-Funktionen, der die aktuelle Forschung berücksichtigt.

Ähnlich wie beim symmetrischen Kryptosystem Advanced Encryption Standard (AES) veranstaltete das NIST einen Wettbewerb. 64 Teams von Kryptografen reichten Vorschläge ein. 14 Kandidaten wurden für Runde zwei ausgewählt. Im Dezember 2010 wurden die fünf Finalisten bekanntgegeben: Skein, BLAKE, Grøstl, Keccak und JH. Am 2. Oktober 2012 wurde Keccak zum Gewinner ernannt. Der Algorithmus wird seitdem als SHA-3 bezeichnet.[5]

Funktionsweise[Bearbeiten]

Darstellung der Sponge-Konstruktion

Keccak verwendet einen mit 0 initialisierten Zustandsvektor aus 25 Wörtern mit je w = 2^l Bit. Der Wert l \in \{0,1, \ldots 6\} ist ein Parameter des Verfahrens. Der Zustandsvektor ist somit b = 25w Bit lang. Der zweite Parameter ist die Bitlänge n des gewünschten Hash-Wertes. In der zum SHA-3-Wettbewerb eingereichten Variante ist l=6, und die Länge des Hash-Wertes kann 224 bis 512 Bit betragen.

Die Nachricht wird in Abschnitte von r Bit Länge geteilt (mit r=b-c und c = 2n), nachdem sie durch Anfügen der Bitfolge 100\ldots 01 (mit 0 bis r-1 Nullen) auf ein Vielfaches der Länge r erweitert wurde.

Das Verfahren verarbeitet die Nachricht schrittweise. In jedem Schritt wird ein r-Bit-Abschnitt der Nachricht mit r Bit des Zustandsvektors XOR-verknüpft, und dann werden die 2^b Werte des Zustandsvektors permutiert. Das geschieht ähnlich wie in einer typischen Blockverschlüsselung, nur dass die Permutation hier nicht von einem Schlüssel abhängig ist. Dazu wird 12+2l mal eine Rundenfunktion auf den Zustandsvektor angewandt. Nach dem letzten Schritt werden n Bit des Zustandsvektors als Hash-Wert verwendet, falls n \leq r ist. Anderenfalls werden die Bits des Hash-Wertes in mehreren Schritten entnommen, maximal r Bit in jedem Schritt, und dazwischen wird wieder die Permutation der Zustandswerte durchgeführt.

Der Wert c=2n ist die sogenannte Kapazität, die Länge des Teils des Zustandsvektors, der beim XOR-Verknüpfen mit den Nachrichtenabschnitten und bei der Entnahme des Hash-Wertes unberührt bleib. Aus der Kapazität ergibt sich eine Obergrenze für die Sicherheit des Verfahrens gegen Kollisions- und Preimage-Angriffe. Um hinsichtlich der Sicherheit konservativ zu sein, haben die Entwickler die Kapazität auf die doppelte Länge des Hash-Wertes festgelegt.

Kritik[Bearbeiten]

Die vier Versionen des für den SHA-3-Wettbewerb eingereichten Algorithmus Keccak sahen Ausgabelängen von 224 Bit, 256 Bit, 384 Bit und 512 Bit vor, was eine Sicherheit gegen Kollisionsangriffe von 112, 128, 192 bzw. 256 Bit ergibt, wegen des Geburtstagsparadoxons. Der NIST-Mitarbeiter John Kelsey erläuterte im August 2013 auf dem „Workshop on Cryptographic Hardware and Embedded Systems 2013“ (CHES 2013), dass das NIST nur noch die zwei Sicherheitsstufen 128 Bit und 256 Bit standardisieren wolle.[6] Weiterhin wurden im Rahmen des Standardisierungsprozesses Änderungen an den Parametern vorgenommen, die laut NIST die Ausführungsgeschwindigkeit erhöhen. Einige Forscher kritisierten, dass dies die Sicherheit beeinträchtigt und es sich dabei auch nicht mehr um den bereits ausführlich untersuchten, ursprünglichen Algorithmus handeln würde.[7] In der Präsentation wird vorgeschlagen, die Kapazität c zu halbieren, weil dann ein Preimage-Angriff bei Sponge-Konstruktionen wie Keccak genauso schwierig sei wie ein Kollisionsangriff. Diese Änderung ist substantiell, allerdings ist die ursprüngliche Sicherheitsmarge grundsätzlich sehr konservativ gewählt.

Ein Kritikpunkt am Gewinner selbst ist, dass er - im Vergleich zu den anderen Finalisten - in Software implementiert eine geringere Performanz aufweist. [8] Es wurde der Vorwurf laut, das NIST würde sein Augenmerk zu sehr auf Implementierungen in Hardware legen.

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Daniel J. Bernstein: Second preimages for 6 (7? (8??)) rounds of Keccak? veröffentlicht auf der NIST mailing list 2010
  2. Guido Bertoni, Joan Daemen, Michaël Peeters und Gilles Van Assche: The Keccak sponge function family. 27. Januar 2011, abgerufen am 3. Oktober 2012 (englisch).
  3. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST, 2. Oktober 2012, abgerufen am 3. Oktober 2012 (englisch).
  4. NIST's Policy on Hash Functions. NIST, 28. September 2012, abgerufen am 28. März 2013 (englisch).
  5. SHA-3 WINNER. Abgerufen am 2. Oktober 2012.
  6. SHA3 Past, Present, and Future. Abgerufen am 6. Oktober 2013.
  7. Fabian Scherschel: Kryptographie: NIST will angeblich Sicherheit von SHA-3 schmälern. In: heise online. 30. September 2013, abgerufen am 30. September 2013.
  8. Comparison of seven SHA-3 candidates software implementations on smart cards. Abgerufen am 14. Februar 2014.