State-Recovery Analysis of Spritz

Ralph Ankele, Stefan Kölbl, Christian Rechberger

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


RC4 suffered from a range of plaintext-recovery attacks using statistical biases, which use substantial, albeit close-to-practical, amounts of known keystream in applications such as TLS or WEP/WPA. Spritz was recently proposed at the rump session of CRYPTO 2014 as a slower redesign of RC4 by Rivest and Schuldt, aiming at reducing the statistical biases that lead to these attacks on RC4.

Even more devastating than those plaintext-recovery attacks from large amounts of keystream would be state- or key-recovery attacks from small amounts of known keystream. For RC4, there is unsubstantiated evidence that they may exist, the situation for Spritz is however not clear, as resistance against such attacks was not a design goal.

In this paper, we provide the first cryptanalytic results on Spritz and introduce three different state recovery algorithms. Our first algorithm recovers an internal state, requiring only a short segment of keystream, with an approximated complexity of 21400, which is much faster than exhaustive search through all possible states, but is still far away from a practical attack. Furthermore, we introduce a second algorithm that uses a pattern in the keystream to reduce the number of guessed values in our state recovery algorithm. Our third algorithm uses a probabilistic approach by considering the permutation table as probability distribution.

All in all, rather than showing a weakness, our analysis supports the conjecture that compared to RC4, Spritz may also provide higher resistance against potentially devastating state-recovery attacks.
Original languageEnglish
Title of host publicationProgress in Cryptology – LATINCRYPT 2015 : Proceedings of the 4th International Conference on Cryptology and Information Security in Latin America
EditorsKristin Lauter, Francisco Rodríguez-Henríquez
Publication date2015
ISBN (Print)978-3-319-22173-1
ISBN (Electronic)978-3-319-22174-8
Publication statusPublished - 2015
Event4th International Conference on Cryptology and Information Security in Latin America (LATINCRYPT 2015) - Guadalajara, Mexico
Duration: 23 Aug 201526 Aug 2015
Conference number: 4


Conference4th International Conference on Cryptology and Information Security in Latin America (LATINCRYPT 2015)
Internet address
SeriesLecture Notes in Computer Science


  • Spritz
  • RC4
  • Stream cipher
  • State recovery
  • Cryptanalysis


Dive into the research topics of 'State-Recovery Analysis of Spritz'. Together they form a unique fingerprint.

Cite this