Cryptography Reference
In-Depth Information
for a cipher. When the critical bias can be expressed by the XOR of many terms
and when there shows no clear dependency between them (though we are also
sure that they are not really independent), it is convenient and common to as-
sume these terms are independent and use the famous Piling-up lemma [8] to
combine the individual bias of each term to get the total bias estimate. This
independence assumption, however, is not always appropriate to approximate
the total bias. In [6], it was shown that in the context of block ciphers, the ap-
proximation by Piling-up lemma sometimes can differ considerably from the real
value of the bias.
In this paper, we take the dependency
1
between the terms of the sum into
account and study the above bias problem. More precisely, let each term be a
Boolean function
2
of a variable over
GF
(2)
n
. We assume the distribution 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. It grows linearly in
k
and is practical
for modest
n
. In contrast, under the independence assumption, it needs
O
(
k
·
2
n
)
time to compute the bias by Piling-up lemma. Note that a special case of our
result was given in [9] previously; [9] considered the bias of our problem when
all the functions are the same and the XOR of all variables is the constant of
the all zero vector.
Furthermore, we compare the general bias in our problem with the bias in
the independent case. We note that the former can differ significantly from the
latter: 1) if one function is balanced, then the real bias is always no smaller than
the bias in the independence case; 2) if no functions are balanced, then the real
bias can be smaller than the bias in the independence case, which implies that
the convenient independence assumption sometimes
over-estimates
the real bias;
3) if all functions are the same and
k
is even, then the real bias can be negative,
while the bias in the independence case is never negative.
As one application, our result is applied to analyze precisely the bias for the
famous encryption standard E0, which is used in the short-range wireless radio
standard Bluetooth [2]. We observe that the dependency between the involved
variables is strong. We show that if the multiple polynomial of the related LFSR
feedback polynomial has even weight, we have four largest biases; if the weight
is odd, we have two largest biases. In comparison, according to the traditional
bias estimate approach based on independence assumption, it was believed that
there are two largest biases [7], regardless of the multiple polynomial weight.
We demonstrate that the two biases used in the key-recovery attack [7] are
both
under-estimated
and should be doubled instead. This allows to make the
best known key-recovery attack on E0, with precomputation, time and data
complexities
O
(2
37
).
Another application is a recently proposed stream cipher Shannon [11] de-
signed by Qualcomm group [10]. We revisit the keystream bias of Shannon
·
1
The bias problem which considered dependency of another form was studied in [3].
2
Not necessarily the same Boolean function.
Search WWH ::
Custom Search