Cryptography Reference
In-Depth Information
Block B
1
:
Block B
2
:
Block B
3
:
P unchanged,
P updated to P
N
, P
N
unchanged,
Q updated.
Q unchanged.
Q updated to Q
N
.
(Q denotes the updated array)
Block B
4
, that is not shown in the diagram, would only be used for verifying
whether the reconstruction is correct or not. Algorithm 10.5.1 (called Recon-
structState) takes as inputs the 512 words of the array P and (assuming that
the 2048 keystream words corresponding to the four blocks B
1
, B
2
, B
3
and B
4
are known) produces as output 512 words of the array Q
N
. Since the update
of an array depends only on itself, it turns out that from block B
3
onwards
the complete state becomes known.
In B
1
and B
3
, Q is updated. Let Q denote the updated array after the
completion of block B
1
and let Q
N
be the new array after Q is updated in
block B
3
. In B
1
, P remains unchanged and in B
2
, it is updated to P
N
. Let s
b,i
denote the i-th keystream word produced in block B
b
, 1 ≤ b ≤ 4, 0 ≤ i≤ 511.
The update of P (or Q) depends only on itself, i.e.,
8
<
P[i] + g
1
(P[509 + i],P[502 + i],P[i + 1]), for 0 ≤i ≤ 2;
P[i] + g
1
(P
N
[i−3],P[502 + i],P[i + 1]), for 3 ≤i ≤ 9;
P[i] + g
1
(P
N
[i−3],P
N
[i−10],P[i + 1]), for 10 ≤ i≤ 510;
P[i] + g
1
(P
N
[i−3],P
N
[i−10],P
N
[i−511]), for i = 511.
(10.14)
Thus, if one knows the 512 words of P (or Q) corresponding to any one block,
then one can easily derive the complete P (or Q) array corresponding to any
subsequent block.
Consider that the keystream words s
b,i
, 1 ≤ b ≤ 4, 0 ≤ i ≤ 511, are
observable. A state reconstruction problem can be formulated as follows.
P
N
[i] =
:
Given the partial state information P[0...511],
reconstruct the complete state (P
N
[0...511],Q
N
[0...511]).
Since the update of each of P and Q depends only on P and Q respectively,
once we determine P
N
and Q
N
, we essentially recover the complete state
information for all subsequent steps.
10.5.2 State Reconstruction Strategy
The state reconstruction proceeds in five phases. The First Phase would
be to determine P
N
from P using (10.14).
The keystream generation of block B
2
follows the equation
h
1
(P[500 + i])⊕P
N
[i], for 0 ≤i ≤ 11;
h
1
(P
N
[i−12])⊕P
N
[i], for 12 ≤ i≤ 511.
s
2,i
=
(10.15)
Since h
1
(x) = Q[x
(0)
] + Q[256 + x
(2)
], we can rewrite (10.15) as
Q[l
i
] + Q[u
i
] = s
2,i
⊕P
N
[i],
(10.16)
