Passwort Hashing Teil 2

Passwort-Hashing-Verfahren

Kryptographische Hashfunktionen

Eine Hashfunktion bildet eine Zeichenfolge beliebiger Länge auf eine Zeichenfolge fester Länge ab. Typischerweise wird eine längere Zeichenfolge, beispielsweise eine Datei, auf eine kürzere Zeichenfolge, den "Hashwert" abgebildet. Eine sehr simple Hashfunktion ist z.B. die einstellige Quersumme.
Kryptographische Hashfunktionen zeichnen sich dadurch aus, dass zu einem Hashwert nicht einfach eine Ausgangs-Zeichenfolge gefunden werden kann. Es lässt sich beispielsweise keine andere Datei ermitteln, die den Hashwert einer bestimmten Datei ergibt. Mittels Hashwerten lässt sich überprüfen, ob der Download einer Datei vollständig und fehlerfrei war, mit einem kryptographischen Hashwert lässt sich u.a. sicher überprüfen, ob eine Datei verändert wurde.

Passwort Hashing

Beim Passwort Hashing wird ein Passwort auf einen Hashwert abgebildet. Die Voraussetzungen der kryptographischen Hashfunktion gelten hier auch: Aus einem Hashwert soll nicht der Ausgangswert (das Passwort) berechnet werden können.

Ein typischer Anwendungsfall für das Passwort Hashing ist das Speichern von Passwörtern. Wann immer sich User*innen in einen Onlinedienst einloggen, muss irgendwann geprüft werden, ob das angegebene Passwort mit dem aus der Anmeldung übereinstimmt. Nachlässige Onlinedienste legen das Passwort irgendwo ab und vergleichen es dann mit dem Passwort des Logins. Das führt dazu, dass Hacker*innen sich Zugang dazu verschaffen, die Passwörter einfach kopieren und für ihre Zwecke nutzen, beispielsweise Bestellungen aufgeben. Da viele Menschen ihre Passwörter mehrfach benutzen, stehen die Chancen nicht schlecht, damit auch Zugriff auf Bankkonten zu erlangen.
Wenn statt dem Passwort dessen Hashwert abgelegt wird, dann kann bei jedem Login das Passwort eingegeben und dessen Hashwert wieder berechnet und mit dem abgelegten verglichen werden. Der Login wird nur der Person ermöglicht, die auch das Passwort kennt, ohne dass das Passwort irgendwo gespeichert wird. Wenn Hacker*innen sich dann Zugang verschaffen, finden sie nur einen Haufen zunächst sinnloser Zeichenfolgen (die Hashwerte) vor, mit denen sie sich nirgendwo einloggen können.
Auf den ersten Blick ist das Problem des Speicherns von Passwörtern gelöst.

Wörterbücher und Rainbow Tables

Leider haben diejenigen, die an Hashwerte von Passwörtern gelangen, gute Aussichten, doch daraus die Passwörter zu bestimmen. Kryptoanalyse hilft hier nicht weiter - viele Hashfunktionen sind so gut, dass ein Zurückberechnen praktisch aussichtslos ist. Aber Computer sind schnell und können in Sekunden Millionen von Passwörtern durchprobieren. Es genügt, die Millionen üblichsten Passwörter durch zu probieren, also deren Hashwert zu berechnen und mit dem vorhandenen Hashwert um vergleichen, um einen großen Teil der Passwörter zu ermitteln.
Es gibt sogenannte "Wörterbücher", in denen Passwörter gesammelt werden. Diese Wörterbücher werden immer größer und lassen sich im Netz herunterladen. Speichermedien sind billig und der Größe dieser Wörterbücher ist kaum eine Grenze gesetzt. Aufgeführt sind darin nicht nur alle Kombinationen sinnvoller Wörter mit irgendwelchen Jahreszahlen, sondern mehr oder weniger alle erdenklichen Kombinationen. Das Durchprobieren mittels solcher Wörterbücher um Passwörter zu ermitteln, nennt sich Wörterbuch-Angriff oder "dictionary attack".

Um das Durchprobieren zu vereinfachen bzw. zu beschleunigen, werden nicht nur Wörterbücher erstellt, die mögliche Passwörter enthalten, sondern - da die Anzahl der üblichen Hashfunktionen begrenzt ist - die Hashwerte im Voraus berechnet.

Rainbow by alobos Life, license: CC

Rainbow Tables sind eine Art Nachschlagtabellen, die für bestimmte Hashfunktionen erstellt werden. Sie bestehen normalerweise nicht einfach aus den Paaren "Passwort - Hashwert", denn dann stießen sie aufgrund des Speicherplatzes schnell an ihre Grenzen, sondern aus Ketten oder Sequenzen aus Passwörtern für die nur ein Passwort und ein Hashwert gespeichert wird und die dann durchlaufen werden müssen, um ein Passwort zu finden. Mit Rainbow Tables können sehr viel mehr Hashwerte bzw. Passwörter abgedeckt werden als durch das einfache Speichern von Passwort-Hashwert-Paaren.
Natürlich können auch Datenbanken über die häufigsten Passwörter und ihr Hashwerte erstellt werden, die dann nur noch abgefragt werden müssen. Sie benötigen mehr Speicherplatz pro Passwort, das abgedeckt ist, aber da mit den 1000 häufigsten Passwörtern schon ein großer Teil geknackt werden kann, lohnt sich dieses Verfahren ebenfalls.
Rainbow Tables und Passwort-Datenbanken beruhen auf Voraus-Berechnungen ("precomputations"), die einmal angestellt, immer wieder verwendbar sind. Sie vereinfachen das Verfahren ungemein und reduzieren den Aufwand zur Bestimmung des Passworts aus dem Hashwert wesentlich.

Salt gegen Rainbow Tables

Salz

Mit "Salt" wird ein Zufallswert bezeichnet, mit dem Passwörter sozusagen "gesalzen" werden. Der Hashwert wird nicht allein aus dem Passwort berechnet, sondern aus dem Passwort mit dem Zufallswert. Für jede User*in bzw. jedes Konto wird ein neuer Salt erzeugt. Selbst gleiche Passwörter haben dann keine gleichen Hashwerte mehr zur Folge. Der Salt muss nicht den strengen Kriterien der Zufälligkeit (randomness) entsprechen, er muss jedoch einzigartig sein, d.h. er darf nicht mehrfach verwendet werden.
Wir müssen uns diesen Zufallswert glücklicherweise nicht merken, er kann einfach "öffentlich" zusammen mit dem Hashwert abgelegt werden. Der Sinn dieses "Salt" ist hauptsächlich, Rainbow Tables unbrauchbar zu machen. Diese Listen müssten dann nämlich nämlich für jedes erdenkliche Passwort zusammen mit jedem möglichen Zufallswert einen Hashwert aufführen. Speichermedien sind zwar billig, aber ihre Kapazitäten sind nicht grenzenlos. Bei einem Zufallswert von 16 Bytes wird dieses Unterfangen aussichtslos. Außerdem sind die Hashwerte zweier Logins auch dann unterschiedlich, wenn deren Passwörter gleich sind. Das verhindert, dass ein einmal gewonnene Zuordnung zwischen Hashwert und Passwort noch einmal verwendet werden kann.

Die begrenzte Entropie von Passwörtern

Rainbow Tables können mit wenig Aufwand unbrauchbar gemacht werden, aber ein Wörterbuch-Angriff ist immer noch möglich. Es muss lediglich für jedes aufgeführte Passwort zusammen mit dem Salt (der ja öffentlich ist), der Hashwert berechnet werden, bis der gesuchte Hashwert gefunden ist und dem Passwort zugeordnet werden kann.
Die "Entropie" von Passwörtern ist in der Regel so gering, dass dictionary attacks schnell erfolgreich sind. Die Länge eines sicheren Passwortes müsste mindestens 16 Zeichen betragen (das lässt sich bewerkstelligen), aber vor allem zufällig sein, also beispielsweise so aussehen "3(hn=,fz6@kKd9\g". Sichere Passwörter können sich die wenigsten Menschen merken. Es gibt viele Strategien, wie Passwörter - besser "Passphrasen" - so konstruiert werden, dass es zumindest unwahrscheinlich ist, dass sie in Wörterbüchern aufgeführt werden, aber gute Strategien sind kompliziert und ihre Produkte lassen sich meist auch nicht leicht merken. Auf jeden Fall ist es sinnvoll lange Passphrasen zu benutzen, also ganze Sätze, und zwar solche, die nicht in irgendwelchen Büchern oder gar im Internet aufgeführt sind.
Es ist aber Fakt, dass die meisten Menschen keine guten Passphrasen benutzen. Und es ist irgendwie unfair, dass den Menschen mit schlechter Gedächtnisleistung die Konten leer geräumt werden können.

Der Kostenfaktor von Passwort-Hashing-Verfahren

Wenn durch den Salt Rainbow Tables unbrauchbar geworden sind, muss für jedes Passwort, das durchprobiert wird, die Berechnung der Hashfunktion ausgeführt werden. Für die User*in beim Login muss nur eine Berechnung gemacht werden, sofern das Passwort richtig eingegeben wurde. Eine Angreifer*in muss viele Milliarden solcher Berechnungen ausführen, bis der passende Hashwert gefunden ist. Wenn die Berechnung aufwendiger wird, ändert sich für die User*in so gut wie nichts, für die Angreifer*in multipliziert sich jedoch der Aufwand. Das war die Grundidee, die den ersten Passwort-Hashing-Verfahren zugrunde lag. Das Verfahren "Crypt" beruhte beispielsweise auf einer 25fachen Verschlüsselung des Passworts mit der Verschlüsselungsfunktion DES.
Die User*in merkte von diesen 25 Berechnungen nichts, aber der Aufwand für die Angreifer*in hatte sich mit 25 multipliziert. Aus einer Stunde zur Ermittlung eines Passworts war damit mehr als ein ganzer Tag geworden.

Passwörter mit einem Salt zu versehen und in zeitaufwendigen Verfahren daraus Hashwerte zu berechnen, markiert die erste Generation von Passwort-Hashing-Verfahren.
Der Faktor 25 stellte sich bald als ungenügend heraus und irgendwann kam jemand auf die Idee, den Kostenfaktor variabel zu machen und ihn an die aktuelle Rechenleistung anzupassen. Der Faktor erhöhte sich schnell: Schon bald galten Werte unter 1000 als unsicher.
Die Verschlüsselungsfunktion wurde üblicherweise durch eine kryptographische Hashfunktion ersetzt und neben dem Salt noch ein Zähler für jede Runde der Berechnung eingeführt, aber das Grundschema blieb bis zu den 90er Jahren gleich. Es sah so aus als könnte die Rechenleistung, die sich ständig erhöhte, einfach durch den Kostenfaktor ausgeglichen werden und das Schema ewig weitergeführt werden.

Angriffe mit spezialisierter Hardware: "custom hardware attacks"

Das Aufkommen von spezialisierter Hardware wie ASICs, FPGAs und GPUs änderte die Situation grundlegend. Ein Kostenfaktor von 100.000 war plötzlich kein Problem mehr: sofern genügend finanzielle Mittel zur Verfügung standen, änderte der Faktor am Zeitaufwand wenig. Um diesem neuen Typ des Angriff, dem "custom hardware attack" vorzubeugen, musste der Kostenfaktor so hoch gesetzt werden, dass schon bei einem einfachen Login-Prozess unfreiwillige Kaffeepausen entstanden. Tatsächlich wurde in den wenigsten Fällen der Kostenfaktor den neuen Gegebenheiten angepasst, denn das hätte die User*innen verprellt. Es wurde einfach billigend in Kauf genommen, dass die Passwörter geknackt werden konnten.
An dieser Situation hat sich bis heute kaum etwas geändert. Passwort-Speicherung und Passwort-basierte Verschlüsselungen sind ein bekannter Schachpunkt in der Kryptographie.

weiter zu Teil 2