Algebraic Cryptanalysis of the Data Encryption Standard

Nicolas T.  Courtois; Gregory V.  Bard

Paper 2006/402

Algebraic Cryptanalysis of the Data Encryption Standard

Nicolas T. Courtois and Gregory V. Bard

Abstract

In spite of growing importance of AES, the Data Encryption Standard is by no means obsolete. DES has never been broken from the practical point of view. The triple DES is believed very secure, is widely used, especially in the financial sector, and should remain so for many many years to come. In addition, some doubts have been risen whether its replacement AES is secure, given the extreme level of ``algebraic vulnerability'' of the AES S-boxes (their low I/O degree and exceptionally large number of quadratic I/O equations). 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.

Note: Updated version now quotes Chaum and Evertse.

Metadata

Available format(s): PDF PS
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: block ciphers algebraic cryptanalysis DES AES Gröbner bases logical cryptanalysis automated learning SAT solvers.
Contact author(s): n courtois @ ucl ac uk
History: 2007-09-09: last of 10 revisions; 2006-11-12: received; See all versions
Short URL: https://ia.cr/2006/402
License: CC BY

BibTeX

@misc{cryptoeprint:2006/402,
      author = {Nicolas T.  Courtois and Gregory V.  Bard},
      title = {Algebraic Cryptanalysis of the Data Encryption Standard},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/402},
      year = {2006},
      url = {https://eprint.iacr.org/2006/402}
}