Wikipedia · einfach zusammengefasst · Stand
Secure Hash Algorithm
Der Begriff Secure Hash Algorithm (kurz SHA, englisch für sicherer Hash-Algorithmus) bezeichnet eine Gruppe standardisierter kryptologischer Hashfunktionen.
Inhalt5 Abschnitte
Zweck und Grundprinzip
Secure Hash Algorithm (SHA) bezeichnet eine Gruppe standardisierter kryptologischer Hashfunktionen. Eine Hashfunktion berechnet aus digitalen Daten beliebiger Art einen Prüfwert, den Hashwert. Dieser dient dazu, die Integrität einer Nachricht zu prüfen, und bildet unter anderem eine Grundlage digitaler Signaturen.
Ein wesentliches Sicherheitsziel ist die Kollisionssicherheit: Es soll praktisch unmöglich sein, zwei verschiedene Nachrichten zu erzeugen, die denselben Hashwert besitzen. Stimmen zwei Hashwerte überein, soll deshalb nach normalem Ermessen davon ausgegangen werden können, dass auch die Nachrichten gleich sind.
Der 1993 veröffentlichte ursprüngliche Secure Hash Standard erzeugt einen 160 Bit langen Hashwert und verarbeitet digitale Daten mit höchstens 2^{64} − 1 Bit, also ungefähr 2 Exbibyte. SHA ist wie MD4 und MD5 eine Merkle-Damgård-Konstruktion mit Davies-Meyer-Kompressionsfunktion. Der längere Hashwert von 160 Bit macht SHA gegenüber den 128-Bit-Hashwerten von MD4 und MD5 widerstandsfähiger gegen Brute-Force-Angriffe, bei denen viele Möglichkeiten systematisch ausprobiert werden.
Zur Verarbeitung wird die Nachricht um ein Endstück ergänzt, das ihre ursprüngliche Länge codiert. Anschließend wird sie in 512 Bit lange Blöcke zerlegt. Diese Blöcke werden nacheinander in einen internen Datenblock eingearbeitet. Nach dem letzten Block wird der entstandene Datenblock als Hashwert ausgegeben.
SHA-0, SHA-1 und Berechnung
Das National Institute of Standards and Technology (NIST) entwickelte die ursprüngliche Funktion gemeinsam mit der National Security Agency (NSA) als Bestandteil des Digital Signature Algorithms (DSA) für den Digital Signature Standard (DSS). Wegen eines „Konstruktionsfehlers“ wurde sie bereits 1995 korrigiert. Die ursprüngliche, praktisch kaum verwendete Fassung heißt heute SHA-0, die korrigierte Variante SHA-1.
Die Korrektur besteht lediglich in der Rotation eines Datenwortes bei der Schlüsseleinteilung. Die Anzahl der Runden blieb unverändert. Kryptoanalysen zeigten jedoch, dass diese kleine Änderung die Berechnung von Kollisionen erheblich erschwert.
SHA-1 arbeitet ausschließlich mit vorzeichenlosen 32-Bit-Werten; Berechnungen erfolgen modulo 2^32. Zunächst werden fünf Zustandswerte mit h0 = 0x67452301, h1 = 0xEFCDAB89, h2 = 0x98BADCFE, h3 = 0x10325476 und h4 = 0xC3D2E1F0 initialisiert. An die Nachricht wird zuerst das Bit 1 angehängt, dann folgen so viele 0-Bits, dass ihre Länge 448 modulo 512 beträgt. Danach wird die ursprüngliche Nachrichtenlänge als 64-Bit-Big-Endian-Zahl ergänzt.
Jeder 512-Bit-Block wird in 16 Wörter zu je 32 Bit geteilt. Diese werden durch XOR-Verknüpfungen und eine Linksrotation um ein Bit auf 80 Wörter erweitert. Anschließend folgen 80 Runden, unterteilt in vier Bereiche von jeweils 20 Runden. Dabei werden unterschiedliche logische Funktionen und die Konstanten 0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC und 0xCA62C1D6 verwendet. Die fünf Arbeitswerte a bis e werden in jeder Runde durch logische Operationen, Additionen und Rotationen verändert. Nach jedem Block werden sie zu h0 bis h4 addiert. Der endgültige 160-Bit-Hash entsteht durch das Aneinanderhängen von h0, h1, h2, h3 und h4 in Big-Endian-Darstellung.
Sicherheitsprobleme von SHA-1
Mehrere Forschungsergebnisse haben die Kollisionssicherheit von SHA-1 zunehmend geschwächt. Am 15. Februar 2005 wurde bekannt, dass Xiaoyun Wang, Yiqun Lisa Yin und Hongbo Yu den Aufwand für eine Kollisionsberechnung vom theoretischen Wert 2^{80} auf 2^{69} verringert hatten. Am 17. August 2005 stellten Xiaoyun Wang, Andrew Yao und Frances Yao auf der CRYPTO 2005 einen Angriff mit einem Aufwand von 2^{63} vor.
Ein 2006 präsentierter Angriff erlaubte es, bis zu 25 % der gefälschten Nachricht frei zu wählen. Das war bedeutsam, weil frühere „Hash-Zwillinge“ hauptsächlich aus leicht erkennbarem Datenmüll bestanden. In einem möglichen Angriff könnte eine teilweise sinnvolle gefälschte Dokumentvariante denselben SHA-1-Wert und damit dieselbe Signatur wie das Original erhalten; die übrigen 75 % sinnloser Zeichen könnten technisch verborgen werden.
Im Oktober 2015 veröffentlichten Marc Stevens, Pierre Karpman und Thomas Peyrin eine Freestart-Kollision für die Kompressionsfunktion von SHA-1. Dadurch waren frühere Schätzungen zu den Kosten von Chosen-Prefix-Kollisionen überholt. Bei einer Chosen-Prefix-Kollision werden zwei Nachrichten mit vorgegebenen unterschiedlichen Anfängen so ergänzt, dass sie denselben Hash erhalten; damit könnten beispielsweise TLS-Zertifikate gefälscht werden.
Im Februar 2017 veröffentlichten Google-Mitarbeiter die erste konkrete SHA-1-Kollision: zwei verschiedene, funktionsfähige PDF-Dateien mit demselben SHA-1-Prüfwert. Eine einzelne CPU hätte dafür ungefähr 6500 Jahre benötigt. Öffentlich bekannte Chosen-Prefix-Angriffe benötigten 2019 zwischen 2^{66,9} und 2^{69,4} SHA-1-Berechnungen; dies entsprach nach dem Stand von 2017 etwa 100 GPU-Jahren Rechenkapazität.
Varianten und Empfehlungen
Wegen der Angriffe empfiehlt das NIST, SHA-1 nicht mehr für digitale Signaturen einzusetzen. Für Anwendungen, die keine Kollisionsresistenz benötigen, lässt es die Nutzung noch bis 2030 zu. Das Bundesamt für Sicherheit in der Informationstechnik (BSI) empfiehlt SHA-2 oder SHA-3. Auch Bruce Schneier empfahl im Oktober 2015, SHA-1 nicht mehr zu verwenden.
Unter SHA-2 werden mehrere vom NIST veröffentlichte Algorithmen zusammengefasst: SHA-224, SHA-256, SHA-384 und SHA-512 sowie die später hinzugekommenen Varianten SHA-512/256 und SHA-512/224. Die Zahlen geben jeweils die Länge des Hashwerts in Bit an. SHA-2 folgt demselben grundsätzlichen Konstruktionsprinzip wie SHA-1, verwendet aber interne Datenblöcke von 256 beziehungsweise 512 Bit und eine veränderte Blockverschlüsselung innerhalb der Kompressionsfunktion. Aus den internen Blockverschlüsselungen von SHA-1 und SHA-256 wurde außerdem die eigenständig verwendbare Blockverschlüsselung SHACAL abgeleitet.
Nachdem 2004 grundlegende Schwächen der Merkle-Damgård-Konstruktion entdeckt worden waren, veranstaltete das NIST einen Wettbewerb für eine neue, gegenüber SHA-2 wesentlich zukunftssicherere Hashfunktion. Im Oktober 2012 fiel die Wahl auf Keccak. Im August 2015 wurde Keccak in mehreren Varianten als SHA-3 standardisiert. SHA-3 unterscheidet sich grundlegend von SHA-2, da es als Sponge-Konstruktion aufgebaut ist.
Typische Hashwerte und Standards
SHA-1 zeigt einen Lawineneffekt: Bereits eine sehr kleine Änderung der Eingabe führt zu einem völlig anderen Hashwert. Für den Text „Franz jagt im komplett verwahrlosten Taxi quer durch Bayern“ lautet der Wert:
SHA1 = 68ac906495480a3404beee4874ed853a037a7a8f
Wird nur das F durch ein G ersetzt – im ASCII-Code 0x46 durch 0x47 und damit nur ein Bit geändert –, ergibt „Granz jagt im komplett verwahrlosten Taxi quer durch Bayern“ den Wert:
SHA1 = 89fdde0b28373dc4f361cfb810b35342cc2c3232
Der SHA-1-Hash einer Zeichenkette der Länge null ist:
SHA1("") = da39a3ee5e6b4b0d3255bfef95601890afd80709
Wichtige technische Spezifikationen sind RFC 3174 „US Secure Hash Algorithm 1 (SHA1)“ von D. Eastlake und P. Jones aus September 2001, RFC 4634 „US Secure Hash Algorithms (SHA and HMAC-SHA)“ von D. Eastlake und T. Hansen aus Juli 2006 sowie RFC 6234 „US Secure Hash Algorithms (SHA and SHA-based HMAC and HKDF)“ derselben Autoren aus Mai 2011. RFC 6234 löste RFC 4634 ab.
