Passwort-Hashing-Verfahren, Teil 2

zurück zu Teil 1

Die Problemlage

Mit dem Aufkommen neuer Hardwareeinheiten wie ASICs änderte sich die Situation für Passwort- Hashing-Verfahren dramatisch.
Das Problem besteht nicht nur darin, dass spezialisierte Hardware schneller ist, sondern vor allem darin, dass Berechnungen parallel ausgeführt werden können. Dabei kommt neben der reinen Zeit-Performance auch die Stromversorgung und Kühlung ins Spiel, wenn es um die Beurteilung der Effizienz geht.
Die Effizienz multipliziert sich bei jedem Schritt:
CPUs (normale PCs) -> GPUs -> FPGAs -> ASICs
Ganz normale User*innen und erst recht Angreifer*innen mit genügend finanziellen Ressourcen verfügten plötzlich über die Möglichkeit durch parallele Berechnungen den Kostenfaktor sozusagen auszuhebeln.

ASICs: Application-specific integrated circuit

ASICs, übersetzt in etwa "Anwendungsspezifische integrierte Schaltungen", sind kleine elektronische Bauteile, die nur eine bestimmte Berechnung anstellen können - die jedoch viel schneller sind als herkömmliche Rechner. Sie sind auf bestimmte Algorithmen spezialisiert, beispielsweise auf die Ausführung einer Hashfunktion. Sie sind klein und verbrauchen wenig Strom, d.h. es ist kein Problem eine große Anzahl von ihnen gleichzeitig zu betreiben und etwa Tausende von Hashwerten parallel zu berechnen.

ASICs: Bitcoin Miner Bitcoin Miner Box Butterfly Labs bitcoin miner John Biehler, license: CC
ASICs sind die unflexibelsten, aber schnellsten spezialisierten Hardware-Bausteine. Ihr Aufkommen in den 80er Jahren stellte die Passwort-Hashing-Verfahren zunächst noch nicht vor große Probleme. Der große Nachteil der ASICs ist ihre Spezialisierung. Zunächst einmal muss ein ASIC für einen bestimmten Anwendungszweck entwickelt werden, das ist sehr teuer, auch wenn dann die Produktionskosten pro Stück rapide sinken.
Schon bald wurden ASICs auch für kryptographische Aufgaben entwickelt, denn das beschleunigte deren Ausführung. Die Standardisierung der kryptographischen Verfahren sorgte dafür, dass die Anzahl der verwendeten Algorithmen überschaubar war.
Durch die weite Verbreitung von ASICs für kryptographische Aufgaben waren diese plötzlich relativ billig geworden. Das hatte Auswirkungen auf das Passwort-Hashing. Eine einfache Hashfunktion konnte nun parallel und viel schneller ausgeführt werden.
Heutige Bitcoin-Miner sind kleine handliche Boxen, die aus ASICs bestehen und mehr als 10 Milliarden SHA-2-Hashwerte pro Sekunde berechnen können und gerade mal 50$ kosten. Professionelle Miner berechnen 15 Billionen Hashwerte pro Sekunde. Das lässt erahnen, wie viele Hashwerte Organisationen wie die NSA pro Sekunde berechnen können.

Eine erfolgversprechende Strategie, Angriffe mit ASICs zu verhindern, besteht darin, das Passwort-Hashing-Verfahren so zu gestalten, dass große Vektoren im Arbeitsspeicher benötigt werden, der Algorithmus memory-hard (Speicher-aufwändig) ist. Arbeitsspeicher ist teuer und so verfügen die meisten (und vor allem billigeren) ASICs über relativ wenig Arbeitsspeicher und eigenen sich nicht für solche Berechnungen. Die Strategie besteht im Grunde darin, einen Angriff allein aufgrund des Preises undurchführbar zu machen.
Das Passwort-Hashing-Verfahren Scrypt basiert auf dieser Idee und vergleicht die Sicherheit der Verfahren bzw. die Angriffe auf diese nicht in Zeit- oder Platzkomplexität, wie in der Kryptographie üblich, sondern in dollar seconds.
Schon das Verfahren Bcrypt enthielt die Idee, durch eine moderate Speicheranforderung Angriffe mit spezialisierter Hardware zu verhindern, allerdings entspricht der Speicheraufwand von Bcrypt in keiner Weise mehr den heutigen Anforderungen.
ASICs müssen für jeden Algorithmus speziell entwickelt werden. Ein einziges standardisiertes Verfahren (wie zur Zeit PBKDF2) kommt dieser Angriffsweise entgegen, eine gewisse Bandbreite an Verfahren dagegen bereitet dieser Angriffsweise Probleme.

FPGAs: Field Programmable Gate Array

FPGAs sind integrierte Schaltkreise, die den großen Nachteil des ASICs wettmachen: deren Spezialisierung. FPGAs sind programmierbar bzw. konfigurierbar, also nicht nur für eine bestimmte Aufgabe tauglich. Das spart die Entwicklungskosten, die der Produktion von ASICs vorausgehen ein. FPGAs sind teurer als einmal entwickelte ASICs und langsamer, aber immer noch schneller als herkömmliche Rechner. Vor allem sind sie stromsparend und erlauben so eine parallele Ausführung durch viele FPGAs.

Die Strategie gegen FPGAs ähnelt der gegen ASICs. Auch FPGAs verfügen üblicherweise nur über ein überschaubaren Arbeitsspeicher.
Ein Bandbreite an Passwort-Hashing-Verfahren verhindert Angriffe mit FPGAs nicht.

GPUs: Grafikprozessoren ("graphics processing unit")

GPU-Card für den
professionellen Einsatz
Bitcoin Miner Box Tesla-K80-Dual-GPU by GBPublic_PR, license: CC
GPUs stellen den dritten Problemfall für Passwort-Hashing-Verfaren dar. Ursprünglich waren GPUs zur Grafikberechnung vorgesehen. Sie wurden in Rechner implementiert, um 3D-Berechnungen parallel ausführen zu können und damit (auf ein erträgliches Maß) zu beschleunigen. GPUs können jedoch auch andere Berechnungen anstellen, beispielsweise Passwort-Hashing-Verfahren. Das besondere Problem der GPUs ist, dass sie vielfach vorhanden sind. Multimedia-PCs verfügen darüber und sind damit auch zum Knacken von Passwörtern geeignet. GPUs haben das parallele Brechen von Passwörtern sozusagen zum potenziellen Volkssport gemacht und nicht mehr dem professionellen Bereich vorbehalten.
Mit genügend GPU-Power lassen sich viele Millionen Hashwerte pro Sekunde berechnen.

Auch GPUs verfügen nur über einen begrenzten Arbeitsspeicher, auch wenn dieser üblicherweise größer ist als der von FPGAs der gar ASICs, insofern ist ein genügend großer Speicheraufwand auch geeignet, Angriffe mit GPUs zu verhindern.
Zudem hat sich gezeigt, dass manche Algorithmen mit GPUs nicht effektiv berechnet werden können, auch wenn die Speicheranforderung gering ist. Das hat sich für das Passwort-Hashing-Verfahren Bcrypt sozusagen im Nachhinein herausgestellt. Viele neue Verfahren orientieren sich daher an Bcrypt (Battcryt, Pufferfish, Yescrypt).


Botnetze

Hierbei handelt es sich nicht um eine spezialisierte Hardware, sondern um eine (oft unfreiwillige) Vernetzung von Rechnern.
Manche (illegale) Botnetze haben mehrere Hunderttausend oder Millionen Rechner infiziert und können deren Rechenleistung nutzen. Die Nutzung solcher Botnetze kann sozusagen "angemietet" werden.

Im Falle der Passwort-Hashings ist der Einsatz von Botnetzen besonders problematisch, weil moderne Passwort-Hashing-Verfahren den Vorteil spezialisierter Hardware zu verhindern suchen und für die Berechnung auf "normalen" PCs optimiert sind. Nun verfügen Botnetze gerade über eine große Zahl dieser "normalen" PCs. Daher sind nur sehr wenige Passwort Hashing Verfahren auf Angriffe mit Botnetzen ausgerichtet.
Eine Strategie, solchen Angriffen vorzubeugen, besteht in einem pseudo-zufälligen Zugriff auf sehr große Datenmengen (mehrere Terabyte), die nicht mehr im Arbeitsspeicher verfügbar sein können, sondern beispielsweise auf Festplatten gespeichert werden. Botnetze müssten diese riesigen Datenmengen zunächst auf die infiltrierten Rechner übertragen oder jeden Zugriff via Internet realisieren. In beiden Fällen bremst bzw. verhindert die Datenübertragung einen effizienten Angriff, entweder durch die große Menge an Daten oder durch die große Anzahl der Zugriffe.
Die Passwort-Hashing-Verfahren Yescrypt und EARWORM sind darauf ausgerichtet, Angriffe mit Botnetzen zu vereiteln. Im Grunde ließe sich ein solcher ROM-Zugriff aber auch als Extra-Schritt nach jedem Passwort-Hashing-Verfahren realisieren.