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.

scrypt und ähnliche Funktionen (z. B. Argon2) nutzt man auch dafür, den Hashwert zu einem Benutzerkonto aus dem Passwort des Kontoinhabers zu berechnen und in der Datenbank eines Servers zu speichern, um den Benutzer, wenn dieser sich anmeldet, zu authentifizieren.

Hintergrund

Passwörter selbst sind als kryptographische Schlüssel nicht geeignet, deshalb wird durch eine Hashfunktion daraus ein Schlüssel berechnet. Aus dem Hashwert einer normalen kryptografischen Hashfunktion wie SHA-2 kann man zwar das Passwort nicht direkt berechnen, aber sie schützt kaum 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öglicher Passwörter 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 Parallelisierung kann grundsätzlich nicht verhindert werden. Scrypt nutzt den Umstand aus, dass Arbeitsspeicher verhältnismäßig teuer ist, hat einen Mindestspeicherbedarf von (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. 2012 veröffentlichte die IETF einen Entwurf von scrypt als Internet-Draft. Im August 2020 gab Colin Percival Version scrypt-1.3.1 frei.

Obwohl Colin Percival als Experte an der Password Hashing Competition, einem Auswahlverfahren für ein neues Passwort-Hashing-Verfahren, beteiligt war, nahm Scrypt selbst nicht daran teil, dafür aber Yescrypt von Alexander Peslyak, das mit der Erweiterung YESCRYPT-WORM auch originale scrypt-Hashwerte produzieren kann.

Beschreibung

Scrypt gilt als sequential memory-hard (sequenziellspeicherintensiv). Zunächst wird ein Speicherbereich 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 dadurch sichergestellt, dass die Werte permanent im Speicher gehalten werden müssen oder aber die Rechenzeit sich durch Cache Misses (und daraus resultierendes Paging usw.) extrem erhöht.

Scrypt erlaubt die Parametrisierung der CPU-Kosten (Rechenzeit) und der Speicherkosten über drei Parameter:

• $N$: CPU- und Speicherfaktor
• $r$: Speicherfaktor
• $p$: Parallelfaktor

Colin Percival empfahl bei der Veröffentlichung 2010 die Parameterwerte $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$ sind 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 bei 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 scrypt jedoch 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, 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 und eine Kandidatin in der Password Hashing Competition ist. Im Gegensatz zu scrypt sind diese Parameter bei Lyra2 jedoch nicht aneinander gekoppelt. Mittlerweile benutzt Vertcoin einen eigenen Algorithmus (Verthash).

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 Stand 2013 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 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 nur theoretisch gegeben sei.

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 bei coinwiki.org: Liste von Kryptowährungen. Aufgeführt sind auch die Algorithmen für das Mining.