Secure Hash Algorithm

Am 15. Februar 2005 meldete der Kryptographieexperte Bruce Schneier in seinem Blog[1], dass die Wissenschaftler Xiaoyun Wang, Yiqun Lisa Yin und Hongbo Yu von Shandong University in China erfolgreich SHA-1 gebrochen hätten. Ihnen war es gelungen, den Aufwand zur Kollisionsberechnung von 2⁸⁰ auf 2⁶⁹ zu verringern.[2] 2⁶⁹ Berechnungen könnten eventuell mit Hochleistungsrechnern durchgeführt werden.

Kurze Zeit später, am 17. August 2005, wurde von Xiaoyun Wang, Andrew Yao und Frances Yao auf der Konferenz CRYPTO 2005 ein weiterer, effizienterer Kollisionsangriff auf SHA-1 vorgestellt, welcher den Berechnungsaufwand auf 2⁶³ reduziert.

Im August 2006 wurde auf der CRYPTO 2006 ein weit schwerwiegenderer Angriff gegen SHA-1 präsentiert. Dabei sind bis zu 25 % der gefälschten Nachricht frei wählbar. Bei bisherigen Kollisionsangriffen wurden die so genannten Hash-Zwillinge nur mit sinnlosen Buchstabenkombinationen des Klartextes gebildet. Diese waren leicht erkennbar.

Ein kritisches Angriffsszenario erfordert, dass Angreifer eine zweite, in Teilen sinnvolle Variante eines Dokuments erzeugen, die den gleichen SHA-1-Wert und damit die gleiche Signatur ergibt. Die beim Angriff verbleibenden 75 % sinnloser Zeichen (also Datenmüll) können vor ungeschulten Betrachtern ggf. technisch verborgen werden. Der Angreifer kann behaupten, die gefälschte Variante sei anstatt der originalen Variante signiert worden.

Im Oktober 2015 veröffentlichten Marc Stevens, Pierre Karpman und Thomas Peyrin eine Freestart-Kollision für die Kompressionsfunktion von SHA1. Damit waren bis dahin geltende Abschätzungen, wann es zu welchen Kosten möglich ist, für SHA-1 aufgrund steigender Rechenleistung Chosen-Prefix-Kollisionen zur Fälschung von TLS-Zertifikaten zu finden, hinfällig.[3][4] Sie empfahlen, von SHA-1 baldmöglichst zu SHA-2 oder SHA-3 überzugehen.

Im Februar 2017 veröffentlichten Google-Mitarbeiter eine erste Kollision von SHA-1. Sie erzeugten zwei verschiedene funktionierende PDF-Dateien mit gleichem SHA-1-Prüfwert unter enormem Aufwand. Eine einzelne CPU hätte etwa 6500 Jahre dafür benötigt.[5]
Im Jahre 2019 benötigten öffentlich bekannte Chosen-Prefix-Angriffe 2^66,9 bis 2^69,4 SHA-1-Berechnungen, um Kollisionen zu finden. Das entsprach im Jahre 2017 100 GPU-Jahren Rechenkapazität.[6]

Als Reaktion auf die bekanntgewordenen Angriffe gegen SHA-1 hielt das National Institute of Standards and Technology (NIST) im Oktober 2005 einen Workshop ab, in dem der aktuelle Stand kryptologischer Hashfunktionen diskutiert wurde. NIST empfiehlt, SHA-1 nicht mehr für digitale Signaturen zu verwenden, lässt die Nutzung für Anwendungszwecke, die keine Kollisionsresistenz benötigen, aber noch bis 2030 zu.[7][8] Das BSI empfiehlt die Verwendung von SHA-2 oder SHA-3 anstelle von SHA-1.[9] Im Oktober 2015 empfahl Bruce Schneier SHA-1 nicht mehr zu verwenden.[4]

SHA1("Franz jagt im komplett verwahrlosten Taxi quer durch Bayern")
 = 68ac906495480a3404beee4874ed853a037a7a8f

Ein Tippfehler (G statt F) ändert den Text um nur ein Bit (ASCII-Code 0x47 statt 0x46):

SHA1("Granz jagt im komplett verwahrlosten Taxi quer durch Bayern")
 = 89fdde0b28373dc4f361cfb810b35342cc2c3232

Eine kleine Änderung der Nachricht erzeugt also einen komplett anderen Hash. Diese Eigenschaft wird in der Kryptographie auch als Lawineneffekt bezeichnet.

Der Hash eines Strings der Länge Null ist:

SHA1("")
 = da39a3ee5e6b4b0d3255bfef95601890afd80709

Es folgt der Pseudocode für den SHA-1.

// Beachte: Alle Variablen sind vorzeichenlose 32-Bit-Werte und
// verhalten sich bei Berechnungen kongruent (≡) modulo 2^32

// Initialisiere die Variablen:
var int h0 := 0x67452301
var int h1 := 0xEFCDAB89
var int h2 := 0x98BADCFE
var int h3 := 0x10325476
var int h4 := 0xC3D2E1F0

// Vorbereitung der Nachricht 'message':
var int message_laenge := bit_length(message)
erweitere message um bit "1"
erweitere message um bits "0" bis Länge von message in bits ≡ 448 (mod 512)
erweitere message um message_laenge als 64-Bit big-endian Integer

// Verarbeite die Nachricht in aufeinander folgenden 512-Bit-Blöcken:
für alle 512-Bit Block von message
   unterteile Block in 16 32-bit big-endian Worte w(i), 0 ≤ i ≤ 15

   // Erweitere die 16 32-Bit-Worte auf 80 32-Bit-Worte:
   für alle i von 16 bis 79
       w(i) := (w(i-3) xor w(i-8) xor w(i-14) xor w(i-16)) leftrotate 1

   // Initialisiere den Hash-Wert für diesen Block:
   var int a := h0
   var int b := h1
   var int c := h2
   var int d := h3
   var int e := h4

   // Hauptschleife:
   für alle i von 0 bis 79
       wenn 0 ≤ i ≤ 19 dann
           f := (b and c) or ((not b) and d)
           k := 0x5A827999
       sonst wenn 20 ≤ i ≤ 39 dann
           f := b xor c xor d
           k := 0x6ED9EBA1
       sonst wenn 40 ≤ i ≤ 59 dann
           f := (b and c) or (b and d) or (c and d)
           k := 0x8F1BBCDC
       sonst wenn 60 ≤ i ≤ 79 dann
           f := b xor c xor d
           k := 0xCA62C1D6
       wenn_ende

       temp := (a leftrotate 5) + f + e + k + w(i)
       e := d
       d := c
       c := b leftrotate 30
       b := a
       a := temp

   // Addiere den Hash-Wert des Blocks zur Summe der vorherigen Hashes:
   h0 := h0 + a
   h1 := h1 + b
   h2 := h2 + c
   h3 := h3 + d
   h4 := h4 + e

digest = hash = h0 append h1 append h2 append h3 append h4 //(Darstellung als big-endian)

Beachte: Anstatt der Original-Formulierung aus dem FIPS PUB 180-1 können alternativ auch folgende Formulierungen verwendet werden:

(0 ≤ i ≤ 19): f := d xor (b and (c xor d)) (Alternative)

(40 ≤ i ≤ 59): f := (b and c) or (d and (b or c)) (Alternative 1)
(40 ≤ i ≤ 59): f := (b and c) or (d and (b xor c)) (Alternative 2)
(40 ≤ i ≤ 59): f := (b and c) + (d and (b xor c)) (Alternative 3)
(40 ≤ i ≤ 59): f := (b and c) xor (d and (b xor c)) (Alternative 4)

• Arjen Lenstra: Further progress in hashing cryptanalysis, 26. Februar 2005 (englisch, PDF; 89 kB)
• Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Finding Collisions in the Full SHA-1 (englisch, PDF; ZIP; 190 kB)
• Zweifel an der Notwendigkeit des Kryptostandards SHA3 heise online 30. März 2012