Secure Hash Algorithm

Der Begriff secure hash algorithm (kurz SHA, englisch für sicherer Hash-Algorithmus) bezeichnet eine Gruppe standardisierter kryptologischer Hashfunktionen. Diese dienen zur Berechnung eines eindeutigen Prüfwerts für beliebige digitale Daten (Nachrichten) und sind die Grundlage zur Erstellung einer digitalen Signatur.

Der Prüfwert wird verwendet, um die Integrität einer Nachricht zu sichern. Wenn zwei Nachrichten den gleichen Prüfwert ergeben, soll die Gleichheit der Nachrichten nach normalem Ermessen garantiert sein, unbeschadet gezielter Manipulationsversuche an den Nachrichten. Darum fordert man von einer kryptologischen Hashfunktion die Eigenschaft der Kollisionssicherheit: es soll praktisch unmöglich sein, zwei verschiedene Nachrichten mit dem gleichen Prüfwert zu erzeugen.

Geschichte – SHA/SHA-0

Das National Institute of Standards and Technology (NIST) entwickelte zusammen mit der National Security Agency (NSA) eine Hash-Funktion als Bestandteil des Digital Signature Algorithms (DSA) für den Digital Signature Standard (DSS). Die Funktion wurde 1993 veröffentlicht. Diese als Secure Hash Standard (SHS) bezeichnete Norm spezifiziert den sicheren Hash-Algorithmus (SHA) mit einem Hash-Wert von 160 Bit Länge für beliebige digitale Daten von maximal 2⁶⁴ − 1 Bit (≈ 2 Exbibyte) Länge. Intern werden Blöcke der Größe 512 Bit (64 Bytes) verwendet. Der Algorithmus ähnelt im Aufbau dem von Ronald L. Rivest entwickelten MD4. Der SHA wurde wegen eines „Konstruktionsfehlers“ schon 1995 korrigiert und spielte deswegen nie eine Rolle. Diese neue Variante ist heute als SHA-1 bekannt, die ursprüngliche als SHA-0.

½

SHA-1

Aufbau einer Runde von SHA-1

Die korrigierte Version des SHA unterscheidet sich von SHA-0 nur in einem kleinen Detail (Linksshift), nicht jedoch in der Anzahl der durchlaufenen Runden oder sonstiger Maßnahmen, die unmittelbar eine wesentlich höhere Sicherheit erwarten lassen. Die Kryptoanalyse bestätigt jedoch, dass der Linksshift die Berechnung von Kollisionen offenbar erheblich erschwert.

Prinzipiell wurde von den gleichen Entwurfszielen wie beim MD4 ausgegangen. Mit seinem längeren Hash-Wert von 160 Bit ist SHA aber widerstandsfähiger gegen Brute-Force-Angriffe zum Auffinden von Kollisionen.

Schwächen

Am 15. Februar 2005 meldete der Kryptographieexperte Bruce Schneier in seinem Blog, dass die Wissenschaftler Xiaoyun Wang, Yiqun Lisa Yin und Hongbo Yu an der 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⁶⁹ Berechnungen könnten eventuell mit Hochleistungsrechnern durchgeführt werden. Kollisionen wurden aber bis heute nicht veröffentlicht.

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 weiterer, wesentlich schwerwiegenderer Angriff gegen SHA-1 präsentiert, der möglicherweise auch in der Praxis Auswirkungen zeigen kann. Bei diesem Angriff kann ein Teil der gefälschten Nachricht (derzeit bis zu 25 %) im Inhalt frei gewählt werden. Bei den bisherigen Kollisionsangriffen wurden die so genannten Hash-Zwillinge lediglich mit sinnlosen Buchstabenkombinationen des Klartextes gebildet und waren damit leicht zu erkennen.

Ein kritisches Angriffsszenario setzt aber voraus, dass der Angreifer eine zweite, zumindest in Teilen sinnvolle Variante eines Dokuments erzeugen kann, die den gleichen SHA-1-Wert und damit auch die gleiche Signatur ergibt. Die bei der neuen Angriffsmethode derzeit verbleibenden 75 % sinnloser Buchstabenkombinationen (also Datenmüll) können vor den Augen eines ungeschulten Betrachters ggf. technisch leicht verborgen werden. Der Angreifer kann daher behaupten, die gefälschte Variante sei an Stelle der originalen Variante signiert worden.

Vom 8. August 2007 bis 12. Mai 2009 versuchte eine Forschungsgruppe der Technischen Universität Graz mittels eines Distributed-Computing-Projektes Kollisionen im SHA-1-Algorithmus zu finden (SHA-1 Collision Search Graz). Das Projekt wurde aufgrund zu geringen Fortschritts beendet.

Im Oktober 2015 veröffentlichten die Forscher Marc Stevens, Pierre Karpman und Thomas Peyrin eine Freestart-Kollision für die Kompressionsfunktion von SHA1. Aufgrund dieses Ergebnisses korrigierten sie die bis dahin akzeptierten Vorausberechnungen, wann es zu welchen Kosten möglich ist, für SHA-1 aufgrund der kontinuierlichen Erhöhung der Rechenleistung Chosen-Prefix-Kollisionen zu finden, die zur Fälschung von TLS-Zertifikaten notwendig sind. Sie empfahlen, die Nutzung von SHA-1 so bald wie möglich einzustellen und zu SHA-2 oder SHA-3 überzugehen.

Empfehlungen

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 den Übergang von SHA-1 zu Hashfunktionen der SHA-2-Familie (SHA-224, SHA-256, SHA-384, SHA-512). Langfristig sollen diese durch einen neuen Standard SHA-3 ersetzt werden. Dazu rief das NIST nach Vorbild des Advanced Encryption Standard (AES) zu einer Ausschreibung auf. Die endgültige Wahl und Benennung fiel dann im Oktober 2012 auf Keccak.

Im Oktober 2015 empfahl Bruce Schneier zu SHA-3 überzugehen.

Beispiel-Hashes

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

Pseudocode

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)

SHA-2

→ Hauptartikel: SHA-2

Das NIST hat vier weitere Varianten des Algorithmus veröffentlicht, die größere Hash-Werte erzeugen. Es handelt sich dabei um den SHA-224, SHA-256, SHA-384 und SHA-512 wobei die angefügte Zahl jeweils die Länge des Hash-Werts (in Bit) angibt. Diese Weiterentwicklungen werden häufig unter der Bezeichnung SHA-2 zusammengefasst. Die Algorithmen SHA-1 und SHA-256 sind auch die Basis für die Blockverschlüsselung SHACAL.

SHA-3

→ Hauptartikel: SHA-3

Spezifikationen

• RFC 3174, US Secure Hash Algorithm 1 (SHA1) (September 2001)
• RFC 4634, US Secure Hash Algorithms (SHA and HMAC-SHA) (Juli 2006)
• RFC 6234, US Secure Hash Algorithms (SHA and SHA-based HMAC and HKDF) (Mai 2011)

Siehe auch

• Zyklische Redundanzprüfung (ZRP, engl. CRC)
• Prüfsumme
• Hamming-Code
• Elliptic Curve Cryptography
• Paritätsbit
• MD5

Weblinks

• FIPS PUB 180-4, Secure Hash Standard (PDF-Datei; 251 kB)
• SHA1-Passwort-Generator Online-Konverter zur Generierung von SHA1-Hashwerten aus normalem Text

Zu den Schwächen von SHA

• heise online (19. August 2005): Angriffe auf Hash-Algorithmus SHA-1 weiter vereinfacht
• heise online (25. August 2006): Hash-Funktion SHA-1 in Bedrängnis
• heise online(19. November 2010): GPUs knacken Passwörter in der Cloud
• Bruce Schneier: SHA-1 Broken (englisch)
• Arjen Lenstra: Further progress in hashing cryptanalysis (englisch, PDF; 89 kB)
• Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Finding Collisions in the Full SHA-1 (englisch, PDF; ZIP; 190 kB)
• Cryptographic Hash Project