SHA-3 ist eine kryptographische Hashfunktion, die von Guido Bertoni, Joan Daemen, Michaël Peeters und Gilles Van Assche unter dem Namen Keccak [] entwickelt wurde. Keccak gewann 2012 den vom US-amerikanischen NIST organisierten SHA-3-Wettbewerb () und wurde am 5. August 2015 als SHA-3 standardisiert.
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 mini|300px|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, ist eine Bittkette aus b Bits mit dem Wert 0, 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. Bei Sponge-Konstruktionen mit Hash-Länge Bit beträgt die Sicherheit gegen Kollisionsangriffe Bit und gegen Urbild-Angriffe Bit, 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.
(Theta): lineare Mischoperation: Paritätsbits jeder 5-Wort-Spalte mit den Wörtern der benachbarten Spalten XOR-verknüpfen
(Rho): Wörter des Zustandsvektors rotieren
die Indizes ergeben sich aus der Matrizengleichung
(Pi): Wörter des Zustandsvektors permutieren
(Chi): nichtlineare Operation
(Iota): XOR-Verknüpfen des Worts mit einer rundenabhängigen Konstanten
Das Bit an Position (mit ) in wird durch Bit eines LFSR mit dem erzeugenden Polynom gegeben. Die übrigen Bits in den sind 0.
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; 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 = a; 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; v = 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 ^= (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 SHA3https://www.nist.gov/itl/csd/201508_sha3.cfm (alle Angaben in Bit):
Name Hash-Längen Nachrichten-blocklänge r Kapazitätc=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.