Cryptography Reference
In-Depth Information
• is exactly the subarray (e.g., at indices y,y + 1,y + 2,...) of the initial
permutation (in most of the cases), or
• is the subarray (e.g., at indices y,y + 1,y + 3,y + 4,...) of the initial
permutation with a jump in the initial permutation (in very few cases).
Input: Scrambled permutation array S[0...N −1], output of KSA.
Output: Pseudo-random keystream bytes z.
Initialization:
i = j = 0;
Output Keystream Generation Loop:
i = i + 1;
j = x;
Swap(S[i], S[j]);
t = S[i] + S[j];
Output z = S[t];
Algorithm 8.4.1: StuckPRGA
For the remainder of this section we assume, without loss of generality,
that
S
0
= < a
0
,a
1
,a
2
,...,a
N−1
> .
The subscripts in a
y
's follow arithmetic modulo N. For example, a
−y
, a
N−y
and in general a
ρN−y
for any integer ρ represent the same element. Our goal
is to recover < a
0
,a
1
,a
2
,...,a
N−1
> from the faulty keystream.
8.4.1 Analysis of StuckPRGA
We begin with a few definitions that will be needed in the subsequent
analysis.
Definition 8.4.1. (Run) A run of the RC4 PRGA is defined to be a set of
any N consecutive rounds of keystream output byte generation during which
the deterministic index i
G
takes each value in {0,...,N −1} exactly once.
Definition 8.4.2. (Successor) Given a permutation P of size N, the n-
th successor of an element u in P, denoted by suc
n
(u), is defined to be the
element which appears n locations after u, if we move from left to right in P
in a circular fashion. If P = < b
0
,b
1
,b
2
,...,b
N−1
>, then suc
n
(b
y
) = b
y+n
.
Definition 8.4.3. (Rotated Permutation) Given a permutation P of
size N, the n-rotated permutation, denoted by rot
n
(P), is defined to be
the permutation obtained by circularly right-shifting P by n positions.
If
P = < b
0
,b
1
,b
2
,...,b
N−1
>, then
rot
n
(P) = < b
n
,b
n+1
,...,b
N−1
,b
0
,b
1
,...,b
n−2
,b
n−1
> .
