Cryptography Reference
In-Depth Information
11
E(m
r
) = 8(1−
43
512
)
M
+ 4(1−
42
512
)
M
.
Substituting M by its theoretical mean estimate 443 as well as by its
empirical mean estimate 408 yields E(Y ) ≈ 0. In fact, for any M > 200, the
expression (1 −
43
Thus, E(Y ) =
r=0
512
)
M
for E(Y ) becomes vanishingly small.
The experimental data also supports that in every instance, none of the words
Q[500],Q[501],...,Q[511] remains unknown.
Next, the following result can be used to determine the entire Q
N
array.
512
)
M
+ 4 (1 −
42
Theorem 10.5.8. Suppose the complete array P
N
and the 12 words Q[500],
Q[501], ..., Q[511] from the array Q are known. Then the entire Q
N
array
can be reconstructed in a time complexity linear in the size of Q.
Proof: Following the notation in Section 10.5.1, the equation for the
keystream generation of the first 12 steps of block B
3
is s
3,i
= h
2
(Q[500 +
i])⊕Q
N
[i], 0 ≤ i≤ 11. Expanding h
2
(.), we get, for 0 ≤ i ≤ 11,
P
N
256 + (Q[500 + i])
(2)
(Q[500 + i])
(0)
Q
N
[i] = s
3,i
⊕
+ P
N
.
Thus, we can determine
Q
N
[0],Q
N
[1],...Q
N
[11]
from
Q[500],Q[501],...Q[511].
Now, applying Theorem 10.5.6 on these first 12 words of Q
N
, we can determine
all the words of Q
N
in linear time (in size of Q).
Applying Theorem 10.5.8 constitute the Fourth Phase of the algorithm.
After Q
N
is derived, its correctness needs to be verified. For this, one can
update P
N
as in block B
4
and generate 512 keystream words (with this P
N
and the derived Q
N
). If the generated keystream words entirely match with
the observed keystream words of block B
4
, then the guess can be assumed to
be correct. This verification is the Fifth (and final) Phase of the algorithm.
If a mismatch is found, the procedure needs to be repeated with the next
guess, i.e., with another possible value in [0,2
32
−1] of the word Q[y
1
].
After Q
N
is correctly determined, the words of the Q array for all the
succeeding blocks can be deterministically computed from the update rule for
Q.
The above discussion is formalized in Algorithm 10.5.1, called Reconstruct-
State.
Theorem 10.5.9. The data complexity of Algorithm 10.5.1 is 2
16
and its
time complexity is 2
42
.
Proof: For the First Phase, we do not need any keystream word. For
each of the Second, Third, Fourth and Fifth Phases, we need a separate block
