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)
Konstruktion 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 wurde am 5. August 2015 als Alternative zu SHA-2 standardisiert.[4]

Vorgeschichte[Bearbeiten | Quelltext 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). Unter anderem wurden grundlegende Schwächen der Merkle-Damgård-Konstruktion gefunden, durch die der Rechenaufwand für bestimmte Angriffs-Szenarien vermindert wird, wenn auch nicht unbedingt in einem Maß, dass der Angriff praktisch durchführbar wäre. Zwar existierte die SHA-2-Familie, gegen die es bislang keine praxisrelevanten Angriffe gibt, aber es bereitet eine gewisse Sorge, dass diese Funktionen ebenso wie ihre Vorläufer MD4, MD5 und SHA-1 Merkle-Damgård-Konstruktionen mit Davies-Meyer-Kompressionsfunktion sind. Angriffe auf diese Vorläufer könnten somit auch gegen SHA-2 anwendbar sein. Wenn sich auch SHA-2 als gefährdet bzw. unsicher erweisen sollte, hätte man keine standardisierte und als sicher anerkannte kryptologische Hashfunktion zur Verfügung. Deshalb beschloss man, einen neuen Standard zu schaffen, der die aktuelle Forschung berücksichtigt und zukunftssicherer als SHA-2 ist.

Ähnlich wie beim symmetrischen Kryptosystem Advanced Encryption Standard (AES) veranstaltete das NIST einen Wettbewerb. 64 Teams von Kryptografen reichten ihre Hash-Funktionen 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 erklärt und wird seitdem als SHA-3 bezeichnet.[5]

Funktionsweise[Bearbeiten | Quelltext bearbeiten]

Darstellung der Sponge-Konstruktion

Keccak verwendet einen mit 0 initialisierten Zustandsvektor aus 25 Wörtern mit je Bit. Der Wert ist ein Parameter des Verfahrens. Der Zustandsvektor ist somit Bit lang. Der zweite Parameter ist die Bitlänge n des gewünschten Hash-Wertes. In der zum SHA-3-Wettbewerb eingereichten Variante ist , und die Länge des Hash-Wertes variiert von bis .

Die Nachricht wird in Blöcke von Bit Länge geteilt (mit und ), nachdem sie durch Anfügen der Bitfolge (mit bis Nullen) auf ein Vielfaches der Länge erweitert wurde. Das erste 1-Bit macht das Nachrichtenende kenntlich, so dass verschieden lange Nachrichten auch verschiedene Hash-Werte ergeben. Das 1-Bit am Ende garantiert, dass, wenn die Hash-Länge und damit auch die Länge der Nachrichtenblöcke verschieden ist, die berechneten Hash-Werte sich völlig unterscheiden und nicht, wie es sonst passieren könnte, einer ein Anfangsstück des anderen ist.

Das Verfahren verarbeitet die Nachricht schrittweise. In jedem Schritt wird ein r-Bit-Block der Nachricht mit r Bit des Zustandsvektors XOR-verknüpft, und dann werden die möglichen Zustände des Bit langen 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 mal eine Rundenfunktion auf den Zustandsvektor angewandt. Nach dem letzten Schritt werden n Bit des Zustandsvektors als Hash-Wert verwendet, falls ist. Anderenfalls werden die Bits des Hash-Wertes in mehreren Schritten entnommen, maximal r Bit in jedem Schritt, und dazwischen werden wieder die Zustandswerte permutiert.

Der Wert ist die sogenannte Kapazität, die Größe des Teils des Zustandsvektors, der beim XOR-Verknüpfen mit den Nachrichtenblöcken und bei der Entnahme des Hash-Wertes unberührt bleibt. Man kann beweisen, dass bei Sponge-Konstruktionen die Sicherheit gegen Kollisionsangriffe Bit und gegen Urbild-Angriffe Bit beträgt, vorausgesetzt, die Permutation der Zustandswerte ist nicht von einer Zufallspermutation unterscheidbar. Um hinsichtlich der Sicherheit konservativ zu sein, haben die Entwickler die Kapazität auf die doppelte Länge des Hash-Wertes festgelegt(), wodurch für gegebenes die maximal mögliche Sicherheit gegen jeden Angriff erreicht wird (wegen des Geburtstagsparadoxons kann die Sicherheit gegen Kollisionsangriffe nicht höher als Bit sein).

Rundenfunktion[Bearbeiten | Quelltext bearbeiten]

Die Rundenfunktion besteht aus fünf aufeinanderfolgenden Operationen, die von den Erfindern mit griechischen Buchstaben bezeichnet wurden. Die Wörter des Zustandsvektors werden mit bezeichnet, mit . Alle Indizes werden modulo 5 genommen:

(Theta): lineare Mischoperation: Parität einer 5-Wort-Spalte mit den benachbarten Spalten XOR-verknüpfen
(Rho): Wörter des Zustandsvektors rotieren
die Indizes ergeben sich aus der Matrizengleichung , deren Komponenten modulo 5 genommen werden
(Pi): Wörter des Zustandsvektors permutieren
(Chi): nichtlineare Operation
(Iota): XOR-Verknüpfen mit einer rundenabhängigen Konstanten

Dabei bezeichnet das bitweise XOR, die bitweise Negation, die bitweise UND-Verknüpfung und a die Bitrotation von um Bitpositionen zum höherwertigen Ende hin.

Kritik[Bearbeiten | Quelltext bearbeiten]

Der NIST-Mitarbeiter John Kelsey schlug im August 2013 auf dem „Workshop on Cryptographic Hardware and Embedded Systems 2013“ (CHES 2013) vor, nur noch die zwei Sicherheitsstufen 128 Bit und 256 Bit zu standardisieren.[6] Die Kapazität c sollte für die kleineren Varianten SHA3-224 und SHA3-256 auf 256 Bit und für die beiden größeren auf 512 Bit vermindert werden. Das verbessert die Ausführungsgeschwindigkeit, weil die Nachrichtenblocklänge r entsprechend größer wird, die Nachricht also in weniger Schritten verarbeitet wird. Ein Urbild-Angriff wäre damit immer noch mindestens genauso schwierig wie ein Kollisionsangriff, auf welchen die Änderung keine Auswirkung hätte.

Einige Forscher kritisierten diese Verminderung der Sicherheit und bemängelten das Verfahren, den Gewinner des Wettbewerbs nachträglich zu ändern, so dass es sich dabei nicht mehr um den ausführlich untersuchten, ursprünglichen Algorithmus handeln würde.[7] Die Autoren von Keccak verteidigten andererseits die vorgeschlagenen Änderungen.[8] Als Reaktion auf die Kritik entschied NIST, die Kapazität bei den vier Varianten SHA3-224 bis SHA3-512 doch nicht zu reduzieren.[9][10]

Ein Kritikpunkt an Keccak selbst ist, dass es – im Vergleich zu den anderen Finalisten – in Software implementiert eine geringere Performanz aufweist.[11] Es wurde der Vorwurf laut, das NIST würde sein Augenmerk zu sehr auf Implementierungen in Hardware legen.

Standardisierung[Bearbeiten | Quelltext bearbeiten]

Im August 2015 gab das NIST den endgültigen Standard heraus, der folgende Versionen von SHA3 vorsieht:[12]

Name Hash-Länge Nachrichten-Blocklänge Kapazität c Sicherheit
(Kollision)
Sicherheit
(Urbild)
Padding-Schema
SHA3-224 224 1152 448 112 224 0110*1
SHA3-256 256 1088 512 128 256 0110*1
SHA3-384 384 832 768 192 384 0110*1
SHA3-512 512 576 1024 256 512 0110*1
SHAKE128 variabel (n) 1344 256 min(n/2, 128) min(n, 128) 111110*1
SHAKE256 variabel (n) 1088 512 min(n/2, 256) min(n, 256) 111110*1

alle Angaben in Bit

Damit die SHA3- und die SHAKE-Varianten garantiert verschiedene Hashwerte liefern, hat man das Schema, mit dem die Nachrichten erweitert werden, geändert. Bei SHA3 wird die Bitfolge 011 angehängt und bei SHAKE hingegen 11111, bevor mit Null-Bits aufgefüllt und am Ende noch ein 1-Bit angefügt wird. Diese Padding-Methoden berücksichtigen außerdem eine später mögliche Standardisierung von Baum-Hashverfahren auf Keccak-Basis.

Auf die Effizienz hat diese Änderung in der Praxis keine Auswirkung, da die Nachricht meist aus ganzen Bytes besteht, ebenso wie die Nachrichtenblocklänge r. Die Zahl der im letzten Block freien Bits ist also ein Vielfaches von 8. Entweder muss für die Paddingbits ohnehin ein weiterer Nachrichtenblock angefügt werden, oder im letzten Block ist mindestens ein Byte frei, das die Paddingbits vollständig aufnehmen kann. Im Vergleich zum originalen Keccak-Padding erhöht sich die Zahl der Nachrichtenblöcke also in keinem Fall.

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext 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, 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. Jon Kelsey: 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. Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche: The Keccak sponge function family
  9. Moving Forward with SHA-3.
  10. NIST Computer Security Division (CSD): SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. NIST.
  11. Mourad Gouicem: Comparison of seven SHA-3 candidates software implementations on smart cards. Abgerufen am 14. Februar 2014 (PDF).
  12. http://www.nist.gov/itl/csd/201508_sha3.cfm