Hash und Salt

Das Konzept von Salts ist eigentlich ein sehr einfaches. Da ich jetzt aber ein paarmal über Menschen gestolpert bin, denen das Konzept nicht klar wurde (und es auch selbst am Anfang für etwas hoch-komplexes hielt), versuche ich mich mal an einer einfachen Erklärung.

Funktionsweise

Angenommen, man hat eine Webanwendung, in die sich Leute mit einem Passwort einloggen können (sie könnte Serendipity heißen). Selbstverständlich speichert man das Passwort dieser Nutzer nicht im Klartext ab, weil dann ein einfacher Blick in die Datenbank genügen würde, um das Passwort zu verraten. Stattdessen speichert man den Hash H des Passworts, der durch eine beliebige kryptographische Hashfunktion generiert wird:

H = hash(Passwort)

hash() ist im wesentlichen eine Einwegfunktion, also kann aus H nicht direkt Passwort rekonstruiert werden. Es existiert kein unhash(H) == Passwort.

Bei einem Loginversuch mit dem Passwort wird dann das Hashen wiederholt und mit dem gespeicherten H in der Datenbank verglichen:

bool loginCorrect?(passwort) {
    return (hash(passwort) == H)
}

Nur wenn die beiden Hashes übereinstimmen, stimmen die durch die Hashes repräsentierten Passwörter und der Nutzer kann sich erfolgreich einloggen.

Nun kommt der Salt dazu. Der wird zufällig gewählt, ist also eine zufällige Zeichenfolge, und wird dem Passwort angehängt:

hash(Passwort + Salt) = salted_H

Das wird nun bei jeder Passworterstellung gemacht, also insbesondere jedes Mal ein neuer Salt berechnet. Vom Prinzip her ist das alles.

Der Salt wird natürlich mit dem salted_H in der Datenbank gespeichert. Das ist notwendig, denn bei einem Loginversuch wird ja wieder ein Hash berechnet und mit dem gespeicherten verglichen:

bool loginCorrect?(passwort) {
    return (hash(passwort + Salt) == salted_H)
}

Warum?

Bleibt die Frage, warum man einen solchen Salt nutzen sollte. Die Antwort: Sicherheit. Es soll verhindert werden, dass aus den Hashes indirekt das Passwort berechnet werden kann. In der Konsequenz geht es um ein Gegenmittel gegen Rainbow-Tables.

Die Datenbank der Webanwendung könnte gestohlen werden, wie das ja in letzter Zeit reihenweise passierte. Ziel des Angreifers ist es danach, das Passwort im Klartext herauszufinden. Aus zwei Gründen:

1. Wenn er nur die Datenbank hat, könnte er sich dann in der Webanwendung einloggen und Aktionen durchführen
2. Viele Nutzer verwenden Passwörter mehrfach, sodass der Angreifer bei vielen anderen Diensten gültige Logins und Passwörter bekommen würden

Im Idealfall hat der Angreifer bisher nur die Datenbank mit dem Nutzernamen (der natürlich auch gehasht werden könnte), dem salted_H und dem Salt jedes Nutzers. Schon dank des Hashens reicht das nicht, um sich einzuloggen. Denn die Loginfunktion hasht ja wieder, gibt man den salted_H da ein entsteht also:

return (hash(salted_H + Salt) == salted_H))

Auch ohne den Salt wäre das false, denn man kann davon ausgehen, dass hash(hash(X)) != hash(X).

Ohne den Salt würde der Angreifer jetzt versuchen, eine Rainbow-Table aufzubauen. Dafür nutzt er seinen privaten Rechencluster in etwa so:

1000000000.times {
    passwort = guess_password()
    rainbow_table[hash(passwort)] = passwort
}

Er erstellt also eine Liste von gehashten Passwörtern und ihrem Klartext. Danach braucht er nur in der Datenbank zu schauen, ob der Hash verwendet wurde, und weiß deswegen, welches Passwort verwendet wurde um den Hash zu erstellen. Schon hat er das Passwort im Klartext.

Genau das verhindert der Salt. Da zwei Datenbanken oder sogar zwei Nutzer in einer Datenbank unterschiedliche Salts benutzen, unterscheidet sich ihr salted_H, selbst wenn sie das gleiche Passwort benutzen. Wird also eine Datenbank gestohlen, muss zwingend für jeden einzelnen Nutzer geguckt werden, ob

hash(guess_password() + Salt) == salted_H 

gilt. Eine Rainbow-Table, die die Salts mitspeichert würde absurd groß werden:

for salt in salts {
    1000000000.times {
        passwort = guess_password()
        rainbow_table[salt][hash(passwort +salt)] = passwort
    }
}

Daher kommt auch die Bewegung, teure Hashfunktionen wie bcrypt zu nutzen und sie möglichst noch mehrmals durchlaufen zu lassen. Bei einem Login ist die benötigte Zusatzzeit kaum bemerkbar, aber bei einem Knacken der Hashes tut jede ms weh.

Kurz

Ein Hash mit Salt ist einfach hash(X + Salt). Er schützt nicht generell vor schwachen Passwörtern, aber er erschwert es, dass Passwörter aus dem Hash rekonstruiert werden können.