[Cryptography] Best AES candidate broken

[Jerry Leichter]

On Jul 6, 2015, at 6:30 AM, EddyHawk <quarsicon at yahoo.com> wrote:

> On Sun, 7/5/15, Jerry Leichter <leichter at lrw.com> wrote:
> While there's plenty discussion of the 5
> algorithms that made it to the final round, I haven't
> been able to find anything on why the remaining 10,
> including Crypton, the subject of the paper at hand, were
> rejected.
> 
> Also, this one:
> http://csrc.nist.gov/archive/aes/round1/r1report.htm
Thanks for the reference.  It's interesting reading.

For all the claims that the AES competition ignored various leakage channels, it this reference mentions two different kinds of power analysis attacks.  Ironically, in both cases, Rijndael is estimated to be more vulnerable than Crypton; in one case, Crypton ends up in the "most vulnerable" category.

The overall analysis of Crypton reads:

CRYPTON: This candidate has the same general profile as candidates like Rijndael and Twofish, but CRYPTON has a lower security margin, based on evidence produced during Round 1. Additionally, the original version of CRYPTON has a key schedule weakness (a modified version was submitted but rejected (cf. Sec. 2.8.1)). Rijndael and Twofish have no known general security gaps. Regarding performance, CRYPTON is among the faster of the candidates, but it is slower than either Rijndael or Twofish on most platforms. Taking into account all of these factors, it was considered unlikely that CRYPTON would surpass either Rijndael or Twofish when the AES algorithm(s) is selected. Thus, CRYPTON is not advanced to Round 2.

...2.8.1 CRYPTON
Version 1.0 of CRYPTON was submitted as a modification [28] to the original submission. The submitter claims that the modification will correct the key schedule weaknesses of the original submission. However, the modification also changes the S-boxes. It was felt by NIST that the combination of these two changes violates the criterion that a modification should not invalidate the majority of Round 1 analysis. Since changes to both the key schedule and S-boxes would presumably necessitate significant re-analysis, the modification was not accepted.

Beyond this, Crypton was reported in two separate papers to have 2^32 "weak keys".  NIST didn't consider this a killer problem, but it certainly didn't help.

The claim that started much of this discussion - that Crypton was "the best AES candidate" - is simply false, based on the evidence available at the time; and there's nothing I know of that's emerged since that would change the assessment.

                                                        -- Jerry