Cryptography Reference
In-Depth Information
Old P array: P[0] P[1] ... P[511]
Keystream: s
0
s
1
... s
511
Intermediate Q array: Q[0] Q[1] ... Q[511]
Keystream:
s
512
s
513
... s
1023
New P array:
P[0] P[1] ... P[511]
Keystream:
s
1024
s
1025
... s
1535
New Q array:
Q[0] Q[1] ... Q[511]
Keystream:
s
1536
s
1537
... s
2047
TABLE 10.1: Evolution of the arrays P and Q and the corresponding
keystream words.
511]) to itself, as formulated in Equations (10.1) and (10.2) of Section 10.2.
Let z
i
denote P[i⊟12] at the i-th step. From Equation (10.2), it is easy to see
that any occurrence of P[i mod 512] can be replaced by s
i
⊕h
1
(z
i
). Performing
this replacement in Equation (10.1), we get, for 10 ≤i mod 512 < 511,
⊕h
′
1
(z
i−1024
)
s
i
⊕h
1
(z
i
)
=
s
i−1024
+ g
1
s
i−3
⊕h
1
(z
i−3
),s
i−10
.
⊕h
′
1
(z
i−1023
)
⊕h
1
(z
i−10
),s
i−1023
(10.3)
Since h
1
(.) and h
′
1
(.) are related to two P arrays at two different 1024 size
blocks that act as two different S-boxes, h
1
(.) and h
′
1
(.) are treated as two
different functions.
Inside the function g
1
, there are three rotations, one XOR and one addition
and outside g
1
there is one more addition. Since the LSB of the XOR of any
number of words equals the LSB of the sum of those words, one can write
Equation (10.3) as
[s
i
]
0
⊕[s
i−1024
]
0
⊕[s
i−3
]
10
⊕[s
i−10
]
8
⊕[s
i−1023
]
23
= [h
1
(z
i
)]
0
⊕[h
′
1
(z
i−1024
)]
0
⊕[h
1
(z
i−3
)]
10
⊕[h
1
(z
i−10
)]
8
⊕[h
′
1
(z
i−1023
)]
23
.
Thus, for 1024τ + 10 ≤j < i < 1024τ + 511,
[s
i
]
0
⊕[s
i−1024
]
0
⊕[s
i−3
]
10
⊕[s
i−10
]
8
⊕[s
i−1023
]
23
= [s
j
]
0
⊕[s
j−1024
]
0
⊕[s
j−3
]
10
⊕[s
j−10
]
8
⊕[s
j−1023
]
23
, if and only if H(ξ
i
) =
H(ξ
j
), where
H(ξ
i
) = [h
1
(z
i
)]
0
⊕[h
′
1
(z
i−1024
)]
0
⊕[h
1
(z
i−3
)]
10
⊕[h
1
(z
i−10
)]
8
⊕[h
′
1
(z
i−1023
)]
23
.
Here ξ
i
= (z
i
,z
i−1024
,z
i−3
,z
i−10
,z
i−1023
) is an 80-bit input and H(.) can be
considered as a random 80-bit-to-1-bit S-box.
The following result gives the collision probability for a general random
m-bit-to-n-bit S-box.
Theorem 10.3.1. Let H be an m-bit-to-n-bit S-box and all those n-bit ele-
ments are randomly generated, where m ≥n. Let x
1
and x
2
be two m-bit ran-
dom inputs to H. Then H(x
1
) = H(x
2
) with probability 2
−m
+ 2
−n
−2
−m−n
.
