Best Paper Award für Kryptographie-Experten des IST Austria und ihre Kollegen

Postdoc Joël Alwen und Professor Krzysztof Pietrzak wurden auf der Eurocrypt’17-Konferenz in Paris zusammen mit ihren US-Kollegen mit dem Best Paper Award ausgezeichnet. Ihre preisgekrönte Arbeit beweist die Existenz einer bestimmten Art von kryptographischen Funktionen, so genannten „memory hard functions“. Diese sind besonders speicherintensiv und daher „egalitär“ in dem Sinne, dass sie auch auf speziell dafür entwickelter Hardware nicht zu niedrigeren Kosten als auf Standard-CPUs berechnet werden können. Diese Funktionen sind entscheidend für die Sicherung von Passwort-Servern und für Anwendungen in der nächsten Generation dezentraler digitaler Zahlungsmittel, so genannter Kryptowährungen.

Ein Server speichert Benutzerpasswörter normalerweise nicht im Klartext, sondern wendet stattdessen eine kryptografische Hashfunktion an und speichert danach nur das Ergebnis, den so genannten Hashwert. Auf diese Weise kann ein Server das Passwort immer noch verifizieren, indem er die Hashfunktion anwendet und prüft, ob die Ausgabe mit dem gespeicherten Wert übereinstimmt. Wird allerdings die Passwortdatei gestohlen, was „leider anscheinend ständig vorkommt“, wie Pietrzak es formuliert, sind die Passwörter nicht sofort kompromittiert: Um das Passwort zu finden, das dem Hashwert entspricht, muss der Gegner verschiedene Passwort-Kandidaten „hashen“ bis der Hashwert dem gespeicherten Wert entspricht. Für ein typisches von einem Menschen erzeugtes Passwort ist das Hashen von etwa einer Milliarde Werte erforderlich. Doch eine Milliarde ist nicht genug. Um dem Gegner die Aufgabe noch weiter zu erschweren, benutzt man üblicherweise eine „moderately hard“ Hashfunktion. Diese mittelgradig harte Funktion ist zwar kostspielig in der Berechnung, aber nicht zu sehr. Für den Server, der die Funktion nur einmal pro Login-Versuch berechnen muss, stellt sie keine große Belastung dar. Für den Angreifer aber, der Milliarden von Hashes berechnen muss, wird sie extrem teuer.

Die klassische Methode zur Erzeugung mittelharter Funktionen besteht darin, dass eine Standard-Hashfunktion einfach ein paar tausend Mal iteriert wird. Doch leider gewinnt man damit nicht so viel Sicherheit, wie man hoffen würde: Während Server normale CPUs verwenden, kann ein Gegner Spezialhardware verwenden, auf der die Auswertung solcher Funktionen in Bezug auf Hardware- und Energiekosten um Größenordnungen günstiger ist. So war das Knacken von Passwörter mittels „brute force“ bei weitem nicht so kostspielig wie ursprünglich erwartet!

Um dieses Problem zu lösen, hat Colin Percival im Jahr 2009 den Begriff der „Memory-Hard“ -Funktionen (MHFs) eingeführt. Dabei handelt es sich um mittelgradig harte Funktionen, deren Auswertungskosten vor allem durch Speicherkosten verursacht werden. MHFs wären egalitär: Da die Speicherkosten auf verschiedenen Hardwareplattformen etwa gleich sind, würde die spezielle Hardware dem Gegner nicht mehr nutzen. Percival schlug auch gleich einen Kandidaten für eine MHF vor: scrypt. Diese ist heute weit verbreitet.

Eine erste formale Definition, die die Speicherintensität (genauer gesagt: die so genannte parallele kumulative Speicherkomplexität) erfasste, wurde erst sechs Jahre später, im Jahr 2015, von IST Austria Postdoc Joël Alwen und Vladimir Serbinenko der ETH Zürich vorgelegt. Es stellte sich heraus, dass eine Vielzahl von Kandidaten für MHFs, darunter auch ein Gewinner eines zweijährigen Passwort-Hashing-Wettbewerbs, diese Definition nicht erfüllten. Der Status von Percivals ursprünglicher Funktion scrypt blieb jedoch ungelöst.

Im Jahr 2016 präsentierten die Kryptographie-Forschungsgruppen des IST Austria und der University of California Santa Barbara erste Fortschritte in diese Richtung. Nun, ein Jahr später, ist es ihnen gelungen, zusammen mit Leonid Reyzin von der Boston University, der im Jahr 2016 ein Sabbatical am IST Austria verbrachte, die letzten Schritte zu machen, und zu bewiesen, dass scrypt tatsächlich „Memory Hard“ ist.

Dieses Ergebnis, das sie dieser Tage in Paris auf einer der zwei wichtigsten Kryptographie-Konferenzen, der Eurocrypt, präsentieren, erweitert unser Wissen über speicherintensive Funktionen im Allgemeinen und scrypt im Speziellen. Dies erhöht nicht nur das Vertrauen, das man in scrypt als Hashfunktion für Passwörter setzen darf, sondern ist auch für eine Vielzahl von dezentralisierten Kryptowährungen wie Litecoin und Dogecoin relevant, da diese scrypt bereits nutzen.

„Dieses Forschungsfeld hält immer noch viele spannende offene Probleme bereit, an denen wir derzeit arbeiten“, sagt Pietrzak, „zum Beispiel erfassen die aktuellen Modelle nur die Hardware-Kosten, aber wie man auch in Bezug auf Energiekosten eine Gleichheit erreichen kann, ist noch unklar.“
Joël Alwen kam im Jahr 2014 als Postdoc an das IST Austria. Seine Interessen reichen von gitterbasierter Kryptographie bis hin zu „Leackage“-Resilienz. Er ist auch an einer Vielzahl von Programmierprojekten beteiligt, darunter zum Beispiel auch an der Netflix Challenge und am Entwerfen von Angriffen auf Passwort-Hashfunktionen. Professor Krzysztof Piertzak leitet seit 2011 die Kryptographie-Forschungsgruppe am IST Austria und erforscht eine breite Palette theoretischer und praktischer Aspekte der Kryptographie, darunter speicherintensive Funktionen, Kryptographie für kleine Geräte, symmetrische Kryptographie und nachhaltige Kryptowährungen.

Weiterführende Informationen

Scrypt
Password Hashing Competition

Publikation

“Scrypt is Maximally Memory-Hard” Joel Alwen (IST Austria), Binyi Chen (UCSB), Krzysztof Pietrzak (IST Austria), Leonid Reyzin (Boston University), Stefano Tessaro (UCSB) https://eprint.iacr.org/2016/989