Skip to Main content Skip to Navigation
Conference papers

Cache Timing Analysis of RC4

Thomas Chardin 1 Pierre-Alain Fouque 2 Delphine Leresteux 3
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : In this paper we present an attack that recovers the whole internal state of RC4 using a cache timing attack model first introduced in the cache timing attack of Osvik, Shamir and Tromer against some highly efficient AES implementations. In this model, the adversary can obtain some information related to the elements of a secret state used during the encryption process. Zenner formalized this model for LFSR-based stream ciphers. In this theoretical model inspired from practical attacks, we propose a new state recovery analysis on RC4 using a belief propagation algorithm. The algorithm works well and its soundness is proved for known or unknown plaintext and only requires that the attacker queries the RC4 encryption process byte by byte for a practical attack. Depending on the processor, our simulations show that we need between 300 to 1,300 keystream bytes and a computation time of less than a minute.
Document type :
Conference papers
Complete list of metadata
Contributor : Brigitte Briot <>
Submitted on : Wednesday, January 28, 2015 - 10:09:28 AM
Last modification on : Tuesday, May 4, 2021 - 2:06:02 PM

Links full text




Thomas Chardin, Pierre-Alain Fouque, Delphine Leresteux. Cache Timing Analysis of RC4. ACNS 2011 - 9th International Conference Applied Cryptography and Network Security, Jun 2011, Nerja, Spain. pp.110-129, ⟨10.1007/978-3-642-21554-4_7⟩. ⟨hal-01110389⟩



Record views