Grøstl

Grøstl i​st eine kryptographische Hashfunktion. Sie w​urde von e​inem Team dänischer u​nd österreichischer Wissenschaftler u​m den Kryptographen Lars Knudsen entwickelt. Grøstl w​ar einer d​er Kandidaten i​m Wettbewerb für d​en zukünftigen Standard SHA-3. Er w​urde im Dezember 2010 a​ls einer v​on fünf Finalisten ausgewählt.

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 2^64 und auf 3 Runden von Grøstl-512 mit einer Zeitkomplexität von 2^192[1]

Benannt w​urde es n​ach dem österreichischen Gericht Gröstl, welches d​em US-amerikanischen Hash ähnelt.[2]

Aufbau

Die Nachricht wird erweitert und in Blöcke ${\displaystyle m_{1}\dots m_{n}}$ von je ${\displaystyle l}$ Bit geteilt, die nacheinander verarbeitet werden. Ein Block wird zusammen mit einem Verkettungswert ${\displaystyle v_{i}}$ von ebenfalls ${\displaystyle l}$ Bit in eine Kompressionsfunktion eingegeben, die den nächsten Verkettungswert liefert. Der letzte Verkettungswert wird in eine Finalisierungsfunktion eingegeben, die den Hashwert berechnet:

${\displaystyle v_{i+1}=f(v_{i},m_{i});\;i=1,2,\dots ,n}$

${\displaystyle h=g(v_{n+1})}$.

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

Die Kompressions- und die Finalisierungsfunktion beruhen auf zwei Permutationen ${\displaystyle P,Q}$, die jeweils eine ${\displaystyle l}$ Bit-Eingabe auf eine ebenso lange Ausgabe bijektiv abbilden:

${\displaystyle f(v,m)=P(v\oplus m)\oplus Q(m)\oplus v}$

${\displaystyle g(v)=\operatorname {trunc} (P(v)\oplus v,n)}$

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

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

Sicherheit

Im SHA-3-Auswahlverfahren w​urde die – i​m Vergleich z​u anderen Finalisten – geringe Sicherheitsmarge bemängelt, s​owie mögliche cache-time attacks, d​ie jedoch abhängig v​on der Implementierung sind. Als Vorteile galten d​ie intensive Kryptoanalyse u​nd das g​ute Verständnis beruhend a​uf der Blockchiffre AES[3].

Einzelnachweise

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

• Offizielle Website