### Nicolas T. Courtois

Dept. of Computer Science

University College London

UK

## Algebraic Attacks on Stream Ciphers

#### Abstract

Stream ciphers can be used for encryption and generation of random numbers. In this course we will study a large and very popular family of stream ciphers in which [most of] the state bits are updated linearly, the cipher is regularly clocked [this condition can be relaxed], and the output is produced by some highly non-linear component that can have a [small] extra state/memory. In particular we will cover stream ciphers that combine one or several LFSR, cellular automata, and the output is obtained by a filter or combiner with or without memory, for example, the cipher E0 used in Bluetooth wireless interface or Snow 2.0 that became an ISO standard for stream encryption. These ciphers can be studied in terms of multivariate algebraic equations over finite fields. We will recall a number of useful facts about finite fields. Hardness of solving certain systems of equations is what underpins the security of these [and other] ciphers. The linear feedback property is a key weakness. We will study a number of Theorems that establish worst-case attacks. We will explain various ways in which even better attacks can be discovered experimentally through a pre-computation step, looking for a single algebraic relation of a certain type. We will study fast algebraic attacks, annihilators of Boolean functions, and probabilistic versions of all the attacks. We will also mention totally 'wild' attacks in which the key is found by experimentation, with Gröbner bases or SAT solver software, that are characterized by exceptionally low plaintext requirements, and by lack of theory being able to predict their complexity.

#### Course materials

- N. Courtois. Algebraic attacks on stream ciphers. Lecture slides for EWSCS 2009. 2009. pdf
- N. Courtois. Basic algebra and number theory. Slides. 2006. pdf
- N. Courtois. A new frontier in symmetric cryptanalysis. IndoCrypt 2008 presentation. 2008. pdf

Last changed **
March 9, 2009 0:25 EET**
by
local organizers, ewscs09(at)cs.ioc.ee

EWSCS'09 page:
http://cs.ioc.ee/ewscs/2009/