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 BSDCan-Konferenz präsentiert. Bereits 2012 wurde von der IETF ein Entwurf von scrypt als Internet-Draft veröffentlicht. Im August 2020 gab Colin Percival Version scrypt-1.3.1 frei.

Scrypt nahm nicht an der Password Hashing Competition teil, einem Auswahlverfahren für ein neues Passwort-Hashing-Verfahren, obwohl Colin Percival als Experte daran beteiligt war. Mit Yescrypt von Alexander Peslyak nahm jedoch ein Algorithmus teil, der mit der Erweiterung "YESCRYPT-WORM" 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. Zwischenzeitlich hatte Vertcoin scrypt durch die Funktion Lyra2 ersetzt, 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. Mittlerweile benutzt Vertcoin allerdings einen eigenen Algorithmus (Verthash). 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.

Weblinks

• scrypt-Seite. tarsnap.com (englisch).
• RFC 7914 – The scrypt Password-Based Key Derivation Function. August 2016 (englisch).
• List of all Coins. Liste von Kryptowährungen. Aufgeführt sind auch die Algorithmen für das Mining. coinwiki.org

Einzelnachweise

1. Markus Dürmuth, Tim Güneysu, Markus Kasper, Christof Paar, Tolga Yalcin, Ralf Zimmermann: Evaluation of Standardized Password-Based Key Derivation against Parallel Processing Platforms. In: Computer Security – ESORICS 2012. Springer-Verlag, Berlin / Heidelberg 2012, ISBN 978-3-642-33166-4, S. 716–733.
2. Arnold Reinhold: HEKS: A Family of Key Stretching Algorithms.
3. scrypt – A new key derivation function. Vortrag über Scrypt auf der BSDCan (englisch).
4. scrypt 1.3.1 released. Tarsnap-Mitteilung.
5. Introduction. Website des Password Hashing Competition (englisch).
6. yescrypt - modern KDF and password hashing scheme. Vorstellung von YESCRYPT 1.0.0, Openwall (englisch).
7. Vergleich zwischen Litecoin und Bitcoin Mining (englisch). Abgerufen am 20. Juni 2022.
8. Litecoin-Webseite: Block hashing algorithm (englisch). Abgerufen am 20. Juni 2022.
9. ASICS for Litecoin. Here They Come. Bitcoinmagazine (englisch)
10. David Muller: What is Vertcoin? (PDF) coinpaprika.com (englisch); abgerufen am 20. Juni 2022.
11. Vertcoin (VTC) plans algorithm change to Lyra2. coinbrief.net (englisch).
12. (Memento vom 11. August 2015 im Internet Archive) Password Hashing Competition (englisch).
13. About YACoin. (englisch). Abgerufen am 20. Juni 2022.
14. A flexible implementation of Colin Percival’s scrypt. Scrypt-Jane, GitHub (englisch)
15. Einleitung. des Password Hashing Competition (englisch)
16. Christian Forler, Stefan Lucks, Jakob Wenzel: Catena: A Memory-Consuming Password Scrambler. Cryptology ePrint Archive: Report 2013/525.
17. Markus Dürmuth, Thorsten Kranz: On Password Guessing with GPUs and FPGAs. (PDF; 391 kB)
18. Openwall Mailingliste: using scrypt for user authentication.
19. Anthony Ferrara: Why I Don’t Recommend Scrypt. ircmaxell’s blog