Catena (Hashfunktion)

Catena ist eine grundlegende Struktur (framework) zum Hashen von Passwörtern. Sie eignet sich zum sicheren Authentifizieren (Speichern von Passwörtern), als Passwort-basierte Schlüsselableitungsfunktion und als Proof-of-Work-Verfahren. Catena wurde 2013 von Christian Forler, Stefan Lucks und Jakob Wenzel entwickelt und nahm als Kandidat an der Password Hashing Competition teil. Der Name Catena ist von dem lateinischen Wort für Kette abgeleitet.

Geschichte

Catena wurde 2013 zunächst als eine Alternative zu der Passwort-Hashfunktion Scrypt vorgestellt. Catena nahm als Kandidatin an der Password Hashing Competition teil und wurde in deren Verlauf mehrfach modifiziert. Mit Version v2 ist Catena kein konkreter Algorithmus (Password Scrambler) mehr, sondern ein Rahmenwerk, das von verschiedenen Algorithmen instantiiert werden kann. Die vorgestellten Instanzen in der Version v3 sind Catena-Dragonfly und Catena-Butterfly. 2015 wurde Catena von der Password Hashing Competition als einer von vier Vorschlägen neben dem Gewinner Argon2 mit besonderer Anerkennung für sein agiles Rahmenwerk und seine Widerstandsfähigkeit gegen Seitenkanal-Angriffe ausgezeichnet.

Kritik an Scrypt

Motiviert wurde die Entwicklung von Catena durch die Kritik an der Funktion Scrypt, deren Grundidee (Arbeitsspeicher-Intensität) aufgegriffen wurde. Die aufgeführten Kritikpunkte waren:

• Komplexität: Scrypt verwendet zwei unterschiedliche kryptographische Primitive (Salsa20/8 und SHA-256) und vier weitere Operationen (ROMix, BlockMix, PBKDF2, HMAC)
• Anfälligkeit für cache timing attacks: Die Adressen für den Datenzugriff in der Funktion ROMix sind abhängig vom Passwort
• Anfälligkeit für garbage-collector attack: Speicherfragmente können dazu genutzt werden, das Durchprobieren von Passwörtern zu vereinfachen

Struktur

Das Rahmenwerk Catena ist definiert durch:

1. eine kryptographische Hashfunktion: Die neueste Referenz-Implementierung enthält Blake2b als einzige Funktion. In den Versionen v1 und v2 wurde neben Blake2b auch SHA-512 implementiert, in Version v3 jedoch nur noch als Möglichkeit genannt. Theoretisch kann jede Hashfunktion mit einer Länge von 64 Byte verwendet werden.
2. eine reduzierte Variante dieser Hashfunktion: Verwendet wird in der Version v3 die von ursprünglich 12 auf eine Runde reduzierte Hashfunktion Blake2b.
3. eine optionale Funktion Γ (gamma) als randomization layer (Zufalls-Zugriffsschicht): Die Funktion Γ soll zusätzlich die Arbeitsspeicher-Anforderung sichern. Um Time-Memory Tradeoffs zu verhindern, wird der Speicher-intensive Vektor (der Status) in Abhängigkeit vom Salt modifiziert. Derzeit wird für alle vorgestellten Instanzen die Funktion saltMix verwendet, die auf einem Xorshift-Generator basiert. Das Catena-Team erklärt jedoch, dass diese Funktion grundsätzlich auch ersetzt werden kann.
4. eine Arbeitsspeicher-intensive Funktion F, die mit einem Graphen-gesteuerten Datenfluss auf einen Vektor zugreift: Die Funktion F zeichnet sich durch eine Cachezeit-konstante Ausführung aus. Vorgestellt werde ab der Version v2 zwei Varianten: Catena-BRG (bit reversalt graph) und Catena-DBG (double butterfly graph).

Parameter

Catena erlaubt Passwörter und Salts beliebiger Länge. Zusätzlich kann ein weiteres Argument eingegeben werden, beispielsweise ein kryptographischer Schlüssel oder ein Personal String. Die Sicherheit kann vor allem über drei Parameter eingestellt werden:

• den Salt oder Teile davon geheim halten (Pepper)
• durch den Parameter garlic die Speicheranforderung erhöhen: Der empfohlene Wert für Catena Butterfly ist 16, für Catena-Butterfly-Full 14, für Catena-Dragonfly 21, für Catena-Dragonfly-FULL 18. Wenn Catena als Schlüsselableitungsfunktion verwendet wird, erhöht sich der empfohlene Wert auf 22 (Dragonfly) beziehungsweise 17 (Butterfly).
• durch den Parameter λ (lambda) den Rechenaufwand durch die Tiefe des Graphen erhöhen: Der empfohlene Wert für Catena-Dragonfly ist 2, für Catena-Butterfly 4.

Eigenschaften

Client-unabhängige Einstellung (client-independent update)

Mit der ersten Version von Catena wurde erstmals ein Mechanismus vorgestellt, mit dem auf der Server-Seite die Sicherheitseinstellungen für die Authentifizierung geändert werden können. Auf diese Weise können die Sicherheitsparameter auch für inaktive oder selten genutzte Accounts neuen Erfordernissen angepasst werden – ohne Interaktion mit dem User und ohne Wissen des Passworts. Dieser Mechanismus wurde in der Folge auch von anderen Passwort-Hashing-Verfahren übernommen.

Server-Entlastung

Das Server Relief erlaubt das Auslagern eines großen Teils des Authentifizierungs-Prozesses vom Server auf den Client: Der Server schickt zuerst den Salt an den Client. Die Zeit- und Arbeitsspeicher-aufwändige Funktion F wird auf der Client-Seite ausgeführt, der Server berechnet im Anschluss lediglich eine effiziente Hashfunktion.

Schlüsselableitungsfunktion Catena-KG

Catena kann in einem speziellen Modus als Schlüsselableitungsfunktion (key derivation function) ausgeführt werden und erlaubt als solche die effiziente Berechnung von extrem langen Schlüssel, sowie die Erzeugung mehrerer, voneinander unabhängiger Schlüssel.

Proof of Work

Catena hat einen eigenen Modus für ein Proof-of-Work-Szenario. Dieser Modus ist beispielsweise für Kryptowährungen und für das Erschweren von Spam-Versand für E-Mail-Provider gedacht.

Konkrete Instanzen

Mit Version v2 wurde Catena als Rahmenwerk (framework) beschrieben mit zwei verschiedene Instanzen: Catena-BRG und Catena-DBG. In Version v3 wurden diese leicht geändert, konkretisiert und als Catena-Dragonfly und Catena-Butterfly vorgestellt. Beide Instanzen können mit einer Runden-reduzierten und einer vollständigen Hashfunktion ausgeführt werden.

Die Auswahl der Instanz richtet sich nach den Systemvoraussetzungen, dem Einsatzszenario und dem erwarteten Angriff.

Catena-Dragonfly

Catena-Dragonfly und Catena-Dragonfly-FULL basieren auf dem Bit Reversal Graph für die F-Funktion und der Hashfunktion Blake2b. In der „FULL“-Variante wird die Hashfunktion vollständig ausgeführt, in der anderen Variante nur eine Runde. Catena-Dragonfly-FULL entspricht in den meisten Punkten der ursprünglichen Version von Catena als Password Scrambler und gilt als Instanz der in der Version v2 vorgestellten Variante Catena-BRG. Catena-Dragenfly wurde erstmals im Januar 2015 in der Version v3 als Instanz des Rahmenwerks im Verlauf der Password Hashing Competition vorgestellt.

Catena-Dragonfly wird für Anwendungen empfohlen, bei denen ausreichend Arbeitsspeicher zur Verfügung steht und ein Angreifer mit hohem Budget (Verfügbarkeit von ASICs) abgewehrt werden soll. Typische Anwendungsfälle sind Schlüsselableitungsfunktionen und Proof-of-Work-Szenarien.

Catena-Butterfly

Catena-Butterfly und Catena-Butterfly-FULL basieren auf dem Double Butterfly Graph für die F-Funktion und wie Catena-Dragenfly auf der vollständigen oder Runden-reduzierten Hashfunktion Blake2b. Catena-Butterfly ist eine Instanz der in Version v2 vorgestellten Variante Catena-DBG und wurde ebenfalls in der Version v3 vom Januar 2015 zum ersten Mal aufgeführt.

Catena-Butterfly wird für Anwendungen mit begrenztem Arbeitsspeicher empfohlen und wenn Angreifer mit geringem Budget (lediglich Verfügbarkeit von GPUs und FPGAs) erwartet werden. Typischer Anwendungsfall ist die Authentifizierung auf einem Server.

Weitere Varianten

Im Dezember 2015 stellte Jakob Wenzel auf dem Kongress „Passwords15“ in Cambridge vier weitere Instanzen von Catena vor, die jeweils auf eine bestimmte Sicherheits-Eigenschaft abzielen.

Weblinks

• PHC Candidates. Kandidaten der Password Hashing Competition.
• Catena-Seite der Bauhaus-Universität Weimar: Catena
• Christian Forler Stefan Lucks Jakob Wenzel: Catena: A Memory-Consuming Password Scrambler (PDF). Erste Version v1 von 2013.
• Christian Forler Stefan Lucks Jakob Wenzel: Catena: A Memory-Consuming Password-Scrambling Framework (PDF). Zweite Version v2 von 2014.
• Christian Forler Stefan Lucks Jakob Wenzel: The Catena Password-Scrambling Framework. 2nd Round of the Password Hashing Competition (PHC) (PDF; 615 kB). Dritte Version v3 von 2015.

Einzelnachweise

1. Password Hashing Competition: (Memento vom 11. August 2015 im Internet Archive).
2. Christian Forler, Stefan Lucks, Jakob Wenzel: The Catena Password-Scrambling Framework. 2nd Round of the Password Hashing Competition (PHC). S. 27 (PDF; 615 kB)
3. Christian Forler, Stefan Lucks, Jakob Wenzel: The Catena Password-Scrambling Framework. 2nd Round of the Password Hashing Competition (PHC). S. 31 (PDF; 615 kB)
4. Christian Forler, Stefan Lucks, Jakob Wenzel: Catena: A Memory-Consuming Password Scrambler. (pdf, 308 KiB) 23. August 2013, S. 6, abgerufen am 26. Oktober 2015 (englisch). 
5. Christian Forler, Stefan Lucks, Jakob Wenzel: The Catena Password-Scrambling Framework. (PDF, 669 KiB) Version 3.2. 29. September 2015, S. 45, abgerufen am 26. Oktober 2015 (englisch). 
6. Stefan Lucks, Jakob Wenzel: (Memento vom 21. April 2016 im Internet Archive) (Präsentation als pdf)