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.
Type de document :
Communication dans un congrès
Javier Lopez; Gene Tsudik. ACNS 2011 - 9th International Conference Applied Cryptography and Network Security, Jun 2011, Nerja, Spain. Springer, 6715, pp.110-129, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-642-21554-4_7〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01110389
Contributeur : Brigitte Briot <>
Soumis le : mercredi 28 janvier 2015 - 10:09:28
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral

Identifiants

Collections

Citation

Thomas Chardin, Pierre-Alain Fouque, Delphine Leresteux. Cache Timing Analysis of RC4. Javier Lopez; Gene Tsudik. ACNS 2011 - 9th International Conference Applied Cryptography and Network Security, Jun 2011, Nerja, Spain. Springer, 6715, pp.110-129, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-642-21554-4_7〉. 〈hal-01110389〉

Partager

Métriques

Consultations de la notice

170