Hashverfahren und Sicherheit

Es gehört mittlerweile zum guten Ton, auf md5 herumzuhacken. Dabei fällt immer wieder das Argument, dass in md5 Kollisionen entdeckt wurden. Eine Kollision bedeutet, dass zwei unterschiedliche Strings zum gleichen Hash führen. Dies muss zwangsläufig bei allen Hashverfahren der Fall sein, denn eine Abbildung von viel Text auf wenig Text wird naturgemäß irgendwann eine Überschneidung bei zwei verschiedenen Inputs ergeben. Ein gutes Hashverfahren kommt also mit weniger Kollisionen daher als ein schlechtes.

Zum selbst testen (Unterschiede im Input sind mit einem Ausrufezeichen vermerkt):

$a = md5("\xA6\x64\xEA\xB8\x89\x04\xC2\xAC\x48\x43\x41\x0E\x0A\x63\x42\x54\x16\x60\x6C\x81\x44\x2D\xD6\x8D\x40\x04\x58\x3E\xB8\xFB\x7F\x89\x55\xAD\x34\x06\x09\xF4\xB3\x02\x83\xE4\x88\x83\x25\x71\x41\x5A\x08\x51\x25\xE8\xF7\xCD\xC9\x9F\xD9\x1D\xBD\xF2\x80\x37\x3C\x5B\x97\x9E\xBD\xB4\x0E\x2A\x6E\x17\xA6\x23\x57\x24\xD1\xDF\x41\xB4\x46\x73\xF9\x96\xF1\x62\x4A\xDD\x10\x29\x31\x67\xD0\x09\xB1\x8F\x75\xA7\x7F\x79\x30\xD9\x5C\xEB\x02\xE8\xAD\xBA\x7A\xC8\x55\x5C\xED\x74\xCA\xDD\x5F\xC9\x93\x6D\xB1\x9B\x4A\xD8\x35\xCC\x67\xE3");
$b = md5("\xA6\x64\xEA\xB8\x89\x04\xC2\xAC\x48\x43\x41\x0E\x0A\x63\x42\x54\x16\x60\x6C\x01\x44\x2D\xD6\x8D\x40\x04\x58\x3E\xB8\xFB\x7F\x89\x55\xAD\x34\x06\x09\xF4\xB3\x02\x83\xE4\x88\x83\x25\xF1\x41\x5A\x08\x51\x25\xE8\xF7\xCD\xC9\x9F\xD9\x1D\xBD\x72\x80\x37\x3C\x5B\x97\x9E\xBD\xB4\x0E\x2A\x6E\x17\xA6\x23\x57\x24\xD1\xDF\x41\xB4\x46\x73\xF9\x16\xF1\x62\x4A\xDD\x10\x29\x31\x67\xD0\x09\xB1\x8F\x75\xA7\x7F\x79\x30\xD9\x5C\xEB\x02\xE8\xAD\xBA\x7A\x48\x55\x5C\xED\x74\xCA\xDD\x5F\xC9\x93\x6D\xB1\x9B\x4A\x58\x35\xCC\x67\xE3");
//--------------------------------------------------------------------------------------!-------------------------------------------------------------------------------------------------------!-------------------------------------------------------!-----------------------------------------------------------------------------------------------!-------------------------------------------------------------------------------------------------------!-------------------------------------------------------!------------------

var_dump($a); //string(32) "2ba3be5aa541006b62370111282d19f5"
var_dump($b); //string(32) "2ba3be5aa541006b62370111282d19f5"
var_dump($a === $b); //bool(true)

Darüberhinaus existieren mittlerweile sogar Generatoren, die zwei völlig verschiedenen exe-Dateien den gleichen md5-Hash verschaffen. Auch Zertifikate lassen sich fälschen. So lässt sich jemandem ein selbst erstelltes Zertifikat unterjubeln oder ein Virus anstelle der eigentlich erwarteten Datei schicken, ohne dass dies durch einen md5-Check auffallen würde.

Okay, das sieht jetzt erstmal gemein aus – aber in wie weit stellt das für Webanwendungen ein Sicherheitsrisiko dar? Dazu fragen wir uns erstmal, was denn das typische Horrorszenario ist. Einem Angreifer fällt unsere komplette Datenbank in die Hände, in der alle (hoffentlich) gehashten Passwörter enthalten sind. Der Angreifer versucht nun, Strings zu erzeugen, die mit dem Hash übereinstimmen. Das kann das wirkliche Passwort sein, oder irgendein anderes, was zum gleichen Hash-Ergebnis führt (= Kollision). Bei einem Hashverfahren, bei dem es viele Kollisionen gibt, hat der Angreifer also weniger Arbeit beim Brute-Forcen des Passworts. Aber oft ist Bruteforce garnicht nötig…

Das Märchen mit den Rainbowtables

Wer reine Hashes der Form md5($password) / sha1($password) / … in der Datenbank ablegt, kann es eigentlich auch gleich sein lassen und die Passwörter im Plaintext speichern. Gut, die Aussage ist jetzt leicht provokant, aber in Zeiten von online reverse lookups und 600GB großen Rainbowtables für alle bekannten Hashverfahren bewegt man sich auf dünnem Eis.

… und alle schreien nach dem salt

define("MY_SALT", "abc123");
$password = md5(MY_SALT . $_POST['password']);

Wer das für toll hält, hält sicher auch register_globals für eine praktische Sache. Das offensichtliche Problem mit solch einem globalen salt ist, dass es mittlerweile auch vorberechnete Rainbowtables für typische salts gibt. Und selbst wenn nicht, berechnen wir in Zeiten von Amazon EC2 mit GPU Rechenunterstützung mal eben 7 Billionen Passwörter pro Sekunde – vorausgesetzt natürlich, dass der Angreifer unser salt kennt. Besser ist es da schon, für jeden User ein eigenes salt zu verwenden:

$salt = uniqid(mt_rand(), true);
$password = md5($salt . "x" . $userid . "y" . $userpassword);

Die userid und die zwei Buchstaben packen wir noch dazu, da ein simples konkatenieren von Passwort und salt im Stile $password = md5($salt . $userpassword); sehr voraussehbar ist. Wenn nun also dem Angreifer „bloß“ unsere Datenbank (als ob das nicht schon schlimm genug wäre…), nicht aber der Programmcode in die Hände fällt, wird er voraussichtlich dran scheitern die genaue Zusammensetzung zu rekonstruieren. Jetzt speichern wir $salt und $password für jeden User in der Datenbank und sind schonmal einen Schritt weiter.

Da geht noch mehr!

Das Problem mit md5 (und dem kollisionsfreieren sha1) ist, dass sie unglaublich schnell zu berechnen sind. Wenn wir also erreichen könnten, dass ein Angreifer pro Sekunde nicht 7 Billionen, sondern nur 3 Hashes erstellen kann, wären wir einen weiteren großen Schritt gekommen. Dazu können wir uns einen simplen Loop basteln:

define("ITERATIONS", 400000);
$salt = uniqid(mt_rand(), true);
$password = md5($salt . "x" . $userid . "y" . $userpassword);

for ($i = 0; $i < ITERATIONS; $i++)
{
	$password = md5($password);
}

Wenn dem Angreifer nun also zusätzlich zur Datenbank auch noch unser Quellcode in die Hände fällt, hat er trotzdem nicht viel gewonnen. Schließlich muss er für jedes Passwort eine eigene Rainbow-Tabelle anhand des einzigartigen salts erstellen und leidet zusätzlich noch fürchterlich durch die langsame Berechnungsdauer aufgrund der vielen Iterationen. Wenn man noch einen draufsetzen will, könnte man eine leicht variierende Iterationsanzahl verwenden und diese analog zum salt zusätzlich in der Datenbank mit speichern, etwa so:

$iterations = rand(300000, 500000);

Achja, in diesem Zusammenhang erwähnt sei auch „Is “double hashing” a password less secure than just hashing it once?„.

Letzte Worte

Abschließend möchte ich noch den tollen Artikel An Illustrated Guide to Cryptographic Hashes empfehlen und auf die PHP-Funktion crypt hinweisen (siehe auch den Wikipedia-Artikel zur darunterliegenden Unix-Crypt-Funktion). Hierbei wird das salten und iterieren direkt von der Funktion übernommen. Da allerdings als Hashverfahren bisher nur DES, Blowfish und MD5 unterstützt werden und ich das Handling der Funktion als sehr mühselig empfinde, spreche ich hier keine Empfehlung aus.

Um das oben angesprochene md5-Bashing nochmal aufzugreifen: Ich glaube, dass die Wahl des Hashverfahrens verglichen mit den sonstigen „Worst Practices“ wie das Versenden von Passwörtern per Email oder die Speicherung im Cookie eine eher untergeordnete Rolle einnnimmt. Nichtsdestotrotz: Da es das bessere sha1 gibt, kann man es natürlich verwenden. Achja, der übliche Disclaimer bei solchen Themen: Ich bin kein Kryptographie-Experte, sonden käue nur Meinungen bzw. Erfahrungen von mir und anderen wieder ;).

Wie geht ihr mit dem Thema um?

Weitere Posts:

Dieser Beitrag wurde unter php, Security, webdev veröffentlicht. Setze ein Lesezeichen auf den Permalink.

18 Antworten auf Hashverfahren und Sicherheit

  1. Camma sagt:

    Zum Verständnis die Frage:

    Damit ich ein Passwort validieren kann, muss ich den Salt kennen? Wie funktioniert die Validierung eines solchen Passworts?

    • david sagt:

      Hi! Du musst den salt kennen, ja.

      Angenommen du hast in deiner Usertabelle das gesaltete Passwort und den salt gespeichert, würdest einfach analog zur Erstellung des Passworts so validieren:


      $salt = getSaltFromDatabase($userid);

      $password = md5($salt . "x" . $userid . "y" . $_POST['password']);

      for ($i = 0; $i < PW_ITERATIONS; $i++) { $password = md5($password); } if ($password === getPassFromDatabase($userid)) { //pass }

      Hoffe, man kanns verstehen ;)

  2. digilist sagt:

    Statt sha1 kann man auch sha256 oder sha512 verwenden, um eine noch höhere Kollisionsfreiheit zu erhalten ;-)

    • david sagt:

      jup, du hast recht. Ich hab bewusst als Provokation bis zum bitteren Ende md5 verwendet ;).

      Wer zu faul zum googlen ist:


      print_r(hash_algos());
      hash("sha512", $pw);
      <7code>

  3. Camma sagt:

    So in der Art habe ich es mir gedacht, war jedoch vorallem Sicherheitsmässig unsicher:

    Beim einem Diebstahl der SQL Datenbank hat der Dieb somit Salt wie auch die gespeicherten Iterations neben dem Passwort. Erleichtert dies nicht die Abfrage per Rainbow-Table? Oder wirkt sich das durchlaufen der for Schlaufe mit 400000 Durchgängen bremsend aus?

    • david sagt:

      Der Punkt dabei ist, dass der Angreifer für JEDES Passwort (da ja unterschiedlicher salt) eine komplette Bruteforce-Attacke fahren muss. In Kombination mit den Iterationen und wenn man davon ausgeht, dass dem Angreifer NICHT auch der Quellcode in die Hände fällt, machst du ein Knacken schon verdammt schwer.

      Klar, man kann immernoch mit Dictionary-Attacks rangehen und die am häufigsten verwendeten Passwörter durchrattern, ein paar gehen einem immer ins Netz.

  4. Du kannst aber auch verfahren kombinieren, das fehlt mir leider in deinem Artikel.
    Beispielgenerierung eines Benutzerpasswortes:

    Irgendwo ist eine Konstante definiert
    define(‚SYSTEMSALT,’jh32h37djb73dbf8b2′);

    Zusätzlich benutzt du irgendeinen Wert aus der Zeile des Users, das kann ein eigenes Feld ’salt‘ sein oder z.B. der Md5-Hash der Mail oder sogar eine Kombi davon. Ich mache es einfach und benutze ein eigenes Feld ’salt‘, lege dort beim anlegen die aktuelle Zeit der anmeldung rein und generiere das Passwort als SHA1 mit pre- und postSalt (das ganzeist stark vereinfacht, bitte nicht über die querys herziehen, danke). In $userpass steht das vom User benutzte passwort.
    $time = time();
    $pass = mysql_query(‚INSERT INTO user (email, pass, salt) VALUES (‚max@example.com‘, SHA1(CONCAT(‚.SYSTEMSALT.‘,‘.$userpass.‘,‘.$time.‘)),‘.$time.‘ )‘;

    Prüfen geht via:
    $check = mysql_query(‚SELECT ID FROM user WHERE pass = SHA1(CONCAT(‚.SYSTEMSALT.‘,‘.$userpass.‘,salt)) AND email = ‚.$emaileingabe.“);

    Ich denke, ein verfahren, was diese Technik anwendet (und evtl. noch um einige Sachen ergänzt, wie z.B. IP Prüfung [ein dienst für de nutzer muss keine chinesichen oder russichen IP zulassen], oder die mischung verschiedener Hashes [der salt könnte z.B. md5 sein]), der lebt schon sicherer als ohne diese Sachen.

    • david sagt:

      Servus, danke für deinen Kommentar.

      Du hast natürlich recht, ich wollte meinen Post auch nicht als heiligen Gral verstanden wissen, sondern eher als Diskussionsgrundlage – was ja anscheinend geglückt ist ;).

      Je mehr Verfahren du kombinierst, desto schwieriger machst du es einem Angreifer – logisch (selbes Konzept wie bei multi factor authorization). Bei deinem Vorgehen sehe ich allerdings keine Iterationen, was es trotz aller noch zusätzlich verwendeten Felder verwundbar für Bruteforce macht.

  5. Interessanter Artikel. Vor allem die Technik mit dem Loop war mir noch nicht bewusst und wird wahrscheinlich für zukünftige Entscheidungen in Erwägung gezogen.

    Andererseits verstehe ich das Festhalten an md5 nicht. Bashing hin oder her (hab davon noch nicht allzu viel mitbekommen), sehe ich nicht die Vorteile in einer weiteren Verwendung von md5 gegenüber der sha-Familie. Performance? Kann ja bzgl. Passwörter nicht das Argument sein oder?

    Bitte um Aufklärung. Danke.

    • david sagt:

      Hi – md5 hab ich nur verwendet, um euch zu ärgern ;). Siehe auch mein Fazit

      Um das oben angesprochene md5-Bashing nochmal aufzugreifen: Ich glaube, dass die Wahl des Hashverfahrens verglichen mit den sonstigen “Worst Practices” wie das Versenden von Passwörtern per Email oder die Speicherung im Cookie eine eher untergeordnete Rolle einnnimmt. Nichtsdestotrotz: Da es das bessere sha1 gibt, kann man es natürlich verwenden.

      Wenn du vernünftig mit salt und Iterationen arbeitest, ist dir die „Kollionsfreiheit“ recht egal. Aber logisch, wenn ich aktuell etwas auth-mäßiges zu bauen hätte, würde ich auf SHA512 setzen. Interessant an dem Thema find ich auch, dass man in dem Bereich mit einer „Eigenbaulösung“ den built-in-Maßnahmen vieler Frameworks überlegen sein dürfte – was ja sehr selten der Fall ist.

  6. Fabian sagt:

    Wenn du vernünftig mit salt und Iterationen arbeitest, ist dir die “Kollionsfreiheit” recht egal

    Hmm, das sollte allerding auch dynamische Salts in den Iterationen einschließen. Ich habe gerade keine Quelle aber da man die Informationen beim Hashen reduziert müsste 400 000 mal deutlich kollisionsanfälliger sein als einmal oder nicht?

    Damit würde dann jeder Brute Force Versuch länger dauern aber weniger Versuche benötigt werden. Mag sein dass das nicht ins Gewicht fällt aber bei pauschalem „mehr hashen = mehr Sicherheit“ bin ich vorsichtig.

    • david sagt:

      Servus!

      In Anbetracht der Tatsache, dass bisher noch keine SHA1-Kollision gefunden wurde, überwiegt für mich der Vorteil der Sicherheit gegen Bruteforce.

      Yes, re-hashing reduces the search space, but no, it doesn’t matter – the effective reduction is insignificant.

      In dem fies wisschenschaftlichen Plädoyer „Password-Based Cryptography Standard“ heißt es auch

      An iteration count has traditionally served the purpose of increasing the cost of producing keys from a password, thereby also increasing the difficulty of attack. For the methods in this document, a minimum of 1000 iterations is recommended. This will increase the cost of exhaustive search for passwords significantly, without a noticeable impact in the cost of deriving individual keys.

      Gott, ich liebe den blockquote seit er so gut aussieht ;)

  7. Michael Rüfenacht sagt:

    Und wenn der ftp gehackt ist hilft alles hashen und salten (tönt nach Jamie Oliver) nichts mehr…

    • david sagt:

      Klar hilft das noch was. Und zwar den Usern des Services.

      Oder wölltest du, dass dein Passwort – welches du selbstverständlich auch für Onlinebanking, Email und Ebay verwendest – der serbokroatischen Mafia in die Hände fällt ;)?

  8. Oliver sagt:

    Ich halte es relativ schlicht und schmerzfrei.
    sha256($user.SALT.$pass);

    $user ist die email, SALT ist im Quelltext hinterlegt und $pass ist das Passwort.

  9. Mittlerweile gibt es die Methoden \password_hash und \password_verify.

  10. Pingback: PHP Hashes und ihre Probleme | David Müller: Webarchitektur

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.