Wie funktioniert SHA-256?
SHA-256 nimmt eine Nachricht, verarbeitet sie in mehreren genau definierten Schritten und erzeugt daraus einen Hashwert mit 256 Bit – als bekanntester Vertreter der SHA-2-Familie.
Auf den ersten Blick wirkt der Algorithmus kompliziert: Padding, 512-Bit-Blöcke, Rotationen, XOR-Verknüpfungen, ein Message Schedule und schließlich 64 Kompressionsrunden pro Block.
Wenn man diese Schritte einzeln betrachtet, wird der Aufbau jedoch deutlich verständlicher.
In diesem Artikel öffne ich deshalb die Blackbox von SHA-256 und zeige, was während der Berechnung passiert.
Wenn du zunächst wissen möchtest, was SHA-256 grundsätzlich ist, welche Sicherheitsstärke der Algorithmus besitzt und wo er eingesetzt wird, findest du den Einstieg im Artikel Was ist SHA-256?. Was eine Hashfunktion ganz allgemein ausmacht, erkläre ich in Was ist eine Hashfunktion?.
Der Ablauf von SHA-256
Vereinfacht lässt sich die Berechnung so darstellen:
Eingabe
↓
Nachricht als Bits
↓
Padding
↓
512-Bit-Blöcke
↓
16 × 32-Bit-Wörter
↓
Message Schedule W₀ … W₆₃
↓
Initialer Hashzustand H₀ … H₇
↓
64 Kompressionsrunden
↓
neuer Hashzustand
↓
nächster 512-Bit-Block
↓
...
↓
256-Bit-Digest
SHA-256 arbeitet dabei hauptsächlich mit 32-Bit-Wörtern.
Viele Operationen, die zunächst kompliziert aussehen, sind letztlich Kombinationen weniger grundlegender Bitoperationen:
- AND
- XOR
- NOT
- Right Shift
- Rotate Right
- Addition modulo
2³²
Diese Operationen begegnen uns während des gesamten Algorithmus.
Schritt 1: Aus der Nachricht werden Bits
SHA-256 verarbeitet letztlich eine Folge von Bits.
Nehmen wir als einfaches Beispiel die ASCII-Zeichen:
abc
Ihre Bytewerte lauten:
a = 0x61
b = 0x62
c = 0x63
Binär:
a b c
01100001 01100010 01100011
Unsere Nachricht besitzt damit zunächst:
3 × 8 Bit = 24 Bit
Diese 24 Bit können allerdings noch nicht direkt von der SHA-256-Kompressionsfunktion verarbeitet werden.
Zunächst muss die Nachricht vorbereitet werden.
Schritt 2: Das Padding
SHA-256 verarbeitet Nachrichten in Blöcken von jeweils 512 Bit.
Deshalb wird die ursprüngliche Nachricht durch ein genau definiertes Padding erweitert.
Zunächst wird ein einzelnes 1-Bit angehängt:
Nachricht
01100001 01100010 01100011
↓
01100001 01100010 01100011 1
Danach folgen so viele 0-Bits, dass vor dem abschließenden Längenfeld noch genau 64 Bit innerhalb des letzten 512-Bit-Blocks frei bleiben.
Zum Schluss wird die Länge der ursprünglichen Nachricht als 64-Bit-Integer angehängt.
Für abc beträgt diese Länge:
24 Bit
also:
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00011000
Die gepaddete Nachricht besitzt anschließend eine Länge, die ein Vielfaches von 512 Bit ist.
Für kurze Nachrichten wie abc entsteht genau ein 512-Bit-Block.
Bei längeren Nachrichten entstehen mehrere Blöcke.
Warum wird die Nachrichtenlänge gespeichert?
Das Padding sorgt nicht einfach nur dafür, dass der letzte Block voll wird.
Die ursprüngliche Nachrichtenlänge ist Bestandteil der gepaddeten Nachricht.
Dadurch führen beispielsweise eine Nachricht und dieselbe Nachricht mit zusätzlich angehängten Nullbits nicht einfach zur identischen gepaddeten Darstellung.
Für SHA-256 gilt dabei:
Nachrichtenlänge < 2⁶⁴ Bit
Die ursprüngliche Länge kann deshalb in dem dafür vorgesehenen 64-Bit-Feld dargestellt werden.
Schritt 3: Aufteilung in 512-Bit-Blöcke
Nach dem Padding wird die Nachricht in Blöcke mit jeweils 512 Bit aufgeteilt:
M¹
M²
M³
...
Mᴺ
Jeder Block besteht aus:
512 Bit
÷
32 Bit
=
16 Wörter
Diese Wörter werden als:
M₀ M₁ M₂ ... M₁₅
beziehungsweise während der Bildung des Message Schedules als:
W₀ W₁ W₂ ... W₁₅
verwendet.
Bei unserem Beispiel abc beginnt der Block in hexadezimaler Darstellung mit:
61626380
Darin steckt:
61 = a
62 = b
63 = c
80 = Beginn des Paddings
Das letzte 32-Bit-Wort enthält schließlich einen Teil der kodierten ursprünglichen Nachrichtenlänge:
00000018
0x18 entspricht dezimal 24 – also genau der Länge von abc in Bit.
Schritt 4: Das Message Schedule
Die Kompressionsfunktion benötigt für ihre 64 Runden insgesamt 64 Wörter:
W₀ ... W₆₃
Der Nachrichtenblock liefert aber zunächst nur 16 Wörter.
Die ersten 16 Werte werden direkt aus dem aktuellen 512-Bit-Block übernommen:
W₀ ... W₁₅
Die restlichen:
W₁₆ ... W₆₃
werden aus bereits vorhandenen Wörtern berechnet.
Dafür definiert SHA-256 zwei Funktionen:
σ₀(x)
σ₁(x)
Für SHA-256 gilt:
σ₀(x) =
ROTR⁷(x)
XOR ROTR¹⁸(x)
XOR SHR³(x)
und:
σ₁(x) =
ROTR¹⁷(x)
XOR ROTR¹⁹(x)
XOR SHR¹⁰(x)
Damit wird für t = 16 ... 63 berechnet:
Wₜ =
σ₁(Wₜ₋₂)
+ Wₜ₋₇
+ σ₀(Wₜ₋₁₅)
+ Wₜ₋₁₆
Alle Additionen erfolgen modulo 2³².
Aus 16 Wörtern des Nachrichtenblocks entsteht damit ein Message Schedule aus insgesamt 64 Wörtern.
Was bedeutet Rotate Right?
ROTR steht für Rotate Right.
Bei einer Rotation werden Bits nach rechts verschoben. Die Bits, die rechts herausfallen würden, werden links wieder eingesetzt.
Mit einem vereinfachten 8-Bit-Beispiel:
x = 10110001
ROTR²(x)
10110001
└─┐
└┼────────┐
↓ ↓
01101100
Die beiden rechten Bits 01 tauchen links wieder auf.
Das unterscheidet eine Rotation von einem normalen Right Shift.
Was bedeutet Right Shift?
Bei einem logischen Right Shift werden die Bits ebenfalls nach rechts verschoben.
Die frei werdenden Positionen links werden jedoch mit Nullen gefüllt.
Beispiel:
x = 10110001
SHR²(x)
00101100
Vergleichen wir beides:
x 10110001
ROTR² 01101100
SHR² 00101100
Bei der Rotation bleiben alle Bits erhalten und wechseln ihre Position.
Beim Shift verschwinden Bits am rechten Rand.
SHA-256 verwendet beide Operationen.
Die 8-Bit-Beispiele dienen nur der Anschauung: SHA-256 selbst wendet ROTR und SHR immer auf 32-Bit-Wörter an.
Warum werden daraus 64 Wörter?
Das Message Schedule sorgt dafür, dass die Bits eines Nachrichtenblocks während der folgenden Kompressionsrunden immer wieder in neuen Kombinationen einfließen.
Jede der 64 Runden verwendet genau ein Wort:
Runde 0 → W₀
Runde 1 → W₁
Runde 2 → W₂
...
Runde 63 → W₆₃
Damit sind die Nachrichtendaten über das gesamte Message Schedule verteilt.
Schritt 5: Der initiale Hashzustand
Bevor der erste Nachrichtenblock verarbeitet wird, besitzt SHA-256 einen fest definierten internen Zustand.
Dieser besteht aus acht 32-Bit-Wörtern:
H₀ = 6a09e667
H₁ = bb67ae85
H₂ = 3c6ef372
H₃ = a54ff53a
H₄ = 510e527f
H₅ = 9b05688c
H₆ = 1f83d9ab
H₇ = 5be0cd19
Diese Initialwerte sind Bestandteil der SHA-256-Spezifikation.
Sie entsprechen den ersten 32 Bits der Nachkommabits der Quadratwurzeln der ersten acht Primzahlen.
Für jeden Nachrichtenblock werden daraus zunächst acht Arbeitsvariablen:
a = H₀
b = H₁
c = H₂
d = H₃
e = H₄
f = H₅
g = H₆
h = H₇
Diese acht Werte werden nun während der 64 Runden verändert.
Schritt 6: Die SHA-256-Funktionen
Für die Kompressionsrunden definiert SHA-256 vier zentrale Funktionen:
Ch
Maj
Σ₀
Σ₁
Die großen Sigma-Funktionen sind dabei nicht dieselben Funktionen wie die kleinen σ₀ und σ₁ aus dem Message Schedule.
Ch – Choose
Die Funktion Ch ist definiert als:
Ch(x,y,z) =
(x AND y)
XOR
(NOT x AND z)
Mathematisch:
Ch(x,y,z) = (x ∧ y) ⊕ (¬x ∧ z)
Der Name Choose beschreibt ziemlich gut, was auf Bitebene passiert.
Für jedes Bit gilt vereinfacht:
wenn x = 1 → wähle das Bit aus y
wenn x = 0 → wähle das Bit aus z
Beispielsweise für einzelne Bits:
| x | y | z | Ch |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
x entscheidet also, aus welcher der beiden anderen Eingaben das Ergebnisbit stammt.
Maj – Majority
Die Funktion Maj ist definiert als:
Maj(x,y,z) =
(x AND y)
XOR
(x AND z)
XOR
(y AND z)
oder:
Maj(x,y,z) =
(x ∧ y) ⊕ (x ∧ z) ⊕ (y ∧ z)
Der Name steht für Majority.
Für jedes Bit gewinnt der Wert, der mindestens zweimal vorkommt:
0 0 1 → 0
0 1 1 → 1
1 0 1 → 1
1 1 0 → 1
Ch und Maj kombinieren also die aktuellen Arbeitsvariablen auf unterschiedliche Weise.
Die großen Sigma-Funktionen
Zusätzlich verwendet die Kompressionsfunktion:
Σ₀(x) =
ROTR²(x)
XOR ROTR¹³(x)
XOR ROTR²²(x)
und:
Σ₁(x) =
ROTR⁶(x)
XOR ROTR¹¹(x)
XOR ROTR²⁵(x)
Hier werden ausschließlich Rotationen verwendet.
Zum Vergleich:
Message Schedule:
σ₀ → ROTR 7, 18 + SHR 3
σ₁ → ROTR 17, 19 + SHR 10
Compression:
Σ₀ → ROTR 2, 13, 22
Σ₁ → ROTR 6, 11, 25
Die Unterscheidung zwischen kleinem und großem Sigma ist deshalb wichtig.
Schritt 7: Die 64 Runden
Jetzt haben wir fast alle Bestandteile zusammen:
W₀ ... W₆₃
aus dem Message Schedule,
a b c d e f g h
als Arbeitsvariablen und vier Funktionen:
Ch
Maj
Σ₀
Σ₁
Zusätzlich besitzt jede Runde eine eigene Konstante:
K₀ ... K₆₃
Für jede Runde t werden zwei temporäre Werte berechnet.
Der erste lautet:
T₁ =
h
+ Σ₁(e)
+ Ch(e,f,g)
+ Kₜ
+ Wₜ
Der zweite:
T₂ =
Σ₀(a)
+ Maj(a,b,c)
Auch diese Additionen erfolgen modulo 2³².
Was bedeutet Addition modulo 2³²?
Ein 32-Bit-Wort kann nur Werte von:
0
bis:
2³² - 1
darstellen.
Wird dieser Bereich bei einer Addition überschritten, werden nur die unteren 32 Bit des Ergebnisses verwendet.
Anschaulich kann man sich das wie einen Zähler vorstellen, der nach seinem höchsten Wert wieder von vorne beginnt.
Beispielsweise:
0xffffffff + 1
ergibt bei einer 32-Bit-Addition modulo 2³²:
0x00000000
Diese Art von Addition wird an vielen Stellen innerhalb von SHA-256 verwendet.
Wie verändern T₁ und T₂ den Zustand?
Nach der Berechnung von T₁ und T₂ werden die acht Arbeitsvariablen aktualisiert.
Für jede Runde gilt:
h = g
g = f
f = e
e = d + T₁
d = c
c = b
b = a
a = T₁ + T₂
Die beiden Additionen erfolgen wiederum modulo 2³².
Dadurch wandern Teile des bisherigen Zustands weiter, während T₁ und T₂ neue Werte einbringen.
Dann beginnt die nächste Runde.
Runde 0
↓
neue Werte a ... h
↓
Runde 1
↓
neue Werte a ... h
↓
...
↓
Runde 63
Nach 64 Runden hat sich der Arbeitszustand stark verändert.
Was sind die Konstanten K₀ bis K₆₃?
Jede Runde verwendet zusätzlich eine festgelegte 32-Bit-Konstante:
K₀
K₁
...
K₆₃
Beispielsweise beginnt die Liste mit:
K₀ = 428a2f98
K₁ = 71374491
K₂ = b5c0fbcf
K₃ = e9b5dba5
Die 64 Konstanten entsprechen den ersten 32 Bits der Nachkommabits der Kubikwurzeln der ersten 64 Primzahlen.
Auch diese Werte sind vollständig öffentlich und im Secure Hash Standard festgelegt.
Sie sind also keine geheimen Schlüssel.
Was passiert nach den 64 Runden?
Die Arbeitsvariablen ersetzen den bisherigen Hashzustand nicht einfach.
Stattdessen werden sie mit den acht Wörtern des vorherigen Hashzustands addiert:
H₀ = H₀ + a
H₁ = H₁ + b
H₂ = H₂ + c
H₃ = H₃ + d
H₄ = H₄ + e
H₅ = H₅ + f
H₆ = H₆ + g
H₇ = H₇ + h
Wiederum jeweils modulo 2³².
Damit entsteht der neue intermediate hash value.
Wenn weitere 512-Bit-Blöcke vorhanden sind, dient dieser Zustand als Ausgangspunkt für die Verarbeitung des nächsten Blocks.
Initialwerte
↓
Block 1
↓
H₀ ... H₇
↓
Block 2
↓
H₀ ... H₇
↓
Block 3
↓
...
Die Blöcke werden also nicht unabhängig voneinander gehasht.
Der Zustand wird von Block zu Block weitergeführt.
Wie entsteht der endgültige SHA-256-Hash?
Nach der Verarbeitung des letzten Blocks besitzt SHA-256 acht endgültige 32-Bit-Wörter:
H₀
H₁
H₂
H₃
H₄
H₅
H₆
H₇
Diese werden hintereinander gesetzt:
H₀ || H₁ || H₂ || H₃ || H₄ || H₅ || H₆ || H₇
Damit erhalten wir:
8 × 32 Bit
=
256 Bit
Das ist der SHA-256-Digest.
Die häufig verwendete hexadezimale Darstellung besitzt deshalb:
256 ÷ 4 = 64
Hex-Zeichen.
Woher kommt der Avalanche Effect?
Jetzt lässt sich auch besser nachvollziehen, warum eine kleine Änderung der Eingabe so große Auswirkungen haben kann.
Ein verändertes Eingabebit kann zunächst ein Wort des Nachrichtenblocks verändern.
Dieses Wort beeinflusst das Message Schedule:
W₀ ... W₆₃
Die Wörter des Message Schedules fließen wiederum in die einzelnen Kompressionsrunden ein.
Dort werden sie mit:
Ch
Maj
Σ₀
Σ₁
Kₜ
und dem aktuellen Zustand kombiniert.
Die veränderten Zustandswerte beeinflussen anschließend die folgenden Runden.
Eine Änderung kann sich dadurch über die Berechnung ausbreiten.
Bei einer guten kryptografischen Hashfunktion ist zu erwarten, dass eine kleine Änderung der Eingabe schließlich viele Bits der Ausgabe beeinflusst.
Dieses Verhalten bezeichnet man als Avalanche Effect.
Im Artikel Was ist der Avalanche Effect? kannst du den Effekt bereits interaktiv ausprobieren.
Im nächsten SHA-256-Artikel gehe ich noch einen Schritt weiter und zeige, wie sich eine konkrete Eingabe durch den Algorithmus bewegt.
Muss ich SHA-256 selbst implementieren?
Für produktive kryptografische Software solltest du SHA-256 normalerweise nicht selbst implementieren.
Die Beschreibung in diesem Artikel dient dazu, den Algorithmus zu verstehen.
In realer Software sollten etablierte kryptografische Bibliotheken beziehungsweise die kryptografischen Funktionen der jeweiligen Plattform verwendet werden.
Eine eigene Implementierung kann trotz eines scheinbar einfachen Algorithmus Fehler enthalten – beispielsweise bei Padding, Byte-Reihenfolge, 32-Bit-Operationen oder der Verarbeitung mehrerer Blöcke.
Für Lernzwecke ist eine eigene Implementierung dagegen sehr interessant.
Genau das werde ich für den interaktiven SHA-256 Explorer nutzen: eine nachvollziehbare Lernimplementierung, die zusätzlich gegen bekannte Testvektoren und eine etablierte SHA-256-Implementierung geprüft werden kann.
Das Wichtigste in Kürze
SHA-256 verarbeitet eine Nachricht nicht in einem einzigen Schritt.
Der Ablauf besteht aus mehreren aufeinander aufbauenden Teilen:
- Die Nachricht wird gepaddet.
- Die vorbereitete Nachricht wird in 512-Bit-Blöcke zerlegt.
- Jeder Block besteht zunächst aus 16 Wörtern mit jeweils 32 Bit.
- Daraus entsteht ein Message Schedule mit 64 Wörtern.
- SHA-256 besitzt acht 32-Bit-Wörter als internen Hashzustand.
- Für jeden Block werden acht Arbeitsvariablen
abishverwendet. - Jeder Block durchläuft 64 Kompressionsrunden.
- Die Funktionen
Ch,Maj,Σ₀undΣ₁kombinieren Teile des aktuellen Zustands. - Jede Runde verwendet ein Wort
Wₜund eine KonstanteKₜ. - Die temporären Werte
T₁undT₂bestimmen den nächsten Arbeitszustand. - Additionen erfolgen modulo
2³². - Nach 64 Runden wird das Ergebnis mit dem bisherigen Hashzustand kombiniert.
- Nach dem letzten Block werden
H₀bisH₇zum 256-Bit-Digest zusammengesetzt.
Wie geht es weiter?
Damit sind die einzelnen Bestandteile der SHA-256-Berechnung bekannt.
Im nächsten Artikel wird es praktisch.
Dort nehme ich eine konkrete Eingabe und verfolge sie Schritt für Schritt durch den Algorithmus:
Dabei sollst du nicht nur meine Beispielwerte betrachten können.
Mit dem SHA-256 Explorer kannst du anschließend eine eigene Eingabe – beispielsweise deinen Namen – verwenden und beobachten, wie daraus zunächst Bytes, dann ein gepaddeter Nachrichtenblock, das Message Schedule, die einzelnen Kompressionsrunden und schließlich dein SHA-256-Hash entstehen.
Dann wird aus:
Henrik
nicht einfach nur:
SHA-256 → Hashwert
sondern ein nachvollziehbarer Weg durch den gesamten Algorithmus.
Wie sich SHA-256 dabei von SHA-512 unterscheidet, zeige ich in SHA-256 vs. SHA-512 – was ist der Unterschied?.
Quellen und weiterführende Standards
Die folgenden Primär- und Normquellen bilden die Grundlage für die technischen Aussagen dieses Artikels:
-
National Institute of Standards and Technology (NIST), FIPS 180-4 – Secure Hash Standard (SHS) Primärquelle für SHA-256, Padding, Message Schedule, Funktionen, Konstanten und Kompressionsalgorithmus.
-
National Institute of Standards and Technology (NIST), Cryptographic Standards and Guidelines: Example Values Offizielle Beispiel- und Testwerte für kryptografische Algorithmen.
-
National Institute of Standards and Technology (NIST), CAVP – Secure Hashing Testvektoren und Informationen zur Validierung von Implementierungen der Secure Hash Algorithms.