Cryptography Reference
In-Depth Information
5.6.4 Further Biases when Pseudo-Random Index Is Known
In all the biases discussed in this chapter so far, it is assumed that the
value of the pseudo-random index j
G
is unknown. In this section, we are
going to show that the biases in the permutation at some stage of the PRGA
propagates to the keystream at a later stage, if the value of the index j
G
at
the earlier stage is known.
Suppose that we know the value j
τ
of j
G
after the round τ in the PRGA.
With high probability, the value V at the index j
τ
would remain there, until
j
τ
is touched by the deterministic index i
G
for the first time after a few more
rounds depending on what was the position (τ mod N) of i
G
at the τ-th stage.
This immediately leaks V in keystream. More importantly, if the value V is
biased to the secret key bytes, then that information will be leaked too.
Formally, let
P(S
τ
[j
τ
] = V ) = η
τ
for some V . j
τ
would be touched by i
G
in round r, where
r = τ + (j
τ
−τ mod N) or τ + (N −τ mod N) + j
τ
depending on whether
j
τ
> τ mod Norj
τ
≤τ mod N
respectively. By Lemma 5.6.1, we have
r−τ−1
−
1
N
N −1
N
1
N
.
P(S
r−1
[j
τ
] = V ) = η
τ
+
Now, Lemma 5.6.3 immediately gives
r−τ−1
−
1
N
1
N
N −1
N
1
N
P(z
r
= r−V ) =
1 + η
τ
+
.
For some special V 's, the form of η
τ
may be known. In that case, it would
be advantageous to probe the values of j
G
at particular rounds. For instance,
according to Corollary 5.6.2, after the (τ−1)-th round of the PRGA, S
τ−1
[τ]
is biased to the linear combination f
τ
of the secret key bytes with probability
2
3
[
τ(τ+1)
2
+N
]
τ−1
−
1
N
N −τ
N
N −1
N
1
N
N −1
N
1
N
.
4
5
η
τ
≈
+
+
At round τ, f
τ
would move to the index j
τ
due to the swap, and hence
S
τ
[j
τ
] would be biased to f
τ
with the same probability. So, the knowledge
of j
τ
would leak information about f
τ
in round
r = τ + (j
τ
−τ mod N) or τ + (N −τ mod N) + j
τ
