Was macht einen Hashing-Algorithmus „sicher“?

Nachdem ich diese interessante Frage gelesen hatte , hatte ich das Gefühl, eine gute Vorstellung davon zu haben, welchen unsicheren Hashalgorithmus ich verwenden würde, wenn ich einen brauche, aber keine Ahnung, warum ich stattdessen einen sicheren Algorithmus verwenden könnte.

Was ist der Unterschied? Ist die Ausgabe nicht nur eine Zufallszahl, die den Hash darstellt? Was macht einige Hashalgorithmen sicher?

Es gibt drei Eigenschaften, die von jeder kryptografischen Hash-Funktion gewünscht werden H:

• Urbild Widerstand : Da hsollte es schwierig sein , einen Wert zu finden , xmit h = H(x).

• zweiter preimage widerstand : x1da sollte es schwer zu finden sein x2 != x1mit H(x1) = H(x2).

• Kollision Widerstand : Es sollte schwer sein , zwei Werte zu finden , x1 != x2mit H(x1) = H(x2).

Mit Hash-Funktionen, wie sie in gängigen Programmiersprachen für Hash-Tabellen (von Strings) verwendet werden, wird in der Regel keine von diesen angegeben. Sie bieten nur Folgendes:

• Schwache Kollisionsbeständigkeit : Für zufällig (oder "typisch") ausgewählte Werte der Domäne ist die Kollisionswahrscheinlichkeit gering. Dies sagt nichts darüber aus, dass ein Angreifer absichtlich versucht, Kollisionen zu erzeugen oder Vorbilder zu finden.

Die drei oben genannten Eigenschaften sind (unter) die Entwurfsziele für jede kryptografische Hashfunktion. Für einige Funktionen (wie MD4, SHA-0, MD5) ist bekannt, dass dies (zumindest teilweise) fehlgeschlagen ist. Die aktuelle Generation (SHA-2) gilt als sicher, und die nächste ("Secure Hash Algorithm 3") wird derzeit nach einem Wettbewerb standardisiert .

Für einige Verwendungszwecke (z. B. Kennwort-Hashing und Schlüsselableitung von Kennwörtern) ist die Domäne der tatsächlich verwendeten Werte xso klein, dass das Erzwingen dieses Speicherplatzes mit normalen (schnellen) sicheren Hash-Funktionen möglich wird. In diesem Fall möchten wir auch:

• langsame Ausführung : Vorausgesetzt x, die Berechnung des Werts erfordert einen minimalen (vorzugsweise konfigurierbaren) Ressourcenaufwand H(x).

Für die meisten anderen Anwendungen ist dies jedoch nicht erwünscht. Stattdessen möchte man:

• Schnelle Ausführung : Vorausgesetzt x, die Berechnung von H(x)erfolgt so schnell wie möglich (und trotzdem sicher).

Es gibt einige Konstruktionen (wie PBKDF2 und Scrypt), um eine langsame Hash-Funktion aus einer schnellen zu erstellen, indem sie häufig iteriert wird.

Weitere Informationen finden Sie im Hashtag auf unserer Schwestersite Cryptography Stack Exchange.

Sicher bedeutet, dass jemand, der Sie durch die Verwendung einer Kollision in einen Fehler verwickeln möchte (dh die Tatsache, dass zwei Quellen auf den gleichen Wert gehasht werden), Schwierigkeiten hat.

Einige Eigenschaften:

• Es ist schwierig, den Hash zu kennen und eine Datei zu erstellen, die auf diesen Wert hasht (Variante, ein Teil der neuen Datei wird angegeben sowie der gewünschte Hash).

• Es ist schwierig, zwei verschiedene Dateien zu erstellen, die den gleichen Wert haben (Variante, ein Teil der Dateien ist angegeben).

Der Hauptunterschied ist ziemlich einfach: Ein normaler Hash soll die Anzahl der versehentlichen Kollisionen so gering wie möglich halten, ohne dabei eine ganze Menge zu verlangsamen.

Ein sicherer Hash, der Kollisionen verhindern soll, auch wenn jemand sein Bestes tut, um sie auszulösen. Im Allgemeinen möchten Sie keine Kollisionsmöglichkeit gegen eine schnellere Operation eintauschen. Tatsächlich hat die absichtliche Verlangsamung des Betriebs einige Sicherheitsvorteile, auch wenn das Auffinden von Kollisionen nicht erschwert wird.

Ein Beispiel für Letzteres: Wenn das Berechnen eines Hashs 50 ms dauert, hat dies keine wesentlichen Auswirkungen auf die Anmeldung eines normalen Benutzers (dh die meisten Benutzer bemerken beim Anmelden keinen Unterschied von 50 ms). Wenn ein Angreifer einen Wörterbuchangriff ausführen möchte, ist es ein schwerwiegendes Handicap , nur 20 Hashes pro Sekunde zu erzeugen . Mit anderen Worten, aus irgendeinem Grund ist langsamer für einen sicheren Hash besser.

Lesen Sie diese http://www.codinghorror.com/blog/2012/04/speed-hashing.html es wird alles viel besser erklären, als ich es jemals erklären könnte. Hier sind die beiden wichtigsten Überschriften im Artikel, die sich direkt mit Ihrer Frage befassen:

• Sichere Hashes sind manipulationssicher
  • ändert seine Ausgabe radikal mit winzigen Einzelbitänderungen an den Eingabedaten
• Sichere Hashes sind so konzipiert, dass sie langsam sind

Sein TL; DR-Teil am Ende:

Wenn Sie ein Benutzer sind:

Vergewissern Sie sich, dass alle Ihre Passwörter aus mindestens 12 Zeichen bestehen, im Idealfall aus sehr viel mehr. Ich empfehle, Passphrasen zu verwenden, die nicht nur viel einfacher zu merken sind als Passwörter (wenn nicht Typ), sondern auch auf Grund ihrer Länge lächerlich sicher gegen brachiales Erzwingen sind.

Wenn Sie ein Entwickler sind:

Verwenden Sie bcrypt oder PBKDF2 ausschließlich, um alles zu hacken, was Sie für die Sicherheit benötigen. Diese neuen Hashes wurden speziell dafür entwickelt, dass sie auf GPUs nur schwer zu implementieren sind. Verwenden Sie keine andere Form von Hash. Nahezu jedes andere bekannte Hashing-System ist anfällig für Brute-Forcing durch Arrays von Standard-GPUs, die von Jahr zu Jahr schneller und paralleler werden und einfacher zu programmieren sind.

Ein "sicherer" Hash ist ein Hash, von dem angenommen wird, dass er auf formelhafte und reproduzierbare Weise nur schwer zu "fälschen" ist, wenn die zur Erstellung des Hashs verwendete Nachricht im Voraus bekannt ist. Da diese Informationen im Allgemeinen geheim sind und daher ein Hash erforderlich ist, ist dies eine gute Eigenschaft einer Hash-Funktion, die zur Verwendung bei der Authentifizierung vorgesehen ist.

Ein Hash wird im Allgemeinen als "sicher" betrachtet, wenn bei einer gegebenen Nachricht M, einem Hash-Funktions-Hash () und einem Hash-Wert H, der durch Hash (M) mit einer Länge in Bits L erzeugt wird, keines der Folgenden in weniger als ausgeführt werden kann O (2 ^L ) Zeit:

• Mit Hash () und H erhält man M. (Preimage Resistance)
• Erzeugt bei gegebenem Hash () und M ein anderes M _2, so dass Hash (M ₂ ) == H. (schwacher Kollisionswiderstand)
• Wenn hash () gegeben ist, produziere M ₁ und M ₂ so, dass hash (M ₁ ) == hash (M ₂ ) ist. (starke Kollisionsfestigkeit)

Zusätzlich muss ein "sicherer" Hash eine Hash-Länge L von 2 ^{L haben}Dies ist keine praktikable Anzahl von Schritten, die ein Computer ausführen kann, wenn die aktuelle Hardware vorhanden ist. Ein 32-Bit-Ganzzahl-Hash kann nur 2,1 Milliarden Werte haben. Während ein Preimage-Angriff (das Auffinden einer Nachricht, die ein bestimmtes Hash-H erzeugt) eine Weile dauern würde, ist er für viele Computer nicht durchführbar, insbesondere für diejenigen in den Händen von Regierungsbehörden, die mit Code-Breaking gechartert sind. Darüber hinaus würde ein Algorithmus, der zufällige Nachrichten und deren Hashes erstellt und speichert, mit einer Wahrscheinlichkeit von 50% versuchen, mit jeder neuen Nachricht einen doppelten Hash zu finden, nachdem er nur 77.000 Nachrichten ausprobiert hat duplizieren nach nur 110.000. Selbst 64-Bit-Hashes haben noch eine 50-prozentige Chance zu kollidieren, nachdem sie nur etwa 5 Milliarden Werte ausprobiert haben. Das ist die Macht des Geburtstagsangriffs auf kleine Haschischarten. Im Gegensatz,Dezillionszahlen (1,5 * 10 ³⁴ ).

Die meisten zeigten Angriffe auf kryptographischen Hashes haben Kollision Angriffe gewesen und haben die Fähigkeit gezeigt , zu erzeugen Nachrichten in weniger als 2 kollidiert ^L Zeit ( die meisten haben noch exponentiell Zeit gewesen, aber den Exponenten um die Hälfte reduziert ist eine signifikante Reduktion der Komplexität , da es macht ein 256-Bit-Hash, der so einfach zu lösen ist wie ein 128-Bit-Hash, ein 128-Bit-Hash, der so einfach zu lösen ist wie ein 64-Bit-Hash usw.).

Neben der geringen Hash-Größe können folgende Faktoren einen Hash nachweislich unsicher machen:

Geringer Arbeitsaufwand - Ein Hash, der für die Verwendung durch eine Hash-Tabelle oder für andere Zwecke vom Typ "Prüfsumme" entwickelt wurde, ist normalerweise so konzipiert, dass er rechnerisch kostengünstig ist. Das macht einen Brute-Force-Angriff so viel einfacher.

"Sticky State" - Die Hash-Funktion ist anfällig für Eingabemuster, bei denen sich der aktuelle Hash-Wert aller Eingaben bei einem bestimmten zusätzlichen Eingabebyte nicht ändert. Wenn Sie den Status "Sticky State" haben, können Kollisionen leicht gefunden werden, da es trivial ist, andere Nachrichten mit demselben Hash zu generieren, indem Sie Eingabebytes anhängen, die den Hash in seinem Status "Sticky State" halten ".

Diffusion - Jedes Eingabebyte der Nachricht sollte auf die Bytes des Hash-Werts in gleich komplexer Weise verteilt werden. Bestimmte Hash-Funktionen erzeugen vorhersehbare Änderungen an bestimmten Bits im Hash. Dies macht die Kollisionserzeugung wieder trivial; Bei einer Nachricht, die einen Hash erzeugt, können leicht Kollisionen erzeugt werden, indem neue Werte in die Nachricht eingefügt werden, die sich nur auf die Bits auswirken, die sich vorhersagbar ändern.

Verwenden Sie den richtigen Algorithmus für die jeweilige Aufgabe.

CRCs werden zur Fehlererkennung / -korrektur verwendet.

Kryptografische Message Digests wie SHA2 werden als Baustein für kryptografische Konstrukte (digitale Signaturen, MACs, Schlüsselableitungs- / Passwort-Hashing-Funktionen) und Sicherheitsprotokolle verwendet.

Verwenden Sie in Hash-Tabellen / Wörterbüchern / Karten SipHash .

Was Sie als unsichere Hashing-Algorithmen bezeichnen, sollten Sie nicht in Hash-Tabellen verwenden , wie die folgenden CVE-Einträge belegen: CVE-2003-0364, CVE-2011-4461, CVE-2011-4838, CVE-2011-4885, CVE-2011- 4462, CVE-2011-4815, CVE-2012-0840, CVE-2012-5371 , CVE-2012-5374, CVE-2012-5375