# Algebraic Attacks on Stream Ciphers with Linear Feedback

@inproceedings{Courtois2003AlgebraicAO, title={Algebraic Attacks on Stream Ciphers with Linear Feedback}, author={Nicolas Courtois and Willi Meier}, booktitle={EUROCRYPT}, year={2003} }

A classical construction of stream ciphers is to combine several LFSRs and a highly non-linear Boolean function f . Their security is usually analysed in terms of correlation attacks, that can be seen as solving a system of multivariate linear equations, true with some probability. At ICISC’02 this approach is extended to systems of higher-degree multivariate equations, and gives an attack in 2 for Toyocrypt, a Cryptrec submission. In this attack the key is found by solving an overdefined… Expand

#### 672 Citations

Higher Order Correlation Attacks, XL Algorithm and Cryptanalysis of Toyocrypt

- Computer Science, Mathematics
- ICISC
- 2002

This paper reduces the cryptanalysis of a stream cipher to solving a system of multivariate equations that is overdefined (much more equations than unknowns), and adapts the XL method, introduced at Eurocrypt 2000 for overdefined quadratic systems, to solving equations of higher degree. Expand

Algebraic Attacks on Combiners with Memory and Several Outputs

- Computer Science
- ICISC
- 2003

It is shown that much faster algebraic attacks exist for any cipher that (in order to be fast) outputs several bits at a time, and substantially reduces the complexity of the best attack known on four well known constructions of stream ciphers when the number of outputs is increased. Expand

Computing the Algebraic Immunity Efficiently

- Mathematics, Computer Science
- FSE
- 2006

An algorithm of complexity O \left( m^d\right)$ (for fixed d) which is able to prove that a given Boolean function in m variables has no annihilator nor multiple of degree less than or equal to d. Expand

The Inverse S-Box, Non-linear Polynomial Relations and Cryptanalysis of Block Ciphers

- Computer Science, Mathematics
- AES Conference
- 2004

This paper presents several constructions of somewhat special practical block ciphers, seemingly satisfying all the design criteria of AES and using similar S-boxes, and yet being extremely weak. Expand

On the Existence of low-degree Equations for Algebraic Attacks

- Computer Science
- IACR Cryptol. ePrint Arch.
- 2004

This paper unifies approaches to the existence of low-degree equations for simple combiners, combiners with memory and S-boxes and introduces a new improved version, adapted to specific keystream generators (e.g., for the Bluetooth keystream generator). Expand

Systematic Construction of Nonlinear Product Attacks on Block Ciphers

- Computer Science
- ICISC
- 2019

This paper abstracts the attack from any particular block cipher, presents a general construction of an attack where multiply all the polynomials lying on one or several cycles and obtains a periodic invariant property holding for any number of rounds. Expand

Simplifying algebraic attacks with univariate analysis

- Mathematics, Computer Science
- 2011 Information Theory and Applications Workshop
- 2011

It is shown that by using the univariate polynomial representation, one gets a much more fine grained picture of cryptanalysis of stream ciphers based on LFSRs and provides an alternative view of the R⊘njom-Helleseth attack. Expand

On Guess and Determine Cryptanalysis of LFSR-Based Stream Ciphers

- Mathematics, Computer Science
- IEEE Transactions on Information Theory
- 2009

This approach efficiently takes advantage of the reduced preimage space for relatively large m and at the same time employing the design structure of the cipher, and outperforms classical algebraic attacks on so-called Linear Feedback Shift register-based stream ciphers. Expand

Counting equations in algebraic attacks on block ciphers

- Computer Science
- International Journal of Information Security
- 2009

It is shown that by splitting the equations defined over a block cipher (an SP-network) into two sets, one can determine the exact number of linearly independent equations which can be generated in algebraic attacks within each of these sets of a certain degree. Expand

On the Design and Analysis of Stream Ciphers

- Computer Science
- 2007

This thesis presents new cryptanalysis results for several different stream cipher constructions, and introduces two new stream ciphers, both based on the same design principle, namely Grain and Grain-128. Expand

#### References

SHOWING 1-10 OF 59 REFERENCES

Fast Algebraic Attacks on Stream Ciphers with Linear Feedback

- Computer Science
- CRYPTO
- 2003

This paper shows how to substantially lower the degree of these equations by multiplying them by well-chosen multivariate polynomials, and is able to break Toyocrypt in 249 CPU clocks, with only 20 Kbytes of keystream, the fastest attack proposed so far. Expand

Higher Order Correlation Attacks, XL Algorithm and Cryptanalysis of Toyocrypt

- Computer Science, Mathematics
- ICISC
- 2002

This paper reduces the cryptanalysis of a stream cipher to solving a system of multivariate equations that is overdefined (much more equations than unknowns), and adapts the XL method, introduced at Eurocrypt 2000 for overdefined quadratic systems, to solving equations of higher degree. Expand

Cryptanalysis of Block Ciphers with Overdefined Systems of Equations

- Computer Science, Mathematics
- ASIACRYPT
- 2002

A new criterion for design of S-boxes in block ciphers should not be describable by a system of polynomial equations that is too small or too overdefined, and this is suggested for both Serpent and Rijndael. Expand

Algebraic Attacks and Decomposition of Boolean Functions

- Computer Science, Mathematics
- EUROCRYPT
- 2004

Algebraic attacks on LFSR-based stream ciphers recover the secret key by solving an overdefined system of multivariate algebraic equations and become very efficient if such relations of low degrees may be found. Expand

Fast correlation attacks on certain stream ciphers

- Mathematics, Computer Science
- Journal of Cryptology
- 2005

Two new correlation attacks are presented to determine the initial digits of a, provided that the numbert of feedback taps is small, and are demonstrated to be successful against shift registers of considerable lengthk (typically,k=1000). Expand

The Security of Hidden Field Equations (HFE)

- Computer Science
- CT-RSA
- 2001

We consider the basic version of the asymmetric cryptosystem HFE from Eurocrypt 96.We propose a notion of non-trivial equations as a tentative to account for a large class of attacks on one-way… Expand

Linear Cryptanalysis of Bluetooth Stream Cipher

- Computer Science
- EUROCRYPT
- 2002

A large class of linear correlations in the Bluetooth combiner, unconditioned or conditioned on the output or on both the output and one input, are found and an attack on the Bluetooth stream cipher that can reconstruct the 128-bit secret key with complexity about 270 from about 45 initializations is proposed. Expand

Attacks based on Conditional Correlations against the Nonlinear Filter Generator

- Computer Science, Mathematics
- IACR Cryptol. ePrint Arch.
- 2003

In this paper we extend the conditional correlation attack ([LCPP96]) against the nonlinear filter generator (NLFG) by introducing new conditions and generalisations and present two known-plaintext… Expand

Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers

- Computer Science
- ASIACRYPT
- 2000

This paper shows that a combination of the two approaches has an improved time/memory/data tradeoff for stream ciphers of the form TM2D2 = N2 for any D2 ≤ T ≤ N. Expand

Nonlinearity Criteria for Cryptographic Functions

- Mathematics, Computer Science
- EUROCRYPT
- 1989

Nonlinearity criteria for Boolean functions are classified in view of their suitability for cryptographic design and two criteria turn out to be of special interest, the distance to linear structures and the Distance to affine functions, which are shown to be invariant under all affine transformations. Expand