Entwicklertools · SHA-Hash-Rechner
Merkle–Damgård erklärt: Die Konstruktion hinter SHA-1 und SHA-2
· Hintergrund
sha-256 Kryptographie Browser-APIs
Eine Komprimierungsfunktion mit fester Größe kann keine beliebigen Eingaben alleine hashen. Merkle–Damgård verkettet es Block für Block; In diesem Beitrag werden die Konstruktion, ihre Beweisidee und die damit verbundenen Schwächen erläutert.
Beliebige Eingabe, feste Ausgabe – das Problem, das jede Hash-Funktion zuerst lösen muss
Eine Hash-Funktion muss eine beliebige Eingabe einer festen Ausgabe zuordnen. Eine Nachricht mit drei Bytes und eine Nachricht mit drei Megabytes müssen beide genau 256 Bit der Ausgabe für SHA-256 erzeugen. Der Hash muss deterministisch sein, sodass dieselbe Eingabe immer dieselbe Ausgabe erzeugt. Die Ausgabe muss zufällig aussehen; Das Ändern eines einzelnen Bits der Eingabe sollte ungefähr die Hälfte der Ausgabebits ändern.
Dies sind auf den ersten Blick widersprüchliche Anforderungen, da ein einzelner schneller Algorithmus nicht mit Nachrichten beliebiger Länge umgehen und eine einheitliche fester Breite-Ausgabe erzeugen kann. Die Merkle-Damgård-Konstruktion löst dieses Problem, indem sie wiederholt eine fixed-size-Komprimierungsfunktion verwendet und die Ausgabe jeder Anwendung in die Eingabe der nächsten einspeist. Diese Konstruktion wird von SHA-1 und allen SHA-2 (SHA-256, SHA-384 und SHA-512) verwendet.
Die Komprimierungsfunktion – ein Mixer fester Größe, der einen Zustand und einen Block annimmt und einen neuen Zustand zurückgibt
Eine Komprimierungsfunktion ist das zentrale kryptografische Grundelement, das einen Merkle-Damgård-Hash unterstützt. Es benötigt einen Status fester Größe, normalerweise 256 Bits für SHA-256 oder 512 Bits für SHA-512, und einen Eingabeblock fester Größe, normalerweise 512 Bits für SHA-256 oder 1024 Bits für SHA-512. Die Komprimierungsfunktion mischt sie mithilfe bitweiser Operationen, Rotationen und Tabellensuchen zusammen und erzeugt so einen neuen Zustand derselben Größe. Diese Funktion muss kollisionssicher sein: Es muss schwierig sein, zwei verschiedene (Zustands-, Block-)Paare zu finden, die die gleiche Ausgabe erzeugen.
Die Komprimierungsfunktion selbst ist keine vollständige Hash-Funktion – sie verarbeitet keine beliebige Eingabelänge und nicht einmal die erste Eingabe, die keinen vorherigen Status hat. Stattdessen ist es der Baustein, um den herum eine größere Konstruktion aufgebaut wird. Die Komprimierungsfunktion ist die einzige kryptografische Operation, die wiederholt ausgeführt wird; alles andere ist Buchhaltung, die diese Funktion mit einem vollständigen Hash verbindet.
Verkettung und der Initialisierungsvektor – wie Blöcke von einem festen Startzustand aus ineinander übergehen
Der Initialisierungsvektor ist der feste Startzustand, der sorgfältig ausgewählt wird, um Symmetrien oder Schwächen zu vermeiden. Für SHA-256 besteht der IV aus acht 32-Bit-Wörtern, die aus den Bruchteilen der Quadratwurzeln der ersten acht Primzahlen abgeleitet sind. Diese Werte sind willkürlich, aber deterministisch, sodass jede Implementierung das gleiche Ergebnis liefert. Der erste Nachrichtenblock wird mithilfe der Komprimierungsfunktion mit der IV gemischt, wodurch ein neuer Status entsteht. Der zweite Nachrichtenblock wird mit diesem Status gemischt, wodurch ein weiterer neuer Status entsteht usw. in jedem Block der Nachricht.
Diese Verkettung ist der entscheidende Teil: Die Ausgabe eines Blocks hängt von allen vorherigen Blöcken ab, sodass die Änderung eines beliebigen Bits eines vorherigen Blocks alle nachfolgenden Blöcke ändert. Wenn der letzte Block verarbeitet wird, enthält der Status Informationen über jedes Bit der Eingabe. Polsterung ist der Trick, der dieser Konstruktion Klang verleiht. Eine Nachricht teilt sich nicht immer gleichmäßig in Blöcke auf. Die Merkle-Damgård-Konstruktion verwendet MD-Stärkung: Hängen Sie ein einzelnes Eins-Bit an die Nachricht an, hängen Sie dann Nullen an, bis fast ein vollständiger Block übrig bleibt, und hängen Sie dann die ursprüngliche Nachrichtenlänge an.
Auffüllen mit der Nachrichtenlänge – warum die MD-Verstärkung die Konstruktion klingen lässt
Das Sicherheitsargument für Merkle-Damgård besagt, dass, wenn die Komprimierungsfunktion kollisionsresistent ist, der gesamte Hash kollisionsresistent ist. Der Beweis ist eine Reduktion: Wenn Sie eine Kollision im Hash finden könnten, könnten Sie eine Kollision in der Komprimierungsfunktion extrahieren, was der Annahme widerspricht, dass die Komprimierungsfunktion schwer zu kollidieren ist. Die Intuition ist, dass jede Kollision im Hash letztendlich zu einer Kollision in einem der Komprimierungsfunktionsaufrufe führen muss, da der Zustand vollständig übertragen wird.
Schwachstellen in Merkle–Damgård wurden im Laufe der Zeit entdeckt, obwohl die Grundkonstruktion solide ist. Eine davon ist die Längenerweiterung: Ein Angreifer, der den Digest einer Nachricht sieht, kann die Nachricht erweitern und einen gültigen Digest für die längere Nachricht berechnen, ohne etwas über die Eingabe zu wissen. Second-Preimage-Angriffe sind eine andere: Bei bestimmten Nachrichtentypen ist es einfacher, eine andere Nachricht mit demselben Hash zu finden, als es für einige Arten von Nachrichten der Fall sein sollte. Diese Schwächen motivierten den Entwurf von SHA-3, der einen anderen Ansatz verwendet, der als Schwammkonstruktion bezeichnet wird.
Längencodierendes Auffüllen trennt aufgefüllte Nachrichten; Ein vollständiger Sicherheitsnachweis ist ein Beweis außerhalb des Repositorys
Die Komprimierungsfunktion für SHA-256 nimmt einen 256-Bit-Zustand (acht 32-Bit-Wörter) und einen 512-Bit-Block an. Die Operation verwendet 64 Runden, wobei jede den Zustand mit einer Konstante und einem Wort aus dem Block mischt. Das Mischen verwendet bitweise Operationen: XOR, AND, NOT. Es verwendet Drehungen und Verschiebungen, die Bits verschieben, ohne zu ändern, welche Bits gesetzt sind. Es verwendet Tabellensuchen, die eine nichtlineare Mischung ermöglichen, die XOR allein nicht erreichen kann.
SHA-512 verwendet den gleichen Aufbau wie SHA-256, jedoch mit 64-Bit-Operationen anstelle von 32-Bit-Operationen. Der Status beträgt 512 Bits (acht 64-Bit-Wörter) und die Blockgröße beträgt 1024 Bits. Die Komprimierungsfunktion verfügt über 80 Runden anstelle von 64, und die Konstanten und Tabellensuchen sind unterschiedlich. Für SHA-384 sind der Status und die Komprimierungsfunktion dieselben wie für SHA-512, es werden jedoch nur die ersten 384-Bits des Endstatus ausgegeben. Die letzten 128 Bits werden verworfen. Aufgrund dieser Kürzung ist SHA-384 resistent gegen Längenverlängerung.
Längenverlängerung ist die überprüfte Konstruktionsgrenze; Multikollisions- und SHA-3-Motivationsansprüche werden weggelassen
Die Sicherheit eines Merkle-Damgård-Hash hängt von mehreren Eigenschaften ab. Die Komprimierungsfunktion muss kollisionssicher sein, daher ist ein direkter Angriff darauf nicht möglich. Das Auffüllschema muss sicherstellen, dass verschiedene Nachrichten unterschiedliche aufgefüllte Formen erzeugen, sodass jede Kollision im Hash eine Kollision der Komprimierungsfunktion beinhalten muss. Die Blockgröße und die Zustandsgröße müssen groß genug sein, dass rohe Gewalt nicht möglich ist. Ein breiterer Status vergrößert den generischen Suchraum, aber dieser Artikel fügt ohne eine Inline-Ableitung und eine überprüfte Quelle keine Vorgangsanzahl oder Machbarkeitsdatum hinzu.
Wenn ein Angreifer eine Schwachstelle in der Komprimierungsfunktion findet oder wenn Quantencomputer praktisch werden und einen unstrukturierten Raum in sqrt(2^n) Zeit statt in 2^n Zeit durchsuchen können, dann erodieren die Sicherheitsmargen. Die Schwachstelle, die SHA-3 motivierte, war nicht eine Unterbrechung der Komprimierungsfunktion, sondern das Problem der Längenverlängerung und andere strukturelle Schwachstellen. Eine Schwammkonstruktion vermeidet diese, indem sie niemals ihren vollständigen internen Zustand veröffentlicht.
Was dies nicht abdeckt – die spezifischen Rundenfunktionen von SHA-256, die in einem separaten Beitrag behandelt werden
Wie die Merkle-Damgård-Konstruktion mit jeder Eingabegröße umgeht, ist die praktische Konsequenz ihres Designs. Teilen Sie die Nachricht in 512-Bit-Blöcke auf, füllen Sie den letzten Block auf, verarbeiten Sie jeden Block nacheinander durch die Komprimierungsfunktion und geben Sie den Endzustand aus. Bei einer Ein-Byte-Eingabe erzeugt das Auffüllen einen 512-Bit-Block (ein Byte Nachricht, ein Bit Auffüllen, 447 Bits Nullen und 64 Bits für die Länge). Die Anzahl der Komprimierungen ist die Anzahl der 512-Bit-Blöcke, die proportional zur Nachrichtenlänge ist.
Jeder Digest, den der ToolAcre SHA-Hash-Rechner erzeugt, stammt aus dieser Konstruktion. Der Digest mit 64-Zeichen SHA-256 ist der endgültige 256-Bit-Zustand, der hexadezimal gedruckt wird. Der 128-Zeichen-SHA-512-Digest ist der endgültige 512-Bit-Zustand, der hexadezimal gedruckt wird. Der Digest mit 96-Zeichen SHA-384 besteht aus den ersten 384 Bits des endgültigen 512-Bit-Zustands. Die Auffüllung hinter den Kulissen stellt sicher, dass jede mögliche Nachricht genau die richtige Anzahl an Blöcken und die richtige Digest-Breite erzeugt. Dies ist die Standard-Merkle-Damgård-Konstruktion, die im Browser ausgeführt wird.
Takeaway: Das gleiche Grundgerüst hinter vier Algorithmen – jeder Digest, den der ToolAcre SHA-Hash-Rechner erzeugt, stammt aus dieser Konstruktion
Das Verständnis der Konstruktion ist hilfreich, um zu verstehen, warum Digests immer die gleiche Breite haben und warum die Änderung eines Bits der Eingabe den gesamten Digest ändert. Die Verkettungseigenschaft bedeutet, dass jedes Bit der Eingabe durch eine Reihe von Mischvorgängen jedes Bit der Ausgabe beeinflusst. Eine Änderung um ein Bit zu Beginn der Nachricht wird durch alle nachfolgenden Komprimierungen weitergegeben, sodass der endgültige Digest völlig anders ist. Diese Eigenschaft wird Lawineneffekt genannt und ist eine Signatur einer soliden Hash-Funktion.
Die Merkle-Damgård-Konstruktion wird seit Jahrzehnten verwendet und bildet die Grundlage der am weitesten verbreiteten Hash-Funktionen. SHA-1 und SHA-2 basieren auf dieser Konstruktion, und viele bereitgestellte Systeme sind auf deren Ausgaben angewiesen. Die Konstruktion ist eher etabliert als experimentell, aber diese Geschichte macht nicht jede Verwendung sicher; Längenausdehnung ist eine dokumentierte Grenze. Das Verständnis dieser Konstruktion hilft Entwicklern zu verstehen, warum bestimmte Sicherheitseigenschaften gelten und warum bestimmte Angriffsvektoren existieren.