scrypt

scrypt ist eine Passwort-basierte Schlüsselableitungsfunktion (password based key derivation function), die 2010 von Colin Percival veröffentlicht wurde. Motiviert wurde die Entwicklung von scrypt durch die Verwundbarkeit bisheriger Schlüsselableitungsfunktionen wie bcrypt und PBKDF2 gegen Brute-Force- und Wörterbuchangriffe mit spezialisierter Hardware.

Hintergrund

Passwörter selbst sind als kryptographische Schlüssel nicht geeignet. Der einfache Hashwert des Passworts verhindert zwar eine Rück-Berechnung des Passworts, schützt aber nicht vor Wörterbuchangriffen, der Brute-Force-Methode und Rainbow Tables. Passwort-basierte Schlüsselableitungsfunktionen lassen in die Schlüsselberechnung zusätzlich eine Zufallszahl, den Salt, einfließen und erhöhen gezielt den Aufwand der Berechnung eines Schlüssels, um das „Durchprobieren“ vieler Möglichkeiten zu erschweren.

Scrypt bemisst den Rechenaufwand im Gegensatz zu anderen Schlüsselableitungsfunktionen nicht nur nach der reinen Rechenzeit. Stattdessen erhöht scrypt auch gezielt die Kosten für die Hardware, die geeignet ist, um ein Passwort in einer bestimmten Zeit zu brechen (dollar-seconds). Dieser Paradigmenwechsel ist dem Umstand geschuldet, dass durch die Entwicklung spezialisierter Hardware wie FPGAs und Grafikprozessoren die reale Rechenzeit zur Brechung eines Passworts dramatisch verkürzt werden kann (custom hardware attack). Die in den Schlüsselableitungsfunktionen bcrypt und PBKDF2 beabsichtigte Verlangsamung der Berechnung durch die Anzahl der Hash-Operationen (Iterationen) kann durch eine Parallelisierung des Angriffs bei Verwendung spezieller Hardware kompensiert werden. Eine solche parallele Programmierung kann grundsätzlich nicht verhindert werden. Scrypt nutzt den Umstand aus, dass Arbeitsspeicher verhältnismäßig teuer ist, fordert einen Vektor mit (standardmäßig) 16 MB an und treibt so die Kosten für den Einsatz spezialisierter Hardware in die Höhe. Diese Idee lag schon der Schlüsselableitungsfunktion HEKS zugrunde, wird aber in scrypt um die Sequentialisierung ergänzt.

Geschichte

Scrypt wurde von Colin Percival für die Firma Tarsnap entwickelt und im Mai 2009 auf der BSD-Konferenz präsentiert. Bereits 2012 wurde von der IETF ein Entwurf von scrypt als Internet-Draft veröffentlicht. Im August 2015 gab Colin Percival Version scrypt-1.2.0 frei.

Scrypt nimmt nicht an der Password Hashing Competition teil, einem Auswahlverfahren für ein neues Passwort-Hashing-Verfahren, obwohl Colin Percival als Experte daran beteiligt ist. Mit Yescrypt von Alexander Peslyak nimmt jedoch ein Algorithmus teil, der nicht nur von scrypt inspiriert ist, sondern auf der Funktion aufbaut und neben yescrypt- auch originale scrypt-Hashwerte produzieren kann.

Beschreibung

Scrypt gilt als sequential memory-hard (sequenziell Speicher-intensiv). In der Funktion ROMix wird ein Vektor mit Werten der Funktion Salsa20/8, einer auf acht Runden verkürzten Version der Stromchiffre Salsa20 gefüllt. Danach wird auf diesen in einer pseudozufälligen Weise zugegriffen und somit sichergestellt, dass der Vektor permanent im Speicher gehalten werden muss – oder die Rechenzeit sich extrem erhöht. Scrypt erlaubt die Parametrisierung der CPU-Kosten (Rechenzeit) und der Speicherkosten und hat zusätzlich einen Parallelisierungs-Parameter.

Parameter:
N: CPU- und Speicherfaktor
r: Speicherfaktor
p: Parallelfaktor
Colin Percival empfahl bei der Veröffentlichung 2010 (N=16384, r=8, p=1) für normale Anforderungen und (N=1048576, r=8, p=1) für hohe Anforderungen. Die Parameter r und p waren dafür gedacht, mit der Zeit an die technische Entwicklung angepasst zu werden.

Verwendung in Kryptowährungen

Neben der Passwort-basierten Schlüsselableitung wird Scrypt auch für das sogenannte Mining in Kryptowährungen wie Litecoin und Dogecoin verwendet. Das Einbringen von Rechenleistung für diese Währungen und damit die Teilhabe an Transaktionsgebühren sollte ursprünglich auf die Teilnehmenden möglichst gleich verteilt werden. Durch den Einsatz von spezieller Hardware (ASICs) ist es jedoch beispielsweise in der Kryptowährung Bitcoin zu einer Abhängigkeit der Rechenleistung von der Finanzkraft und damit zu einer Zentralisierung gekommen. Währungen wie Litecoin wollten dem vorbeugen und nutzten dabei den Umstand aus, dass Scrypt aufgrund der hohen Speicheranforderung schlecht in ASICs implementiert werden kann. Litecoin verwendet jedoch Scrypt mit niedrigeren Parametern (N=1024, r=1, p=1) als von Colin Percival empfohlen und daher mit wesentlich geringerer Speicheranforderung. Inzwischen sind auch für die in diesen Kryptowährungen verwendete Scrypt-Version ASICs auf dem Markt.

Die Kryptowährung Vertcoin führte daraufhin Scrypt mit variablem N-Faktor (Adaptive N-Factor) ein, einem Parameter, der die Speicheranforderung an die Entwicklung anpasst und so eine Implementierung in ASICs verhindern soll. Inzwischen hat Vertcoin angekündigt, Scrypt durch die Funktion Lyra2 zu ersetzen, die ähnlich wie Scrypt Parameter für die Speicheranforderung und die Rechenleistung besitzt. Im Gegensatz zu Scrypt sind diese Parameter bei Lyra2 jedoch nicht aneinander gekoppelt. Die Passwort-Hashing-Funktion Lyra2 ist eine Kandidatin in der Password Hashing Competition.

Viele kleinere Kryptowährungen wie YaCoin benutzen Scrypt-Jane, eine flexible Implementierung von Scrypt (andere Hashfunktionen wie Keccak und ChaCha20/8), deren Speicheranforderung ebenfalls mit der Zeit ansteigt.

Sicherheit

Scrypt ist relativ neu und unerprobt, gilt aber als eine Alternative zu bcrypt und PBKDF2. Da sich die Sicherheit Passwort-basierter Schlüsselableitungsfunktionen in erster Linie nach deren Schutz vor Wörterbuchangriffen und der Brute-Force-Methode bemisst, motiviert die offensichtliche Verwundbarkeit anderer Funktionen dazu, auch relativ neue Funktionen wie scrypt zu verwenden.

2013 wurde eine theoretische Schwachstelle von scrypt gegenüber einer Seitenkanalattacke durch cache timing veröffentlicht. Die Passwort-abhängig unterschiedlichen Zugriffszeiten auf den Speicher-Vektor in den anschließenden Iterationen von scrypt kann unter bestimmten Umständen für ein Passwort-Sieb genutzt werden (cache-time attack). Die Autoren weisen darauf hin, dass ein solcher Angriff auf scrypt derzeit nur theoretisch gegeben ist.

2014 verglichen Markus Dürmuth und Thorsten Kranz von der Ruhr-Universität Bochum die Passwort Hashing Verfahren bcrypt und Scrypt in Bezug auf Angriffe mit spezialisierter Hardware. Scrypt ist demnach trotz höherer Speicheranforderung für niedrige Parameter angreifbarer als bcrypt, da Scrypt mit niedrigen Parametern effizient von GPUs ausgeführt werden kann. Eine Angreifbarkeit von Scrypt mit niedrigen Parametern durch GPUs wurde auch an anderer Stelle festgestellt.

Externe Links

• scrypt-Seite von Tarsnap (englisch)
• Internet-Draft der IETF zu scrypt (englisch)
• coinwiki.org: List of all Coins. Liste von Kryptowährungen. Aufgeführt sind auch die Algorithmen für das Mining.