Wie funktioniert SHA-3?
SHA-3 unterscheidet sich im Aufbau grundlegend von Hashfunktionen wie SHA-256 oder SHA-512. Während die SHA-2-Familie Nachrichten blockweise mit Kompressionsfunktionen verarbeitet, basiert SHA-3 auf einer Sponge Construction.
Im Artikel Was ist SHA-3? haben wir uns bereits angesehen, was SHA-3 ist und wie sich die Hashfamilie von SHA-2 unterscheidet.
Jetzt gehen wir einen Schritt weiter.
Ich zeige dir, was innerhalb von SHA3-256 passiert – von der Eingabe über Padding und Absorbing bis zum fertigen 256-Bit-Hashwert.
Als Beispiel verwenden wir die Nachricht:
hello
SHA3-256 erzeugt daraus:
3338be694f50c5f338814986cdf06864
53a888b84f424d792af4b9202398f392
Die entscheidende Frage lautet:
Was passiert zwischen hello und diesem Hashwert?
Der Ablauf von SHA3-256 im Überblick
Vereinfacht lässt sich SHA3-256 in mehrere Schritte zerlegen:
Nachricht
│
▼
UTF-8-Bytes
│
▼
Domain Separation + Padding
│
▼
Aufteilung in Rate-Blöcke
│
▼
Absorbing
│
▼
Keccak-Permutation
│
▼
Squeezing
│
▼
256-Bit-Hashwert
Im Zentrum steht dabei ein interner Zustand mit einer Größe von 1600 Bit.
Für SHA3-256 gelten folgende Parameter:
| Parameter | SHA3-256 |
|---|---|
| State | 1600 Bit |
| Rate | 1088 Bit |
| Capacity | 512 Bit |
| Hashlänge | 256 Bit |
| Permutation | KECCAK-p[1600,24] |
| Runden | 24 |
Dabei gilt:
Rate + Capacity = State
1088 + 512 = 1600 Bit
Diese Werte begleiten uns durch den gesamten Algorithmus.
Probiere den Ablauf selbst aus
Mit dem folgenden Explorer kannst du den vollständigen SHA3-256-Ablauf für eine eigene Eingabe untersuchen.
Du kannst unter anderem sehen:
- welche UTF-8-Bytes aus deiner Eingabe entstehen,
- wie Domain Separation und Padding aussehen,
- in wie viele Rate-Blöcke die Nachricht zerlegt wird,
- wie der interne 1600-Bit-Zustand aufgebaut ist,
- wie ein Nachrichtenblock mit dem State XOR-verknüpft wird,
- wie sich der State durch Keccak-f verändert,
- und welche Bytes schließlich den SHA3-256-Hashwert bilden.
SHA3-256 im Prozess
Verfolge Schritt für Schritt, wie aus einer Eingabe ein SHA3-256-Hashwert entsteht. Das Werkzeug zeigt Zwischenzustände derselben Berechnung, die den Hashwert liefert.
- Zustand
- 1600 Bit
- Rate
- 1088 Bit / 136 Byte
- Capacity
- 512 Bit / 64 Byte
- Ausgabe
- 256 Bit / 32 Byte
- Permutation
- Keccak-f[1600]
- Runden
- 24
Diese Implementierung dient der Veranschaulichung. Für produktive Kryptografie sollten geprüfte kryptografische Bibliotheken verwendet werden.
Die angezeigten Zwischenzustände sind dabei nicht nur eine vereinfachte Illustration. Sie stammen direkt aus derselben SHA3-256-Berechnung, aus der auch der endgültige Hashwert erzeugt wird.
Schauen wir uns die einzelnen Schritte jetzt genauer an.
Schritt 1: Die Nachricht wird in Bytes umgewandelt
Eine Hashfunktion arbeitet nicht direkt mit Buchstaben oder Wörtern.
Sie verarbeitet Bits beziehungsweise Bytes.
Unsere Beispielnachricht lautet:
hello
In UTF-8 entsprechen die fünf Zeichen folgenden Bytes:
68 65 6c 6c 6f
Insgesamt besteht die Nachricht damit aus:
5 Byte = 40 Bit
Bei einfachen ASCII-Zeichen entspricht jedes Zeichen genau einem Byte.
Das gilt allerdings nicht für alle Texte.
Ein Zeichen wie:
ö
benötigt in UTF-8 beispielsweise mehr als ein Byte. Deshalb ist für die Verarbeitung nicht die Anzahl sichtbarer Zeichen entscheidend, sondern die tatsächliche Bytefolge der codierten Nachricht.
SHA3-256 verarbeitet letztlich genau diese Bitfolge.
Schritt 2: SHA-3 ergänzt Domain Separation und Padding
Bevor die Nachricht absorbiert werden kann, muss sie auf eine geeignete Länge gebracht werden.
Dabei passieren zwei Dinge:
- SHA-3 ergänzt Bits zur Domain Separation.
- Anschließend wird die Nachricht mit dem Keccak-Padding aufgefüllt.
Für die vier SHA-3-Hashfunktionen definiert FIPS 202:
M || 01
M steht dabei für die ursprüngliche Nachricht.
An die Nachricht werden also zunächst die beiden Bits:
01
angehängt.
Diese Bits dienen der Domain Separation. Sie sorgen unter anderem dafür, dass die SHA-3-Hashfunktionen von anderen Funktionen unterschieden werden können, die dieselbe zugrunde liegende Keccak-Konstruktion verwenden.
Anschließend wird das Padding:
pad10*1
angewendet.
Der Name beschreibt bereits das grundlegende Muster:
1
0...
1
Es wird also ein 1-Bit angefügt, danach folgen so viele 0-Bits wie notwendig und am Ende steht wieder ein 1-Bit.
Die Nachricht wird dadurch so verlängert, dass ihre Länge zu den Blöcken der Sponge Construction passt.
Warum sieht man bei SHA3-256 häufig 0x06 und 0x80?
In Implementierungen begegnet einem bei SHA-3 häufig der Bytewert:
0x06
und am Ende eines Padding-Blocks häufig:
0x80
Das kann leicht zu der vereinfachten Vorstellung führen, SHA-3 würde einfach die Bytes 06 und 80 an eine Nachricht anhängen.
So sollte man es allerdings nicht verstehen.
Die Definition in FIPS 202 erfolgt auf Bitebene:
M || 01
gefolgt von:
pad10*1
Die Bytewerte entstehen aus der konkreten Codierung dieser Bits innerhalb der Bytefolge.
Für unsere Eingabe hello sieht der Anfang des gepaddeten Blocks deshalb beispielsweise so aus:
68 65 6c 6c 6f 06 00 00 ...
und am Ende des Blocks befindet sich das abschließende Padding-Bit.
In der üblichen byteorientierten Darstellung zeigt sich dieses am Ende als gesetztes höchstes Bit:
... 00 00 00 80
Eine interessante Besonderheit entsteht, wenn das Ende der Nachricht unmittelbar vor der Blockgrenze liegt.
Dann können die Suffix-Bits und das abschließende Padding-Bit im selben Byte landen.
Für SHA3-256 kann dadurch beispielsweise:
0x86
entstehen.
0x06, 0x80 oder 0x86 sind also keine willkürlich gewählten „magischen Bytes“, sondern das Ergebnis der Bitdefinition von Domain Separation und Padding.
Schritt 3: Die Nachricht wird in Rate-Blöcke aufgeteilt
SHA3-256 verwendet eine Rate von:
1088 Bit
Das entspricht:
136 Byte
Die vorbereitete Nachricht wird deshalb in Blöcke mit jeweils 136 Byte aufgeteilt.
Unsere Nachricht hello ist sehr kurz.
Nach Domain Separation und Padding passt sie vollständig in einen einzigen Rate-Block:
Block 1
136 Byte
Bei längeren Nachrichten entstehen mehrere Blöcke:
Block 1
136 Byte
Block 2
136 Byte
Block 3
136 Byte
...
Wichtig ist dabei, dass die Anzahl der Blöcke nicht allein von der ursprünglichen Nachrichtenlänge abhängt.
Auch Domain Separation und Padding benötigen Platz.
Eine Nachricht mit genau 136 Byte benötigt deshalb bereits einen weiteren Block für die zusätzlichen Bits.
Schritt 4: SHA3-256 verwendet einen 1600-Bit-State
Das Herzstück der Berechnung ist der interne Zustand – der sogenannte State.
Bei SHA-3 besitzt dieser State eine Größe von:
1600 Bit
Er kann als 25 sogenannte Lanes mit jeweils 64 Bit betrachtet werden:
25 × 64 Bit = 1600 Bit
Diese 25 Lanes werden konzeptionell in einer 5×5-Struktur angeordnet:
5 × 5 Lanes
Zu Beginn der Berechnung sind sämtliche Bits dieses Zustands 0.
Vereinfacht:
0000000000000000
0000000000000000
0000000000000000
...
für alle 25 Lanes.
Die 5×5-Darstellung wird besonders wichtig, wenn wir uns die Keccak-Permutation später genauer ansehen.
Für den grundlegenden SHA3-256-Ablauf reicht zunächst die Vorstellung eines 1600 Bit großen internen Zustands.
Rate und Capacity teilen den State auf
Die 1600 Bit des States werden für die Sponge Construction konzeptionell in zwei Bereiche unterteilt:
┌───────────────────────────────────────┬──────────────────┐
│ Rate: 1088 Bit │ Capacity: 512 Bit│
└───────────────────────────────────────┴──────────────────┘
Zusammen ergeben sie:
1088 + 512 = 1600 Bit
Die Rate ist der Bereich, über den Eingabe und Ausgabe mit dem State interagieren.
Die Capacity wird nicht direkt mit den Nachrichtenblöcken XOR-verknüpft.
Sie ist ein wesentlicher Bestandteil der Sicherheitseigenschaften der Sponge Construction.
Bei SHA3-256 beträgt die Capacity:
512 Bit
und damit das Doppelte der Digest-Länge von 256 Bit.
Warum Rate und Capacity existieren und wie ihre Größen mit den Sicherheitseigenschaften einer Sponge Construction zusammenhängen, schauen wir uns in einem eigenen Artikel genauer an.
Schritt 5: Der erste Block wird absorbiert
Jetzt beginnt die sogenannte Absorbing Phase.
Der erste 136-Byte-Block der vorbereiteten Nachricht wird mit dem Rate-Bereich des States verknüpft.
Dafür verwendet Keccak die bitweise XOR-Operation.
Vereinfacht:
Nachrichtenblock
│
▼
XOR
│
▼
┌──────────────────────────┬──────────────┐
│ Rate │ Capacity │
│ 1088 Bit │ 512 Bit │
└──────────────────────────┴──────────────┘
Nur der Rate-Bereich wird direkt mit dem Nachrichtenblock XOR-verknüpft.
Die Capacity erhält keine Nachrichtenbits direkt.
Beim ersten Block besteht der State zunächst vollständig aus Nullen.
Deshalb entspricht der Rate-Bereich nach dem ersten XOR zunächst den Bits des Nachrichtenblocks.
Das allein würde allerdings noch keine kryptografisch interessante Transformation ergeben.
Deshalb folgt anschließend der entscheidende Schritt:
die Keccak-Permutation.
Schritt 6: Keccak-f transformiert den gesamten State
Nachdem ein Nachrichtenblock mit dem Rate-Bereich XOR-verknüpft wurde, wird der gesamte 1600-Bit-State transformiert.
SHA-3 verwendet dafür die Permutation:
KECCAK-p[1600,24]
Diese entspricht der 24-rundigen Keccak-f-Permutation für einen 1600 Bit großen State.
Jede Runde besteht aus fünf Transformationen:
θ Theta
ρ Rho
π Pi
χ Chi
ι Iota
Diese fünf Schritte verändern und vermischen die Bits des States auf unterschiedliche Weise.
Für das Verständnis des grundlegenden SHA3-256-Ablaufs müssen wir ihre genaue Funktionsweise noch nicht kennen.
Entscheidend ist zunächst:
State vor der Permutation
│
▼
Keccak-f[1600]
24 Runden
│
▼
State nach der Permutation
Der State nach diesen 24 Runden sieht vollständig anders aus als davor.
Diese wiederholte Transformation des internen Zustands bildet den kryptografischen Kern von SHA-3.
Wie Theta, Rho, Pi, Chi und Iota genau funktionieren, schauen wir uns später separat an.
Was passiert bei mehreren Nachrichtenblöcken?
Unsere Beispielnachricht hello benötigt nur einen einzigen Block.
Bei längeren Nachrichten wiederholt sich der Absorbing-Prozess.
Nach dem ersten Block besitzt der State bereits das Ergebnis der Keccak-Permutation.
Der zweite Nachrichtenblock wird anschließend mit dem Rate-Bereich dieses bereits veränderten States XOR-verknüpft.
Danach wird erneut Keccak-f angewendet.
Der Ablauf sieht also so aus:
Block 1
│
▼
XOR
│
▼
Keccak-f
│
▼
State 1
Block 2
│
▼
XOR
│
▼
Keccak-f
│
▼
State 2
Block 3
│
▼
XOR
│
▼
Keccak-f
│
▼
State 3
Dieser Vorgang wird so lange wiederholt, bis alle Nachrichtenblöcke absorbiert wurden.
Jeder Block beeinflusst dadurch den internen Zustand, auf dem der nächste Block weiterarbeitet.
Warum wird der State nach jedem Block transformiert?
Der nächste Nachrichtenblock wird nicht in einen frischen State aufgenommen.
Er trifft auf den Zustand, der bereits aus allen zuvor verarbeiteten Blöcken entstanden ist:
State 0
+
Block 1
↓
Permutation
↓
State 1
+
Block 2
↓
Permutation
↓
State 2
Die bisher verarbeitete Nachricht beeinflusst damit den Zustand, in den der nächste Block aufgenommen wird.
Gleichzeitig wirkt die Keccak-Permutation auf den gesamten 1600-Bit-State. Änderungen, die zunächst über den Rate-Bereich eingebracht wurden, werden dadurch über den State verteilt.
Schritt 7: Nach dem Absorbieren beginnt das Squeezing
Nachdem alle Nachrichtenblöcke verarbeitet wurden, beginnt die zweite große Phase der Sponge Construction:
die Squeezing Phase.
Während beim Absorbieren Daten in den State eingebracht werden, werden beim Squeezing Output-Bits aus dem Rate-Bereich des States entnommen.
Für SHA3-256 benötigen wir:
256 Output-Bits
Der Rate-Bereich enthält:
1088 Bit
Damit passen die benötigten 256 Bit vollständig in die erste verfügbare Ausgabe des Rate-Bereichs.
SHA3-256 muss deshalb für seinen 256 Bit langen Digest keine zusätzliche Permutation durchführen, um weitere Output-Bits zu erhalten.
Bei Sponge-Funktionen mit längerer gewünschter Ausgabe kann das anders aussehen: Reicht der aktuelle Rate-Bereich nicht aus, wird erneut permutiert und anschließend weiterer Output entnommen.
Dieses Prinzip spielt insbesondere bei den SHAKE-Funktionen eine wichtige Rolle.
Schritt 8: Die ersten 256 Bit werden zum SHA3-256-Hash
Für unsere Eingabe:
hello
erhalten wir schließlich 32 Byte beziehungsweise 256 Bit.
Hexadezimal dargestellt sind das:
3338be694f50c5f338814986cdf06864
53a888b84f424d792af4b9202398f392
Damit ist die SHA3-256-Berechnung abgeschlossen.
Der gesamte Datenfluss lässt sich jetzt auf vier zentrale Phasen reduzieren:
Padding
↓
Absorb
↓
Permutation
↓
Squeeze
Die Nachricht wird zunächst für die 136-Byte-Blöcke vorbereitet. Jeder Block wird in den Rate-Bereich absorbiert und anschließend wird der gesamte State durch Keccak-f transformiert.
Nach dem letzten Block werden beim Squeezing die benötigten 256 Output-Bits aus dem Rate-Bereich entnommen.
Aus:
hello
wird so schließlich:
3338be694f50c5f338814986cdf06864
53a888b84f424d792af4b9202398f392
Was wir bisher noch vereinfacht haben
Mit diesem Ablauf können wir bereits nachvollziehen, wie eine Nachricht grundsätzlich durch SHA3-256 verarbeitet wird.
Einige wichtige Details haben wir allerdings bewusst noch nicht vollständig zerlegt.
Zum Beispiel:
- Wie funktioniert eine Sponge Construction genau?
- Warum gibt es Rate und Capacity?
- Warum ist die Capacity bei SHA3-256 512 Bit groß?
- Wie werden die 1600 Bits exakt auf die 25 Lanes verteilt?
- Wie werden Bytes innerhalb der Lanes angeordnet?
- Was passiert innerhalb einer einzelnen Keccak-f-Runde?
- Was machen Theta, Rho, Pi, Chi und Iota?
- Wie unterscheiden sich SHA3-224, SHA3-256, SHA3-384 und SHA3-512 intern?
- Wie können SHAKE128 und SHAKE256 Ausgaben unterschiedlicher Länge erzeugen?
Diese Fragen sind umfangreich genug für eigene Artikel und interaktive Beispiele.
Für das grundlegende Verständnis von SHA3-256 ist zunächst entscheidend, den Datenfluss zu verstehen:
Padding
↓
Absorb
↓
Permutation
↓
Squeeze
Dieser Ablauf zeigt gleichzeitig, warum SHA3-256 trotz derselben Hashlänge technisch grundlegend anders arbeitet als SHA-256. SHA3-256 verwendet einen Sponge mit einem 1600-Bit-State und der Keccak-Permutation statt der Kompressionskonstruktion von SHA-256.
Das Wichtigste in Kürze
SHA3-256 verarbeitet eine Nachricht mit Hilfe einer Sponge Construction und eines 1600 Bit großen internen Zustands.
Die wichtigsten Punkte, die du dir merken solltest:
- SHA3-256 arbeitet mit einem 1600 Bit großen State aus 25 Lanes mit jeweils 64 Bit.
- Die Rate beträgt 1088 Bit beziehungsweise 136 Byte, die Capacity 512 Bit.
- Domain Separation und
pad10*1bereiten die Nachricht für die Verarbeitung vor. - Die vorbereitete Nachricht wird in 136-Byte-Blöcke aufgeteilt.
- Jeder Block wird mit dem Rate-Bereich XOR-verknüpft.
- Anschließend transformiert
KECCAK-p[1600,24]den gesamten State in 24 Runden. - Nach dem letzten Nachrichtenblock beginnt die Squeezing Phase.
- Die ersten 256 benötigten Output-Bits bilden den 32 Byte langen SHA3-256-Digest.
Damit kennen wir jetzt den grundlegenden Weg von einer Nachricht bis zum SHA3-256-Hash.
Der nächste wichtige Baustein ist die Konstruktion, die hinter diesem gesamten Ablauf steckt:
die Sponge Construction.
Quellen und weiterführende Standards
-
NIST FIPS 202 – SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions
Der zentrale Standard für SHA-3. Er definiert unter anderem die SHA-3-Hashfunktionen,KECCAK-p, die Sponge Construction,pad10*1sowie SHAKE128 und SHAKE256. -
NIST – SHA-3 Project
Offizielle NIST-Übersicht zur Entwicklung, Standardisierung und zu weiterführenden SHA-3-Dokumenten. -
NIST ITL Bulletin – Additional Secure Hash Algorithm Standards Offer New Opportunities for Data Protection
NIST-Zusammenfassung von FIPS 202 und der SHA-3-Familie.