Cryptography Reference
In-Depth Information
studied in [5]. We show that unlike E0, the dependency within Shannon in-
ternal states is weak. The estimated complexity
O
(2
107
) of the distinguishing
attack [5], which assumed that the internal states were independent, is still valid.
Meanwhile, we study a variant of Shannon cipher, which shows much stronger
dependency within the internal states. A distinguishing attack on the Shannon
variant with reduced complexity
O
(2
93
) is proposed. Note that if the internal
states were assumed to be independent, the keystream bias of this Shannon
variant remains the same as that of the Shannon cipher and so does the attack
complexity
O
(2
107
).
The rest of the paper is organized as follows. Section 2 introduces our main
bias problem. In Section 3, we apply our results to Bluetooth E0, which allows
to make the best key-recovery attack known so far. We demonstrate another
application of our theory to Shannon cipher and a Shannon variant in Section
4. Finally we conclude in Section 5.
2OurB sProbem
In linear cryptanalysis [8], the following problem is frequently encountered to
the cryptanalyst: given Boolean functions
f
1
,f
2
:
GF
(2)
n
→
GF
(2), what is
the bias
δ
of
f
1
(
a
)
f
2
(
b
)? Here, the bias of a Boolean variable
X
refers to
Pr(
X
=0)
−
Pr(
X
= 1). Due to the famous Piling-up Lemma [8], this problem
has a very simple solution when the inputs
a
and
b
are independent and uniformly
distributed:
δ
=
δ
1
·
⊕
δ
2
,where
δ
1
,
δ
2
is the bias of of
f
1
(
a
),
f
2
(
b
) respectively.
In this paper, we are interested in the above problem for the case that
a
and
b
are dependent. We will study the case that
a
,
b
is uniformly distributed
individually and the only dependency relation between them is that
a
⊕
b
is not
uniformly distributed (but
a
and
a
⊕
b
are independent). Formally speaking,
given
f
1
,f
2
:
GF
(2)
n
GF
(2) and a distribution
D
over
GF
(2)
n
, we study
→
the bias
δ
of
f
1
(
a
)
⊕
f
2
(
b
) assuming that the uniformly distributed
n
-bit
a, b
satisfy that
a
and
a
b
complies with the given
distribution
D
.Notethatif
D
is a uniform distribution, from our assumption we
can deduce that
a
and
a
⊕
b
are independent and that
a
⊕
b
are independent and uniformly distributed. Hence,
a
and
b
are independent and uniformly distributed. Our problem then degrades
to the old well-known problem and we have
δ
=
δ
1
·
⊕
δ
2
.
Algorithm 1.
Computing the bias
δ
of
f
1
(
a
)
⊕
f
2
(
b
)
u ←
0
for all
n
-bit
a
do
for all
n
-bit
x
do
b ← a ⊕ x
u ← u
+
D
(
x
)
·
(
−
1)
f
1
(
a
)
⊕f
2
(
b
)
end for
end for
output
δ ← u/
2
n
Search WWH ::
Custom Search