Cryptography Reference
In-Depth Information
each bias pattern can be expanded to 32 ones of equal bias, and we can further
decrease the complexity of our attack on Shannon variant to 2
98
/
32 = 2
93
.
5Con lu on
In this paper, we study the bias problem of the XOR of many Boolean function
outputs, whose inputs are dependent. When all inputs are independent, our bias
problem degrades to the old well-known problem and can be solved by Piling-
up lemma. We give a simple expression to compute the bias eciently. It takes
time
O
(
kn ยท
2
n
). It turns out that our result generalizes the previous work of [9].
Furthermore, we note that the general bias in our problem can differ significantly
from the bias in the independent case. As a general guideline, we note that when
the distribution
D
of the XOR of the involved variables is weakly biased, the
bias can be approximated by using the Piling-up lemma; otherwise, it is not
appropriate to use the Piling-up lemma to compute the bias. As application,
we demonstrate with two real examples, E0 and Shannon cipher, which have 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
).
References
1. Armknecht, F., Krause, M.: Algebraic attacks on combiners with memory. In:
Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 162-175. Springer, Hei-
delberg (2003)
2. Bluetooth specification,
http://www.bluetooth.org
3. Canteaut, A., Naya-Plasencia, M.: Computing the biases of parity-check relations
(2009),
http://arxiv.org/abs/0904.4412
4. Courtois, N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In:
Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176-194. Springer, Heidelberg
(2003)
5. Hakala, R.M., Nyberg, K.: Linear distinguishing attack on shannon. In: Mu, Y.,
Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol. 5107, pp. 297-305. Springer,
Heidelberg (2008)
6. Kukorelly, Z.: The piling-up lemma and dependent random variables. In: Walker,
M. (ed.) Cryptography and Coding 1999. LNCS, vol. 1746, pp. 186-190. Springer,
Heidelberg (1999)
7. Lu, Y., Vaudenay, S.: Faster correlation attack on bluetooth keystream generator
E0. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 407-425. Springer,
Heidelberg (2004)
Search WWH ::
Custom Search