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 ciphersalgebraic cryptanalysisDESAESGröbner baseslogical cryptanalysisautomated learningSAT 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2006/402}},
      url = {https://eprint.iacr.org/2006/402}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.