Paper 2013/178

Cryptanalysis of RC4(n,m) Stream Cipher

Mohammad Ali Orumiehchiha, Josef Pieprzyk, Elham Shakour, and Ron Steinfeld

Abstract

$RC4(n,m)$ is a stream cipher based on RC4 and is designed by G. Gong $et ~al.$. It can be seen as a generalization of the famous RC4 stream cipher designed by Ron Rivest. The authors of $RC4(n,m)$ claim that the cipher resists all the attacks that are successful against the original RC4. The paper reveals cryptographic weaknesses of the $RC4(n,m)$ stream cipher. We develop two attacks. The first one is based on non-randomness of internal state and allows to distinguish it from a truly random cipher by an algorithm that has access to $2^{4\cdot n}$ bits of the keystream. The second attack exploits low diffusion of bits in the KSA and PRGA algorithms and recovers all bytes of the secret key. This attack works only if the initial value of the cipher can be manipulated. Apart from the secret key, the cipher uses two other inputs, namely, initial value and initial vector. Although these inputs are fixed in the cipher specification, some applications may allow the inputs to be under the attacker control. Assuming that the attacker can control the initial value, we show a distinguisher for the cipher and a secret key recovery attack that for the \textit{L}-bit secret key, is able to recover it with about $(L/n)\cdot 2^n $ steps. The attack has been implemented on a standard PC and can reconstruct the secret key of RC(8,32) in less than a second.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
$RC4(nm)$ Stream cipherCryptanalysisKey Recovery AttackDistinguishing AttackRC4-like cipherWeak KeysWeak States
Contact author(s)
orumiehchi @ gmail com
History
2013-04-01: received
Short URL
https://ia.cr/2013/178
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/178,
      author = {Mohammad Ali Orumiehchiha and Josef Pieprzyk and Elham Shakour and Ron Steinfeld},
      title = {Cryptanalysis of RC4(n,m) Stream Cipher},
      howpublished = {Cryptology ePrint Archive, Paper 2013/178},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/178}},
      url = {https://eprint.iacr.org/2013/178}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.