[Cryptography] Best AES candidate broken
leichter at lrw.com
Sun Jul 5 00:01:36 EDT 2015
On Jul 4, 2015, at 4:23 PM, Ryan Carboni <ryacko at gmail.com> wrote:
> The best AES candidate,
Clearly many of the best cryptographers out there disagreed with you, as it didn't make it to the final round - and there's been general agreement that the AES selection process was of extremely high quality.
> fastest on software, and faster than Rijndael on hardware,
Given that the criteria were a mix of security and performance, if it didn't make it to the final 5 and was the fastest, it must have been dinged on security.
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. Prior to this paper, there are no known obvious breaks. The best published attacks are against Crypton with a significantly reduced number of rounds. In fact, by the (rather weak) measure of "security margin" you get by comparing number of rounds attacked vs. number of rounds proposed, Crypton probably did better than most of the Final Five. As best I can tell, it mainly got dinged on security because of lack of history: The Final Five, in general, were descendants of pre-existing algorithms which had themselves survived significant public attack.
> has finally been broken!
This is an interesting bit of work. We've had arguments on this list that no widely attacked, widely accepted symmetric encryption algorithm has been attacked since before DES - so worrying about what to do if a new attack against AES arises is pointless. Well ... there's no clear reason why Crypton could not have been chosen as the standard rather than Rijndael. It was provably secure against both linear and differential cryptography, and the variations of those in the last 15 years also left it unscathed. As an AES candidate, it received some significant attention during the contest (not as much as the finalists, of course), and additional attacks (against severely reduced-round versions; there's also a related-key attack) have appeared over the years, so it hasn't been forgotten.
Now, the attacks in the paper - which I've only skimmed - are (a) against a slightly different algorithm than was proposed in AES, though the changes were intended to strengthen it, and the paper claims the techniques are applicable to the original algorithm (to be studied in a followup paper); and (b) are far from a complete break (they seem to gain about 2 bits over brute force). Still ... attacks only get better.
I don't think this is by any means a signal that AES is about to fall. But it's a warning about hubris: It remains the case that the most we can say about the security of our encryption algorithms remains "They are secure against all known attacks - some of which are by now extremely general and powerful; and the brightest guys out there haven't found any holes". New attacks are always possible. You can't anticipate when and from what direction they will appear. While I would agree that the probability of a major break in AES is small, it's not zero - and its cost would be incalculably immense. Since any rational cost analysis has to consider the product of those two factors (neither of which we can estimate in any reasonable way!), it can't be something we just ignore - even if we decide that the expected risk is much smaller than that of other failures, so we can rationally decide to accept it.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the cryptography