TATRACRYPT 2007

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
Gower Street, WC1E 6BT, London, UK
Office email: n.courtois[at]ucl.ac.uk
Private email: courtois[at]minrank.org

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.


Last updated on May 28, 2007.