SHA-3 ist eine kryptologische Hashfunktion der SHA-Reihe, 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]

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 Angriffsszenarien vermindert wird, wenn auch nicht unbedingt in einem Maß, dass der Angriff praktisch durchführbar wäre. Zwar existiert die SHA-2-Familie, gegen die es bislang keine praxisrelevanten Angriffe gibt, aber es bereitet eine gewisse Sorge, da 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 also möglicherweise zu Angriffen gegen SHA-2 modifiziert werden. 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]

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 des gewünschten Hash-Wertes. In den zum SHA-3-Wettbewerb eingereichten Varianten ist , und die Länge des Hash-Wertes beträgt oder .

Die Nachricht wird durch Anfügen eines Endstückes auf ein Vielfaches von Bit verlängert und dann in Blöcke der Länge Bit geteilt, mit als drittem Parameter des Verfahrens. Es muss sein, und bei den Wettbewerbsvarianten ist . Anschließend wird die Nachricht schrittweise verarbeitet, ein Block in jedem Schritt.

Das angefügte Endstück hat die Form , mit bis 0-Bits. Das erste 1-Bit macht das Nachrichtenende kenntlich, damit auch Nachrichten, die sich nur durch unterschiedlich viele 0-Bits am Ende unterscheiden, unterschiedlich gehasht werden und somit auch verschiedene Hash-Werte ergeben (vorbehaltlich einer möglichen, aber extrem unwahrscheinlichen Hashkollision). Das 1-Bit am Ende garantiert, dass die Hash-Werte unterschiedlich berechnet werden, wenn die Hash-Länge und damit auch die Länge der Nachrichtenblöcke verschieden ist. Anderenfalls wäre beim Hashen derselben Nachricht mit verschiedenen Versionen des Verfahrens ein Hashwert ein Anfangsstück des anderen, wenn in beiden Fällen die Nachricht nur einen Block lang ist.

In jedem Schritt des Verfahrens wird ein Bit langer Block der Nachricht mit 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 Bit des Zustandsvektors als Hash-Wert verwendet, falls ist. Anderenfalls werden die Bits des Hash-Wertes in mehreren Schritten entnommen, maximal 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).

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ätsbit 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.

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.

Im August 2015 gab das NIST den endgültigen Standard heraus, der folgende Versionen von SHA3 vorsieht^[12][13] (alle Angaben in Bit):

Die Varianten SHAKE128 und SHAKE256 sind sogenannte extendable output functions (XOFs; Funktionen mit erweiterbarer Ausgabe). Die Länge des Hashwertes ist nicht von vornherein festgelegt, sondern es können nach dem Einarbeiten der Nachricht in den Datenblock beliebig viele Hash-Daten entnommen werden. Nach immer 1344 bzw. 1088 entnommenen Bit wird der Datenblock erneut permutiert, wie oben beschrieben. Diese Varianten arbeiten als kryptographisch sichere Pseudozufallszahlengeneratoren, mit der gehashten Nachricht als Saat.

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 0-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 keine Auswirkung, wenn die Nachricht aus ganzen Bytes besteht, was in der Praxis fast immer der Fall ist. Auch die Nachrichtenblocklänge r ist ein Vielfaches von acht, und somit auch die Zahl der im letzten Block freien Bits. 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.

• Website von Keccak
• The SHA-3 Zoo
• SHA-3 at NIST

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. Abgerufen im 1. Januar 1 
10. ↑ NIST Computer Security Division (CSD): SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. NIST; abgerufen im 1. Januar 1 
11. ↑ Mourad Gouicem: Comparison of seven SHA-3 candidates software implementations on smart cards. (PDF) Abgerufen am 14. Februar 2014. 
12. ↑ http://www.nist.gov/itl/csd/201508_sha3.cfm
13. ↑ SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. In: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. National Institute of Standards and Technology, August 2015, abgerufen am 8. Januar 2018 (englisch).