2011 | OriginalPaper | Chapter
Bias Analysis of a Certain Problem with Applications to E0 and Shannon Cipher
Authors : Yi Lu, Yvo Desmedt
Published in: Information Security and Cryptology - ICISC 2010
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 moreover, 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 functions. It takes time
O
(
kn
·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 biased
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 estimated 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 distinguishing attack on the Shannon variant with reduced complexity
O
(2
93
).