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).[1] 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.[2]
Varianten
Salsa20 Core ist der Kern verschiedener Hashfunktionen und Stromverschlüsselungen.
- Salsa20 oder Snuffle 2005 ist eine Familie von 256-Bit-Stromverschlüsselungen:[3]
- 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.[4]
- XSalsa20 ist eine Variante mit erweitertem Nonce (192 Bit statt 64 Bit).[5]
- ChaCha oder Snuffle 2008 sind Varianten von Salsa20.[6] Die Hashfunktion BLAKE basiert auf ChaCha.[7]
Salsa10[8] ist der 2004 eingeführte Vorläufer von Salsa20.
Komponenten von Salsa20 werden auch in der Kompressionsfunktion Rumba20[9] 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 2111, einer Datenkomplexität von 221 und einer Erfolgsquote von 50 % gebrochen werden konnte.[10] 2012 wurde dieser Angriff von Shi et al. noch einmal verbessert.[11] 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 2109, Platzkomplexität 219. 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“).[12]
- ChaCha6 (128-Bit-Schlüssel): Zeitkomplexität 2105, Platzkomplexität 228.
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
- The eSTREAM Portfolio (PDF, 118 kB).
- D. J. Bernstein: Snuffle 2005: the Salsa20 encryption function (PDF, 98 kB).
- D. J. Bernstein: The Salsa20 family of stream ciphers (PDF, 176 kB).
- Colin Percival: Stronger Key Derivation via Sequential Memory-Hard Functions (PDF, 207 kB).
- D. J. Bernstein: Extending the Salsa20 nonce (PDF, 349 kB).
- D. J. Bernstein: ChaCha, a variant of Salsa20.
- SHA-3 proposal BLAKE.
- D. J. Bernstein The Salsa10 hash function.
- D. J. Bernstein: The Rumba20 compression function (PDF, 168 kB).
- 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).
- 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.
- Daniel J. Bernstein: Notes on the Salsa20 key size S. 2 (PDF, 32 kB).