Was macht einen Hashing-Algorithmus „sicher“?

19

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?

CodexArcanum
quelle
8
Diese Frage ist für die IT Security SE-Site besser geeignet .
Bernard
@Bernard Wenn das der Fall ist, bin ich damit einverstanden, aber meine Frage war nicht wirklich, wie oder wann ein sicherer Hash zu verwenden ist, sondern was einen sicheren Hash-Algorithmus von einem unsicheren unterscheidet. Das scheint mir eher eine Programmierfrage zu sein, aber ich suche nicht in IT Security SE. Vielleicht funktioniert das auch dort.
CodexArcanum
2
Eine sehr ähnliche Frage wurde bereits zur IT-Sicherheit gestellt
ChrisF

Antworten:

34

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.

Paŭlo Ebermann
quelle
3

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).

Ein Programmierer
quelle
3

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.

Jerry Sarg
quelle
3
Auf dem Gebiet der kryptografischen Hash-Funktionen gibt es zwei wichtige Untergruppen: die schnellen (für die Nachrichtenauthentifizierung, Signatur und dergleichen) und die langsamen (für die Schlüsselableitung und das Kennwort-Hashing). Mischen Sie diese nicht, es gibt Anwendungen für beide.
Paŭlo Ebermann
Tatsächlich gibt es auch Hash-Funktionen, die Kollisionen maximieren sollen : Soundex ist ein Beispiel. Dies macht es offensichtlich zu einer sehr beschissenen sicheren Hash-Funktion.
Jörg W Mittag
@ JörgWMittag: Nicht nur beschissen als sicherer Hash, sondern wäre auch für die Verwendung mit einem Hash-Tisch ziemlich dürftig. Auf der anderen Seite würde ich Soundex, obwohl es sicherlich etwas hash-artig ist, zögern, eine Hash-Funktion zu bezeichnen, einfach weil seine Absicht und Verwendung sich so grundlegend von normalen Hash-Funktionen unterscheidet.
Jerry Coffin
@ JerryCoffin: Ich denke, es hängt von der Definition ab. Zum Beispiel sagt die englische Wikipedia-Seite einfach, dass eine Hash-Funktion ein Algorithmus oder eine Unterroutine ist, die eine größere (möglicherweise unendliche) Menge von beliebigen Werten in eine kleinere, endliche Menge von (normalerweise skalaren) Werten abbildet. Während die deutsche Wikipedia-Seite besagt, dass das "Hashing" ("zerhacken") ein integraler Bestandteil ist, dh dass Kollisionsvermeidung und Verteilung der abgebildeten Werte der Schlüssel ist. Soundex erfüllt sehr viel die erste Definition, aber nicht die zweite.
Jörg W Mittag
3

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.

Nate
quelle
4
Jeff hat es hier im zweiten Punkt falsch gemacht ... während Sie für einige Verwendungen (als Kennwort-Hashing und Schlüsselableitung von einem Kennwort) langsam sein möchten, für andere Verwendungen (wie Nachrichtenauthentifizierung, Signaturen usw.) schnell (sicher) Hash-Funktionen sind gut.
Paŭlo Ebermann
Sie sind richtig, Paŭlo. Die Leistung des Hash hängt von der Anwendung des Hash ab. Langsame Hashes sind jedoch immer sicherer als schnelle. Der Grund, warum Sie einen schnellen Hash verwenden würden, ist, wenn Sie in Ordnung sind, die Sicherheit für die Leistung zu opfern.
Nate
2
@Nate "Sicherer" ist immer zweideutig, aber auch unter den am meisten gemeinnützigen Anwendungen ist "langsame Hashes sind immer sicherer als schnelle" definitiv falsch. Es gibt viele Anwendungen, bei denen die Geschwindigkeit eines Hashs keine Rolle spielt.
Gilles 'SO- hör auf böse zu sein'
@ Gilles kannst du ein Beispiel geben? Das hört sich für mich tatsächlich richtig an, aber weitere Einzelheiten wären hilfreich.
Nate
2
@Nate Die naheliegendste Anwendung von Hashes ist die Überprüfung der Integrität eines Datenelements: Übertragen Sie den Hash über einen sicheren Kanal mit möglicherweise geringer Bandbreite, übertragen Sie die möglicherweise große Nutzlast über einen unsicheren Kanal, und überprüfen Sie dann, ob die empfangene Nutzlast den Erwartungen entspricht hash. Hashes spielen auch eine wichtige Rolle bei Signaturmethoden (bei denen Sie nicht nur die Integrität überprüfen, sondern auch, wer Ihnen die Daten gesendet hat). Das Hashing von Passwörtern ist eher die Ausnahme.
Gilles 'SO- hör auf böse zu sein'
2

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 2 ) == H. (schwacher Kollisionswiderstand)
  • Wenn hash () gegeben ist, produziere M 1 und M 2 so, dass hash (M 1 ) == hash (M 2 ) ist. (starke Kollisionsfestigkeit)

Zusätzlich muss ein "sicherer" Hash eine Hash-Länge L von 2 L habenDies 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 34 ).

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.

KeithS
quelle
0

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

Erwan Legrand
quelle