it-swarm-eu.dev

Warum wird AES nicht für sicheres Hashing anstelle von SHA-x verwendet?

Soweit ich weiß, gilt AES als äußerst sicher. (Ich habe irgendwo gelesen, dass es in den nächsten 20 Jahren sicherlich nicht kaputt gehen würde, aber ich bin mir immer noch nicht sicher, ob der Autor es ernst meinte.)

DES ist immer noch nicht so schlecht für eine alte Chiffre, und 3DES wird immer noch verwendet (vielleicht nicht so oft, aber zumindest sehe ich 3DES in about: config in Firefox).

Es sieht so aus, als ob (gute) Block-Chiffren von der Crypto-Community als vertrauenswürdig eingestuft werden.

OTOH, viele Probleme mit kryptografischen Hash-Funktionen werden entdeckt.

Aus Sicht des Nicht-Krypto-Spezialisten: Hashing-Funktionen und symmetrische Chiffren sind wirklich dasselbe: eine "zufällige" Funktion (mit unterschiedlichen Ein- und Ausgängen).

Warum also nicht einfach AES zum Hashing verwenden? Dies scheint die naheliegende Maßnahme zu sein, um die Sicherheit von AES beim Hashing zu gewährleisten. Könnten Hardware-Implementierungen von AES als Bonus helfen?

Gibt es eine einfache Erklärung für den tatsächlichen Unterschied zwischen Hash-Funktionen und symmetrischen Chiffren?

46
curiousguy

Eine Blockchiffre hat einen Schlüssel; Die Geheimhaltung des Schlüssels ist das, worauf die Verschlüsselungssicherheit aufbaut. Andererseits hat eine Hash-Funktion überhaupt keinen Schlüssel und es gibt keine "geheimen Daten", auf denen die Sicherheit der Hash-Funktion aufgebaut werden soll.

Eine Blockverschlüsselung ist reversibel: Wenn Sie den Schlüssel kennen, können Sie entschlüsseln, was verschlüsselt wurde. Technisch gesehen ist eine Blockverschlüsselung für einen gegebenen Schlüssel eine Permutation des Raums möglicher Blockwerte. Hash-Funktionen sollen nicht reversibel sein und sind in keiner Weise Permutationen.

Eine Blockverschlüsselung arbeitet mit Blöcken fester Größe (128-Bit-Blöcke für AES) sowohl für die Eingabe als auch für die Ausgabe. Eine Hash-Funktion hat eine Ausgabe mit fester Größe, sollte jedoch beliebig große Eingaben akzeptieren.

Blockchiffren und Hash-Funktionen sind also wirklich verschiedene Tiere. Anstatt zu versuchen, sie zu unterscheiden, ist es einfacher zu erkennen, was sie gemeinsam haben: Die Leute, die wissen, wie man eine Blockverschlüsselung entwirft, sind auch einigermaßen gut darin, Hash-Funktionen zu entwerfen, da die mathematischen Analysewerkzeuge ähnlich sind (ziemlich viele lineare Algebra- und Boolesche Funktionen, wirklich).

Gehen wir zu formaleren Definitionen:

Eine Blockverschlüsselung ist eine Familie von Permutationen, die von einem Schlüssel ausgewählt werden. Wir betrachten den Raum [~ # ~] b [~ # ~] von n - Bitblöcke für einen festen Wert von n; Die Größe von [~ # ~] b [~ # ~] ist dann 2n. Schlüssel sind Werte aus einem Raum [~ # ~] k [~ # ~], normalerweise einem anderen Raum von Sequenzen von m Bits ( m ist nicht unbedingt gleich n). Ein Schlüssel k wählt eine Permutation unter den 2n! mögliche Permutationen von [~ # ~] b [~ # ~].

Eine Blockverschlüsselung gilt als sicher, solange sie rechnerisch nicht von einer Permutation zu unterscheiden ist, die einheitlich und zufällig unter den 2 ausgewählt wurden! mögliche Permutationen. Um dies zu modellieren, stellen Sie sich eine Situation vor, in der ein Angreifer Zugriff auf zwei Black Box erhält, von denen eine die Blockverschlüsselung mit einem Schlüssel implementiert, den der Angreifer nicht kennt, und die andere eine wirklich zufällige Permutation ist. Das Ziel des Angreifers ist es zu sagen, welches welches ist. Er kann jede Box beliebige Daten verschlüsseln oder entschlüsseln lassen. Bei einem möglichen Angriff müssen alle möglichen Schlüssel ausprobiert werden (es gibt 2m solche Schlüssel) es wird nur einer gefunden, der die gleichen Werte ergibt wie eines der Kästchen; Dies hat durchschnittliche Kosten 2m-1 Aufrufe der Chiffre. Eine sichere Blockverschlüsselung ist eine solche, dass dieser generische Angriff der bestmögliche Angriff ist.

Das AES wird über 128-Bit-Blöcke ( n = 128) und 128-, 192- und 256-Bit-Schlüssel definiert.

Eine Hash-Funktion ist eine einzelne, vollständig definierte, berechenbare Funktion, die als Eingabebitfolgen beliebiger Länge verwendet und Werte fester Länge ausgibt r (zB r = 256 Bit für SHA-256). Es gibt keinen Schlüssel, keine Funktionsfamilie, nur eine einzigartige Funktion, die jeder berechnen kann.

Eine Hash-Funktion h gilt als sicher, wenn:

  • Es ist rechnerisch nicht möglich, Vorbilder zu finden: Wenn ein r - Bitwert x gegeben ist, ist es nicht möglich, m zu finden so dass h (m) = x.
  • Es ist rechnerisch nicht möglich, zweite Vorbilder zu finden: Angesichts m ist es nicht möglich, m ' verschieden von m zu finden , so dass h (m) = h (m ').
  • Es ist rechnerisch nicht möglich, Kollisionen zu finden: Es ist nicht möglich, m und m ' zu finden, die sich voneinander unterscheiden, so dass h ( m) = h (m ').

Es gibt generische Angriffe, bei denen Vorbilder, zweite Vorbilder oder Kollisionen mit Kosten von 2 gefunden werden könnenr, 2r und 2r/2. Die tatsächliche Sicherheit kann also nur erreicht werden, wenn r groß genug ist, um 2r/2 ist ein überwältigend großer Preis. In der Praxis bedeutet dies, dass r = 128 (eine 128-Bit-Hash-Funktion wie MD5) nicht genug ist.

Auf informelle Weise ist es gut, wenn die Hash-Funktion "so aussieht", dass sie zufällig und einheitlich unter den möglichen Funktionen ausgewählt wurde, die dieselben Eingaben akzeptieren. Dies ist jedoch eine schlecht definierte Eigenschaft, da es sich um eine eindeutige Funktion handelt (Wahrscheinlichkeiten beziehen sich immer implizit auf Durchschnittswerte und wiederholte Erfahrungen; Wahrscheinlichkeiten können nicht wirklich mit einer einzigen Funktion vorliegen). Eine Zufallsfunktion zu sein ist nicht genau das Gleiche wie eine Kollisions- und Vorbildbeständigkeit. Dies ist die Debatte über das Random Oracle Model .


Trotzdem ist es möglich, eine Hash-Funktion aus einer Blockverschlüsselung zu erstellen. Dies ist, was die Konstruktion Merkle-Damgård bewirkt. Dies beinhaltet die Verwendung der Eingabenachricht als Schlüssel der Blockverschlüsselung; Daher wird die Blockverschlüsselung überhaupt nicht so verwendet, wie sie sein sollte. Bei AES ist dies enttäuschend:

  • Dies führt zu einer Hash-Funktion mit einer 128-Bit-Ausgabe, die für die Sicherheit gegen die 2011 verfügbare Technologie zu klein ist.
  • Die Sicherheit der Hash-Funktion beruht dann auf dem Fehlen von Attacken mit verwandten Schlüsseln auf der Blockverschlüsselung. Angriffe mit verwandten Schlüsseln haben für eine Blockverschlüsselung keine praktische Bedeutung, wenn sie zur Verschlüsselung verwendet werden. Daher war AES nicht darauf ausgelegt, solchen Angriffen zu widerstehen, und tatsächlich hat AES hat a wenige Schwächen in dieser Hinsicht - keine Sorge um die Verschlüsselung, sondern eine große Sorgen Sie sich, wenn AES in einer Merkle-Damgård-Konstruktion verwendet werden soll.
  • Die Leistung wird nicht gut sein.

Die Hash-Funktion Whirlpool ist ein Design, das auf einer Blockchiffre inspiriert vom AES aufbaut - nicht von der realen. Diese Blockverschlüsselung verfügt über einen deutlich verbesserten (und schwereren) Schlüsselplan, der Angriffen auf verwandte Schlüssel widersteht und sie als Kern einer Hash-Funktion verwendet. Diese Blockverschlüsselung funktioniert auch mit 512-Bit-Blöcken, nicht mit 128-Bit-Blöcken. Whirlpool gilt als sicher. Whirlpool ist bekanntermaßen sehr langsam, daher wird er von niemandem verwendet.

Einige neuere Hash-Funktionsdesigns haben versucht, Teile des AES wiederzuverwenden - um genau zu sein, um eine interne Operation zu verwenden, die den Anweisungen AES-NI gut entspricht welche neueren Intel- und AMD-Prozessoren funktionieren. Siehe zum Beispiel ECHO und SHAvite- ; Diese beiden Funktionen wurden im Rahmen des SHA-3-Wettbewerbs ziemlich exponiert und gelten als "ziemlich sicher". Es gibt sehr schnell auf aktuellen Intel- und AMD-Prozessoren. Bei anderen schwächeren Architekturen sind diese Funktionen recht langsam, wenn die Leistung von Hash-Funktionen tatsächlich eine Rolle spielt.

Es gibt andere Konstruktionen, die aus einer Blockverschlüsselung eine Hash-Funktion machen können, z. die in Skein verwendete; Sie erfordern jedoch tendenziell auch größere Blöcke als das, worüber das AES definiert ist.

Zusammenfassung: sind nicht nur Blockchiffren und Hash-Funktionen ganz unterschiedlich; Die Idee, aus dem AES eine Hash-Funktion zu erstellen, erweist sich jedoch als fragwürdig. Es ist nicht einfach und die begrenzte AES-Blockgröße ist das Haupthindernis.

70
Thomas Pornin

Die grundlegende Antwort ist, dass es sich um verschiedene Arten von Algorithmen handelt. AES ist ein symmetrischer Schlüsselalgorithmus. Sie können es nicht in derselben Rolle wie RSA (ein Public-Key-Algorithmus) oder SHA-256 (ein Hashing-Algorithmus) verwenden. Es handelt sich um verschiedene Systeme mit sehr unterschiedlichen Eigenschaften und Schwächen.

Trotzdem machte ich eine Pause und dachte ernsthaft über diese Idee nach, um sie zu erklären, und sagte nur: "Es ist so." Schließlich ist ein Hash im universellen Sinne eine wiederholbare Darstellung von Daten in einer festen oder reduzierten Größe. AES kann dies über den CBC-Modus bereitstellen. Ein sicherer Hash hat jedoch mehr Eigenschaften als eine einfache Reduzierung.

Ein sicherer Hashing-Algorithmus ist ein Einwegsystem. AES verschlüsselt und entschlüsselt auf dieselbe Weise (symmetrische Verschlüsselung), und Sie können für jeden Block eine 1-1-Zuordnung vornehmen, was mit einem bestimmten Schlüssel geschehen wird. Sofern die Daten nicht verkettet und damit verlustbehaftet sind, können Sie den AES- "Hash" einfach zu den Quelldaten entschlüsseln.

Man kann einen SHA - Prozess nicht vernünftigerweise umkehren, außer nur andere Eingabedaten auszuprobieren. Aus den Gründen, dass Sie SHA-x nicht zum Verschlüsseln verwenden können, können Sie AES nicht verwenden Hasch etwas.

11
Jeff Ferland

Gibt es eine einfache Erklärung für den tatsächlichen Unterschied zwischen Hash-Funktionen und symmetrischen Chiffren?

  • Eine Chiffre ist reversibel, eine Hash-Funktion nicht
  • Die Länge der Ausgabe einer Chiffre hängt von der Länge der Eingabe ab; Eine Hash-Funktion erzeugt unabhängig von der Eingabe die gleiche Längenausgabe
  • Eine einzelne Bitänderung an einer beliebigen Stelle in einer kryptografischen Hash-Funktion führt zu einer kaskadierenden (dramatischen) Änderung der Hash-Ausgabe. Dies gilt in der Regel nicht für Chiffren.
  • Eine Chiffre erfordert einen Schlüssel, ein Hash nicht

Das Design und der Zweck der beiden unterscheiden sich grundlegend und sind nicht austauschbar.

9
tylerl

Sie können grundsätzlich jede Blockverschlüsselung mithilfe der Merkle-Damgard-Konstruktion in eine Hash-Funktion umwandeln, und Sie können grundsätzlich jede Hash-Funktion mithilfe von Feistel-Netzwerken in eine Blockverschlüsselung umwandeln, wenn Sie die Feistel-Funktion F folgendermaßen definieren.

F(half_block, round_key) = hash(concatenate(half_block, round_key))

Die Berechnung ist jedoch ziemlich ineffizient (die Berechnung dauert lange), da die Berechnung von F bereits teuer ist (es handelt sich um einen iterativen Algorithmus, der im Fall von SHA-512 beispielsweise 80 interne "Runden" verwendet), und für die Feistel-Struktur wird F selbst mehrmals iteriert. Angenommen, Sie haben ein 20-stufiges Feistel-Netzwerk mit einer 80-Runden-Rundenfunktion F. Sie führen 1600 SHA-2 "Runden" pro Block durch. Dies führt auch zu ziemlich großen Blockgrößen (doppelt so groß wie die Ausgabe der Hash-Funktion), z. G. 1024-Bit-Blockverschlüsselung, wenn Sie SHA-512 als Hash-Funktion verwenden.

Aber praktisch ist es nicht unbedingt "unsicher". Es ist nur so, dass leicht verfügbare "Blockchiffren" (eher pseudozufällige Permutationen - keine Permutation wie bei der Permutation von Bits/Bytes, sondern Permutation im Sinne einer bijektiven Zuordnung zwischen "allen möglichen Eingabeblöcken" und "allen möglichen Ausgabeblöcken") weitaus mehr sind effizient, weiter verbreitet und daher gründlicher auf die Eigenschaften guter pseudozufälliger Permutationen untersucht. Wenn Sie Rechenleistung verschwenden müssen, verwenden Sie SHA-512 in einem Feistel-Netzwerk als Blockverschlüsselung. Es besteht die Möglichkeit, dass es nicht weniger sicher ist als AES (vorausgesetzt, Sie fügen einen guten Schlüsselplan zum Ableiten der "runden Schlüssel" hinzu), es wird jedoch viele CPU-Zyklen benötigen, um einen Block zu verarbeiten.

3
no.human.being

M. Abel ist richtig. Ein weiteres Beispiel für AES, das als Hash verwendet wird, ist AES-CBC oder AES-PCBC.

https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Propagating_Cipher_Block_Chaining_.28PCBC.29

Wenn CBC oder PCBC oder sogar CFB in einer "Datei" mit und ohne Fehler ausgeführt wird, ist der letzte Block anders.

Es ist ineffizient, kann aber durchgeführt werden. Die Logik lautet: "Wenn Sie nur einen Hammer haben, sieht alles aus wie ein Nagel." Gleiches gilt für AES. Es gibt vielleicht bessere Möglichkeiten zum Hashing, aber wenn Sie nur AES haben. . .

0
aesuser