Cryptography Reference
In-Depth Information
5.5.1 Results for Any Arbitrary Secret Key
Using Theorem 5.3.1 and Proposition 3.1.1, one can prove (Theorem 5.5.2)
that for any arbitrary key, the first byte of the keystream output is significantly
biased to the first three bytes of the secret key, thus revealing a weakness of
the KSA. This result first appeared in [131].
We need the following technical result that will be used in the proof of
Theorem 5.5.2.
Proposition 5.5.1. P(S 1 [2] = K[0] + K[1] + K[2] + 3) ≈ φ N .
Proof: As in the KSA, the index j G of the PRGA is assumed to take
values uniformly at random. During the first round of the PRGA, i 1 takes
the value 1 and j 1 takes the value S 0 [1]. Thus the index 1 is always involved
in the first swap. The other index involved in the first swap depends on the
value of S 0 [1]. Let
f(K) = K[0] + K[1] + K[2] + 3.
Recall from item 2 of Corollary 3.1.2 that
N
S 0 [2] = f(K)
N −1
N
P
.
Case I: After the KSA, S 0 [2] = f(K), and there is no swap involving index
2 in the first round of the PRGA. The contribution of this part is
N
N −1
N
1− 1
N
S 0 [2] = f(K)
P(S 0 [1] = 2) =
P
.
Case II: Following the KSA, S 0 [2] = f(K), and f(K) comes into index 2
from index 1 by the swap in the first round of the PRGA. The contri-
bution of this part is
S 0 [2] = f(K)
S 0 [1] = f(K),S 0 [1] = 2
P
P
S 0 [2] = f(K)
S 0 [1] = 2)P(f(K) = 2
= P
P
1−
N
N −1
N
1
N 2 .
Adding the above two contributions, we get
N
N −1
N
1− 1
N
1
N 2
1
N 2
S 1 [2] = f(K)
P
+
= φ N .
Search WWH ::




Custom Search