{"id":1422,"date":"2013-05-09T16:00:32","date_gmt":"2013-05-09T14:00:32","guid":{"rendered":"http:\/\/blog.benny-baumann.de\/?p=1422"},"modified":"2013-05-14T09:51:31","modified_gmt":"2013-05-14T07:51:31","slug":"fuzzy-passwords","status":"publish","type":"post","link":"https:\/\/blog.benny-baumann.de\/?p=1422","title":{"rendered":"Fuzzy Passwords"},"content":{"rendered":"

Jeder kennt das: Man m\u00f6chte sich bei einem Dienst seiner Wahl mit seinem ultra-sicheren 42-stelligen Passwort mit 1337 Byte Entropie anmelden und stellt 0.23 Sekunden nach dem Absenden fest, dass man an der 5. Stelle statt dem Kanji* f\u00fcr 10^28 nur 10^4 geschrieben hat. Und da der Server wie so h\u00e4ufig \u00fcberlastet, und das Mobilfunknetz am Handy schon vor 3 Minuten wegen obligatorischer \u00dcberlastung von jeder toten Schnecke \u00fcberholt wird, denkt man sich, wie froh man doch sein kann, dass man nach weiteren 5 Minuten Bildschirm-Starren endlich erneut seine kostbare Zeit darauf verwenden darf, sein aus Buchstaben, Zahlen, Sonderzeichen, Keilschrift, Rhunen, Kanji und Klingonisch zusammengesetztes 42-stelliges Passwort auf der 3 Millimeter gro\u00dfen Touch-Tastatur einzutippen.<\/p>\n

Doch dies muss nicht sein!<\/p>\n

Ein Ansatz<\/h2>\n

Warum lassen wir nicht einfach die Blechkiste auf der anderen Seite der Verbindung entscheiden, dass die prinzipielle Kenntnis des Passwortes f\u00fcr diesen Account vorhanden ist und man sich einfach nur ungl\u00fccklich verschrieben hat? M\u00f6glich w\u00e4re das doch immerhin, da der Vergleich des Passwortes auf Server-Seite nahezu beliebig gestaltet werden kann.<\/p>\n

Eine L\u00f6sung zur Erh\u00f6hung des Komforts bei der Kennwort-Eingabe hat nun der Heise-Verlag vorgestellt<\/a>, nachdem bei der Analyse der Logfiles aufgefallen war, das insbesondere Nutzer von Handy-Tastaturen \u00fcberdurchschnittlich h\u00e4ufig an der Eingabe des Passwortes scheitern und dadurch unn\u00f6tige Last durch die erneuten Versuche beim wiederholten Eingeben des Passwortes auf dem Server erzeugt wird.<\/p>\n

Die L\u00f6sung<\/h2>\n

Die L\u00f6sung ist so einfach, wie genial: Fuzzy Passwords!<\/p>\n

Statt also einen exakten Vergleich zwischen gespeichertem und eingegebenen Passwort zu erzwingen, wird die Pr\u00fcfroutine auf dem Server derart angepasst, dass auch Abvarianten des Passwortes, die nah genug am Original sind, akzeptiert werden; neben „test1234“ werden also auch „text1234“ und „test123“ akzeptiert.<\/p>\n

Ein Einwand, der hierbei spontan einf\u00e4llt, wenn man das Vorgehen zur Speicherung von Passworten kennt, h\u00e4ngt mit dem Hashen des Passwortes zusammen: Hashes sind darauf ausgelegt, dass die gehashten Daten nicht wieder in lesbare Informationen \u00fcberf\u00fchrt werden k\u00f6nnen. M\u00f6chte man aber eine Autokorrektur haben, so m\u00fcsste das korrekte Passwort aber bekannt sein oder zumindest rekonstruierbar. Naiv gesehen stimmt das, rein praktisch gesehen kann man aber sagen, dass der Login-Server das Klartext-Passwort eh kennen muss, danach aber in eine Form \u00fcberf\u00fchrt, in der keine Rekonstruktion mehr m\u00f6glich ist und erst dann vergleicht.<\/p>\n

Herausforderung ist es also, das gehashte Passwort so zu hinterlegen, dass ein Angreifer aus den gespeicherten Informationen nur dann rekonstruieren kann, wenn er das Passwort eh bereits so gut kennt, dass das System dieses Passwort eh akzeptieren w\u00fcrde. Der hierzu notwendige Weg ist jedoch nicht auf den ersten Blick ersichtlich, da er mit klassischem Hashen, Crypten oder Pr\u00fcfsummieren, wie es f\u00fcr Passworte standardm\u00e4\u00dfig verwendet wird, nichts zu tun hat. Ein reiner Hash hilft nur f\u00fcr den exakten vergleich, ein verschl\u00fcsseltes Passwort verr\u00e4t bei Kenntnis des Schl\u00fcssls das Passwort und eine Pr\u00fcfsumme sagt einem nur, dass man falsch geraten hat. Die Performance von MACs und HMACs ist vergleichbar der von Hashes, steigert aber die Sicherheitsschranke auf eine Art vergleichbar mit Salted Hashes.<\/p>\n

Die Fuzzyness<\/h2>\n

Der Ansatz ist einfach: Fehlerkorrektur!<\/p>\n

Bereits in den 1960er Jahren wurde an Verfahren gearbeitet, die es erlauben, dass selbst bei fehlerhafter \u00dcbertragung von Daten diese nicht vollst\u00e4ndig neu \u00fcbertragen werden mussten, solange die Fehlerrate unterhalb einer gewissen Schranke blieb. Dies wurde erreicht, indem in den zu \u00fcbertragenden Datenstrom zus\u00e4tzliche Korrektur-Informationen eingebettet wurden, die Redundanz im Datenstrom erzeugt haben und somit das Lokalisieren von Fehlerstellen im empfangenen Datenstrom erm\u00f6glichen. Einer der bekanntesten Fehlerkorrekturcodes ist der auf CDs verwendete Reed-Solomon-Code – Auf CDs kommt zus\u00e4tzlich noch eine Redundanz-Kodierung zum Einsatz, die f\u00fcr unseren Fall aber uninteressant ist.<\/p>\n

Aber wie hilft uns das?<\/p>\n

Bei Reed-Solomon-Codes handelt es sich um einen separierbaren Fehlerkorrektur-Code, bei dem die Ausgangsinformation und die Fehlerkorrektur-Information getrennt codiert werden – zu der kodierten Information ist bekannt, welche Stellen Daten und welche Stellen Korrektur-Information besitzen. Betrachtet man jetzt unser obiges Szenario unter diesem Aspekt, ergibt sich, dass ein Passwort genau dann \u00e4hnlich ist, wenn bei Eingabe eines Passwortes dieses unter Zuhilfenahme der Fehlerkorrektur-Informationen so korrigiert werden kann, so das aus dem korrigierten Passwort der korrekte Passwort-Hash gebildet werden kann. Hat man jedoch nur die Fehlerkorrektur-Information reicht diese f\u00fcr die Rekonstruktion des Passwortes nicht aus, solange das Passwort l\u00e4nger als die Fehlerkorrektur-Information ist**.<\/p>\n

Soweit die Theorie, aber es wird noch besser: \u00dcber die Menge an Fehlerkorrektur kann man sogar die Fuzzyness dieser Korrektur steuern. Die Stufe Komfort-Toleranz auf der Heise-Testseite<\/a> h\u00e4tte beispielsweise deutlich mehr Korrektur-Information als mittlere oder wenig Toleranz. Nachteilig ist jedoch, dass Buchstabendreher als jeweils zwei Fehler erkannt werden und fehlende Zeichen als so viele Fehle interpretiert werden, wie noch nachfolgende Zeichen auftreten. Mit etwas mehr Aufwand lassen sich aber auch diese Probleme erkennen und korrigieren, ohne Klartextinformation zu ben\u00f6tigen.<\/p>\n

Aber der Reihe nach.<\/p>\n

Die Umsetzung<\/h2>\n

Im ersten Schritt k\u00fcmmern wir uns um das Speichern des Passwortes. Wie bereits angedeutet reicht hierf\u00fcr ein einfacher Hash nicht aus, da mit diesem keine Fehler korrigiert werden k\u00f6nnen. Daher muss neben dem Hash noch ein Fehlerkorrekturwert gespeichert werden. Um das Bruteforcen zus\u00e4tzlich zu erschweren, salzen wir den Hash zudem und sorgen mit stark erh\u00f6hten Iterationszahlen f\u00fcr zus\u00e4tzlichen Aufwand beim Pr\u00fcfen der Korrektheit. Um zus\u00e4tzlich das Ausnutzen der Codierung des Passwortes innerhalb des Fehlerkorrekturcodes zu erschweren, randomisieren wir die Reihenfolge der Buchstaben im Fehlerkorrekturcode; ein Angreifer hat nun zus\u00e4tzliche Arbeit, um die Fehlerkorrektur durchzuf\u00fchren, die er in jedem Schritt erledigen muss.<\/p>\n

Neben diesen – im Wesentlichen die Pr\u00fcfung betreffenden – Optionen haben wir aber auch beim Kodieren der Fehlerkorrektur-Informationen reichlich Auswahl: Neben der Bitbreite der kodierten Zeichen (wir k\u00f6nnen hier w\u00e4hlen von 2 bis unendlich), k\u00f6nnen wir auch das Generator-Polynom des Feldes beeinflussen. Codiert man nun noch eine zuf\u00e4llige Basis-Information in die nicht genutzten Positionen, vermeidet man Probleme mit als Konstant bekannten Positionen.<\/p>\n

F\u00fcr unseren Fuzzy-Hash nutzen wir demnach folgendes Format:<\/p>\n

$fuzzy$[salt]$[iterations]$gf$[gfsize]$[gfpoly]$[correctables]$[permutation]$[noise]$[hashtype]$[hash]$[fecbytes]<\/pre>\n
Der Aufbau folgt hierbei einem Standard-Crypt-Hash, f\u00fcgt jedoch eine Reihe weiterer Felder hinzu:<\/p>\n