Paper 2016/337

State recovery of RC4 and Spritz Revisited

Martin Gábriš and Martin Stanek

Abstract

We provide an improved complexity analysis of backtracking-based state recovery attacks on RC4 and Spritz. Comparing new estimates with known results on Spritz, our analysis shows a significantly lower complexity estimate for simple state recovery attack as well as special state recovery attack. We validated the estimates by performing experiments for selected feasible parameters. We also propose a prefix check optimization for simple state recovery attack on Spritz. We believe that the simple state recovery attack with this optimization and so-called ``change order'' optimization inspired by Knudsen et al. attack on RC4 constitutes currently the best state recovery attack on Spritz (when no special state is observed).

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
RC4Spritzcryptanalysisstate recoverycomplexity
Contact author(s)
martin gabris22 @ gmail com
History
2016-03-30: received
Short URL
https://ia.cr/2016/337
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/337,
      author = {Martin Gábriš and Martin Stanek},
      title = {State recovery of RC4 and Spritz Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2016/337},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/337}},
      url = {https://eprint.iacr.org/2016/337}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.