The 7th Central European Conference on Cryptology
June 22-24, 2007, Smolenice, Slovakia
Abstract of a plenary talk
Two Sources of Algebraic Vulnerability and Applications in Cryptanalysis
Nicolas T. Courtois
University College of London
In this talk we will study the question of algebraic cryptanalysis. There are two main sources
of algebraic vulnerability in symmetric cryptography: algebraic I/O equations of low degree,
and the general possibility to implement a cipher with a small gate count that will give an extremely
sparse system of equations with extra variables. The first family of vulnerabilities are now better
understood with precise applications in breaking many stream ciphers and multivariate public key systems.
The applicability to block ciphers remains a challenge, both quite pessimistic and some very optimistic
results are obtained. For example, all notions of algebraic immunity and the fact the Gröbner bases must
go to a high degree to compute a solution are easy to circumvent from the point of view of the attacker.
Moreover, in the mean time, the interest for the second "source of algebraic vulnerability" has been
renewed by Bard and Courtois showing the power of SAT solvers to solve very efficiently arbitrary but
sparse systems of algebraic equations. This is a very strong result obtained mostly by experimentation.
As a result we get new-style algebraic attacks on round-reduced DES and (full) KeeLoq cipher
that is broken quite badly.
Gower Street, WC1E 6BT, London, UK
Office email: n.courtois[at]ucl.ac.uk
Private email: courtois[at]minrank.org
Last updated on May 28, 2007.