Cryptography Reference
In-Depth Information
Table 3.
Comparison of
δ
with
δ
0
for
w
=2
,...,
6, where
M
= (10111)
2
w
23 4 56
log
2
|δ|
-3 X -10.2 X -17
log
2
|δ
0
|
-12 -18 -24 -30 -36
Table 4.
Comparison of
δ
with
δ
0
for
w
=2
,...,
6, where
M
= (110001)
2
w
23 4 56
log
2
|δ|
-2.6 -12.1 -10.2 -22.7 -17
log
2
|δ
0
|
XX X XX
Table 5.
Comparison of our improved key-recovery attack on one-level E0 with previ-
ous attacks
attack
precomputation time data memory
2
67
.
6
2
23
.
1
2
46
.
1
[1]
X
2
28
2
49
2
23
.
4
2
37
[4]
2
37
2
39
2
39
2
27
[7]
2
37
2
37
2
37
2
27
this paper
to Remark 2, the bias with
w
= 3 or 5 in Table 3 shows that the independence
assumption
over-estimates
the real bias here.
Based on our above bias analysis, we can now improve the best known key-
recovery attack [7] on one-level E0 as follows. Note that to recover the shortest
LFSR
R
1
in [7], the multiple polynomial of
4
i
=2
β
i
(
x
) is used rather than the
multiple polynomial of
β
(
x
). This affects the relevant distribution
D
as well as
the bias. Assuming that the involved state of
R
1
and the involved state of FSM
are random and uniformly distributed,
D
is uniformly distributed over 25+4=29
bits rather than over 4 bits as mentioned in Section 3.1. Similar analysis shows
that the bias is 2
−
15
.
7
for
w
=5with
M
= (11111)
2
,M
= (100001)
2
. Finally,
Table 5 compares our improved attack with the previous attacks [1, 4, 7]. This
is the best key-recovery attack on E0 known so far with precomputation, time
and data complexities
O
(2
37
).
4 Application Two: Shannon Cipher
Shannon [11] is a recently proposed synchronous stream cipher designed by G.
Rose et al. from Qualcomm [10]. It has been designed according to Profile 1A of
the ECRYPT call for stream cipher primitives, and it uses a secret key of up to
256 bits. The internal state uses a single nonlinear feedback shift register. This
shift register state at time
t
≥
0 consists of 16 elements
s
t
+
i
(
i
=0
,...,
15) of
Search WWH ::
Custom Search