Cryptography Reference
In-Depth Information
Bias Analysis of a Certain Problem
with Applications to E0 and Shannon Cipher
Yi Lu
and Yvo Desmedt
Department of Computer Science
University College London, UK
Abstract.
Bias analysis is an important problem in cryptanalysis. When
the critical bias can be expressed by the XOR of many terms, it is well-
known that we can compute the bias of their sum by the famous Piling-up
lemma assuming all the terms are independent. In this paper, we consider
the terms of the sum are dependent and we study above bias problem.
More precisely, let each term be a Boolean function of a variable over
GF
(2)
n
. We assume the distribution
D
of the XOR of
k
variables is
known, each variable is uniformly distributed individually, and more-
over, the XOR of
k
variables and (
k −
1) variables all are independent.
We give a simple expression for the bias of the sum of
k
Boolean func-
tions. It takes time
2
n
) to compute the bias, while under the
independence assumption, it takes time
O
(
k ·
2
n
) to compute by Piling-
up lemma. We further compare the general bias in our problem with the
bias in the independent case. It is remarkable to note that the former can
differ significantly from the latter. As application, we apply our results
to cryptanalysis of two real examples, Bluetooth encryption standard
E0 and Shannon cipher, which show a strongly biased and weakly bi-
ased
D
respectively. For E0, our analysis allows to make the best known
key-recovery attack with precomputation, time and data complexities
O
(2
37
). For Shannon cipher, our analysis verifies the validity of the es-
timated complexity
O
(2
107
) of the previous distinguishing attack [5]. As
comparison, we also studied a variant of Shannon cipher, which shows
much stronger dependency within the internal states. We gave a distin-
guishing attack on the Shannon variant with reduced complexity
O
(2
93
).
O
(
kn ·
Keywords:
linear cryptanalysis, bias, Piling-up lemma, E0, Shannon
cipher.
1
Introduction
In linear cryptanalysis [8], bias analysis is an important problem. A large bias will
make distinguishing attacks or even key-recovery attacks possible. The cryptan-
alyst is thus often faced with the problem of trying to find a possibly large bias
Funded by British Telecommunications under Grant Number ML858284/CT506918.
Funded by EPSRC EP/C538285/1, by BT, (as BT Chair of Information Security),
andbyRCIS(AIST).
Search WWH ::
Custom Search