2011 | OriginalPaper | Buchkapitel
Some Combinatorial Results towards State Recovery Attack on RC4
verfasst von : Apurba Das, Subhamoy Maitra, Goutam Paul, Santanu Sarkar
Erschienen in: Information Systems Security
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
A stream cipher has an unobservable internal state that is updated in every step and a keystream output (bit or word) is generated at every state transition. State recovery attack on stream cipher attempts to recover the hidden internal state by observing the keystream. RC4 is a very widely used commercial stream cipher that has a huge internal state. No known state recovery attack on RC4 is feasible in practice and the best so far has a complexity of 2
241
(Maximov et al., CRYPTO 2008). In this paper, we take a different approach to the problem. RC4 has a secret index
j
of size one byte. We perform a combinatorial analysis of the complexity of RC4 state recovery under the assumption that the values of
j
are known for several rounds. This assumption of knowledge of
j
is reasonable under some attack models, such as fault analysis, cache analysis, side channel attacks etc. Our objective is not to devise an unconditional full state recovery attack on RC4, but to investigate how much information of
j
leaks how much information of the internal state. In the process, we reveal a nice combinatorial structure of RC4 evolution and establish certain interesting results related to the complexity of state recovery.