Cryptography Reference
In-Depth Information
of the internal states of Shannon is weak and the keystream bias (15) can be
approximated
3
with Piling-up lemma, which was estimated as
O
(2
−
56
)in[5].
Thus, the estimated complexity
O
(2
107
) of the distinguishing attack [5], which
uses 32 such largest biases, is still valid.
Furthermore, we consider a variant of Shannon when both
f
1
,f
2
only uses
one element from the shift register as the input instead of two in the Shannon
cipher. For convenience of our discussion, we consider the variant of removing
the second
s
term in the inputs of both
f
1
,f
2
(
K
is still present). The keystream
bias relation (15) for our Shannon variant then becomes
(
z
t
≪
1)
⊕
z
t
+16
=
f
1
(
s
t
+21
⊕
K
)
⊕
f
1
(
s
t
+25
⊕
K
)
⊕
f
2
(
s
t
+11
≪
1)
⊕
f
2
(
s
t
+15
≪
1)
⊕
f
2
(
s
t
+19
)
⊕
f
2
(
s
t
+3
≪
1)
.
(18)
Under the independence assumption, this will not change the keystream bias.
However, note that the involved distributions of the input difference change now.
We can see that now
D
(
x
)=
D
f
2
(
x
z
t
+12
),
D
(
x
)=
D
f
2
((
x
⊕
≫
1)
⊕
z
t
+2
),
D
=
f
1
⊗
f
2
. Given a bias pattern, we can use Corollary 1 to compute the
individual bias (denote by
δ
1
,δ
2
,δ
3
respectively) of
f
1
(
s
t
+21
⊕
K
)
⊕
f
1
(
s
t
+25
⊕
K
),
f
2
(
s
t
+11
≪
1)
⊕
f
2
(
s
t
+15
≪
1) and
f
2
(
s
t
+19
)
⊕
f
2
(
s
t
+3
≪
1). With the
2
−
18
; in contrast, the
independence assumption makes
δ
1
= 0. Meanwhile, we have
4
bias pattern
M
=0
x
9292949 and
z
t
+12
=0
x
80,
δ
1
≈
2
−
16
,
which are approximately the same as using Piling-up lemma to compute. Thus,
given
z
t
+12
=0
x
80, the bias of
M
δ
2
≈
δ
3
≈
z
t
+16
)is2
−
18
−
16
−
16
=2
−
50
.
This translates to a distinguishing attack with complexity
O
(2
100
). Moreover,
we found 15 other bias patterns
5
·
((
z
t
≪
1)
⊕
with corresponding
z
t
+12
's,whichallhave
δ
1
≈
2
−
16
. Considering all these biases, we have a distinguishing
attack with complexity 2
(19+16+16)
∗
2
/
16 = 2
98
.
Additionally, we can prove that given the values of
M
and
z
t
+12
,
δ
1
remains
the same for the bias patterns
M
≪
a
and
z
t
+12
≪
a
,where
a
=0
,...,
31. We
give a brief sketch of proof here. In order to prove above statement, it suces
to show that
δ
1
=
δ
1
,where
δ
1
denotes the corresponding bias for
M
=
M
2
−
19
,δ
2
≈
δ
3
≈
≪
1)
M·f
1
(
x
)
and
g
1
(
x
)=(
1)
M
·f
1
(
x
)
.First,wehave
g
1
(
x
)=
1. Let
g
1
(
x
)=(
−
−
g
1
(
x
)=
g
1
(
x
g
1
(
x
≪
1) for all
x
. From this we deduce
≪
1) for all
x
.On
the other hand, we use the property that
f
2
(
x
≪
a
)=
f
2
(
x
)
≪
a
for all
x
(see [5]) to deduce
D
f
2
(
y
)=
D
f
2
(
y
≪
1) for all
y
.So,
D
f
2
(
x
⊕
z
t
+12
)=
1). Finally we apply Corollary 1 to conclude
δ
1
=
δ
1
. Hence,
3
Note that the input difference to another item
f
2
(
s
t
+19
⊕s
t
+32
)
⊕f
2
((
s
t
+3
⊕s
t
+16
)
≪
1) is ((
s
t
+3
≪
1)
⊕ s
t
+19
)
⊕
((
s
t
+16
≪
1)
⊕ s
t
+32
). From [5], the following holds
(
s
t
≪
1)
⊕ s
t
+16
=
f
1
(
s
t
+12
⊕ s
t
+13
⊕ K
)
⊕ f
2
((
s
t
+2
⊕ s
t
+15
)
≪
1). Thus the
distribution
D
of the input difference to this item is
D
=
D
f
1
⊗ D
f
1
⊗ D
f
2
⊗ D
f
2
.
From
D
f
1
,D
f
2
we deduce that
D
is too flat and we can approximate the bias of
this item by Piling-up lemma.
4
Here
δ
2
fluctuates insignificantly over the value of
z
t
+2
.
5
They are 0x424a425, 0x420a525, 0x420a4a5, 0x420a425, 0x414a4a5, 0x414a4a1,
0x410a4a5, 0x9294949, 0x9292929, 0x9290949, 0x1292929, 0x1012929, 0x292949,
0x292941, 0x24a525.
D
f
2
((
x
⊕
z
t
+12
)
≪
Search WWH ::
Custom Search