Is DES secure from the point of view of algebraic cryptanalysis, a new very fast-growing area of research? We do not really hope to break it, but just to advance the field of cryptanalysis. At a first glance, DES seems to be a very poor target - as there is (apparently) no strong algebraic structure of any kind in DES. However Courtois and Pieprzyk showed that ``small'' S-boxes always have a low I/O degree (cubic for DES as we show). In addition, due to their low gate count requirements, by introducing additional variables, we can always get an extremely sparse system of quadratic equations. To assess the algebraic vulnerabilities is the easy part, that may appear unproductive. In this paper we demonstrate that in this way, several interesting attacks on a real-life ``industrial'' block cipher can be found. One of our attacks is the fastest known algebraic attack on 6 rounds of DES. Yet, it requires only ONE SINGLE known plaintext (instead of a very large quantity) which is quite interesting in itself.
Though (on a PC) we recover the key for only six rounds, in a much weaker sense we can also attack 12 rounds of DES. These results are very interesting because DES is known to be a very robust cipher, and our methods are very generic. They can be applied to DES with modified S-boxes and potentially other reduced-round block ciphers.
Category / Keywords: secret-key cryptography / block ciphers, algebraic cryptanalysis, DES, AES, solving overdefined and sparse systems of multivariate equations, Gröbner bases, logical cryptanalysis, automated learning, SAT solvers. Date: received 10 Nov 2006, last revised 9 Sep 2007 Contact author: n courtois at ucl ac uk Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: Updated version now quotes Chaum and Evertse. Version: 20070909:214901 (All versions of this report) Discussion forum: Show discussion | Start new discussion