SHA-3

SHA-3 ist eine kryptographische Hashfunktion, die von Guido Bertoni, Joan Daemen, Michaël Peeters und Gilles Van Assche unter dem Namen Keccak [kɛtʃak] entwickelt wurde. Keccak gewann 2012 den vom US-amerikanischen NIST organisierten SHA-3-Wettbewerb und wurde am 5. August 2015 als Alternative zu SHA-2 standardisiert.

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	NIST SHA-3 Standard
Länge des Hashwertes (Bit)	je nach Version 224, 256, 384, 512 oder frei wählbar
Konstruktion	Sponge-Konstruktion
Runden	SHA-3: 24 Keccak: 12 bis 24 (abh. von Größe des Zustandsdatenblocks)
Beste bekannte Kryptoanalyse
second preimage attack von Daniel J. Bernstein auf 6 von 24 Runden von SHA3-512 mit 2^506 Funktionsaufrufen und Platzkomplexität 2^176 oder auf 8 Runden mit 2^511,5 Aufrufen und 2^508 Platz

Kryptographische Hashfunktionen werden zum Beispiel für das digitale Signieren eingesetzt. SHA-3 ist die neueste, effizienteste und sicherste Hashfunktion der SHA-Reihe.

Geschichte

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 diese Funktionen sind – ebenso wie ihre Vorläufer MD4, MD5 und SHA-1 – Merkle-Damgård-Konstruktionen mit Davies-Meyer-Kompressionsfunktion. Man befürchtete, dass Angriffe auf diese Vorläufer zu Angriffen gegen SHA-2 modifiziert werden könnten. 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 für die Auswahl der Blockverschlüsselung AES (Advanced Encryption Standard) veranstaltete das NIST von November 2007 bis Oktober 2012 einen Wettbewerb. Von den eingereichten Hashfunktionen wurde gefordert, dass sie Nachrichten bis zu einer Obergrenze von mindestens Bit hashen und mindestens die vier Hash-Längen 224, 256, 384 und 512 Bit unterstützen. Die teilnehmenden Teams von Kryptografen reichten 64 Hashfunktionen ein, wovon 51 die Teilnahmebedingungen erfüllten und für Runde 1 akzeptiert wurden. Nach Analyse der Sicherheit und Performanz in einem offenen Bewertungsprozess, an dem Kryptologen aus aller Welt teilnahmen, wurden 14 Kandidaten für Runde zwei ausgewählt.

Die Teilnehmer durften in jeder Runde des Wettbewerbs Veränderungen an ihren Algorithmen vornehmen, um auf die Ergebnisse der Analysen zu reagieren. Im Fall von Keccak hat man die Zahl der Runden der Permutationsfunktion für eine größere Sicherheitsreserve von 18 auf 24 erhöht und die Länge der Nachrichtenblöcke für einige der Varianten vergrößert und dadurch die Effizienz verbessert.

Im Dezember 2010 wurden die fünf Finalisten bekanntgegeben:

• BLAKE (HAIFA-Konstruktion)
• Grøstl (wide-pipe Merkle-Damgård)
• JH (ähnlich einer Sponge-Konstruktion)
• Keccak (Sponge-Konstruktion)
• Skein (ähnlich HAIFA)

Am 2. Oktober 2012 wurde Keccak zum Gewinner erklärt und wird seitdem als SHA-3 bezeichnet. SHA-3 weist eine hohe kryptografische Sicherheitsreserve auf und ist in Hardware auch effizient implementierbar. Vorteilhaft ist auch der einfache und elegante Aufbau, der die Kryptoanalyse erleichtert. Ein Kritikpunkt ist jedoch, dass die Performanz bei Software-Implementierung im Vergleich zu den anderen Finalisten eher gering ist. Es wurde der Vorwurf erhoben, das NIST würde sein Augenmerk zu sehr auf Implementierungen in Hardware legen.

Funktionsweise

Darstellung der Sponge-Konstruktion

Keccak ist eine sogenannte Sponge-Konstruktion. Ein Zustandsvektor von Bit „absorbiert“ die Nachricht blockweise, die dazu in Blöcke von Bit geteilt wird. Mit jedem Block werden Bit des Zustandsvektors verändert, wonach die Daten im Zustandsvektor durch eine Permutationsfunktion durchmischt werden. Diese ist eine bijektive Abbildung , sie permutiert also die möglichen Zustände des Vektors auf pseudozufällige Weise.

Der Zustandsvektor besteht aus 25 Wörtern mit je Bit und wird mit 0 initialisiert. 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 damit , 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. Bei den Wettbewerbsvarianten ist jeweils . Das angefügte Endstück besteht aus bis Bits mit dem Wert 0, die von 1-Bits eingerahmt werden: . Das erste 1-Bit macht das Nachrichtenende kenntlich, damit Nachrichten, die sich nur durch unterschiedlich viele 0-Bits am Ende unterscheiden, nach der Erweiterung noch verschieden sind. Das 1-Bit am Ende sorgt dafür, dass sich die Varianten mit verschiedener Hash-Länge wie völlig unterschiedliche Hashfunktionen verhalten. Es markiert das Ende des letzten Blocks und ist jeweils an einer anderen Position, da die Nachrichtenblocklänge von der Hash-Länge abhängt. Es wirkt sich somit unterschiedlich auf den Hashprozess aus. Ansonsten könnten zwei (gleiche oder verschiedene) Nachrichten Hash-Werte ergeben, von denen einer ein Anfangsstück des anderen ist.

Die Nachrichtenblöcke werden nun nacheinander in den Zustandsvektor eingearbeitet. Bit des Zustandsvektors werden mit dem Nachrichtenblock bitweise XOR-verknüpft, und dann werden die möglichen Zustände des Zustandsvektors permutiert, was ähnlich wie in einer Blockverschlüsselung (mit konstantem Schlüssel) geschieht. Dazu wird mal (bei SHA-3 also mal) eine Rundenfunktion auf den Zustandsvektor angewandt. Diese ist nach den kryptologischen Prinzipien der Konfusion und der Diffusion entworfen und sorgt dafür, dass die Permutationsfunktion den Zustandsvektor mehrmals vollständig durchmischt und dabei chaotisch verändert.

Nachdem der letzte Block eingearbeitet ist, werden Bit des Zustandsvektors als Hash-Wert ausgelesen, falls ist. Anderenfalls werden die Bits des Hash-Wertes in mehreren Schritten entnommen, maximal Bit in jedem Schritt, und dazwischen werden die Werte des Zustandsvektors wie oben permutiert. Der Gesamtvorgang im Überblick mit als Ursprungsnachricht:

Dabei steht für die Konkatenation (das Aneinanderfügen) von Bitketten, und bezeichnet die ersten Bit von .

Der Wert ist die sogenannte Kapazität, d. h. 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 mit Hash-Länge Bit 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 die für ein gegebenes höchstmögliche Sicherheit gegen jeden Angriff erreicht wird (wegen des Geburtstagsparadoxons kann die Sicherheit gegen Kollisionsangriffe nicht höher als Bit sein).

Permutationsfunktion

Der Datenblock wird permutiert, indem mal (abhängig vom Wortgrößenparameter ) eine Rundenfunktion darauf angewandt wird. Die Rundenfunktion besteht aus fünf aufeinanderfolgenden Operationen, die von den Erfindern mit griechischen Buchstaben bezeichnet wurden. Die Runden unterscheiden sich nur in der Konstante, die in der Iota-Operation mit einem Datenwort verknüpft wird.

Die Wörter des Zustandsvektors werden mit bezeichnet, mit , und ist jeweils der neue Zustandsvektor nach jeder Operation. Alle Indizes werden modulo 5 genommen ( ist ). bedeutet das bitweise XOR, die bitweise Negation, die bitweise UND-Verknüpfung und a die Bitrotation von um Bitpositionen zum höherwertigen Ende hin.

Die Permutationsfunktion als C-Code:

 void keccak_p(uint64_t *a, int rounds = 24) {  //a_{i,j} entspricht a[5*i+j]  uint64_t v[5];  uint64_t lfsr = 1;  for (int r=0 ; r<rounds ; ++r) {  // Theta:  for (int j=0 ; j<5 ; ++j) {  v[j] = 0;  for (int i=0 ; i<5 ; ++i) v[j] ^= a[5*i+j];  }  for (int j=0 ; j<5 ; ++j) {  uint64_t h = v[(j+1) % 5];  h = v[(j+4) % 5] ^ (h << 1 | h >> 63);  for (int i=0 ; i<5 ; ++i) a[5*i+j] ^= h;  }  // Rho und Pi:  int i = 0, j = 1;  v[0] = a[1];  for (int t=1 ; t<25 ; ++t) {  int x = i;  i = (3*i + 2*j) % 5;  j = x;  x = 5*i + j;  uint64_t h = v[0];  v[0] = a[x];  int w = t*(t+1)/2 % 64;  a[x] = h << w | h >> (64-w);  }  // Chi:  for (int i=0 ; i<25 ; i += 5) {  for (int j=0 ; j<5 ; ++j)  v[j] = a[i+j];  for (int j=0 ; j<5 ; ++j)  a[i+j] ^= ~v[(j+1) % 5] & v[(j+2) % 5];  }  // Iota:  for (int w=0 ; w < 64 ; w = 2*w+1) {  a[0] ^= (lfsr & 1) << w;  lfsr <<= 1;  if (lfsr & 0x100) lfsr ^= 0x171;  }  }  } 

Beim Übernehmen eines Nachrichtenblocks werden die ersten 64 Bit aufsteigend mit XOR-verknüpft, das erste Bit also mit dem niederwertigsten in . Danach werden ebenso die folgenden Nachrichtenbits in übernommen. Der Hashwert wird am Ende ebenfalls entnommen.

Standardisierung

Der NIST-Mitarbeiter John Kelsey schlug im August 2013 auf dem „Workshop on Cryptographic Hardware and Embedded Systems 2013“ (CHES 2013) vor, nur die zwei Sicherheitsstufen 128 Bit und 256 Bit zu standardisieren. 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 und die Zahl der zu verarbeitenden Nachrichtenblöcke kleiner 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. Die Autoren von Keccak verteidigten andererseits die vorgeschlagenen Änderungen.

Als Reaktion auf die Kritik entschied sich NIST bei den vier Varianten SHA3-224 bis SHA3-512 gegen die Reduzierung der Kapazität. Diese ist letztlich auch unnötig, da auch die Varianten SHAKE128 und SHAKE256 mit 256 bzw. 512 Bit Kapazität standardisiert wurden. Bis auf die vom Nutzer frei wählbare Hash-Länge entsprechen sie den vorgeschlagenen kapazitätsreduzierten Versionen und bieten somit die gleiche Effizienz.

Standard

Im August 2015 standardisierte das NIST folgende Versionen von SHA3 (alle Angaben in Bit):

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

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 Bits 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 unterschiedlich hashen, 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. Dadurch erreicht man eine Domänentrennung: Nach der Erweiterung kann man der Nachricht ansehen, auf welche der beiden Weisen sie erweitert wurde. Zwei Nachrichten, die auf verschiedene Weise erweitert werden, unterscheiden sich danach also in jedem Fall. Bei der Wahl dieser Padding-Methoden hat man auch an eine spätere Standardisierung von weiteren Hashverfahren auf Keccak-Basis gedacht (z. B. Baum-Hashverfahren).

Auf die Effizienz hat diese Padding-Ä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.

Im Dezember 2016 gab das NIST ein Dokument heraus, in dem weitere von SHA-3 abgeleitete Hashverfahren beschrieben werden. Diese gibt es jeweils in zwei Varianten, mit 256 Bit und 512 Bit Kapazität:

• cSHAKE: ermöglicht explizite Domänentrennung durch einen zusätzlich eingegebenen String
• KMAC: Variante für Keyed-Hash Message Authentication
• KMACXOF: XOF-Version von KMAC mit beliebig erweiterbarer Hash-Ausgabe (entsprechend SHAKE)
• TupleHash und TupleHashXOF: hashen Tupel mit beliebig vielen Strings, wobei verschiedene Tupel unterschiedlich gehasht werden, z. B. auch ("ab", "c") und ("a", "bc") und ("a", "bc", "")
• ParallelHash und ParallelHashXOF: sind dafür ausgelegt, die parallele Rechenfähigkeit moderner CPUs besser zu unterstützen

Weitere Varianten

Die Entwickler von Keccak haben außerdem zwei Baum-Hashverfahren namens KangarooTwelve und MarsupilamiFourteen vorgestellt, die mit einer auf 12 bzw. 14 Runden reduzierten Permutationsfunktion arbeiten, gegenüber 24 Runden bei den übrigen Varianten. Damit nutzen sie die große Sicherheitsreserve von Keccak aus, um die Effizienz zu verbessern.

Sicherheit

SHA-3 besitzt eine sehr hohe Sicherheitsreserve. Die beste bekannte Kryptoanalyse kann nur eine auf 8 (von 24) Runden reduzierte Version von SHA3-512 brechen, und das auch nur mit einem völlig unrealistischen Aufwand von Funktionsaufrufen und einem Speicherplatz von . Das ist nur um den Faktor 1,4 effizienter als ein Brute-Force-Angriff.

Es ist möglich, die Zustandspermutation mit der vollen Zahl von 24 Runden von einer Zufallspermutation zu unterscheiden, was aber etwa Funktionsaufrufe erfordert. Ein Angriff auf SHA-3 selbst ergibt sich daraus nicht.

Weil von den 1600 Zustandsbits immer nur ein Teil (um die Kapazität vermindert) ausgegeben wird, ist SHA-3 immun gegen einen Erweiterungsangriff, bei dem man den Hashwert einer mit erweiterten unbekannten Nachricht unter Kenntnis von deren Hashwert bestimmt.

Weblinks

• Website von Keccak
• The SHA-3 Zoo
• SHA-3 at NIST
• Spezifikationen auf der Keccak-Website

Einzelnachweise

1. NIST, 28. September 2012, archiviert vom Original am 9. Juni 2011; abgerufen am 28. März 2013 (englisch). 
2. SHA-3 Project. NIST, abgerufen am 10. August 2020 (englisch). 
3. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST, 2. Oktober 2012, abgerufen am 3. Oktober 2012 (englisch). 
4. Mourad Gouicem: Comparison of seven SHA-3 candidates software implementations on smart cards. (PDF) Oktober 2010, abgerufen am 14. Februar 2014. 
5. Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche: The Keccak sponge function family. 27. Januar 2011, abgerufen am 3. Oktober 2012 (englisch). 
6. Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche: The Keccak reference. 14. Januar 2011, abgerufen am 2. August 2020 (englisch). 
7. Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles van Assche: Cryptographic sponge functions. 14. Januar 2011, abgerufen am 26. August 2020 (englisch). 
8. Jon Kelsey: SHA3 Past, Present, and Future. Abgerufen am 6. Oktober 2013. 
9. John Kelsey, Bill Burr: SHA3, Where we’ve been, Where we're going. 1. Mai 2013, abgerufen am 18. Juli 2020. 
10. Fabian Scherschel: Kryptographie: NIST will angeblich Sicherheit von SHA-3 schmälern. In: heise online. 30. September 2013, abgerufen am 30. September 2013. 
11. Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche: Yes, this is Keccak! 4. Oktober 2013, abgerufen am 18. Juli 2020. 
12. John Kelsey: Moving Forward with SHA-3. 1. November 2013, abgerufen am 18. Juli 2020. 
13. NIST Computer Security Division (CSD): SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. DRAFT FIPS PUB 202. NIST, Mai 2014, abgerufen am 18. Juli 2020 (englisch). 
14. http://www.nist.gov/itl/csd/201508_sha3.cfm
15. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. FIPS PUB 202. National Institute of Standards and Technology (NIST), August 2015, abgerufen am 8. Januar 2018 (englisch). 
16. John Kelsey, Shu-jen Chang, Ray Perlner: SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash. NIST Special Publication 800-185. NIST, Oktober 2016, abgerufen am 15. Juli 2020 (englisch). 
17. Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche, Ronny Van Keer, Benoit Viguier: KangarooTwelve: fast hashing based on Keccak-p. Abgerufen am 16. Juli 2020 (englisch). 
18. Daniel J. Bernstein: Second preimages for 6 (7? (8??)) rounds of Keccak? In: NIST mailing list. 2010, abgerufen am 15. Juli 2020 (englisch). 
19. Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles van Assche: The Keccak SHA-3 submission. 14. Januar 2011, abgerufen am 15. Juli 2020 (englisch).