Grøstl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Grøstl
Entwickler Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Veröffentlicht 2008
Abgeleitet von AES
Zertifizierung Finalist im SHA-3 Auswahlverfahren
Länge des Hashwertes (Bit) 224, 256, 384, 512
Konstruktion wide-pipe Merkle-Damgård-Konstruktion
Runden 10 (Grøstl-224, Grøstl-256)
14 (Grøstl-384, Grøstl-512)
Beste bekannte Kryptoanalyse
M. Schläffer: Updated Differential Analysis of Grøstl. January 2011.
Kollision auf 3 Runden von Grøstl-224 und Grøstl-256 mit einer Zeitkomplexität von 264 und auf 3 Runden von Grøstl-512 mit einer Zeitkomplexität von 2192[1]

Grøstl ist eine kryptographische Hashfunktion. Sie wurde von einem Team dänischer und österreichischer Wissenschaftler um den Kryptographen Lars Knudsen entwickelt. Grøstl war einer der Kandidaten im Wettbewerb für den zukünftigen Standard SHA-3. Er wurde im Dezember 2010 als einer von fünf Finalisten ausgewählt.

Benannt wurde es nach dem österreichischen Gericht Gröstl, welches dem US-amerikanischen Hash ähnelt.[2]

Aufbau[Bearbeiten | Quelltext bearbeiten]

Die Nachricht wird erweitert und in Blöcke m_1 \dots m_n von je l Bit geteilt, die nacheinander verarbeitet werden. Ein Block wird zusammen mit einem Verkettungswert v_i von ebenfalls l Bit in eine Kompressionsfunktion eingegeben, die den nächsten Verkettungswert liefert. Der letzte Verkettungswert wird in eine Finalisierungsfunktion eingegeben, die den Hashwert berechnet:

v_{i+1} = f(v_i, m_i); \; i = 1,2,\dots,n
h = g(v_{n+1}).

v_1 ist ein konstanter Initialisierungsvektor. Grøstl kann Hashwerte von n=8 bis n=512 Bit berechnen, in ganzen Byte-Schritten. Mit Grøstl-n bezeichnet man die Variante mit n Bit Hash-Länge. l richtet sich nach der Hash-Länge; es ist l = 512 für n \le 256 und l = 1024 für größere Hash-Längen.

Die Kompressions- und die Finalisierungsfunktion beruhen auf zwei Permutationen P,Q, die jeweils eine lBit-Eingabe auf eine ebenso lange Ausgabe bijektiv abbilden:

f(v,m) = P(v \oplus m) \oplus Q(m) \oplus v
g(v) = \operatorname{trunc}(P(v) \oplus v,n)

\oplus steht für die bitweise XOR-Verknüpfung. Die Ausgabe von g entsteht durch Weglassen der über n hinausgehenden Bits (Trunkierung).

P und Q sind sehr ähnlich wie die Blockverschlüsselung AES aufgebaut, unter anderem wird dafür dieselbe S-Box genutzt. Sie wenden 10 mal (l=512) bzw 14 mal (l=1024) eine Rundenfunktion auf den Datenblock an, um dessen Werte zu permutieren.

Sicherheit[Bearbeiten | Quelltext bearbeiten]

Im SHA-3-Auswahlverfahren wurde die - im Vergleich zu anderen Finalisten - geringe Sicherheitsmarge bemängelt, sowie mögliche cache-time attacks, die jedoch abhängig von der Implementierung sind. Als Vorteile galten die intensive Kryptoanalyse und das gute Verständnis beruhend auf der Blockchiffre AES[3].

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. M. Schläffer: Updated Differential Analysis of Grøstl. January 2011.
  2. Herleitung des Namens
  3. National Institute of Standards and Technology: Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition. November 2010. S.33 doi:10.6028/NIST.IR.7896

Weblinks[Bearbeiten | Quelltext bearbeiten]