Benutzer:Beloumi/Catena-Entwurf

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoßen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Beloumi auf.

Catena ist eine grundlegende Struktur (framework) zum Hashen von Passwörtern. Sie eignet sich zum sicheren Authentifizieren (Speichern von Passwörtern) und als Passwort-basierte Schlüsselableitungsfunktion. 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 lateinisches 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 Hashfunktionen (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

Design-Kriterien

• einfach und leicht zu analysieren: Basiert auf einer einzigen Hashfunktion und einer Bit-Reversal Graph beziehungsweise Double Butterfly Graph genannten Struktur.
• Parameter für Zeit- und Speicheranforderung
• Catena kann einen Teil der Berechnungen auf den Client auslagern und damit ein Server-Protokoll erleichtern. Damit kann ein Server leichter mehrere parallele Anfragen abarbeiten.
• Server-seitige (Client-unabhängige) Änderung der Sicherheitsparameter (client-independent updates). Damit können auch für inaktve Accounts die Sicherheitseinstellungen angehoben werden. Diese Eigenschaft wurde zuerst im Rahmen von Catena entwickelt.
• Schutz vor spezialisierter Hardware (GPUs, ASICs) durch hohe Speicheranforderung
• Schutz vor cache-timing attacks: Kein Datenzugriff auf Passwort-abhängige Adressen
• Schutz vor garbage-collector attack: Der Speicher wird mehrmals überschrieben (über Parameter lambda einstellbar)
• Unterstützt Schlüssel-basiertes Hashing

Catena ist im Gegensatz zu Scrypt nicht sequentially memory-hard. Dieser Umstand ist den Graphenfunktionen geschuldet, die dagegen jedoch Cachezeit-constant ausgeführt werden können.

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 Angreifer.

Catena-Dragenfly

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 Cometition vorgestellt.

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

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 gilt in Bezug auf einen Time-Memory Tradeoff sicherer als Catena-Dragonfly. (v3 S. 40)

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

Struktur

Das Rahmenwerk Catena ist definiert durch:

1. eine kryptographische Hashfunktion: Die Referenz-Implementierung enthält die Funktion Blake2b, doch die Entwickler nennen auch SHA-512 als eine Möglichkeit. Theoretisch kann jede Hashfunktion mit einem Länge von 64 Byte verwendet werden.Die Diversität hat auch den Zweck, Angriffe mit nicht programmierbarer Hardware (ASICs) zu erschweren.(v3 S. 46)
2. eine reduzierte Variante dieser Hashfunktion: Verwendet wird in der Version v3 die 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 werden 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 eine 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 Version v1.0 von Catena wurde erstmals ein Mechanismus vorgestellt, mit dem auf der Server-Seite die Sicherheitseinstellungen für die Authentifizierung ohne Modifikation des Passworts 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. (v3 S. 18 und 25) 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. (v3 S. 18 und 25)

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. (v3 S. 19)

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. (v3 S. 47 f)

Weblinks

• PHC Candidates. Kandidaten der Password Hashing Competition.
• Catena: A Memory-Consuming Password Scrambler.

Einzelnachweise

Version v1: http://dblp.uni-trier.de/db/journals/iacr/iacr2013.html#ForlerLW13 https://eprint.iacr.org/eprint-bin/getfile.pl?entry=2013/525&version=20130830:084400&file=525.pdf Christian Forler Stefan Lucks Jakob Wenzel: Catena: A Memory-Consuming Password Scrambler

Version v2: https://eprint.iacr.org/eprint-bin/getfile.pl?entry=2013/525&version=20140919:165002&file=525.pdf Christian Forler Stefan Lucks Jakob Wenzel: Catena: A Memory-Consuming Password-Scrambling Framework

Version v3: https://password-hashing.net/submissions/Catena-v3.tar.gz Christian Forler Stefan Lucks Jakob Wenzel: The Catena Password-Scrambling Framework. 2nd Round of the Password Hashing Competition (PHC) (pdf)