SHA-3

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 2506 Funktionsaufrufen und Platzkomplexität 2176 oder auf 8 Runden mit 2511,5 Aufrufen und 2508 Platz

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.

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 $2^{64}-1$ 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 $b$ Bit „absorbiert“ die Nachricht blockweise, die dazu in Blöcke von $r<b$ Bit geteilt wird. Mit jedem Block werden $r$ Bit des Zustandsvektors verändert, wonach die Daten im Zustandsvektor durch eine Permutationsfunktion durchmischt werden. Diese ist eine bijektive Abbildung $f:\{0,1\}^{b}\rightarrow \{0,1\}^{b}$, sie permutiert also die $2^{b}$ möglichen Zustände des Vektors auf pseudozufällige Weise.

Der Zustandsvektor besteht aus 25 Wörtern mit je $2^{l}$ Bit und wird mit 0 initialisiert. Der Wert $l\in \{0,1,\ldots ,6\}$ ist ein Parameter des Verfahrens. Der Zustandsvektor ist somit $b=25\cdot 2^{l}$ Bit lang. Der zweite Parameter ist die Bitlänge $n$ des gewünschten Hash-Wertes. In den zum SHA-3-Wettbewerb eingereichten Varianten ist $l=6$ und damit $b=1600$, und die Länge des Hash-Wertes beträgt $n=224,256,384$ oder $512$.

Die Nachricht wird durch Anfügen eines Endstückes auf ein Vielfaches von $r$ Bit verlängert und dann in Blöcke der Länge $r$ Bit geteilt, mit $r$ als drittem Parameter des Verfahrens. Bei den Wettbewerbsvarianten ist jeweils $r=b-2n$. Das angefügte Endstück besteht aus $0$ bis $r-1$ Bits mit dem Wert 0, die von 1-Bits eingerahmt werden: $100\ldots 01$. 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 $r$ von der Hash-Länge $n$ 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. $r$ Bit des Zustandsvektors werden mit dem Nachrichtenblock bitweise XOR-verknüpft, und dann werden die $2^{b}$ möglichen Zustände des Zustandsvektors permutiert, was ähnlich wie in einer Blockverschlüsselung (mit konstantem Schlüssel) geschieht. Dazu wird $12+2l$ mal (bei SHA-3 also $24$ 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 $n$ Bit des Zustandsvektors als Hash-Wert ausgelesen, falls $n\leq r$ ist. Anderenfalls werden die Bits des Hash-Wertes in mehreren Schritten entnommen, maximal $r$ Bit in jedem Schritt, und dazwischen werden die Werte des Zustandsvektors wie oben permutiert. Der Gesamtvorgang im Überblick mit $m$ als Ursprungsnachricht:

$m\,\|\,10^{j}1=m_{1}\,\|\,m_{2}\,\|\,\cdots \,\|\,m_{k};\quad |m_{i}|=r,\,j<r$

$s_{0}=0^{b}$

$s_{i}=f(s_{i-1}\oplus (m_{i}\,\|\,0^{b-r}));\quad i=1,2,\cdots ,k$

$h=\operatorname {trunc} (s_{k},r)\,\|\,\operatorname {trunc} (f(s_{k}),r)\,\|\,\operatorname {trunc} (f(f(s_{k})),r)\,\|\,\cdots$

$hash=\operatorname {trunc} (h,n)$

Dabei steht $\|$ für die Konkatenation (das Aneinanderfügen) von Bitketten, und $\operatorname {trunc} (x,n)$ bezeichnet die ersten $n$ Bit von $x$.

Der Wert $c=b-r$ 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 $n$ Bit die Sicherheit gegen Kollisionsangriffe $\min(n/2,c/2)$ Bit und gegen Urbild-Angriffe $\min(n,c/2)$ 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($c=2n$), wodurch die für ein gegebenes $n$ höchstmögliche Sicherheit gegen jeden Angriff erreicht wird (wegen des Geburtstagsparadoxons kann die Sicherheit gegen Kollisionsangriffe nicht höher als $n/2$ Bit sein).

Permutationsfunktion

Der Datenblock wird permutiert, indem $12+2l$ mal (abhängig vom Wortgrößenparameter $l$) 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 $a_{i,j}$ bezeichnet, mit $i,j\in \{0,1,2,3,4\}$, und ${\overline {a}}_{i,j}$ ist jeweils der neue Zustandsvektor nach jeder Operation. Alle Indizes werden modulo 5 genommen ($a_{2,-1}$ ist $a_{2,4}$). $\oplus$ bedeutet das bitweise XOR, $\neg$ die bitweise Negation, $\&$ die bitweise UND-Verknüpfung und a $\lll w$ die Bitrotation von $a$ um $w$ Bitpositionen zum höherwertigen Ende hin.

$\theta$ (Theta): lineare Mischoperation: Paritätsbits jeder 5-Wort-Spalte mit den Wörtern der benachbarten Spalten XOR-verknüpfen

$p_{j}\,\leftarrow \,a_{0,j}\oplus a_{1,j}\oplus a_{2,j}\oplus a_{3,j}\oplus a_{4,j}$

${\overline {a}}_{i,j}\,\leftarrow \,a_{i,j}\oplus p_{j-1}\oplus (p_{j+1}\lll 1)$

$\rho$ (Rho): Wörter des Zustandsvektors rotieren

${\overline {a}}_{i,j}\,\leftarrow \,a_{i,j}\lll (w_{i,j}\,{\bmod {\,}}2^{l});\;w_{0,0}=0;\;w_{i,j}={\frac {(t+1)(t+2)}{2}};\;t\in \{0,\dots ,23\};$

die Indizes $i,j$ ergeben sich aus der Matrizengleichung ${\binom {i}{j}}={\begin{pmatrix}3&2\\1&0\end{pmatrix}}^{t}\cdot {\binom {0}{1}}$

$\pi$ (Pi): Wörter des Zustandsvektors permutieren

${\overline {a}}_{3i+2j,i}\,\leftarrow \,a_{i,j}$

$\chi$ (Chi): nichtlineare Operation

${\overline {a}}_{i,j}\,\leftarrow \,a_{i,j}\oplus (\neg a_{i,j+1}\;\&\;a_{i,j+2})$

$\iota$ (Iota): XOR-Verknüpfen des Worts $a_{0,0}$ mit einer rundenabhängigen Konstanten

${\overline {a}}_{0,0}\,\leftarrow \,a_{0,0}\oplus C_{r};\;r=0,1,\dots ,11+2l$

Das Bit an Position $2^{m}-1$ (mit $0\leq m<7$) in $C_{r}$ wird durch Bit $7r+m$ eines LFSR mit dem erzeugenden Polynom $x^{8}+x^{6}+x^{5}+x^{4}+1$ gegeben. Die übrigen Bits in den $C_{r}$ 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[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 $a_{0,0}$ XOR-verknüpft, das erste Bit also mit dem niederwertigsten in $a_{0,0}$. Danach werden ebenso die folgenden Nachrichtenbits in $a_{0,1},a_{0,2},\cdots ,a_{1,0},\cdots$ übernommen. Der Hashwert wird am Ende ebenfalls $a_{0,0},a_{0,1},\cdots$ 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.

Das geänderte Padding gegenüber dem originalen Keccak-Algorithmus bedeutet auch, dass Keccak und SHA-3 verschiedene Hashfunktionen sind, und diese Bezeichnungen sollten nicht synonym verwendet werden.

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 $2^{511,5}$ Funktionsaufrufen und einem Speicherplatz von $2^{508}$. 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 $2^{1575}$ 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 $h(N\,\|\,x)$ einer mit $x$ erweiterten unbekannten Nachricht $N$ unter Kenntnis von deren Hashwert $h(N)$ bestimmt.

Weblinks

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