Hashfunktionen – Key Player in der Datensicherheit
Hashfunktionen spielen in vielen kryptografischen Anwendungen eine zentrale Rolle. Ob bei der Erzeugung von digitalen Signaturen, dem sicheren Speichern von Passwörtern, der Schlüsselableitung oder dem Sicherstellen von Datenintegrität. Eine Hashfunktion ist dabei eine Abbildung, die Texte beliebiger Länge auf eine Zeichenfolge fester Länge abbildet.
Eine Hashfunktion h heißt
- Einwegfunktion genau dann, wenn es schwierig ist, zu gegebenem y0 ein x0 zu finden mit h(x0) = y0 .
- schwach kollisionsresistent genau dann, wenn es schwierig ist, zu einem gegebenen x ein x‘ zu finden mit h(x) = h(x‘).
- stark kollisionsresistent genau dann, wenn es schwierig ist, x und x‘ zu finden mit x != x‘ und h(x) = h(x‘).
Eine kryptografische Hashfunktion ist eine stark kollisionsresistente Einweg-Hashfunktion.
Bekannte Hashfunktionen sind MD4 (gilt nicht mehr als kollisionsresistent), MD5 (gilt seit 2009 als gebrochen) und die SHA-Familie. Die Algorithmen SHA-1 und SHA-2 beruhen dabei auf dem Damgård-Merkle-Prinzip.
Geschichte
Nach den erfolgreichen Angriffen auf MD5 und SHA-1 war die Befürchtung groß, dass sich auch SHA-2 als unsicher erweisen würde. Also startete die amerikanische Standardisierungsbehörde National Institute of Standards and Technology (NIST) im Jahre 2007 den SHA-3-Wettbewerb.
Im Zuge dieses Wettbewerbes wurde im Oktober 2012 der Algorithmus Keccack zum Sieger ernannt. Dieser basiert, anders als seine Vorgänger, nicht auf dem Damgård-Merkle-Prinzip, sondern auf einer sogenannten Schwammfunktion.
Am 5. August 2015 wurde er offiziell als SHA-2-Nachfolger standardisiert. Der Standard SHA-3 beschreibt dabei festgelegte Parameter für den Algorithmus Keccak.
SHA-3 – Schwammfunktion
Die Schwamm-Konstruktion ist eine relativ neue Art Hashfunktionen zu konstruieren. Sie erlaubt es, Hashwerte beliebiger Länge zu generieren. Basierend auf einer festen Permutation f besteht ein Schwamm-Algorithmus aus zwei Phasen. In der ersten Phase wird die Nachricht mit einer definierten Bitrate aufgesogen und in der zweiten Phase wieder ausgedrückt. Durch mehrfaches Ausdrücken kann so ein kontinuierlicher Datenstrom mit einer festen Bitrate generiert werden.
Parameter
Der Algorithmus Keccak besitzt eine ganze Reihe von Parametern, die eine flexible Steuerung von Performanz und Sicherheit erlauben. Hier werden im Folgenden alle Möglichkeiten angegeben, die der Algorithmus annehmen kann. Die Werte, die für den SHA-3 Standard genutzt werden, sind fett gedruckt.
Der interne Status, state genannt, ist ein mit 0 initialisierter Zustandsvektor, welcher aus 25 Wörtern besteht. Jedes Wort ist w = 2 * l Bits lang, mit l ∈ {0, 1, . . . , 6}.
Ein Wort entspricht damit einer Zeile in z-Richtung. Daraus ergibt sich der gesamte Zustandsvektor als b = 25 ∗ w
Ein weiterer Parameter ist die Hashausgabelänge n. Diese kann bei Keccak frei gewählt werden. Für den SHA-3 Standard gilt jedoch: n ∈ {224, 256, 384, 512}
Der Zustandsvektor b besteht außerdem aus zwei Teilen (siehe Abb. 1).
Der Kapazität c = 2 ∗ n und der Bitrate r = b − c.
Funktionsweise
Zuerst wird die Nachricht mit der Bitfolge „1000 . . . 01“ auf ein Vielfaches von r erweitert.
Wie die Abb. 1 zeigt, werden in der Aufsaugphase immer r-Bit der Nachricht mit den r-Bit des Zustandsvektors XOR verknüpft. Zusammen mit den restlichen c-Bit durchläuft der Zustandsvektor die Permutation f.
Die Ausgabe des Hashwertes erfolgt, indem immer r-Bit des Zustandsvektors ausgegeben werden und anschließend dieser noch einmal die Permutation durchläuft. Dieser Vorgang wird solange wiederholt, bis die gewünschte Ausgabelänge n erreicht ist. Dabei kann es vorkommen, dass bei der letzten Ausgabe nicht die kompletten r-Bit ausgegeben werden, falls n kein Vielfaches von r ist.
Sicherheit
Die Schwammfunktion bietet mit ihrem Parametern folgende Sicherheiten:
- Kollisionsresistenz von min(n/2, c/2)
- Urbild-Sicherheitvon min(min(n,c+r),max(min(n−r,c),c−2)
Dadurch entstehen eine große Anzahl an Kompromissen zwischen Sicherheit und Performanz. Dazu folgende Überlegungen: Von einem Hashwert der Länge n wird in der Regel eine Kollisionsresistenz von n/2 und eine Urbild-Sicherheit von n Bits gefordert. Indem n so gewählt wird, dass 2(n/2) Operationen unmöglich auszuführen sind, werden Kollisionen ausgeschlossen, beispielsweise n = 256.
Daraus folgt, dass eine Urbild-Sicherheit von n Bits, also 2n Operationen eine unnötig hohe Schranke ist. Durch eine Anpassung der Parameter in der Schwammfunktion ist es möglich, Urbild-Sicherheit und Kollisionsresistenz gleich zu wählen. Das hat auch den Vorteil einer erhöhten Performanz.
Die Permutation f
Diese Permutation besteht aus vier Funktionen, welche bei SHA-3 insgesamt 24 mal durchlaufen werden. Der Algorithmus Keccak beschreibt die Anzahl der Runden mit 12 + 2 ∗ l
Funktion: Theta θ
Bei dieser Funktion wird jedes Bit des Zustandsvektors, abhängig der Paritäten zweier Spalten, invertiert. Die Spalten, deren Parität berechnet wird, ist zum einen die links neben dem Bit (x−1) und die vorne rechts (x+1,z−1). Dabei wird der Index in x-Richtung Mudolo 5 und der in z-Richtung Mudolo w gerechnet.
Beide Paritätsbits werden mit dem zu manipulierenden Bit XOR-Verknüpft.
So wird schon nach wenigen Runden eine gute Diffusion, das heißt ein „Verschmieren“ jedes einzelnen Ausgangsbits über den gesamten Zustandsquader erreicht.
Funktion: Rho ρ
Rho rotiert jede der 25 Zeilen in z-Richtung um eine vorgegebene Anzahl von Bits nach links. Diese vorgegeben Anzahl kann als feste Konstante hinterlegt oder durch eine Funktion beschrieben werden. Die Liste der Konstanten aus dem Standard ist dabei Mudolo w zu rechnen.
Funktion: Pi π
Hierbei wird eine komplette Line (Zeile in z-Richtung) bewegt. Die mittlere Line hat dabei die Koordinate (0, 0). Wie schon bei Rho kann die Verschiebung durch Konstanten im Speicher erfolgen oder durch eine Funktion beschrieben werden. Alle Koordinaten müssen Mudolo 5 gerechnet werden.
Funktion Xsi x
Xsi ist die nichtlineare Komponente einer jeden Runde, das heißt die Teilfunktion, bei der nicht einfach jedes Ausgabebit als XOR-Summe verschiedener Eingabebits dargestellt werden kann. Gäbe es Xsi nicht, wäre die ganze Schwammfunktion f als großes, aber lösbares lineares Gleichungssystem aus einzelnen Bits darstellbar und auf diesem Wege zu brechen. Xsi addiert zu jeder Lane per XOR die „Not a AND b“-Verknüpfung der beiden folgenden Lanes a und b aus der jeweiligen 5er-Zeile des Zustandsvektors. Es ist auch hier darauf zu achten, dass die x-Koordinaten Mudolo 5 gerechnet werden müssen.
χ : S[x][y][z] ← S[x][y][z] ⊕ (¬S[x + 1][y][z] & S[x + 2][y][z])
Funktion: Iota ι
Iota schließlich addiert (wieder bitweise per XOR) zum 0., 1., 3., 7., 15., 31. und 63. Bit der Lane „links unten“ eine - für jede der 24 Runden unterschiedliche - 7-Bit-Rundenkonstante. Dieser Schritt sorgt dafür, dass eventuelle Symmetrien im Zustandsvektor, die sich durch von einem Angreifer gezielt gewählte Eingabewerte ergeben könnten, schon nach wenigen Runden verschwinden. Eine der Besonderheiten von Keccak ist, dass diese Rundenkonstanten als Ausgabe eines kurzen, linear rückgekoppelten Schieberegisters definiert sind, sodass sie mit wenigen Schaltkreisen oder Prozessorbefehlen „just in time“ für jede Runde neu berechnet werden können, anstatt sie als Tabelle im Speicher zu halten.
ι : S[x][y][.] ← S[x][y][.] ⊕ RC[μ]
für alle 0 ≤ μ ≤ 12 + 2 ∗ l = 24
Beispiel
An dieser Stelle soll kein komplettes Durchrechnen eines Zustandsvektors aufgezeichnet werden. Es soll nur an einem Beispiel das Definieren der Parameter gezeigt werden. Es wird ein Hash der Länge n = 512Bit generiert.
=> c = 2 ∗ 512Bit = 1024Bit
Der Parameter b = 25 ∗ 26 ist bei SHA-3 fest.
=> r = b − c = 25 ∗ 64Bit − 1024Bit = 576Bit
Als Eingabe soll eine Datei der Größe M = 4096Bit dienen.
4096Bit − (7 ∗ 576Bit) = 64Bit
Das bedeutet, dass die Eingabedaten mit folgendem padding ergänzt werden:
=> M = M + 100 . . . 01 ( 62 Nullen)
M ist also 4160 Bit groß. Durch die Bitrate r ergeben sich daher 8 Aufsaugvorgänge. Nach jedem Aufsaugvorgang wird die Permutation f 24 mal durchlaufen.
In der Ausdrückphase werden mit der Bitrate r Bits gleichzeitig für den Hash ausgegeben. Da r > n werden nur einmalig 512 Bit "herausgerückt“.