Cryptography Reference
In-Depth Information
uniformly randomly distributed, the probability that the set of M random
keystream bytes obtained by running PRGA on P would match with the M
keystream bytes in hand (obtained by running PRGA on S
0
) is
N
M
. With
N = 256, a small value of M such as M = 8 yields a negligibly small value
2
64
(close to 0) of this probability. Thus, running PRGA on P for only 8 rounds,
with almost certainty one would be able to determine if that permutation
indeed was the original permutation S
0
.
Now, suppose P is a resolved permutation. So for any arbitrary element
in P, we know what is its successor. Starting from any element u as the first
element, if we write all the elements in sequence, then we get a permutation
Q = < u,suc
1
(u),suc
2
(u),...,suc
N−1
(u) >
such that
P = rot
n
(Q)
for some n, 0 ≤ n ≤ N −1.
We run PRGA starting with the initial permutation once as Q, next as
rot
1
(Q), next as rot
2
(Q), and so on, until the first 8 keystream bytes match
with the observed keystream bytes in hand. With at most N such trials, the
entire permutation can be constructed.
The above Lemma immediately gives an algorithm ConstructPerm to con-
struct S
0
from a partially resolved permutation.
Input: A partially resolved permutation P in the form of an array
Next.
Output: The original permutation S
0
before the PRGA begins.
Set m = the number of unassigned (i.e., −1) entries in the array
1
Next;
for each possible assignment of those m entries do
2
Get the corresponding resolved permutation T;
3
for n = 0 to N −1 do
4
Run StuckPRGA starting with rot
n
(T) as the initial
5
permutation for 8 rounds and generate the first 8 keystream
bytes;
if the above 8 keystream bytes match with the first 8
6
keystream bytes obtained in the actual execution of
StuckPRGA then
Return S
0
= rot
n
(T);
7
end
end
end
Algorithm 8.4.4: ConstructPerm
The procedures PartResolvePerm, ResolveConflicts and ConstructPerm
can be combined to devise an e
cient algorithm InvertStuckPRGA to retrieve
