Cryptography Reference
In-Depth Information
5.8 State Recovery from Keystream
RC4 can be completely broken if one can reconstruct the permutation
S G by observing the keystream output bytes. Such attacks are called state
recovery attacks.
The RC4 state consists of two 8-bit indices i and j and a permutation of 256
possible 8-bit elements. Thus, the size of the state space is 2 8 !×(2 8 ) 2 ≈ 2 1700 ,
making the exhaustive search completely infeasible.
5.8.1 Partial Recovery Using Predictive States
The notion of fortuitous state was introduced in [51, Section 5]. The RC4
state in which only a consecutive permutation elements are known and only
those a elements participate in producing the next a successive keystream
bytes, is called a fortuitous state of length a. The authors analyzed these
special states to demonstrate that sometimes the attacker may be able to
determine portions of the internal state by observing the keystream with non-
trivial probability.
In [110, Chapter 2], Mantin generalizes the notion of fortuitous states into
three wider classes as follows.
1. b-Predictive a-States: A state A = (S G ,i G ,j G ) is called an a-state, if
only a elements of S G are known. An a-state A is called b-predictive, if
it can predict the outputs of b consecutive rounds.
2. Profitable States: An a-state A is called weak a-profitable, if all the
states compatible with A have the same sequence of j G 's during the
next a rounds. Further, if these a values of j G lie in the interval [i G +
1,...,i G + a], then A is called a-profitable.
3. Useful States: An RC4 state (S G ,i G ,j G ) is called useful if S G [i G ] +
S G [j G ] = i G .
Note that every fortuitous state of length a is an a-predictive a-state, but
the converse is not true. Also, it is pointed out in [110, Chapter 2] that
though the profitable states occur more frequently and they can be stored
more e ciently than the fortuitous states of the same order, an attack based
on a single profitable state takes significantly more time than the time of a
similar attack based on a single fortuitous state. Interestingly, the useful states
are the origin of the glimpse bias discovered by Jenkins [78] (see Theorem 5.2).
A sequence of a useful states provides 2a indications to entries in S G .
As already mentioned, an a-predictive a-state may or may not be a for-
tuitous state of length a. In [138], analysis of non-fortuitous predictive states
of length a is performed in great detail. This analysis reveals that if φ a and
Search WWH ::




Custom Search