NESSIE
New European Schemes for Signatures,  Integrity, and Encryption

 Rijndael and other block ciphers
Author: Steve Babbage ()
Date:   11-11-02 16:29

We are nearing the point at which NESSIE must make its final selection of recommended algorithms.

For general purpose algorithms, we must always take a precautionary approach - for instance, recommending a key size which will remain out of reach for long enough even with accelerated progress in computing technology, and recommending a number of rounds that resists all known attacks with a comfortable security margin.

It seems to me, therefore, that we should take a similar precautionary approach when it comes to promising but unproven methods of attack. It is still very unclear whether the multivariate methods of Courtois and Pieprzyk, possibly taken together with Murphy and Robshaw's "BES" representation, will lead to a genuine attack on Rijndael; but to my mind there is enough of a threat that it would be quite wrong for NESSIE to recommend Rijndael.

And what about other block ciphers? Camellia, Misty, Serpent, Khazad ... all seem under at least some threat from the same techniques. I would suggest that NESSIE should only recommend these algorithms for short-term security requirements, if at all.

One specific comment: the NESSIE security report currently states "As a result of the combination of the Courtois attacks and the BES, it may be advisable for NESSIE to recommend a more secure variant of Rijndael with 12 rounds." This is not appropriate. If these attacks do work then their complexity will NOT increase any more than polynomially with the number of rounds.

 Re: Rijndael and other block ciphers
Author: Paulo S. L. M. Barreto ()
Date:   11-12-02 11:48

I'd like to point out that Babbage's viewpoint can easily lead to a new kind of attack against any cipher, namely, a fear-inducing attack (somehow related to a denial-of-service attack).

It is enough that someone publishes a technically involved analysis of the target cipher and speculates that it might be a security threat (even though further analysis by third parties shows it does not work - see e.g. Don Coppersmith's comment on NIST's AES discussion forum). Publicity in certain forums or newsletters certainly helps implementing the attack. This immediately labels the cipher as questionable or unacceptable to some people, and may cause its rejection on grounds themselves questionable. The cipher is henceforth psychologically broken.

I wonder what would happen is someone started publishing fear-inducing attacks against all NESSIE candidates. Would this cause the entire NESSIE effort to be cancelled? What are the exact NESSIE criteria for choosing or rejecting ciphers - real attacks or flawed analyses?

Best regards,

Paulo Barreto.

 Re: Rijndael and other block ciphers
Author: Vincent Rijmen (203.196.224.---)
Date:   12-18-02 18:51

Please note the following.

1) The XSL attack is not an attack. It is a dream.

2) The NESSIE project aims to compare submitted algorithms and existing standards.
Rijndael has not been submitted to NESSIE. The AES is an existing standard. The AES is defined as Rijndael with a blocklength of 128 bits, and key lengths of 128, 192 and 256 bits, using 10, 12 or 14 rounds.

All other possible configurations with Rijndael (block lengths, key lengths, number of rounds) are not part of an existing standard and were not submitted to NESSIE. Hence, NESSIE should refrain from recommending any of these.

Vincent

 Re: Rijndael and other block ciphers
Author: Nicolas T. Courtois ()
Date:   05-21-03 13:48

XSL may be a dream.
It may also be a very bad dream and turn into a nightmare.

Nicolas

 Re: Rijndael and other block ciphers
Author: Nicolas T. Courtois ()
Date:   05-21-03 13:52

Personally I do not believe that the XSL-style attacks
could be really polynomial in the number of rounds. This seems to nice to be true and is not confirmed by my simulations.
But they could be sub-exponential and still devastating in practice for some ciphers.

Nicolas

 Re: Rijndael and other block ciphers
Author: Nicolas T. Courtois ()
Date:   05-21-03 14:04

>I'd like to point out that Babbage's viewpoint can easily lead to a new kind of
>attack against any cipher, namely, a fear-inducing attack (somehow related to a
>denial-of-service attack).

Maybe this fear-inducing attack has been already carried against AES ?
See http://eprint.iacr.org/2002/099/ and http://eprint.iacr.org/2002/149/.
Then see http://eprint.iacr.org/2003/003/ and http://eprint.iacr.org/2003/022/.
By the way, the author still claims that he broke AES.


> (even though further analysis by third parties shows it does not work - see e.g. >Don Coppersmith's comment on NIST's AES discussion forum).
What analysis ? Nobody did any as far as I know. The so called objection of Coppersmith never really existed: the author later acknowledged that he wrote this BEFORE he actually understood the full XSL+T' method.
To the best of my knowledge, the arguments of people who claim that XSL will not work are up till now yet completely devoid of scientific background. Simply beliefs.

Nicolas

 Re: Rijndael and other block ciphers
Author: Zhang (219.238.245.---)
Date:   05-27-03 16:18

How can we confirm that the three previous speakers with the one name Nicolas is really the person Nicolas T. Courtois ? It is difficult to understand and believe. It is rather funny.

 Re: Zhang
Author: Golden (159.226.5.---)
Date:   07-04-03 12:04

You can view the homepage of Nicolas T. Courtois.
He expressed the same viewpoint there.

 Re: Zhang
Author: Janusz ()
Date:   09-06-03 19:37

Please evey about Rijndael

 Reply To This Message
 Your Name:
 Your Email:
 Subject:
Email replies to this thread, to the address above.
  


NESSIE Discussion Forum
Moderator: Antoon Bosselaers
Setup: Joris Claessens
NESSIE project coordinator: COSIC, ESAT, K.U.Leuven
URL: http://www.cosic.esat.kuleuven.ac.be/nessie/forum/
phorum.org