SHA-3

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).[1] 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.[2] Von den eingereichten Hashfunktionen wurde gefordert, dass sie Nachrichten bis zu einer Obergrenze von mindestens ${\displaystyle 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.[3] 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.[4] Es wurde der Vorwurf erhoben, das NIST würde sein Augenmerk zu sehr auf Implementierungen in Hardware legen.

Darstellung der Sponge-Konstruktion

Keccak ist eine sogenannte Sponge-Konstruktion. Ein Zustandsvektor von ${\displaystyle b}$ Bit „absorbiert“ die Nachricht blockweise, die dazu in Blöcke von ${\displaystyle r<b}$ Bit geteilt wird. Mit jedem Block werden ${\displaystyle r}$ Bit des Zustandsvektors verändert, wonach die Daten im Zustandsvektor durch eine Permutationsfunktion durchmischt werden. Diese ist eine bijektive Abbildung ${\displaystyle f:\{0,1\}^{b}\rightarrow \{0,1\}^{b}}$, sie permutiert also die ${\displaystyle 2^{b}}$ möglichen Zustände des Vektors auf pseudozufällige Weise.[5][6]

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

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

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

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

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

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

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

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

Der Wert ${\displaystyle 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 ${\displaystyle n}$ Bit die Sicherheit gegen Kollisionsangriffe ${\displaystyle \min(n/2,c/2)}$ Bit und gegen Urbild-Angriffe ${\displaystyle \min(n,c/2)}$ Bit beträgt, vorausgesetzt, die Permutation der Zustandswerte ist nicht von einer Zufallspermutation unterscheidbar.[7] Um hinsichtlich der Sicherheit konservativ zu sein, haben die Entwickler die Kapazität auf die doppelte Länge des Hash-Wertes festgelegt(${\displaystyle c=2n}$), wodurch die für ein gegebenes ${\displaystyle n}$ höchstmögliche Sicherheit gegen jeden Angriff erreicht wird (wegen des Geburtstagsparadoxons kann die Sicherheit gegen Kollisionsangriffe nicht höher als ${\displaystyle n/2}$ Bit sein).

	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;
			}
		}
	}

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.[8][9] 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.[10] Die Autoren von Keccak verteidigten andererseits die vorgeschlagenen Änderungen.[11]

Als Reaktion auf die Kritik entschied sich NIST bei den vier Varianten SHA3-224 bis SHA3-512 gegen die Reduzierung der Kapazität.[12][13] 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.

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.[17] Damit nutzen sie die große Sicherheitsreserve von Keccak aus, um die Effizienz zu verbessern.

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 ${\displaystyle 2^{511,5}}$ Funktionsaufrufen und einem Speicherplatz von ${\displaystyle 2^{508}}$. Das ist nur um den Faktor 1,4 effizienter als ein Brute-Force-Angriff.[18]

Es ist möglich, die Zustandspermutation mit der vollen Zahl von 24 Runden von einer Zufallspermutation zu unterscheiden, was aber etwa ${\displaystyle 2^{1575}}$ Funktionsaufrufe erfordert.[19] 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 ${\displaystyle h(N\,\|\,x)}$ einer mit ${\displaystyle x}$ erweiterten unbekannten Nachricht ${\displaystyle N}$ unter Kenntnis von deren Hashwert ${\displaystyle h(N)}$ bestimmt.

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

1. NIST's Policy on Hash Functions. 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).