Hauptmenü öffnen

Wikipedia β

SHA-3

kryptologische Hashfunktion

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]

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 SHA-3 Standard
Länge des Hashwertes (Bit) variabel
(üblich sind: 224, 256, 384, 512)
Konstruktion Sponge-Konstruktion
Runden 24
(12+2ℓ, in SHA-3 ist ℓ = 6)
Beste bekannte Kryptoanalyse
second preimage attack von Daniel J. Bernstein auf 6 von 24 Runden von Keccak-512 mit 2506 Funktionsaufrufen und einer Platzkomplexität von 2176 [1]

Inhaltsverzeichnis

VorgeschichteBearbeiten

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 existierte die SHA-2-Familie, gegen die es bislang keine praxisrelevanten Angriffe gibt, aber es bereitet eine gewisse Sorge, dass 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]

FunktionsweiseBearbeiten

 
Darstellung der Sponge-Konstruktion

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  .

Das Verfahren verarbeitet die Nachricht schrittweise, wobei in jedem Schritt ein   Bit langer Block der Nachricht verarbeitet wird. Es muss   sein, und bei den Wettbewerbsvarianten ist  .

Zunächst wird die Bitfolge   (mit   bis   Nullen) an die Nachricht angefügt, so dass ihre Länge ein Vielfaches von   ist. Das erste 1-Bit macht das Nachrichtenende kenntlich, so dass verschieden lange Nachrichten 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 kurzen 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).

RundenfunktionBearbeiten

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.

KritikBearbeiten

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.

StandardisierungBearbeiten

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

Name Hash-Länge Nachrichten-Blocklänge Kapazität c 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 (n) 1344 256 min(n/2, 128) min(n, 128) 111110*1
SHAKE256 variabel (n) 1088 512 min(n/2, 256) min(n, 256)

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.

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  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.
  10. NIST Computer Security Division (CSD): SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. NIST.
  11. Mourad Gouicem: Comparison of seven SHA-3 candidates software implementations on smart cards. Abgerufen am 14. Februar 2014 (PDF).
  12. http://www.nist.gov/itl/csd/201508_sha3.cfm