2 Hash-Algorithmen

2.1 Einführung

Kryptografische Hash-Funktionen bilden das Rückgrat von Kryptoverfahren und -algorithmen [39]. Wie die aus der Informatik bekannten Hash-Funktionen auch, bilden sie eine große Eingangsmenge {𝑥} eindeutig (deterministisch) auf eine viel kleinere Ausgangsmenge 𝑦 = H(𝑥) ab. Sie haben jedoch folgende ergänzende Eigenschaften, welche deren algorithmische Komplexität mit dem jeweiligen Stand der Technik in Verbindung bringen:

1. Es ist praktisch unmöglich zwei Eingangswerte 𝑥 ≠ 𝑥′ zu finden (wahlfrei), die denselben Hashwert 𝑦 besitzen (Kollisionsfreiheit).
2. Der Algorithmus ist eine Einweg-Funktion, d. h. für einen gegebenen Hash-Wert 𝑦 kann man praktisch keinen zugehörigen Wert 𝑥 = H ⁻¹(𝑦) berechnen (1. Urbild-Festigkeit).¹⁴
3. Es ist praktisch unmöglich zu einem vorgegebenen Eingangswert 𝑥 einen weiteren Wert 𝑥′ ≠ 𝑥 zu finden, der denselben Hash-Wert 𝑦 erzeugt (2. Urbild-Festigkeit).

Insbesondere ältere Hash-Funktionen, wie z. B. der MD5 können dies heute nicht mehr gewährleisten, aber auch der SHA-1 gilt seit 2005 als „geknackt”. Alternativen wie SHA-256 oder SHA-512 (auch kurz SHA-2 genannt) stehen zwar zur Verfügung, werden aber noch nicht überall konsequent genutzt.¹⁵

Wirkprinzip Die Berechnung des Hash-Wertes 𝑦 erfolgt üblicherweise durch Zerlegung des Eingangs-Vektors 𝑥 in 𝑘 Blöcke fester Breite, die dann iterativ mit Hilfe einer nichtlinearen Kompressionsfunktion C verarbeitet werden. Abbildung 13 zeigt die unter dem Namen Merkle/Damgård-Konstruktion bekannte Struktur [40, 14].¹⁶ Für jeden Zwischenwert gilt ausgehend von 𝑦₀ = IV die Gleichung 𝑦_𝑖 = C(𝑦_𝑖−1,𝑥_𝑖) und so für das Ergebnis: 𝑦 = H(𝑥) = 𝑦_𝑘.

2.2 Die MD-Familie

Zu den Mitgliedern dieser Hash-Familie, welche von R. RIVEST entwickelt wurde, gehören unter anderem der MD2…MD5, SHA-1 und SHA-2 [55, 44, 27]. Am Beispiel des SHA-1 soll deren prinzipielle Arbeitsweise verdeutlicht werden, wofür in Abbildung 14 die zugehörige Kompressionsfunktion C dargestellt ist.

Der SHA-1 ist für 32-Bit Architekturen optimiert, d. h. alle Variablen in Abbildung 14 sind von entsprechender Breite. Die (Eingangs-) Blockbreite 𝑥_𝑖 beträgt 64 Byte, also 16 Worte zu je 32-Bit. Ein Hash-Wert 𝑦_𝑖 besteht aus 160-Bit (20 Byte, 5 Worte) und wird iterativ in 80 sogenannten Runden erzeugt. Speziell beim SHA-1 (nicht so bei SHA-2) werden jeweils 20 Runden mit den gleichen Konstanten und Funktionen realisiert, so daß man die Darstellung auf 4 Funktionsblöcke 𝑓₁,…,𝑓₄ reduzieren kann. Der Algorithmus kann folgendermaßen beschrieben werden:

1. Erzeuge im „Message Schedule” aus den 16 Eingangsworten, welche 𝑊₀,…,𝑊₁₅ zugeordnet werden, iterativ weitere 64 Worte 𝑊_𝑖 nach folgender Vorschrift:¹⁷

   

   Darin steht rol für „Rotate Left” und der zugehörige Exponent für die Anzahl der Bits, um die es nach links zu rotieren gilt.

2. Sollte es sich um den ersten Block 𝑥₁ handeln, dann initialisiere 𝐻₀,…,𝐻₅ mit den Konstanten:

   
3. Ordne (𝐻₀,…,𝐻₄) dem Vektor (𝐴,𝐵,𝐶,𝐷,𝐸) zu.

4. Berechne 80 Runden (0 ≤ 𝑡 ≤ 79), im speziellen Fall von SHA-1 genau 4 · 20 Runden (1 ≤ 𝑛 ≤ 4), nach folgender Vorschrift:

   

   wobei Additionen immer modulo 2³² ausgeführt werden. Die Konstanten 𝐾_𝑡 sind definiert als:

   

   Die Funktionen 𝑓₁,…,𝑓₄, welche für jeweils 20 Runden verwendet werden, sind folgendermaßen spezifiziert:

   

5. Berechne die Ergebniswerte (𝐻₀,…,𝐻₄), welche letztlich den Hash-Wert 𝑦_𝑖 dieses Blocks ausmachen, wiefolgt:¹⁸

   

SHA-2 Bei den SHA-2 Hash-Funktionen ist dieses Prinzip erhalten geblieben, die Änderungen liegen im Detail [44]:

• Die Anzahl der Bits im Hash-Wert wurde erhöht und entspricht dem jeweiligen Namen: SHA-224, SHA-256, SHA-384, SHA-512. Dazu gab es zwei wesentliche Modifikationen:¹⁹

  1. Der Hash-Vektor (𝐻₀,…,𝐻₄) wurde auf (𝐻₀,…,𝐻₇) erweitert, genau wie auch die Zwischenwerte (𝐴,𝐵,𝐶,𝐷,𝐸) auf (𝐴,𝐵,𝐶,𝐷,𝐸,𝐹,𝐺,𝐻).
  2. SHA-384 und SHA-512 sind optimiert für 64-Bit Architekturen, d. h. jedes Wort ist 64-Bit breit und so auch die Blockbreite verdoppelt auf 128 Byte.
• Zur „Rotate Left” Operation sind weitere hinzugekommen: „Rotate Right” und „Shift Left/Right” – insgesamt wurde die Rundenfunktion verkompliziert.
• Innerhalb eines Algorithmus’ ist die Rundenfunktion invariant – es wird in jeder Runde aber eine andere Konstante 𝐾_𝑡 verwendet.
• Beim SHA-224/256 werden anstatt der 80 Runden nur 64 Runden ausgeführt.

2.3 Padding

Da jede Hash-Funktion für eine fixe (Eingangs-) Blockbreite konzipiert ist, muß man den letzten Block meist auf diese erweitern. Bei den standardisierten Hash-Algorithmen scheint sich folgende Vorgehensweise durchgesetzt zu haben:

1. Füge immer ein einzelnes Bit mit dem Wert 1 an (typisches ISO-Padding), bei Byte-orientierten Implementierung den Wert 80H.
2. Gewährleiste, daß am Ende des letzten Blocks 64 Bit Platz sind für die Aufnahme eines Zählers. Ist dies nicht gegeben, schließe den aktuellen Block durch Auffüllen mit Nullen ab und verarbeite ihn mit der Kompressionsfunktion.
3. Fülle den aktuellen Block, ausgenommen die letzten 64 Bit, mit Nullen auf.
4. Füge einen Blockzähler (CNT in Abbildung 14) in die letzten 64 Bit ein und verarbeite diesen Block mit der Kompressionsfunktion.
5. Nehme das Ergebnis 𝑦_𝑘 dieses letzten Blocks als Hash-Wert H(𝑥).