Bias Analysis of a Certain Problem with Applications to E0 and Shannon Cipher - Information Security and Cryptology-ICISC 2010 - page 22

by the keystream generation function. According to [7], the exact bias δ 0 of
M ( c t 0 ,...,c t 0 +25 ) can be calculated. From this, the total bias δ of the sum of

w such terms, which is

·

w

( c t 0 + p i ,...,c t 0 + p i +25 ) , M · (13)

i =1

was deduced in [7] to be δ = δ 0 by the Piling-up lemma. Therefore, by Eq.(12),
[7] concluded that E0 keystream output has a bias of δ 0 , which was then used
to mount the best known attacks on one-level E0 [7].

3.1 Our Analysis

Note that the above application of the Piling-up lemma to deduce δ = δ 0 is

based on the assumption that with i =1 , 2 , 3 , 4,

x t 0 + p 1 +1 ,...,x t 0 + p 1 +24 ,
x t 0 + p 2 +1 ,...,x t 0 + p 2 +24 ,
.
x t 0 + p w +1 ,...,x t 0 + p w +24 ,

together with the FSM states at t = t 0 + p 1 +1 ,t 0 + p 2 +1 ,...,t 0 + p w +1 all are
independent. Furthermore, it was formally proved in [7] that for w = 1 this is
true assuming the initial states are random and uniformly distributed. In fact,
we can check the following equality always holds:

w w w

x t 0 + p j +1 , x t 0 + p j +2 ,..., x t 0 + p j +24 = 0 , (14)

j =1 j =1 j =1

for i =1 , 2 , 3 , 4, where 0 denotes the all zero vector. This implies that the above
independence assumption is wrong and the Piling-up lemma is not appropriate
to use to deduce the bias δ of (13). On the other hand, in order to apply Corollary
1 in Section 2 and calculate the real bias δ of (13), we can use (14) to deduce
the relevant distribution D as follows.
We let D represents the distribution of the 4 24 + 4 = 100 bit vector, in

which, the least significant 4 bits consists of the XOR of the FSM state at
t = t 0 + p i +1 with i =1 ,...,w , and the most significant 96 bits consists of the
XOR of x t 0 + p i +1 ,..., x t 0 + p i +24 , x t 0 + p i +1 ,..., x t 0 + p i +24 , x t 0 + p i +1 ,..., x t 0 + p i +24 ,
x t 0 + p i +1 ,..., x t 0 + p i +24 at i =1 ,...,w respectively. Assuming that the FSM
states at t = t 0 + p 1 +1 ,t 0 + p 2 +1 ,...,t 0 + p w + 1 are random and uniformly
distributed, from (14) we deduce that D (0) = D (1) = D (2) =

∗

1

16 .
It is easy to know the Walsh coecients of D : D ( x ) = 1 for all x whose least
significant 4 bits are zeros (denoted by LSB 4 ( x ) = 0) and

··· = D (15) =

D ( x )=0otherwise.

Define f : GF (2) 100 → GF (2), which maps the FSM state at t = t 0 +1 and 4