Beziehung zwischen den Sicherheitsanforderungen an Hashfunktionen
Nachrichten können auf verschiedene Weisen authentifiziert werden, so dass Man-in-the-Middle-Angriffe (MitM)[1] verhindert werden können.
Szenarien
Im ersten Szenario wird der Hash an die Nachricht angehängt und als ganzes verschlüsselt. Wir erhalten Vertraulichkeit und Authentizität.
Im zweiten Szenario wird der Hash der Nachricht berechnet und dann verschlüsselt. Der Empfänger kann den Hash berechnen und mit dem entschlüsselten Hash vergleichen. Wir erhalten Authentizität, aber keine Vertraulichkeit.
Im dritten Szenario wird an die Nachricht ein geteiltes Secret angehängt und alles zusammen gehasht. Die Nachricht wird dann mit dem Ergebnis der vorhergehenden Operation zusammen verschickt.
Im letzten Szenario werden alle Ansätze kombiniert.
Legende
die Nachricht
die Hashfunktion
der Verschlüsselungsalgorithmus
der Entschlüsselungsalgorithmus
ein geheimer Schlüssel
eine geheime Zeichenkette
die Konkatenation von zwei Werten (d. h. das Aneinanderhängen von zwei Werten)
Digitale Signaturen dienen dem Nachweis der Authentizität einer Nachricht und der Integrität der Nachricht. Jeder, der einen öffentlichen Schlüssel hat, kann die Signatur überprüfen, aber nur der Besitzer des privaten Schlüssels kann die Signatur erstellen.
Legende
die Nachricht
die Hashfunktion
der Verschlüsselungsalgorithmus
der Entschlüsselungsalgorithmus
der private Schlüssel von a
der öffentliche Schlüssel von a
die Konkatenation von zwei Werten (d. h. das Aneinanderhängen von zwei Werten)
(Vorgeschlagen von Merkle.)
\(IV\) = Initialer Wert (Algorithmus-abhängig)
\(CV_i\) = Verkettungsvariable
\(Y_i\) = i-er Eingabeblock
\(f\) = Kompressionsfunktion
\(n\) = Länge des Blocks
\(L\) = Anzahl der Eingabeblöcke
\(b\) = Länge des Eingabeblocks
Diese Struktur liegt insbesondere den Hashfunktionen der SHA-2 Familie zugrunde.
SHA-512 nimmt eine Nachricht beliebiger Größe und gibt einen 512-Bit-Hashwert zurück.
Der IV von SHA-512 besteht aus den folgenden acht 64-Bit-Zahlen:
6a09e667f3bcc908 bb67ae8584caa73b 3c6ef372fe94f82b a54ff53a5f1d36f1 510e527fade682d1 9b05688c2b3e6c1f 1f83d9abfb41bd6b 5be0cd19137e2179
Die Addition erfolgt Wortweise modulo \(2^{64}\).
Die Nachricht wird in 1024-Bit-Blöcke unterteilt. Die Nachricht wird - unabhängig von der tatsächlichen Länge - immer aufgefüllt (padded) und auf eine Länge \(l \equiv 896 (mod\, 1024)\) Bits gebracht.
Das Padding besteht aus einem Bit mit Wert 1, gefolgt von der notwendigen Anzahl Nullen.
Am Ende wird die Länge der Nachricht als 128-Bit-Wert angehängt, um ein Vielfaches von 1024 zu erhalten.
Die Additionen erfolgen Modulo \(2^{64}\).
Berechnung der \(W_i\)
\(W_0\) bis \(W_{15}\) sind die ersten 16 Wörter des 1024-Bit-Blocks. Die restlichen 64 Wörter werden wie folgt berechnet.
\(w_t = \sigma_1(w_{t-2}) + w_{t-7} + \sigma_0(w_{t-15}) + w_{t-16}\)
Mit:
\(\sigma_0(x) = (x \ggg 1) \oplus (x \ggg 8) \oplus (x \gg 7)\)
\(\sigma_1(x) = (x \ggg 19) \oplus (x \ggg 61) \oplus (x \gg 6)\)
Rundenfunktion
Weiterhin gilt:
\(t\) ist die Schrittnummer
\(Ch(e,f,g) = (e \land f) \oplus (\neg e \land g)\)
\(Maj(a,b,c) = (a \land b) \oplus (a \land c) \oplus (b \land c)\)
\(\sum\nolimits_{0}^{512} a = a \ggg 28 \oplus a \ggg 34 \oplus a \ggg 39\)
\(\sum\nolimits_{1}^{512} e = e \ggg 14 \oplus e \ggg 18 \oplus e \ggg 41\)
Berechnung der Konstanten
Die Konstanten \(K\) sind die ersten 64 Bits der Bruchteile der Kubikwurzeln der ersten 80 Primzahlen.
Konzeptionell: \(((\sqrt[3]{n_{te}\, Primzahl} - \lfloor \sqrt[3]{n_{te}\, Primzahl} \rfloor) << 64)\).toInt().toString(16)
Die SHA-512 Konstanten
428a2f98d728ae22 7137449123ef65cd b5c0fbcfec4d3b2f e9b5dba58189dbbc 3956c25bf348b538 59f111f1b605d019 923f82a4af194f9b ab1c5ed5da6d8118 d807aa98a3030242 12835b0145706fbe 243185be4ee4b28c 550c7dc3d5ffb4e2 72be5d74f27b896f 80deb1fe3b1696b1 9bdc06a725c71235 c19bf174cf692694 e49b69c19ef14ad2 efbe4786384f25e3 0fc19dc68b8cd5b5 240ca1cc77ac9c65 2de92c6f592b0275 4a7484aa6ea6e483 5cb0a9dcbd41fbd4 76f988da831153b5 983e5152ee66dfab a831c66d2db43210 b00327c898fb213f bf597fc7beef0ee4 c6e00bf33da88fc2 d5a79147930aa725 06ca6351e003826f 142929670a0e6e70 27b70a8546d22ffc 2e1b21385c26c926 4d2c6dfc5ac42aed 53380d139d95b3df 650a73548baf63de 766a0abb3c77b2a8 81c2c92e47edaee6 92722c851482353b a2bfe8a14cf10364 a81a664bbc423001 c24b8b70d0f89791 c76c51a30654be30 d192e819d6ef5218 d69906245565a910 f40e35855771202a 106aa07032bbd1b8 19a4c116b8d2d0c8 1e376c085141ab53 2748774cdf8eeb99 34b0bcb5e19b48a8 391c0cb3c5c95a63 4ed8aa4ae3418acb 5b9cca4f7763e373 682e6ff3d6b2b8a3 748f82ee5defb2fc 78a5636f43172f60 84c87814a1f0ab72 8cc702081a6439ec 90befffa23631e28 a4506cebde82bde9 bef9a3f7b2c67915 c67178f2e372532b ca273eceea26619c d186b8c721c0c207 eada7dd6cde0eb1e f57d4f7fee6ed178 06f067aa72176fba 0a637dc5a2c898a6 113f9804bef90dae 1b710b35131c471b 28db77f523047d84 32caab7b40c72493 3c9ebe0a15c9bebc 431d67c49c100d4c 4cc5d4becb3e42b6 597f299cfc657e2a 5fcb6fab3ad6faec 6c44198c4a475817
Exemplarischer Code zur Berechnung der Konstanten
Der folgende JavaScript Code demonstriert, wie die Konstanten für SHA-512 berechnet werden bzw. wurden. Die Präzision von Standard JavaScript Gleitkommazahlen (64-Bit Double) ist jedoch nicht ganz ausreichend, um die Konstanten vollständig zu berechnen.
1const primes = [22, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,361, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,4131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,5197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269,6271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,7353, 359, 367, 373, 379, 383, 389, 397, 401, 409 ];89function* genSHA512Constants() {10let i = 0;11while(i < 80) {12const p = primes[i];13const cubeRootP = Math.cbrt(p); // == p ** (1/3);14yield (cubeRootP - Math.floor(cubeRootP));15++i;16}17}18for(const c of genSHA512Constants()) {19console.log(c.toString(16));20}
Der folgenden Java Code demonstriert, wie die Konstanten für SHA-512 berechnet werden können. Wir verwenden hier die Klasse BigDecimal, um die Konstanten zu berechnen, da Java keinen long double Typ (mit 128 Bit) kennt.
1/**2* Compute the cube root using BigDecimals and the Newton-Raphson3* algorithm.4*5* @param n the number for which the cube root should be computed.6* @param guess the current/initial guess. Can be BigDecimal.ONE.7* @param the number of steps to be executed. The algorithm is8* iterative and the number of steps determines the9* precision of the result.10*/11BigDecimal cbrt(BigDecimal n, BigDecimal guess, int steps) {12if (steps == 0) return guess;13final var newGuess =14guess.add(15guess.pow(3).add(n.negate()).divide(16guess.pow(2).multiply(new BigDecimal(3)),17MathContext.DECIMAL12818).negate()19);20return cbrt(n,newGuess,steps -1);21}22/**23* Given a prime number get the first 64 bits of the fractional24* part of the cube root.25*/26String shaConstant(int prime) {27final var cubeRoot = cbrt(new BigDecimal(prime),BigDecimal.ONE,16);28// "extract" the fractional by computing modulo 129final var fractionalPart = cubeRoot.remainder(BigDecimal.ONE);30// To extract the first 64 bits we effectively do a shift-left31// by 64 which we simulate by multiplying with 2^6432final var bits = fractionalPart.multiply(BigDecimal.TWO.pow(64));33// to get the HEX representation we use BigInteger's toString34// method as a convenience method35return bits.toBigInteger().toString(16);36}
Padding und Hashing
Im Rahmen der Speicherung von Passwörtern und Secret Keys ist die Verwendung von Padding Operationen bzw. das Hashing von Passwörtern, um Eingaben in einer wohl-definierten Länge zu bekommen, üblich. Neben dem hier gesehenen Padding, bei dem 0x00 Werte angefügt werden, ist zum Beispiel auch das einfache Wiederholen des ursprünglichen Wertes, bis man auf die notwendige Länge kommt, ein Ansatz.
Diese Art Padding darf jedoch nicht verwechselt werden mit dem Padding, dass ggf. im Rahmen der Verschlüsselung von Nachrichten notwendig ist, um diese ggf. auf eine bestimmte Blockgröße zu bringen (zum Beispiel bei ECB bzw. CBC Block Mode Operations.)
Ein MAC Algorithmus für die Einmalauthentifizierung von Nachrichten.
Entwickelt von Daniel J. Bernstein.
Basierend auf einem 256-Bit-Schlüssel und einer Nachricht wird ein 128-Bit-Tag berechnet.
In Verbindung mit ChaCha20 in einer Reihe von Protokollen verwendet.
Aufteilung des Schlüssels
Verarbeitung der Nachricht
initialisiere den Akkumulator \(a\) mit 0
die Nachricht wird in Blöcke von 16 Byte aufgeteilt und als little-endian Zahl verarbeitet; d. h. ein Block hat 16 Oktette (\(16 \times 8\) Bit)
Füge dem Block \(n\) ein Bit jenseits der Anzahl der Oktette des aktuellen Blocks hinzu \(= n'\); d. h. im Falle eines 16-Byte-Blocks wird die Zahl \(2^{128}\) addiert
(Danach haben wir ggf. eine 17-Byte-Zahl.)
Addiere \(n'\) aus dem letzten Schritt zum Akkumulator \(a\) und multipliziere mit \(\text{clamped r}\)
Aktualisiere den Akkumulator mit dem Ergebnis \(modulo\, P\) mit \(P = 2^{130} - 5\): \(a = ((a + n') \times \text{clamped r})\mod P\)
Beispiel
000 43 72 79 70 74 6f 67 72 61 70 68 69 63 20 46 6f Cryptographic Fo
016 72 75 6d 20 52 65 73 65 61 72 63 68 20 47 72 6f rum Research Gro
032 75 70 upSei \(\text{clamped r} = 806d5400e52447c036d555408bed685\)
Sei \(s = 1bf54941aff6bf4afdb20dfb8a800301\)
Verarbeitung des ersten Blocks
Verarbeitung des letzten Blocks
Abschuss
Addiere auf den Wert des Akkumulators \(a\) den Wert \(s\).
Und somit ist der Tag \(2a927010caf8b2bc2c6365130c11d06a8\) (als Zahl im little-endian Format).
Hinweise
In dieser Diskussion betrachten wir jeden Block der Nachricht als „große Zahl“.
\(P = 2^{130} - 5 = 3fffffffffffffffffffffffffffffffb\)
Dadurch, dass wir den Block als Zahl in little-endian Reihenfolge interpretieren, ist das hinzufügen des Bits jenseits der Anzahl der Oktette gleichbedeutend damit, dass wir den Wert 0x01 am Ende des Blocks hinzufügen.