BenBE's humble thoughts Thoughts the world doesn't need yet …

Jeder kennt das: Man möchte 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ür 10^28 nur 10^4 geschrieben hat. Und da der Server wie so häufig überlastet, und das Mobilfunknetz am Handy schon vor 3 Minuten wegen obligatorischer Überlastung von jeder toten Schnecke überholt 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ßen Touch-Tastatur einzutippen.

Doch dies muss nicht sein!

Ein Ansatz

Warum lassen wir nicht einfach die Blechkiste auf der anderen Seite der Verbindung entscheiden, dass die prinzipielle Kenntnis des Passwortes für diesen Account vorhanden ist und man sich einfach nur unglücklich verschrieben hat? Möglich wäre das doch immerhin, da der Vergleich des Passwortes auf Server-Seite nahezu beliebig gestaltet werden kann.

Eine Lösung zur Erhöhung des Komforts bei der Kennwort-Eingabe hat nun der Heise-Verlag vorgestellt, nachdem bei der Analyse der Logfiles aufgefallen war, das insbesondere Nutzer von Handy-Tastaturen überdurchschnittlich häufig an der Eingabe des Passwortes scheitern und dadurch unnötige Last durch die erneuten Versuche beim wiederholten Eingeben des Passwortes auf dem Server erzeugt wird.

Die Lösung

Die Lösung ist so einfach, wie genial: Fuzzy Passwords!

Statt also einen exakten Vergleich zwischen gespeichertem und eingegebenen Passwort zu erzwingen, wird die Prüfroutine 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.

Ein Einwand, der hierbei spontan einfällt, wenn man das Vorgehen zur Speicherung von Passworten kennt, hängt mit dem Hashen des Passwortes zusammen: Hashes sind darauf ausgelegt, dass die gehashten Daten nicht wieder in lesbare Informationen überführt werden können. Möchte man aber eine Autokorrektur haben, so müsste 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 überführt, in der keine Rekonstruktion mehr möglich ist und erst dann vergleicht.

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ürde. Der hierzu notwendige Weg ist jedoch nicht auf den ersten Blick ersichtlich, da er mit klassischem Hashen, Crypten oder Prüfsummieren, wie es für Passworte standardmäßig verwendet wird, nichts zu tun hat. Ein reiner Hash hilft nur für den exakten vergleich, ein verschlüsseltes Passwort verrät bei Kenntnis des Schlüssls das Passwort und eine Prüfsumme 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.

Die Fuzzyness

Der Ansatz ist einfach: Fehlerkorrektur!

Bereits in den 1960er Jahren wurde an Verfahren gearbeitet, die es erlauben, dass selbst bei fehlerhafter Übertragung von Daten diese nicht vollständig neu übertragen werden mussten, solange die Fehlerrate unterhalb einer gewissen Schranke blieb. Dies wurde erreicht, indem in den zu übertragenden Datenstrom zusätzliche Korrektur-Informationen eingebettet wurden, die Redundanz im Datenstrom erzeugt haben und somit das Lokalisieren von Fehlerstellen im empfangenen Datenstrom ermöglichen. Einer der bekanntesten Fehlerkorrekturcodes ist der auf CDs verwendete Reed-Solomon-Code – Auf CDs kommt zusätzlich noch eine Redundanz-Kodierung zum Einsatz, die für unseren Fall aber uninteressant ist.

Aber wie hilft uns das?

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 ähnlich 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ür die Rekonstruktion des Passwortes nicht aus, solange das Passwort länger als die Fehlerkorrektur-Information ist**.

Soweit die Theorie, aber es wird noch besser: Über die Menge an Fehlerkorrektur kann man sogar die Fuzzyness dieser Korrektur steuern. Die Stufe Komfort-Toleranz auf der Heise-Testseite hätte 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ötigen.

Aber der Reihe nach.

Die Umsetzung

Im ersten Schritt kümmern wir uns um das Speichern des Passwortes. Wie bereits angedeutet reicht hierfür ein einfacher Hash nicht aus, da mit diesem keine Fehler korrigiert werden können. Daher muss neben dem Hash noch ein Fehlerkorrekturwert gespeichert werden. Um das Bruteforcen zusätzlich zu erschweren, salzen wir den Hash zudem und sorgen mit stark erhöhten Iterationszahlen für zusätzlichen Aufwand beim Prüfen der Korrektheit. Um zusätzlich das Ausnutzen der Codierung des Passwortes innerhalb des Fehlerkorrekturcodes zu erschweren, randomisieren wir die Reihenfolge der Buchstaben im Fehlerkorrekturcode; ein Angreifer hat nun zusätzliche Arbeit, um die Fehlerkorrektur durchzuführen, die er in jedem Schritt erledigen muss.

Neben diesen – im Wesentlichen die Prüfung betreffenden – Optionen haben wir aber auch beim Kodieren der Fehlerkorrektur-Informationen reichlich Auswahl: Neben der Bitbreite der kodierten Zeichen (wir können hier wählen von 2 bis unendlich), können wir auch das Generator-Polynom des Feldes beeinflussen. Codiert man nun noch eine zufällige Basis-Information in die nicht genutzten Positionen, vermeidet man Probleme mit als Konstant bekannten Positionen.

Für unseren Fuzzy-Hash nutzen wir demnach folgendes Format:

$fuzzy$[salt]$[iterations]$gf$[gfsize]$[gfpoly]$[correctables]$[permutation]$[noise]$[hashtype]$[hash]$[fecbytes]

Der Aufbau folgt hierbei einem Standard-Crypt-Hash, fügt jedoch eine Reihe weiterer Felder hinzu:

• fuzzy: Literaler String, um auf einen Fuzzy-Hash hinzuweisen
• salt: zufällige Bytes für den Salt
• iterations: Anzahl an Iterationen, die gehasht werden müssen
• gf: Hinweis darauf, dass ein Galois-Feld zur Fehlerkorrektur verwendet wird. Weitere Fehlerkorrektur-Codes könnten alternativ eingesetzt oder kombiniert werden
• gfsize: Die Bitbreite des verwendeten Galois-Feldes
• gfpoly: Das Generator-Polynom für das eingesetzte Galois-Feld
• correctables: Anzahl der korrigierbaren Zeichen
• permutation: Ein Seed-Wert für einen PRNG, um eine zufällige Permutation der Zeichen des Passwortes innerhalb des Fehlerkorrekturcodes zu erhalten
• noise: Ein Seed-Wert zum Erzeugen von Grundrauschen beim zu korrigierenden Passwort
• hashtype: Das verwendete Hash-Verfahren
• hash: Der gesalzene Hash des Passwortes
• fecbytes: Die Fehlerkorrektur-Information

Die Grundlagen

Um zu verstehen, wie die Kodierung funktioniert, ist ein Blick auf etwas Mathe nötig, die am Beispiel von QR-Codes gut veranschaulicht werden kann.

Galois-Felder

Bei Galois-Feldern handelt es sich um Zahlenräume endlicher Größe, in denen definiert ist, wie eine Addition und wie eine Multiplikation je zweier Elemente funktioniert. Dies ähnelt stark der Art und Weise bei den natürlichen oder ganzen Zahlen, mit dem Unterschied, dass Elemente außerhalb des Zahlenraums durch Restbildung wieder in diesen abgebildet werden. Im GF(2^4), der die Elemente von 0 bis 15 enthält, wird also bei Addition von 7 + 11 = 18 ≡ 2. Eine Multiplikation im gleichen Zahlenraum von 7 * 11 = 77 ≡ 13.

Eine einfache Umsetzung in PHP sieht dabei wie folgt aus:

class GF {
    public $value;
    public $len;
    public $high;
    public $mask;

    public $g_exp;
    public $g_log;

    function __construct($value, $length) {
        $this->len = $length;
        $this->high = 1 << $this->len;
        $this->mask = $this->high - 1;
        $this->value = $value & $this->mask | $this->high;

        $this->generate();
    }

    function generate() {
        $this->g_exp = array_fill(0, $this->mask, 1);
        $this->g_log = array_fill(0, $this->high, 0);

        $x = 1;
        for($i = 1; $i < $this->high; $i++) {
            $x += $x;

            if($x & $this->high) {
                $x ^= $this->value;
            }

            $this->g_exp[$i] = $x;
            $this->g_log[$x] = $i;
        }
    }

};

function gf_add(GF $gf, $a, $b) {
    return ($a ^ $b) & $gf->mask;
}

function gf_mul_explicit(GF $gf, $a, $b) {
    $a &= $gf->mask;
    $a += $a;

    $b &= $gf->mask;

    $result = 0;

    for($i = 0; $i < $gf->len; $i++) {
        $result += $result;

        if($result & $gf->high) {
            $result ^= $gf->value;
        }

        if(($a << $i) & $gf->high) {
            $result ^= $b;
        }
    }

    return $result;
}

function gf_mul(GF $gf, $a, $b) {
    $a &= $gf->mask;
    $b &= $gf->mask;

    $la = $gf->g_log[$a];
    $lb = $gf->g_log[$b];

    return ($a && $b) ? $gf->g_exp[($la + $lb) % $gf->mask] : 0;
}

function gf_div(GF $gf, $a, $b) {
    $a &= $gf->mask;
    $b &= $gf->mask;

    if(!$b) {
        throw new Exception('Division by Zero');
    }

    if(!$a) {
        return 0;
    }

    return $gf->g_exp[($gf->g_log[$a] + $gf->mask - $gf->g_log[$b]) % $gf->mask];
}

define('GF_DEFAULT_POLY', 0x1d);
define('GF_DEFAULT_LEN', 8);
$GF_DEFAULT = new GF(GF_DEFAULT_POLY, GF_DEFAULT_LEN);

Polynome mit Koeffizienten aus Galois-Feldern

Ähnlich wie man mit den gewohnten Zahlenbereichen auch Funktionen und Polynome bauen kann, geht dies auch bei einem Galois-Feld: Dabei bildet man ein Polynom und verwendet als Faktoren vor der Unbekannten jeweils ein Element aus dem Galois-Feld. Die unbekannte ist häufig auch ein Element aus dem Galois-Feld, kann aber theoretisch auch aus jedem anderen Zahlenbereich stammen, wenn eine sinnvolle Verknüpfung definiert ist. Aber dies ist für uns erst einmal zweitrangig, da wir ohne diese Verallgemeinerung auskommen.

Nehmen wir also wieder das obige Feld, so kann man wiederum je eine Addition und eine Multiplikation definieren: Aus 3x^2 + 7x + 1 und 0x^2 + 8x + 15 wird durch Addition 3x^2 + 15x + 0 und durch Multiplikation (3*0)x^4 + (3*8)x^3 + (3*15)x^2 + (7*0)x^3 + (7*8)x^2 + (7*15)x + (1*0)x^2 + (1*8)x + (1*15) oder vereinfacht: 31x^3 + 101x^2 + 113x + 15 ≡ 15x^3 + 5x^2 + 1x + 15.

Auch dieser Teil ist mit wenigen Zeilen in PHP umsetzbar:

require_once "gf.php";

function gfpoly_scale(GF $gf, array $a, $scale) {
    return array_map(
        function ($v) use ($gf, $scale) {
            return gf_mul($gf, $v, $scale);
        }, $a);
}

function gfpoly_add(GF $gf, array $a, array $b) {
    $result = array_fill(0, max(count($a), count($b)), 0);

    $cb = function ($v, $k) use ($gf, &$result) {
        $result[$k] = gf_add($gf, $result[$k], $v);
    };

    array_walk($a, $cb);
    array_walk($b, $cb);

    return $result;
}

function gfpoly_mul(GF $gf, array $a, array $b) {
    $result = array_fill(0, count($a) + count($b) - 1, 0);

    foreach($a as $ak => $av) {
        foreach($b as $bk => $bv) {
            $k = $ak + $bk;
            $result[$k] = gf_add($gf, $result[$k], gf_mul($gf, $av, $bv));
        }
    }

    return $result;
}

function gfpoly_eval(GF $gf, array $p, $x) {
    $x &= $gf->mask;

    $result = 0;

    for($i = count($p); $i > 0; $i--) {
        $result = gf_add($gf, $p[$i-1], gf_mul($gf, $result, $x));
    }

    return $result;
}

Reed-Solomon-Codes

Reed-Solomon-Codes bilden eine Unterklasse von sogenannten separierbaren BCH-Blockcodes und dienen der Fehlerkorrektur bei der Datenübertragung. Im Falle von RS-Codes wird die Fehlerkorektur-Information unabhängig von den zu übertragenden Daten übermittelt, d.h. in einem Codewort ist ersichtlich, welche Elemente die ursprüngliche Nachricht bilden und welche der Fehlerkorrektur dienen. Diese Eigenschaft lässt sich für unseren Anwendungsfall sehr gut nutzen, nur dass die Nutzinformation nie übertragen wird und daher zur Prüfung geliefert werden muss.

Die Kodierung dieser Information basiert nun darauf, dass man jedes Polynom n-ten Grades durch n+1 Stützstellen eindeutig bestimmen kann. Kennt man mehr als n+1 Stützstellen, so ist das Polynom überbestimmt und man kann bei Abweichungen an einer Stelle das ursprüngliche Polynom bestimmen und somit auch den ursprünglichen Wert an der Fehlerstelle wiederherstellen.

Die eigentlichen Algorithmen sind auf der oben verlinkten Seite genauer erklärt, eine passende Implementierung in PHP lässt sich wie folgt realisieren:

require_once 'gf.php';
require_once 'gfpoly.php';

function rs_poly_gen(GF $gf, $sym) {
    $p = array(1);

    for($i = 0; $i < $sym; $i++) {
        $p = gfpoly_mul($gf, $p, array($gf->g_exp[$i], 1));
    }

    return $p;
}

function rs_encode_data(GF $gf, array $poly, array $value) {
    $cpoly = count($poly);
    $cvalue = count($value);

    $result = array_fill(0, $cpoly + $cvalue - 2, 0);

    for($i = 0; $i < $cvalue; $i++) {
        $result[$cpoly+$i-1] = $value[$i];
    }

    for($i = $cvalue; $i > 0; $i--) {
        $icoeff = $cpoly + $i - 2;
        $coeff = $result[$icoeff];

        if(!$coeff) {
            continue;
        }

        for($j = 0; $j < $cpoly; $j++) {
            $icoeff2 = $i + $j - 1;
            $result[$icoeff2] = gf_add($gf, $result[$icoeff2], gf_mul($gf, $poly[$j], $coeff));
        }
    }

    for($i = 0; $i < $cvalue; $i++) {
        $result[$cpoly + $i - 1] = $value[$i];
    }

    return $result;
}

function rs_encode_syndrome(GF $gf, array $poly, array $value) {
    return array_slice(rs_encode_data($gf, $poly, $value), 0, count($poly) - 1);
}

function rs_calc_syndrome(GF $gf, array $poly, array $msg) {
    $result = array();

    for($i = 0; $i < count($poly) - 1; $i++) {
        $result[$i] = gfpoly_eval($gf, $msg, $gf->g_exp[$i]);
    }

    return $result;
}

function rs_calc_errlocpoly(GF $gf, array $pos) {
    $result = array(1);

    foreach($pos as $p) {
        $x = $gf->g_exp[$p % $gf->mask];
        $result = gfpoly_mul($gf, $result, array(1, $x));
    }

    return $result;
}

function rs_correct_errata(GF $gf, array $msg, array $syndrome, array $pos) {
    //Error Locator Polynomial
    $errpoly = rs_calc_errlocpoly($gf, $pos);

    $p = array_slice($syndrome, 0, count($pos));
    $p = gfpoly_mul($gf, $p, $errpoly);
    $p = array_slice($p, 0, count($pos));

    for($i = 1, $qq = array(); $i < count($errpoly); $i += 2) {
        $qq[] = $errpoly[$i];
    }
    $errpoly = $qq;

    foreach($pos as $i) {
        $x = $gf->g_exp[($gf->mask - $i) % $gf->mask];
        $y = gfpoly_eval($gf, $p, $x);
        $z = gfpoly_eval($gf, $errpoly, gf_mul($gf, $x, $x));

        $msg[$i] = gf_add($gf, $msg[$i], gf_div($gf, $y, gf_mul($gf, $x, $z)));
    }

    return $msg;
}

function rs_find_errors(GF $gf, array $msg, array $syndrome) {
    $oldpoly = array(1);
    $errpoly = array(1);

    for($i = 0; $i < count($syndrome); $i++) {
        $oldpoly = gfpoly_mul($gf, $oldpoly, array(0,1));
        $delta = $syndrome[$i];

        for($j = 1; $j < count($errpoly); $j++) {
            $delta = gf_add($gf, $delta, gf_mul($gf, $errpoly[$j], $syndrome[$i - $j]));
        }

        if($delta) {
            if(count($errpoly) < count($oldpoly)) {
                $newpoly = gfpoly_scale($gf, $oldpoly, $delta);
                $oldpoly = gfpoly_scale($gf, $errpoly, gf_div($gf, 1, $delta));
                $errpoly = $newpoly;
            }

            $errpoly = gfpoly_add($gf, $errpoly, gfpoly_scale($gf, $oldpoly, $delta));
        }
    }

    $errors = count($errpoly) - 1;
    if( 2 * $errors > count($syndrome) ) {
        return false;
    }

    $errpos = array();
    for($i = 0; $i < count($msg); $i++) {
        $v = gfpoly_eval($gf, $errpoly, $gf->g_exp[$gf->mask - 1 - $i]);
        if(0 == gfpoly_eval($gf, $errpoly, $gf->g_exp[$gf->mask - 1 - $i])) {
            $errpos[] = count($msg) - $i - 2;
        }
    }

    if(count($errpos) != $errors) {
        return false;
    }

    return $errpos;
}

function rs_calc_forney_syndromes(GF $gf, array $syndrome, array $pos) {
    $result = $syndrome;

    foreach($pos as $i) {
        $x = $gf->g_exp[$i];

        for($j = 0; $j < count($result) - 1; $j++) {
            $result[$j] = gf_add($gf, gf_mul($gf, $result[$j], $x), $result[$j+1]);
        }

        array_pop($result);
    }

    return $result;
}

function rs_correct_message(GF $gf, array $poly, array $message) {
    $result = array_reverse($message);

    $erasepos = array();
    foreach($result as $i => $v) {
        if($v < 0) {
            $result[$i] = 0;
            $erasepos[] = $i;
        }
    }

    if(count($erasepos) > count($poly)) {
        return false;
    }

    $syndrome = rs_calc_syndrome($gf, $poly, $message);

    if(!count(array_filter($syndrome))) {
        return array_reverse($result);
    }

    $fsyndromes = rs_calc_forney_syndromes($gf, $syndrome, $erasepos);

    $errorpos = rs_find_errors($gf, $result, $fsyndromes);
    if(!is_array($errorpos)) {
        return false;
    }

    $errloc = array_merge($errorpos, $erasepos);
    $errloc = array_map(function ($l) use ($result) { return count($result) - 1 - $l; }, $errloc);
    $result = rs_correct_errata($gf, array_reverse($result), $syndrome, $errloc);

    $syndrome = rs_calc_syndrome($gf, $syndrome, $result);
    if(!count(array_filter($syndrome))) {
        return $result;
    }

    return false;
}

Die Implementierung

Um mit diesen Bausteinen nun die fertige Crypt-Funktion zu bauen, sind noch ein paar Kleinigkeiten vorzubereiten, aber wir sind bereits fast da!

Der reine Passwort-Hash

Um die Komplexität bei der Prüfung variieren zu können und auf Fortschritte bei der Rechentechnik reagieren zu können, ist es ratsam, einige Gegenmaßnahmen vorzusehen. In der hier verwendeten Implementierung sind dies zum einen wiederholtes Hashing als auch eine für jeden Durchgang zufällig berechnete Permutation der Eingabe basierend auf Fisher-Yates. Die hierfür benötigten „Zufallsdaten“ werden mit hilfe eines PRNG aus den im Hash enthaltenen Seed-Werten generiert.

Im ersten Durchgang erfolgt die Permutation auf Salt + Passwort, in jedem folgenden Durchgang wird zusätzlich der aus der vorherigen Runde erhaltene Hash in die Permutation einbezogen, wodurch diese auf Salt + Hash‘ + Salt angewendet wird.

Hierbei Iterations ist die Anzahl der Hash-Schritte, bei denen ein Hash Teil des Ausgangsmaterials ist. Iterations==0 entspricht somit einem permutiert gehashten Salted Password. Der Parameter im Hash gibt hierbei eine Verschiebung an: die tatsächliche Anzahl an durchläufen berechnet sich aus 64 * 2^Wert und ist somit bereits für normale Computer mit einem Wert um 8 ausreichend komplex.

Format des fehlerzukorrigierenden Blocks

Um den Fehlerkorrekturblock zu erhalten, muss das Password um ein Nullbyte am Ende erweitert werden. Danach wird ein PRNG auf noise geseedet und das Passwort auf ein Vielfaches der Größe eines Datenblocks mit Zufallsdaten aufgefüllt. Diese Information wird nun mit einem auf permutation geseedeten PRNG permutiert. In der ersten, unten gezeigten Implementierung ist dieser Schritt leicht vereinfacht, was am Grundprinzip der Korrektur jedoch nichts ändert, solange bei der Prüfung der äquivalente Datenblock erzeugt werden kann.

Zum Abschluss

Nimmt man die oben dargestellten Einzelteile, so ergibt sich für die Realisierung des Fuzzy-Password-Hashes folgende Beispielimplementierung:

include 'rs.php';

class PRNG {
    public $state = 4; //Choosen by fair dice roll, guaranteed to be random!
};

function fc_permutate($string, PRNG &$prng) {
    mt_srand($prng->state);
    $result = '';

    while(strlen($string)) {
        $r = mt_rand(0, strlen($string));
        $r %= strlen($string);
        $result .= $string[$r];
        $string = substr($string, 0, $r) . substr($string, $r + 1);
    }

    return strrev($result);
}

function fc_dohash($password, $salt, $iterations, $permutation, $hashspec = "sha1") {
    $prng = new PRNG($permutation);

    $iterations = 64 << $iterations;

    $result = $salt . $password;
    $result = fc_permutate($result, $prng);
    $result = $hashspec($result, true);

    do {
        $result = $salt . $result . $password . $salt;
        $result = fc_permutate($result, $prng);
        $result = $hashspec($result, true);
    } while(--$iterations);

    return $result;
}

function fc_gensalt($len) {
    $result = '';
    while(strlen($result) < $len) {
        $result .= chr(mt_rand(0, 256));
    }
    return $result;
}

function fc_fecdata_encode(GF $gf, array $data) {
    $byte_per_item = floor(($gf->len + 7) / 8);

    $result = '';

    foreach($data as $x) {
        for($i = 0; $i < $byte_per_item; $i++) {
            $result .= chr($x & 0xFF);
            $x = $x >> 8;
        }
    }

    return $result;
}

function fc_fecdata_decode(GF $gf, $data) {
    $byte_per_item = floor(($gf->len + 7) / 8);

    $result = array_fill(0, floor((strlen($data) + $byte_per_item - 1) / $byte_per_item), 0);

    for($i = 0; $i < strlen($data); $i++) {
        $result[floor($i/$byte_per_item)] += ord($data[$i]) << (($i % $byte_per_item) << 3);
    }

    return $result;
}

function fc_check_rs(GF $gf, array $gfpoly, $password, $salt, $noise, array $fecdata) {
    $prng = new PRNG($noise);
    mt_srand($prng->state);

    $msg = array_slice(array_map("ord", preg_split('//', $password)), 1, -1);

    $msg_data = array();
    for($i = 0; $i < $gf->mask; $i++) {
        $msg_data[$i] = mt_rand(0, $gf->high);
    }

    $msg_data = array_reverse($msg_data);

    for($i = 0; $i < count($gfpoly)-1; $i++) {
        $msg_data[$i] = $fecdata[$i];
    }
    for($i = 0; $i < strlen($password); $i++) {
        $msg_data[$i+count($gfpoly)-1] = ord($password[$i]);
    }

    $msg = rs_correct_message($gf, $gfpoly, $msg_data);

    if(!is_array($msg)) {
        return $password;
    }

    $pw_len = strlen($password);
    $password = '';
    for($i = 0; $i < $pw_len; $i++) {
        $password .= chr($msg[$i+count($gfpoly)-1]);
    }

    return $password;
}

function fc_calc_rs(GF $gf, array $gfpoly, $password, $salt, $noise) {
    $prng = new PRNG($noise);
    mt_srand($prng->state);

    $msg = array_slice(array_map("ord", preg_split('//', $password)), 1, -1);

    $msg_data = array();
    for($i = 0; $i < $gf->mask; $i++) {
        $msg_data[$i] = mt_rand(0, $gf->high);
    }

    $msg_data = array_reverse($msg_data);

    for($i = 0; $i < count($gfpoly) - 1; $i++) {
        $msg_data[$i] = 0;
    }
    for($i = 0; $i < strlen($password); $i++) {
        $msg_data[$i+count($gfpoly)-1] = $msg[$i];
    }

    $msg_data = array_slice($msg_data, count($gfpoly) - 1);

    $msg = rs_encode_syndrome($gf, $gfpoly, $msg_data);

    return $msg;
}

function fuzzycrypt($password, $hash = "") {
    global $GF_DEFAULT;
    global $GF_POLY_DEFAULT;

    //$hash = $fuzzy$salt$iterations$gf$gfbits$gfpoly$gfdegree$permutation$noise$hashtype$hash$fecdata

    $salt = fc_gensalt(12);
    $iterations = 8;

    $gf = GF_DEFAULT_LEN;
    $gf_poly = GF_DEFAULT_POLY;
    $gf_degree = 5;

    $permutate = mt_rand(0, 1 <<24);
    $noise = mt_rand(0, 1 <<24);

    $hashtype = "sha1";

    $verify_fail = false;

    $fecdata = '';

    if('$fuzzy$' == substr($hash, 0, 7)) {
        //Read arguments from $hash parameter

        $params = explode('$', $hash);
        if(13 != count($params)) {
            $verify_fail = true;
        }

        list($ignore_empty, $ignore_fuzzy, $salt, $iterations,
            $ignore_gf, $gf_bits, $gf_poly, $gf_degree,
            $permutate, $noise, $hashtype, $hash, $fecdata) = $params;

        if(!$verify_fail && '' != $ignore_empty) {
            $verify_fail = true;
        }

        if(!$verify_fail && 'fuzzy' != $ignore_fuzzy) {
            $verify_fail = true;
        }

        if(!$verify_fail && 'gf' != $ignore_gf)     {
            $verify_fail = true;
        }

        if(!$verify_fail && 'sha1' != $hashtype) {
            $verify_fail = true;
        }

        if(!$verify_fail && 8 != $gf_bits) {
            $verify_fail = true;
        }

        if(!$verify_fail && '' == $gf_poly) {
            $verify_fail = true;
        }

        if(!$verify_fail && 2 > $gf_degree) {
            $verify_fail = true;
        }

        $gf = $gf_bits;
        $gf_poly = hexdec($gf_poly);

        $permutate = hexdec($permutate);
        $noise = hexdec($noise);

        $salt = base64_decode($salt);
        $fecdata = base64_decode($fecdata);

    } else {
        if("" != $hash) {
            return crypt($password, $hash);
        }

        //Generate some default parameters for the hash
        $verify_fail = true;
    }

    if($verify_fail) {
        $salt = fc_gensalt(12);
        $iterations = 8;

        $gf = GF_DEFAULT_LEN;
        $gf_poly = GF_DEFAULT_POLY;
        $gf_degree = 5;

        $permutate = mt_rand(0, 1 <<24);
        $noise = mt_rand(0, 1 <<24);

        $hashtype = "sha1";

        $fecdata = 'Fubar';
    }

    $o_gf = new GF($gf_poly, $gf);
    $o_gf_poly = rs_poly_gen($o_gf, $gf_degree);

    $fecdata = fc_fecdata_decode($o_gf, $fecdata);

    if(!$verify_fail) {
        $password = fc_check_rs($o_gf, $o_gf_poly, $password, $salt, $noise, $fecdata);
    }

    $fecdata = fc_calc_rs($o_gf, $o_gf_poly, $password, $salt, $noise);

    $h = fc_dohash($password, $salt, $iterations, $permutate);
    $h = trim(base64_encode($h), '=');

    $s = fc_fecdata_encode($o_gf, $fecdata);
    $s = trim(base64_encode($s), '=');

    //$hash = $fuzzy$salt$iterations$gf$gfbits$gfpoly$gfdegree$permutation$noise$hashtype$hash$fecdata
    $result = sprintf('$fuzzy$%s$%d$%s$%d$%x$%d$%x$%x$%s$%s$%s',
        trim(base64_encode($salt),'='),                 //%s:   salt
        $iterations,                                    //%d:   iterations
        'gf',                                           //%s:   ecc type 'gf'
        $o_gf->len,                                     //%d:   gf bit length
        $o_gf->value,                                   //%x:   gf polynomial
        $gf_degree,                                     //%d:   degree of ecc polynomial
        $permutate,                                     //%x:   permutation IV
        $noise,                                         //%x:   noise IV
        'sha1',                                         //%s:   type of used hash function
        $h,                                             //%s:   strict hash value
        $s                                              //%s:   fuzzy correction information
        );

    return $result;
}

Zum Erzeugen nutzt man nun

$a = fuzzycrypt("Hello World!");

während die Prüfung mittels

$b = fuzzycrypt("Hello World!", $a);

erfolgt. Sind beide identisch, war das vom Nutzer eingegebene Passwort hinreichend ähnlich:

Hello World!	$fuzzy$dcmGLl5RmD1ZYGai$8$gf$8$11d$5$612f1d$c78f42$sha1$UwLJxeScqVDyNvdejjoOiMGNmwo$rMGsJ4Q

Hello World!	$fuzzy$dcmGLl5RmD1ZYGai$8$gf$8$11d$5$612f1d$c78f42$sha1$UwLJxeScqVDyNvdejjoOiMGNmwo$rMGsJ4Q
Hallo World!	$fuzzy$dcmGLl5RmD1ZYGai$8$gf$8$11d$5$612f1d$c78f42$sha1$UwLJxeScqVDyNvdejjoOiMGNmwo$rMGsJ4Q
Hell0 W0rld!	$fuzzy$dcmGLl5RmD1ZYGai$8$gf$8$11d$5$612f1d$c78f42$sha1$UwLJxeScqVDyNvdejjoOiMGNmwo$rMGsJ4Q
Hallo Wellt!	$fuzzy$dcmGLl5RmD1ZYGai$8$gf$8$11d$5$612f1d$c78f42$sha1$5PPJP4YR0lMdsUPCTmBxZXRvTZk$zDxMUY8

Auf weniger fehlgeschlagene Logins!

* Die erwähnten Kanji gibt es 😉
** Da für die Kodierung bekannt ist, wo das Passwort im Code steht ist keine Fehlerkorrektur an zu suchenden Stellen, sondern lediglich eine Störungskorrektur an bekannten Stellen durchzuführen, für die pro Fehlerstelle nur ein Korrekturwert benötigt wird.