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 $2^{1400}$, 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.
Category / Keywords: secret-key cryptography / Spritz, RC4, stream cipher, state recovery, cryptanalysis Original Publication (in the same form): LatinCrypt 2015, LNCS 9230 proceedings Date: received 25 Aug 2015 Contact author: Ralph Ankele 2015 at live rhul ac uk Available format(s): PDF | BibTeX Citation Version: 20150826:145810 (All versions of this report) Short URL: ia.cr/2015/828 Discussion forum: Show discussion | Start new discussion