Cryptography Reference
In-Depth Information
And in that case, z reveals a
N−ρ+y
, i.e., the value at index 0 in S
ρN+y
or
equivalently the value at index N − ρ + y in the original permutation S
0
.
This proves item 1.
Of the N−1 other possible values of t, if t = y+1, then z
ρN+y
= a
N−ρ+y+1
and z
(ρ+1)N+(y+1)
= a
N−ρ+y−1
; and vice versa. This proves item 2.
If, however, t takes any of the remaining N − 2 values (other than 0 and
y + 1), then z
ρN+y
appears next to z
(ρ+1)N+(y+1)
in S
0
; and vice versa. This
proves item 3.
Note that the keystream output bytes coming from the same index in two
consecutive runs are always separated by N + 1 rounds.
Let us elaborate the pattern considered in the above Theorem. Consider
the indices of the keystream output bytes in two consecutive runs as follows.
y run ρ run ρ + 1
1 a
N−ρ
+ a
N−ρ+1
a
N−ρ−1
+ a
N−ρ
2 a
N−ρ+1
+ a
N−ρ+2
a
N−ρ
+ a
N−ρ+1
. . . ... ...
N −2 a
N−ρ−3
+ a
N−ρ−2
a
N−ρ−4
+ a
N−ρ−3
N −1 a
N−ρ−2
+ a
N−ρ−1
a
N−ρ−3
+ a
N−ρ−2
N
2a
N−ρ−1
2a
N−ρ−2
Observe that the keystream output selection indices in run ρ for y = 1 to
N −2 exactly match with those in run ρ + 1 for y = 2 to N −1 respectively.
Further, as discussed in the proof of Theorem 8.4.12, the permutations in run
ρ+ 1 for y = 2 to N−1 are right shifts of the permutations in run ρ for y = 1
to N −2 respectively except at two locations.
8.4.2 State Recovery of RC4 with StuckPRGA
The combinatorial structure identified in Theorem 8.4.12 can be exploited
to devise an e
cient algorithm PartResolvePerm for getting a partially re-
solved permutation from the faulty keystream bytes.
In this algorithm, Next[u] denotes the value that comes immediately after
the value u in the permutation S
0
. If Next[u] = −1, it means that the element
next to the element u in S
0
is not yet determined. The algorithm tallies two
consecutive runs of the PRGA and fill in the array Next by observing the
candidate pairs, i.e., the keystream output bytes that come from the same
index in the respective permutations. Due to item 2 of Theorem 8.4.12, for
some u, one may record suc
2
(u) as suc
1
(u), resulting in some conflict sets, i.e.,
candidate pairs (u,v
1
) and (u,v
2
) such that v
1
= v
2
. Then it is not known
which one of v
1
,v
2
is suc
1
(u). We keep an array Conflict to contain conflict
sets of the form {(u,v
1
),(u,v
2
)}. Each entry of Conflict consists of three
fields, namely, (i) value for storing u, (ii) first for storing v
1
and (iii) second
for storing v
2
.
