Cryptography Reference
In-Depth Information
Remark 1.
If
δ
i
=0for
i
(or equivalently
f
i
is balanced), then it
is easy to see that
δ
in our problem is always no smaller than the bias in the
independent case.
Examples: see Section 3.
Remark 2.
If
δ
i
∈{
1
,...,k
}
=0forall
i
=1
,...,k
,itispossibletohave
δ<δ
1
···
δ
k
.
Examples: see Section 3.
This implies that the independence assumption, which is so often used for
convenience, sometimes would
over-estimate
the real bias.
Remark 3.
If
f
1
=
=
f
k
and
k
is even, it is possible to have
δ<
0. In
comparison, note that the bias in the independent case can never be negative.
As an illustrative example to Remark 3, consider
k
=2
,f
1
=
f
2
with
f
1
(0) =
f
1
(2) =
f
1
(3) = 1 and
f
1
(1) = 0,
D
(0) =
D
(1) = 1
/
8
,D
(2) =
D
(3) = 3
/
8. We
can check that
δ
=
···
−
3
/
16 and the bias in the independent case is
δ
1
=1
/
4.
3 Application One: E0
In this section, we will see that our proposed new tool in Section 2 is applicable
to a precise bias analysis of the famous encryption standard E0, which is used in
the short-range wireless radio standard Bluetooth [2]. E0 uses a 128-bit secret
key. It uses four (regularly clocked) LFSRs of 128 bits in total and a 4-bit Finite
State Memory (FSM). The FSM updates its 4-bit state at each clock by the
outputs of the LFSRs, and the FSM outputs one bit
c
t
out of its 4-bit state.
The keystream bit
z
t
at each clock is computed as
z
t
=
x
t
⊕
x
t
⊕
x
t
⊕
x
t
⊕
c
t
,
(10)
where
x
t
denotes the output of LFSR
R
i
. For a complete and detailed description,
see [2].
In [7], the bias within a consecutive sequence of
c
t
}
up to 26 bits was sys-
tematically analyzed. Let
M
be a 26 bit vector. It was shown [7] that when
M
= (11111)
2
or
M
= (100001)
2
(in binary form), the absolute value of the bias
of
M
{
c
t
c
t−
1
···
c
t−
25
is the largest
25
256
.Let
β
i
(
x
) be the feedback polynomial
of LFSR
R
i
and
β
i
(
x
) is a primitive polynomial. It is well-known that the the
equivalent LFSR, which can generate the same sequence of
x
t
⊕
·
x
t
⊕
x
t
⊕
x
t
,has
the feedback polynomial
β
(
x
)=
4
x
p
w
be
the multiple polynomial of
β
(
x
)withdegree
d
and weight
w
,where
d
=
p
w
>
...>p
2
>p
1
= 0. We have the following equality always holds for all
t
0
,
w
i
=1
β
i
(
x
). Let
p
(
x
)=
x
p
1
⊕
x
p
2
⊕···⊕
(
x
t
0
+
p
i
⊕ x
t
0
+
p
i
⊕ x
t
0
+
p
i
⊕ x
t
0
+
p
i
)=0
.
(11)
i
=1
Therefore, we have the following equality always holds for all
t
0
,
w
w
(
c
t
0
+
p
i
,...,c
t
0
+
p
i
+25
)
M
·
(
z
t
0
+
p
i
,...,z
t
0
+
p
i
+25
)=
M
·
(12)
i
=1
i
=1
Search WWH ::
Custom Search