Der SHA-256 (Secure Hash Algorithm). Kryptografie durch Mathematik

Inhaltsverzeichnis

1. Einleitung

2. Einführung in die Thematik, Operatoren und Funktionen
2.1 Grundlegende Begrifflichkeiten in der IT
2.2 Operatoren
2.2.1 Standardisierte logische Operatoren
2.2.2 Nach „NIST“ definierte Operatoren
2.3 Funktionen
2.3.1 „Ch(x,y,z)“
2.3.2 „Maj(x,y,z)"
2.3.3 „ ∑0{[256]} (x)“ und „ ∑1{[256]} (x)“
2.3.4 „σ0{[256]} (x)“ und „σ1{[256]} (x)“

3. Funktionsweise des SHA-2
3.1 SHA-256 Vorbereitung
3.1.1 Konstanten und Initiativ Hashwert
3.1.2 Datensatzerweiterung
3.1.3 Datengliederung
3.2 SHA-256 Hashberechnung
3.2.1 Ermitteln der Words
3.2.2 Initiierung der Arbeitsvariablen
3.2.3 Kompressionsfunktion
3.2.4 Zusammenführung zum Hashwert

4. Anhang der Abbildungen

5. Literaturverzeichnis

1. Einleitung

Das digitale Leben ist heutzutage allgegenwärtig: Banktransaktionen, Informationsaustausch oder ganz schlicht das Nutzen von sozialen Medien. Doch erfordert dies eine Authentifizierung, praktischer als Benutzerkonto mit Passwort bekannt. Dabei kommt die Frage auf, wie „das Internet“ bzw. die Server feststellen, ob ein individuelles Passwort korrekt ist, ohne dass dabei die Gefahr besteht, dass die auf den Servern gespeicherten Passwörter missbraucht werden könnten. Es wäre schließlich fatal, lägen persönliche Zugangsdaten unverschlüsselt auf jenen vor. Angreifer müssten lediglich solche Server ausspähen und hätten uneingeschränkten Zugang zu sensiblen Daten.

Dort greifen so genannte „Hash-Funktionen“. Diese verschlüsseln Daten wie Passwörter in eine formell festgelegte Informationseinheit, dem „Hash-Wert“. Aus bekannten Daten, sprich einem Passwort, kann ohne Aufwand jener erzeugt werden, andersherum ist es aber nicht möglich, aus einem Hash-Wert das dazugehörige Passwort zu ermitteln.

Zurück zum Beispiel kann so nun der Server das Passwort als Hash-Wert und nicht als „Klartext“ speichern. Beim Einloggen in einen Account schickt nun der Benutzer ein Passwort. Dieses wird vom Server nun in einen Hash-Wert umgeformt und mit dem bereits hinterlegten Wert, der bei der Erstellung des Benutzerkontos erstellt wurde, verglichen. Bei einem Konsens beider erfolgt die Anmeldung.

Angreifer könnten bei einem Angriff auf den Server nur den Hash-Wert auslesen. Dieser ist aber Nutzlos, da man, wie eingangs erwähnt, aus dem Hash nicht das Passwort ermitteln kann.

Wie man also erkennt sind Hash-Funktionen essentiell für unser digitale Leben, zumal dies nur ein Anwendungsgebiet ist.

Der SHA-256 ist als einer der meistgenutzten Hash-Funktionen somit ein prädestiniertes Beispiel für diese Thematik. Dabei wird bezogen auf den Titel dieser Hausarbeit zuerst der „mathematische Anteil“ erläutert, darauf aufbauend wird der SHA erklärt.

Hinsichtlich der Fachsprache wird jedes Fremdwort einfach markiert, anschließend wird es ohne gesonderte Bezeichnung in den Sprachfluss aufgenommen. Dies führt den Leser schneller in das Themengebiet ein. Da es sich beim SHA-256 um einen Standardisierung handelt, gilt es, sich nur auf eine Quelle, dem „National Institute of Standards and Technology“ (kurz „NIST“), zu beziehen.

2.1 Grundlegende Begrifflichkeiten in der IT

Das Boolesche-Algebra ist in der Informationstechnologie von höchster Bedeutung. Dabei unterteilt es seine Datenübermittler in zwei Zustände (folglich digital): True/Wahr/1 und False/Unwahr/0. Die kleinstmögliche Einheit, die einen dieser beiden Zustände tragen kann, nennt man „Bit“. Ein Einzelner Bit reicht nicht, um diese Technologie nutzbar zu machen. Man könnte nur zwei Werte darstellen, auf ein Beispiel bezogen nur die Zahl „0“ und die Zahl „1“.

Um diesen entgegen zu kommen hat man die nächst Größere Einheit „Byte“ definiert. Ein Byte beinhaltet acht hintereinander gereihte Bits. Mit einem Byte können somit schon 2[8] unterschiedliche Informationen wiedergeben, zum Beispiel die Zahlen 0 bis 255. Um einen deutlichen größeren Spielraum zu erhalten, können mehrere Bytes ebenfalls hintereinander gereiht werden.

Erweiternd gibt es noch das Format „Hexadecimal“ kurz „hex digits“. Bei diesem werden vier Bits durch eine Zahl bzw. Buchstaben („0-9“ + „A-F“) repräsentiert. Sobald man die eigentlich „10“ anzeigen möchte, nutz man schlicht die Buchstaben weiter (A=10, B=11…). So wird gewährleistet, dass man jeweils nur eine Stelle nutzt. Diese hex digits werden dann weiterführend wie Bits behandelt, mit dem Vorteil, dass der Binärcode übersichtlicher ist.

Darüber hinaus definiert das NIST noch „Words“, welche beim SHA-256 aus 4 Bytes bzw. 8 hex digits bzw. 32 Bits bestehen.

2.2.1 Standardisierte logische Operatoren

Die folgenden Operatoren vergleichen Bitweise, sprich für jede einzelne Bitstelle separat, ihren Input, hier primär als Words (32-Bit) vorliegend. Abschließend geben sie wieder Bitweise einen Output, welcher die gleiche Länge wie der Input (Words) hat. Somit werden mehrere Inputs, in der Regel zwei, zu einem Output zusammengefasst. In den Beispielen wird zur besseren Übersicht die Informationslänge auf 16-Bit beschränkt.

„Complement/NOT“

Wie eine Übersetzung erahnen lässt, wird bei „NOT“ der Komplementäre, also der gegensätzliche Wert als Output gegeben, wobei hierbei nur ein Input zulässig ist (Abb. Nr.1).

„OR“

Bei „OR“ (Englisch: „Oder“) wird der Output als True/1 ausgegeben, wenn einer der Inputs ebenfalls an der Stelle ein True definiert (Abb. Nr.2).

„XOR“

„XOR“ ist wie man vermuten kann sehr vergleichbar mit „OR“, jedoch mit dem Unterschied, dass wenn beide Inputs True sind, der Output nicht mehr als True sondern als False ausgegeben wird. Sinnbildlich hat „XOR“ die Einstellung „entweder… oder, nicht beides zusammen“ (Abb. Nr.3).

„AND“

Bei diesem Operator wird, im Gegensatz zum „XOR“ nur dann ein True ausgegeben, wenn beide Inputs True sind. Ist nur einer True, so ist der Output False (Abb. Nr.4).

2.2.2 Nach „NIST“ definierte Operatoren

Auch die folgenden Operatoren fungieren wie die vorherigen, jedoch sind sie nicht allgemein gültig definiert.

„Addition modulo 2w“

Dieser Operator ist vergleichbar mit dem grundbekannten „schriftlichen Addieren“. Hierbei ist es unerheblich, ob die Informationen als Binärcode oder als Klartext (übliche Zahlen, auch „Integer“ genannt) vorliegt. Die Zahlen werden mit Übertrag (beim Binärsystem bei „2“, beim Klartext ab „10“) addiert. Ziel der modularen Addition 2w, kurz „mod(2w)“, wobei „w“ die Bitlänge der Words darstellt (hier 32 Bit), ist es, dass der Output die gleiche Stellenanzahl (Binärcode) hat wie die Inputs bzw. keinen größeren Wert erreicht als maximal wiedergebbar (Klartext).

Da dies aber ohne weiteres schnell eintritt, wird die nötige Erweiterung der Stellen, zum Beispiel von 32-Bit auf 33-Bit, schlicht ignoriert. Praktisch auf Klartextzahlen bezogen bedeutet dies, dass sofern das Ergebnis der Addition der Inputs größer als 2w ist, von jenem 2w subtrahiert wird. Dies geschieht so oft, dass der finale Wert kleiner als 2w ist (vgl. (National Institute of Standards and Technology, 2015, S. 8)). Ein Beispiel findet sich in Abbildung Nr.5.

„ROTRn (x)“

Dieser Operator ist abzuleiten von „Rotate Right“. Entsprechend der Übersetzung wird dabei jedes Bit um „n“ Stellen rechts verschoben, wobei Anfang und Ende der Information „x“ wie in einem Kreis verknüpft werden. Dadurch werden keine Bits gelöscht und auch die Sequenz der Bits wird nicht verändert (Anfang und Ende verbunden), lediglich ihre Position wird verschoben (vgl. (National Institute of Standards and Technology, 2015, S. 5)). Da hier keine Informationen verglichen werden, gibt es dementsprechend nur einen Input. Im Beispiel in der Abbildung Nr.6 beträgt n=1.

„SHRn (x)“

„Shift Right“, kurz SHRn(x), ist vergleichbar mit Rotate Right, jedoch mit dem Unterschied, dass Anfang und Ende der Folge nicht miteinander verknüpft sind. Folglich gehen bei der Verschiebung n Stellen verloren. Des Weiteren fehlen n Stellen auf der anderen (linken) Seite, welche durch n Bits mit dem Wert „0“ vervollständigt werden (vgl. (National Institute of Standards and Technology, 2015, S. 6)). Die Abbildung Nr.7 nutz n=4.

2.3.1 „Ch(x,y,z)“

Diese Funktion des NIST ist aus dem Englischen „Choose“ zu Deutsch „Wählen“ abzuleiten.

Sie fungiert ebenfalls Bitweise auf Words und ermittelt aus drei Inputs (x,y,z) einen ebenfalls formatgleichen Output. Dabei ist die Information „x“ der Referenzwert, je nachdem ob nun an einer Bitstelle von „x“ der Wert 0 oder 1 ist, wird als Output der Stellenwert von „z“ (x=0) bzw. der Stellenwert von „y“ (x=1) ausgegeben (vgl. (National Institute of Standards and Technology, 2015, S. 10)). „x“ wählt somit aus, welcher der beiden Nebeninputs weitergegeben wird (Abb. Nr.8).

2.3.2 „Maj(x,y,z)“

Auch diese Funktion hat drei Inputs und einen Output, jedoch gibt sie als letzteren den Wert aus, der bei den drei Inputs je Stelle am häufigsten vorkommt („Majority“ = „Mehrheit“) (vgl. (National Institute of Standards and Technology, 2015, S. 10)). Dieser Fall tritt folglich bei einer Werthäufung von zwei oder drei „0“ bzw. „1“ ein (Abb. Nr.9).

2.3.3 „ ∑0{[256]} (x)“ und „ ∑1{[256]} (x)“

Beide Funktionen nutzen die Operatoren ROTRn(x) und XOR. Darüber hinaus ermitteln sie aus einem Word ein neues als Output, die schematische Zusammenhänge sind so definiert:

Abbildung in dieser Leseprobe nicht enthalten

(National Institute of Standards and Technology, 2015, S. 10)

Bemerkungen:

⊕ = XOR ; ROTRn(x) mit n=Wert, um den Verschoben wird.

Zuerst werden je nach Funktion drei ROTRn(x) auf dasselbe Word durchgeführt. Das Ergebnis dieser Operatoren wird nach XOR kombiniert.

2.3.4 „σ0{[256]} (x)“ und „σ1{[256]} (x)“

Diese Funktionen sind vom Aufbau fast identisch wie die beiden vorrausgegangenen (Kapitel 2.3.3). Sie nutzen den Operator ROTRn(x) jedoch nur zweimal, als dritter wird SHRn(x) herangeführt.

Abbildung in dieser Leseprobe nicht enthalten

(National Institute of Standards and Technology, 2015, S. 10)

Bemerkungen:

⊕ = XOR ; ROTRn(x) und SHRn(x) mit n=Wert, um den Verschoben wird.

Zuerst werden je nach Funktion zweimal ROTRn(x) und einmal SHRn(x) auf dasselbe Word durchgeführt. Das Ergebnis dieser Operatoren wird nach XOR kombiniert.

3.1.1 Konstanten und Initiativ Hashwert

Konstante „Kt“

Bevor der eigentliche Algorithmus, auch „die Kompressionsfunktion genannt“, fungieren kann, müssen die Konstanten „ Kt“ eingearbeitet werden. Diese sind vorab definiert, wobei sie die ersten 32 Bit der Nachkommastellen des Ergebnisses der Kubikwurzel der ersten 64 Primzahlen darstellen (vgl. (National Institute of Standards and Technology, 2015, S. 11)). Somit erhält man 64 Konstanten im 32-Bit Format (siehe Abb. Nr.10).

Initiativ Hashwert „H([0])j“

Die Idee hinter der Kompressionsfunktion ist, dass ein vorrausgegangener Hashwert mit Inputdaten kombiniert zu einem neuen Hashwert ausgegeben wird. Dazu ist es jedoch von Nöten, einen Startwert zu haben, genauer gesagt „ H([0])j“ (vgl. (National Institute of Standards and Technology, 2015, S. 4). Da im Algorithmus mit Words (32-Bit) gearbeitet wird, der eigentliche Hashausgabewert jedoch aus 256-Bit besteht (SHA-256), wird die Information auf acht Words, auch Arbeitsvariablen genannt, aufgeteilt (8*32=256). Mit „ j“ wird somit eine Zugehörigkeit dieser acht gefunden. Die Variablen sind durch die ersten 32 Bit der Nachkommastellen der Quadratwurzeln der ersten acht Primzahlen (siehe Abb. Nr.11) abzuleiten.

[...]