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

Date: received 27 Mar 2016

Contact author: martin gabris22 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160330:075546 (All versions of this report)

Short URL: ia.cr/2016/337

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]