Crucial Cipher Questioned

It was supposed to be as secure as a bank vault: a cryptographic algorithm that would make documents unintelligible to prying eyes for the foreseeable future. But two cryptographers say the vault, the Advanced Encryption Standard (AES), has a hole in it. Although some of their colleagues are skeptical, the cryptographic community is on edge, wondering whether the new cipher can withstand a future assault.

Two years ago, the National Institute of Standards and Technology (NIST) held a competition to select a replacement for the aging Digital Encryption Standard, the national standard for a quarter-century, and arguably the most widely used encryption algorithm in the world. Rijndael, an elegant algorithm created by two Belgians, Vincent Rijmen of the Katholieke Universiteit Leuven and Joan Daemen of Proton World International, a company that makes smart cards, won the contest and became the AES (ScienceNOW, 3 October 2000).

Now, attacks aimed at the heart of Rijndael and other algorithms point to a possible weakness. Cryptographers Nicolas Courtois, who works for technology corporation SchlumbergerSema in Louveciennes, France, and Josef Pieprzyk of Macquarie University in Sydney, Australia, rewrote crucial elements of AES with small systems of equations. This and other simplifications allowed Courtois and Pieprzyk, they believe, to generate an attack on AES of order 2100: That is, it takes roughly 2100 operations to crack the cipher, significantly less than the 2128 to 2256 operations needed to try every combination. They will present their latest findings in December at the Asiacrypt 2002 conference.

"It's nerve-wracking for me that this stuff is going on," says William Burr, the manager of the Security Technology group at NIST in Gaithersburg, Maryland. However, it might take cryptographers years to determine whether an attack would succeed--Don Coppersmith, a cryptographer with IBM in Yorktown, New York, and one of the designers of DES, claims to have found a flaw in the analysis, though Courtois says the criticism does not apply to the latest version of the attack. The only way to prove that the new algorithm works, Courtois says, is to use it to crack AES--and computers aren't up to the job yet.

Related sites
More about AES
The Rijndael Page

Posted in Math