**The Probability Advantages of Two Linear Expressions in Symmetric Ciphers**

*Haina Zhang , Shaohui Wang, Xiaoyun Wang*

**Abstract: **In this paper, we prove the probability advantages of two linear expressions which are summarized from the ABC stream cipher submitted to ECRPYT Estream Project. Two linear expressions with probability advantages reflect the linear correlations among Modular Addition equations. Corresponding to each linear expression and its advantage, a large amount of weak keys are derived under which all the ABC main keys can be retrieved successively. The first linear
expression is a generic bit linear correlation between two Modular Addition equations. The second is a linear correlation of bit carries derived from three Modular Addition equations and the linear equation of LFSR in ABC.

It is remarked that the second is found by Wu and Preneel, and has been used to find $2^{96}$ weak keys. In the cryptanalysis of ABC, Wu and Preneel only utilized its estimated probability advantage which is concluded by experimental data, and they did not give its strict proof.

Modular Addition and XOR operations are widely used in designing symmetric ciphers. We believe that these types of linear expressions with probability advantages not only can be used to analyze some other symmetric ciphers, but also are important criteria in designing secure symmetric ciphers.

**Category / Keywords: **secret-key cryptography / stream ciphers

**Date: **received 13 Jul 2006

**Contact author: **xywang at sdu edu cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20060714:062853 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]