14th Estonian Winter School in Computer Science (EWSCS)
XIV Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 1-6, 2009

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

Valid CSS! Valid XHTML 1.0 Strict 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/