|Title||Algebraic cryptanalysis of the data encryption standard.|
|Author(s)|| Gregory V. Bard, Nicolas T. Courtois|
|Type||Book, Chapter in Book, Conference Proceeding|
|Abstract||In spite of growing importance of the Advanced Encryption Standard (AES), the Data Encryption Standard (DES) is by no means obsolete. DES has never been broken from the practical point of view. The variant “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? 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 in  it was shown that “small” S-boxes always have a low I/O degree (cubic for DES as we show below). 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 of DES 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. It requires only one single known plaintext (instead of a very large quantity) which is quite interesting in itself.
Our attacks will recover the key using an ordinary PC, for only six rounds. Furthermore, 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. We discuss how they can be applied to DES with modified S-boxes, and potentially other reduced-round block ciphers.
|Keywords||block ciphers, algebraic cryptanalysis, DES|