bcrypt

bcrypt ist eine kryptologische Hashfunktion, die speziell für das Hashen und Speichern von Passwörtern entwickelt wurde. Die auf dem Blowfish-Algorithmus basierende Funktion wurde von Niels Provos und David Mazières konzipiert und auf der USENIX-Konferenz im Jahre 1999 der Öffentlichkeit präsentiert.

Hintergrund

Um Benutzer einer Anwendung oder Website zu authentifizieren, wird in der Regel eine Kombination von Benutzername oder E-Mail-Adresse und einem Passwort eingesetzt. Die Website muss das Passwort hierzu speichern, allerdings ist das Speichern des Passworts in unverschlüsselter Form ein beachtliches Sicherheitsrisiko. Falls Passwort und Benutzername einem Dritten bekannt werden (etwa, falls die Website gehackt wird), kann dieser sich gegenüber der Website authentifizieren. Da viele Anwender für viele Dienste die gleiche Kombination von Benutzername und Passwort verwenden, kann dies auch weitere Dienste betreffen.

Dieses Problem wird in der Regel mittels kryptographischer Hashfunktionen umgangen. Dabei wird mit einer solchen Funktion ein Hashwert des Passwortes ermittelt und gespeichert. Solche Funktionen zeichnet aus, dass das Original-Passwort nicht wiederhergestellt werden kann. Um den Benutzer zu authentifizieren, wird die Eingabe des Benutzers mit der gleichen Funktion gehasht und die beiden Hashwerte verglichen – wenn die Original-Passwörter gleich sind, sind auch die Hashwerte gleich.

Die Hashfunktionen MD5 und die Secure Hash Algorithm (SHA1 usw.) sind mit dem Ziel entwickelt worden, die Daten möglichst effizient zu hashen, da sie etwa auch zur Verifizierung von großen Dateien verwendet werden. Diese Effizienz erleichtert es aber auf der anderen Seite, die Passwörter mittels Brute-Force-Attacken zu erraten oder sog. Rainbow-Tables zu erstellen, weswegen diese nicht mehr zum Hashen von Passwörtern verwendet werden sollten.

Design

Passwort-Hashing-Verfahren wie PBKDF2, scrypt und auch bcrypt wurden im Gegensatz zu regulären Hashing-Verfahren mit dem Ziel entwickelt, das Hashing möglichst aufwändig zu gestalten. Für normale Anwendungszwecke fällt dieser Aufwand gegenüber anderen Faktoren nicht ins Gewicht, erst wenn die Berechnung häufig hintereinander durchgeführt werden soll (wie z. B. bei einem Brute-Force-Angriff) tritt eine erhebliche Verlangsamung ein.

Die Präsentation von bcrypt führte zu diesem Zweck einige Design-Kriterien für Passwort-basierte Schlüsselableitungsfunktionen ein:

• Bcrypt verfügt über einen je nach Anwendungszweck einstellbaren Kostenfaktor, der den Arbeitsaufwand der Hashwert-Berechnung definiert. Mit diesem Faktor kann auch der Aufwand erhöht werden, wenn sich in der Zukunft die Leistungsfähigkeit der Computer weiterentwickelt.
• Die Funktion soll für den Kontext, für den sie konstruiert wurde, optimiert sein. Performance-Vorteile für Hardware-Implementierungen und andere Programmiersprachen sollen gering ausfallen, da solche Vorteile einem Angriff zugutekommen.
  • Eine (moderate) Speicheranforderung begrenzt den Vorteil von Hardware-Optimierungen. Bcrypt fordert 4 KB Arbeitsspeicher an.
  • Software-Implementierungen sollen auf Operationen beruhen, die für CPUs optimiert sind, wie exklusiv-Oder, Addition oder Shift-Operationen.

Die NIST-Empfehlung von 2010 zur PBKDF2 berücksichtigt nur das erste Kriterium. Aufgenommen und erweitert wurden diese Kriterien jedoch in der Schlüsselableitungsfunktion scrypt und von der Password Hashing Competition.

Funktionsweise

Bcrypt unterscheidet sich nur in einigen Punkten von der Blockverschlüsselung Blowfish. Die Verlangsamung findet hauptsächlich innerhalb der Passwort-abhängigen Berechnung der Runden-Schlüssel und der S-Boxen statt. Diese werden in mehreren Runden abhängig vom Salt und dem Passwort durch die Funktion EksBlowfishSetup modifiziert. Die Anzahl dieser Runden ist 2 hoch der cost-Parameter. Im Anschluss daran wird mit den so erzeugten Runden-Schlüsseln und S-Boxen der 192-Bit-Wert „OrpheanBeholderScryDoubt“ 64-mal im ECB-Modus verschlüsselt.

Das Resultat der bcrypt-Referenz-Implementierung ist eine 60 Zeichen lange Zeichenabfolge, die an die Erfordernisse des ursprünglichen Anwendungszwecks, der Benutzer-Authentifizierung von OpenBSD, angepasst ist. Mit dem Zeichen „$“ wird die Zeichenfolge eingeleitet und jeweils Versionsnummer, Kostenfaktor und eine Zeichenfolge bestehend aus Salt und Hashwert getrennt. Salt und Hashwert werden mit einer speziellen Base64-Kodierung abgebildet; der eigentliche Hashwert ist in den letzten 31 Zeichen enthalten. Dieses Format wird auch von anderen Implementierungen übernommen.

Sicherheit

Die Länge des Passworts ist bei bcrypt auf 56 Bytes beschränkt, auch wenn die meisten Passwörter diese Grenze nicht überschreiten. Die Speicheranforderung von 4 KB wird der Anforderung, Hardware-Implementierungen beispielsweise in FPGAs und ASICs zu limitieren, nicht gerecht. Unter Einbeziehung der Energieeffizienz und der Kosten für die Hardware ist bcrypt vor allem durch parallel rechnende FPGAs angreifbar (Wörterbuchangriff oder Brute-Force-Methode). Ein Angriffsszenario mit speziellen ASICs wäre noch aussichtsreicher. Dennoch schneidet bcrypt bei Vergleichen in Bezug auf Angriffe mit spezialisierter Hardware oft besser ab als die meisten anderen Passwort-basierten Schlüsselableitungsfunktionen, abgesehen von scrypt.

Weiterentwicklung

Mit Pufferfish von Jeremi Gosney nimmt ein Algorithmus an der Password Hashing Competition teil, der stark an bcrypt angelehnt ist. Auch der an scrypt angelehnte Algorithmus yescrypt nimmt den Mechanismus des schnellen, zufälligen Zugriffs, der den Algorithmus GPU-resistent macht, auf.

Weblinks

• A Future-Adaptable Password Scheme, von Niels Provos und David Mazières (englisch)

Einzelnachweise

1. Meltem Sonmez Turan; Elaine B. Barker; William E. Burr; Lidong Chen: Recommendation for Password-Based Key Derivation Part I: Storage Applications. NIST SP – 800-132, 2010.
2. Password Hashing Competition: (Memento vom 2. September 2013 im Internet Archive). Kriterien für Passwort-basierte Schlüsselableitungsfunktionen.
3. Katja Malvoni, Solar Designer, Josip Knezovic: Are Your Passwords Safe: Energy-Efficient Bcrypt Cracking with Low-Cost Parallel Hardware. Untersuchung über die Performance von Hardware zum Brechen von bcrypt-Hashwerten (pdf). (englisch)
4. Energy-efficient bcrypt cracking: Takeaways. Präsentation bei openwall. (englisch)
5. Wiemer, F., Zimmermann, R.: High-speed implementation of bcrypt password search using special-purpose hardware. In 2014 International Conference on Reconfigurable Computing and FPGAs (ReCoFig), 2014.
6. Colin Percival: Stronger Key Derivation via Sequential Memory-Hard Functions. Präsentation auf dem BSDCan'09. Auf S. 14 werden die Kosten zum Brechen verschiedene Funktionen miteinander verglichen.
7. European Union Agency for Network and Information Security: (Memento vom 17. Oktober 2015 im Internet Archive) S. 53. (pdf)
8. http://www.openwall.com/presentations/Passwords12-The-Future-Of-Hashing/ Enthält auf S. 45 und 46 einen Vergleich bezüglich FPGAs/ASICs und GPUs.
9. Markus Dürmuth and Thorsten Kranz: (Memento vom 26. Juni 2015 im Internet Archive). 2014 (PDF; 391 kB).
10. Wiki der Password Hashing Competition: (Memento vom 19. August 2014 im Internet Archive) (englisch)
11. Wiki der Password Hashing Competition: (Memento vom 19. August 2014 im Internet Archive) (englisch)