## Cryptology ePrint Archive: Report 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).

Category / Keywords: secret-key cryptography / RC4, Spritz, cryptanalysis, state recovery, complexity