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

32-bits. Let z t denotes the 32-bit output of Shannon at time t . The following
important relation was identified and formally proved in [5]:

( z t ≪ 1) ⊕ z t +16

= f 1 ( s t +21 ⊕

s t +22 ⊕ K ) ⊕ f 2 (( s t +11 ⊕ s t +24 ) ≪ ⊕

1)

f 1 ( s t +25 ⊕ s t +26 ⊕ K ) ⊕ f 2 (( s t +15 ⊕ s t +28 ) ≪ ⊕

1)

f 2 ( s t +19 ⊕ s t +32 ) ⊕ f 2 (( s t +3 ⊕ s t +16 ) ≪ 1) , (15)

where f 1 ,f 2 : GF (2 32 ) → GF (2 32 ) are nonlinear and defined in [11], and K is

a 32-bit secret constant derived from the initialization process. Treating each
term in the right-hand sum (15) as independent ones, [5] uses Piling-up lemma
to compute the largest bias of (15) from the individual bias of each term. The
largest bias (15) was shown in [5] to be 2 − 56 . In total, 32 such equally largest
biases makes the complexity O (2 107 ) for the distinguishing attack (see [5]).

4.1 Our Analysis on Shannon Cipher and a Shannon Variant

Here, we want to analyze the influence of the dependency between the terms in
the right-hand sum (15) to the total bias. Our starting point is that (15) can be
viewed as the sum of three items, f 1 ( s t +21 ⊕ s t +22 ⊕ K ) ⊕ f 1 ( s t +25 ⊕ s t +26 ⊕ K ),

f 2 (( s t +11 ⊕ s t +24 ) ≪ 1) ⊕ f 2 (( s t +15 ⊕ s t +28 ) ≪ 1) and f 2 ( s t +19 ⊕ s t +32 ) ⊕

f 2 (( s t +3 ⊕ 1). For each item, the inputs are dependent as explained

below. The input difference to the two terms of the first item is

s t +16 ) ≪

( s t +21 ⊕ s t +22 ⊕ K ) ⊕ ( s t +25 ⊕ s t +26 ⊕ K )=( s t +21 ⊕ s t +25 ) ⊕ ( s t +22 ⊕ s t +26 ) . (16)

As the Shannon keystream output is defined as z t = s t +9 ⊕ s t +13 ⊕ f 2 ( s t +3 ⊕

s t +16 ), we have s t +9 ⊕ s t +13 = z t ⊕ f 2 ( s t +3 ⊕ s t +16 ). We rewrite (16) by

z t +12 ⊕ z t +13 ⊕ f 2 ( s t +15 ⊕ s t +28 ) ⊕ f 2 ( s t +16 ⊕ s t +29 ) (17)

Given the keystream, we consider z t +12 ⊕ z t +13 as a known value (denoted by

c t +12 ). Let D f 2 be the distribution of f 2 assuming a uniform distribution of
the input. From (17), the distribution D ( x ) of the input difference to the item
f 1 ( s t +21 ⊕ s t +22 ⊕ K ) ⊕ f 1 ( s t +25 ⊕ s t +26 ⊕ K ) can be expressed by D ( x )=

D f 2 ⊗ D f 2 ( x ⊕ c t +12 ), where ⊗

denotes convolution. Similarly, we express the
distribution D ( x ) of the input difference to the item f 2 (( s t +11 ⊕ s t +24 ) ≪
1) ⊕ f 2 (( s t +15 ⊕ s t +28 ) ≪ 1) by D ( x )= D f 2 ⊗ D f 2 (( x ≫ 1) ⊕ α t +2 ), where
α t +2 = z t +2 ⊕ z t +15 is known from the keystream.
For the bias pattern (also called output mask) 0 x 410 a 4 a 1 used in [5], we use
Corollary 1 to compute the bias for f 1 ( s t +21 ⊕ s t +22 ⊕ K ) ⊕ f 1 ( s t +25 ⊕ s t +26 ⊕ K )

and f 2 (( s t +11 ⊕ 1) respectively. We found

that D, D are very weakly biased, and they show no significant fluctuations
over the value of c t +12 ,α t +2 respectively. We conclude that the dependency

s t +24 ) ≪ 1) ⊕ f 2 (( s t +15 ⊕ s t +28 ) ≪