2008 | OriginalPaper | Buchkapitel
New State Recovery Attack on RC4
verfasst von : Alexander Maximov, Dmitry Khovratovich
Erschienen in: Advances in Cryptology – CRYPTO 2008
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The stream cipher RC4 was designed by R. Rivest in 1987, and it is a widely deployed cipher. In this paper we analyse the class RC4-
N
of RC4-like stream ciphers, where
N
is the modulus of operations, as well as the length of internal arrays. Our new attack is a state recovery attack which accepts the keystream of a certain length, and recovers the internal state. For the reduced RC4-100, our attack has total complexity of around 2
93
operations, whereas the best previous attack (from Knudsen et al.) needs 2
236
of time.
The complexity of the attack applied to the original RC4-256 depends on the parameters of specific states (patterns), which are in turn hard to discover. Extrapolated parameters from smaller patterns give us the attack of complexity about 2
241
, and it is much smaller than the complexity of the best known previous attack 2
779
. The algorithm of the new attack was implemented and verified on small cases.