Salsa20

Salsa20 (auch Snuffle 2005) ist eine Stromverschlüsselung, die 2005 von Daniel J. Bernstein entwickelt wurde. Im europäischen Projekt eSTREAM ist die auf 12 Runden reduzierte Version Salsa20/12 einer der Finalisten (Profil 1 – Software-Anwendungen). Salsa20 ist frei von Patenten.

Entstehung

Daniel J. Bernstein entwickelte Snuffle 2005 als Antwort auf die früheren Versuche der USA, kryptographische Publikationen zu beschränken. Von den Beschränkungen waren Hashfunktionen ausgenommen; mit Snuffle 2005 wurde gezeigt, dass eine starke Verschlüsselung auch mittels Hashfunktionen vorgenommen werden kann.

Varianten

Salsa20 Core ist der Kern verschiedener Hashfunktionen und Stromverschlüsselungen.

• Salsa20 oder Snuffle 2005 ist eine Familie von 256-Bit-Stromverschlüsselungen:
  • Salsa20/20 mit 20 Runden ist als Standard gedacht.
  • Salsa20/12 mit 12 Runden für zeitkritische Anwendungen war Finalist im eSTREAM-Projekt, einem europäischen Auswahlverfahren für Stromverschlüsselungen.
  • Salsa20/8 mit 8 Runden für zeitkritische Anwendungen wird in der Schlüsselableitungsfunktion scrypt benutzt.
• XSalsa20 ist eine Variante mit erweiterter Nonce (192 Bit statt 64 Bit).
• ChaCha oder Snuffle 2008 sind Varianten von Salsa20. Die Hashfunktion BLAKE basiert auf ChaCha.

Salsa10 ist der 2004 eingeführte Vorläufer von Salsa20.

Komponenten von Salsa20 werden auch in der Kompressionsfunktion Rumba20 benutzt.

Design

Salsa20 beruht auf wenigen einfachen Operationen und ist damit ähnlich aufgebaut wie die Verschlüsselungsfunktionen XTEA und IDEA. Durch das konservative Design wird eine gute und konstante Software-Performance auf vielen CPUs und eine weitgehende Resistenz gegen einige Seitenkanalattacken (time-attacks) erreicht. Der Kern besteht aus einer Funktion, die Schlüssel, Nonce und Zähler auf einen 64-Byte-Block abbildet. Die Funktion besteht aus einer langen Verkettung von nur drei Operationen: 32-Bit-Addition, 32-Bit-XOR, 32-Bit-Rotation (mit konstanten Abständen). Für die Stromverschlüsselung wird das Ergebnis der Funktion im Counter Mode benutzt und mit dem Klartext exklusiv-Oder-verknüpft (XOR). Die empfohlene Schlüssellänge beträgt 256 Bit, kürzere Schlüssel sind jedoch möglich. Salsa20 hat eine kompakte Implementierung, ist schnell und Speicher-schonend.

Sicherheit

In einem neuen Verfahren, basierend auf den probabilistic neutral bits (PNBs), stellten Aumasson et al. 2008 einen Angriff auf Salsa20/7, Salsa20/8, ChaCha6, ChaCha7 und Rumba3 vor, in dem unter anderem Salsa20/7 (128-Bit-Schlüssel) mit einer Zeitkomplexität von 2¹¹¹, einer Datenkomplexität von 2²¹ und einer Erfolgsquote von 50 % gebrochen werden konnte. 2012 wurde dieser Angriff von Shi et al. noch einmal verbessert. Die besten Kryptoanalysen für die rundenreduzierten Varianten von Salsa20 und ChaCha sind demnach (Stand: September 2014):

• Salsa20/7 (128-Bit-Schlüssel): Zeitkomplexität 2¹⁰⁹, Platzkomplexität 2¹⁹. Zur Veranschaulichung: der Superrechner Roadrunner bräuchte ungefähr 20.580.831.662 Jahre dafür und müsste außerdem für frei gewählte Klartexte Zugang zu den entsprechenden Geheimtexten haben (Chosen-Plaintext-Attacke). Unberücksichtigt bleibt dabei jedoch die Möglichkeit der Parallelisierung; Daniel J. Bernstein, der Erfinder von Salsa20, hält daher 128-Bit-Schlüssel für „uncomfortably risky“ („beunruhigend riskant“).
• ChaCha6 (128-Bit-Schlüssel): Zeitkomplexität 2¹⁰⁵, Platzkomplexität 2²⁸.

Weblinks

• D. J. Bernsteins Seite zu Salsa20 (englisch)
• eSTREAM Portfolio zu Salsa20/12 (englisch)
• S. Josefsson: The Salsa20 Stream Cipher for Transport Layer Security draft-josefsson-salsa20-tls-02 (englisch)

Einzelnachweise

1. The eSTREAM Portfolio (PDF, 118 kB).
2. D. J. Bernstein: Snuffle 2005: the Salsa20 encryption function (PDF, 98 kB).
3. D. J. Bernstein: The Salsa20 family of stream ciphers (PDF, 176 kB).
4. Colin Percival: Stronger Key Derivation via Sequential Memory-Hard Functions (PDF, 207 kB).
5. D. J. Bernstein: Extending the Salsa20 nonce (PDF, 349 kB).
6. D. J. Bernstein: ChaCha, a variant of Salsa20.
7. SHA-3 proposal BLAKE.
8. D. J. Bernstein The Salsa10 hash function.
9. D. J. Bernstein: The Rumba20 compression function (PDF, 168 kB).
10. Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, and Christian Rechberger: New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba. Cryptology ePrint Archive: Report 2007/472 (englisch).
11. Zhenqing Shi, Bin Zhang, Dengguo Feng, Wenling Wu: Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha. In: Information Security and Cryptology – ICISC 2012. Springer Berlin Heidelberg 2013. ISBN 978-3-642-37681-8, S. 337–351.
12. Daniel J. Bernstein: Notes on the Salsa20 key size S. 2 (PDF, 32 kB).