Cryptography Reference
In-Depth Information
After 2
n
more steps, i
r+2
n+1
= i
r
and
j
r+2
n+1
= j
r
+ 2.2
n−1
= j
r
(mod 2
n
).
Hence z
r+2
n+1
= z
r
.
At any point of time r, i
r
is always known. In the known plaintext attack
model, z
r
is also assumed to be known. Thus, there are four unknowns,
namely, j
r
,S
G
[i
r
],S
G
[j
r
],(S
G
)
−1
[z
r
]. For any three of these, the fourth one
can be calculated as follows.
j
r
= (S
G
)
−1
[(S
G
)
−1
[z
r
]−S
G
[i
r
]] (5.5)
S
G
[i
r
] = (S
G
)
−1
[z
r
]−S
G
[j
r
] (5.6)
S
G
[j
r
] = (S
G
)
−1
[z
r
]−S
G
[i
r
] (5.7)
(S
G
)
−1
[z
r
] = S
G
[i
r
] + S
G
[j
r
] (5.8)
The algorithm to recover S
G
works as follows. Initially, we guess a small
subset of the values of S
G
. As r progresses, Equations (5.5) to (5.8) are used
to derive additional entries of S
G
. If a contradiction arises, then the initial
guess was wrong. We repeat this process for all possible guesses.
At the beginning, i
0
and j
0
are both known (0). If we guess the first
x values of S
G
, then j
0
through j
x−1
becomes known. For each of these,
Equations (5.7) and (5.8) can be used to determine more values of S
G
. Once i
r
goes past x, we lose the knowledge of j
r
, if S
G
[x+1] is not known. We discard
the next values of z
r
until we can use Equation (5.5) to discover j
r
again using
a known S
G
[i
r
]. Once j
r
is recovered, we can then work backward using
Equation (5.6) to recover more entries of S
G
. Once the backward movement
is finished, we continue as we started, using Equations (5.7) and (5.8) to
discover values of S
G
until we lose the value of j
r
.
A modification of the above strategy allows one to attack the real RC4.
In the modified version, no values of S
G
are guessed initially. A permutation
entry is guessed only when it is needed. For times r = 1,2,..., if S
r1
[i
r
] or
S
r−1
[j
r
] have not already been assigned values in a previous time t < r, we
need to choose a value v for S
r−1
[i
r
], 0 ≤ v < 2
n
, derive j
r
and then choose
S
r−1
[j
r
]. The next update of the RC4 PRGA is then followed. We proceed in
such a way that at each time r, an output word is generated with the property
that it matches with the actual z
r
that is observed. This imposes the following
three restrictions on the possible choices for S
r1
[i
r
] and S
r−1
[j
r
].
1. Since S
G
is a permutation, every new value assigned to S
r1
[i
r
] or
S
r−1
[j
r
] must be different from a value already assigned to some other
entry in S
G
.
2. If the known z
r
differs from all entries previously fixed in S
G
, then
t
r
= S
r
[i
r
] + S
r
[j
r
] must also differ from all index positions which
have already been assigned values. If this condition is met, then we set
S
r
[i
r
] = z
r
, otherwise we have a contradiction in the search.
