Was bedeutet das: Vergleichen Sie zwei Strings $ a und $ b in der Länge-Konstante Zeit?

8

Beim Erlernen von Passwort-Hashing und Speichern in DB habe ich diesen Artikel gefunden: Ссылка

Alles war klar, außer dieser Funktion, die ich nicht genau verstehen kann, warum nicht normale Gleichheit benutzt wurde? Und was ist gemeint mit: Vergleicht zwei Strings $ a und $ b in längenkonstanter Zeit.

%Vor%     
Jason OOO 15.09.2013, 08:29
quelle

1 Antwort

19

Wenn Sie normalerweise vergleichen, ob zwei Strings gleich sind oder nicht, stoppt der Algorithmus, wenn er auf die erste Ungleichung stößt.

So: "aaa" == "aba"? Erster Charakter? Beide "ein". Zweiter Charakter? "a" ist nicht "b", also hör hier auf, um Zeit zu sparen. Das letzte Zeichen wird nicht verglichen.

Beim Vergleich von sicherheitsrelevanten Strings kann ein Angreifer einen Hinweis bekommen, welches Zeichen korrekt und welches wegen der Laufzeit einer solchen Vergleichsfunktion falsch ist.

Bedenken Sie einen Moment die unsichere Praxis, Klartextpasswörter zu haben. Wenn der Angreifer herausfinden kann, ob das erste Zeichen seines erratenen Passworts korrekt ist oder nicht, indem er misst, wie lange der Passwortvergleich läuft, benötigt er nur ungefähr 62 Annahmen (Buchstaben, Klein- und Großbuchstaben und Zahlen), um den ersten Buchstaben zu erkennen. Mit einem Buchstaben war die Laufzeit länger, weil dieser erste Buchstabe mit dem echten Passwort identisch war und der zweite Buchstabe verglichen wurde. Jetzt wird der zweite Buchstabe wiederholt. Und nach 62 weiteren Vermutungen ist bekannt.

Dies schwächt die Sicherheit sehr, denn ohne zu wissen, ob der erste Buchstabe richtig ist, würden Sie 62 * 62 Vermutungen für ein aus zwei Buchstaben bestehendes Passwort benötigen. Mit einem Hinweis benötigen Sie nur 62 + 62 Vermutungen.

Eine längenkonstante Vergleichsfunktion vergleicht alle Buchstaben und zeigt erst am Ende, ob die Strings übereinstimmen. Auf diese Weise können Sie keine Ahnung bekommen, welcher Buchstabe bereits richtig ist.

Das Hashing von Strings verwechselt die Dinge ein wenig, aber weil Sie nicht wissen können, ob der Angreifer eine Reihe von Hashes vorgeneriert hat oder sie im laufenden Betrieb generiert und das entsprechende Passwort NICHT brute-force, wenn der Hash nicht übereinstimmt , Sie wollen nicht, dass irgendjemand weiß, wo dieser Hash nicht passt. Es ist eine kleine zusätzliche Sicherheitskomponente, aber eine sehr wichtige.

    
Sven 15.09.2013, 08:53
quelle

Tags und Links