Slashdot Mirror

← Back to Stories (view on slashdot.org)

AES: Learn All About It

Posted by timothy on from the paranoia-is-always-justified dept.

Jason Bennett, frequent reviewer of books, now regales you with this great piece on the background and development of the new encryption standard to replace the pretty-good-till-now DES. It's full of linked information you'll want to digest, too. Update: 02/23 12:32 AM by T : Note: The links I borked are better now; mea culpa (and beware copying in Mozilla).

Since it was officially approved by the U.S. Government in November of 1976, most of the world's sensitive commercial traffic has been secured through the use of the Data Encryption Standard (DES). In its twenty-five year lifetime, it has become the most widely used, most widely trusted, and most widely studied encryption algorithm in existence. Alas, in the same way that your Atari 2600 [?] is currently sitting on the floor of your closet, DES' lifetime has come to an end as well. This was most dramatically demonstrated in the three DES Challenges sponsored by RSA Labs between January of 1997 and January of 1999, with a DES-encrypted message eventually being broken in less than 24 hours. This challenge also witnessed the birth of a DES-specific cracking computer, a machine widely theorized about, but never before (publicly) built. Although variants of DES (most notably Triple DES) are still widely used, it became clear that a new algorithm would be needed for the next twenty-five years.

Thus was born the Advanced Encryption Algorithm Development Effort. Beginning in January, 1997 (just before the RSA challenges finally broke DES), the National Institute of Standards and Technology announced its intent to begin the Advanced Encryption Standard (AES) process. The initial AES workshop was held in April, with the official call for algorithms going forth in September. Importantly, this call specified that the algorithms submitted have a key length of 128 bits, and be free of intellectual property constraints. Algorithms would be accepted from domestic and international submitters, and the resulting algorithm would be completely public. The con test would also consider both the hardware and the software implementation -- a divergence from DES, which was specifically designed for use in hardware. Importantly, the hardware that the AES had to operate in could vary from the largest supercomputer to a ROM-based smart card or other embedded ed environment. A candidate algorithm might well be optimized for one or the other, but had to perform at least reasonably well on all to have a real chance of being selected. Finally, this algorithm would be designed from the ground up to use the long key length, and thus would be faster and more secure than Triple-DES is at that length.

Thus came the warriors to the joust. On August 20-22, 1998, the first AES conference was held, with fifteen different algorithms being presented. Over the next seven months, these algorithms were tested in laboratories around the world to probe for weaknesses and to test the their speeds. There is a huge selection of papers on these tests at the AES1 site for your perusal, so I will not try and detail those tests here. Suffice to say, several of the algorithms had serious problems identified, while others came through with flying colors. The next March, the second AES conference was the forum for the presentation of these results, and a subsequent discussion of which algorithms should thus advance to the final round. These finalists were announced in August of 1999, thus beginning the second round of competition. NIST subsequently issued an excellent report detailing their rationale about each algorithm, including the problems and benefits associated with each.

The AES finalists were:

Obviously, each candidate comes to the conclusion that their cipher is the best. Nevertheless, there are some shared criticisms of the various ciphers that show patterns in each one. Serpent, for example, is universally named the slowest algorithm (in software), even by its creators. Nevertheless, they make their case based on being the most secure algorithm of the bunch. RC6 and MARS are both very fast on certain processors, but terrible on others. As noted above, any serious AES candidate had to perform well across all platforms, and thus this variable performance tended t o compromise these candidates. None of the algorithms were ever broken by a practical attack, however, and all should be considered secure enough for serious encryption work. Thus was held the third AES conference in April of 2000. This was the final conference before the official AES selection, and the last chance for each algorithm to make it s case. The statements above were presented at the end of this conference in an effort to make that case. Once the conference ended, it was up to NIST to make its selection. The candidates could only wait.

Finally, on October 2, 2000, NIST released their final decision, that R ijndael was to be the AES selection. Simultaneously, NIST released a paper detailing their rationale for the selection. In sum, this paper says that any of the finalists could have been selected (an opinion echoed by man y in the industry), but that Rijndael proved to have the proper balance necessary between speed in hardware, speed in software, and security. To quote from NIST's statement:

Rijndael appears to be consistently a very good performer in both hardware and software across a wide range of computing environments regardless of its use in feedback or non-feedback modes. Its key setup time is excellent, and its key agility is good. Rijndael's very l ow memory requirements make it very well suited for restricted-space environ environments, in which it also demonstrates excellent performance. Rijndael's operations ons are among the easiest to defend against power and timing attacks. Additionally, it appears that some defense can be provided against such attacks without significantly impacting Rijndael's performance. Rijndael is designed with th some flexibility in terms of block and key sizes, and the algorithm can accommodate alterations in the number of rounds, although these features would require e further study and are not being considered at this time. Finally, Rijndael's internal round structure appears to have good potential to benefit from instruction-level parallelism.

At this point, it's all over but the shouting. At some point later this year, the Secretary of Commerce will officially designate Rijndael the Advanced Encryption Standard, and a new era will have begun. AES was specified (and is expected) to remain a standard for at least as long as DES, and to protect data for even longer, and barring a major development (such as faster-than-forseen developments in quantum computing), this standard will likely be met. No one expects research into new algorithms to die, however. There will continue to be parallel algorithms developed and used, just as there are today. Thanks to be combined efforts of NIST and the community, however, there will always be the bedrock of AES available.

In conclusion, I'd like to point out the positive role that the U.S. Government, as represented by NIST, has played in this process. The Free Software/Open Source community has taken its share of shots at the government over patents, copyright and crypto export over the past several years, and deservedly so. The AES process, however, was lauded throughout the encryption community as a fair and open process that brought together the best minds available to select the algorithm for the next century (as NIST likes to say). Making an algorithm a FIPS standard gives it a legitimacy that cannot be obtained in any other way, especially given the way that this standard was arrived at. The algorithm is completely free of any IP hurdles, as was specified at the beginning of the process, and since the code is open, it can be downloaded by anyone in the world (and since it was designed outside of the U.S., any attempt to regulate its export from the U.S. would be silly). It is reasonable to criticize when a situation is bad, but it is only fair to praise when something is good.

Bibliography

I used a great number of sources from print and the web, so it's only fair to list them here. I also put many links in the body itself, most of which go into much more detail than I did.

2 of 55 comments (clear)

  1. NIST "covered themselves with glory" this time. by Paul+Crowley · · Score: 5

    I was at the third AES candidate conference, and everyone I spoke to was basically entirely happy with the way the competition was run. I've heard no complaints from anyone involved; in the Cryptogram, I think Schneier's phrase was that NIST had "covered themselves with glory" in the cipher selection process. This is a cipher the academic crypto community can happily stand behind.

    Some may worry that NIST chose one of the ciphers it rated as "Adequate security" rather than those rated "Highest security" like Serpent. However, to be secure the AES must achieve one thing: *it must get used*. If Serpent were named as the winner, it would perhaps be one option in a cipher negotiation stack, but people would tend to avoid using it, preferring faster alternatives. And when they're designing protocols, Serpent would tempt them to include cipher negotiation levels, a notorious source of possible insecurities; attackers try and force you onto your weakest cipher with fake packets before you have the cipher in place. Because Rijndael is so efficient on every platform, it's likely to get used everywhere without negotiation, and overall I think that'll make our protocols more efficient and more secure.
    --

    --
    Xenu loves you!
  2. Rijndael will last much more than 30 years by Paul+Crowley · · Score: 5

    The simple sum says if 56-bit DES was relatively easy in 1998, and if Moore's Law adds two keybits every three years, 128-bit Rijndael falls 108 years later, in 2106, and 256-bit Rijndael falls in 2298. Thus the apt slogan "A cipher for the next century".

    Of course, there are many factors that alter this, chief of which is that we'll probably hit theoretical limits on Moore's Law by then. Ross Anderson speculates that the AES may *never* be replaced.

    (Unrelated footnote: Slashdotter Nic C Weaver presented a paper at the AES3 conference on hardware implementations of AES candidates on FPGAs, and handed out neat little summaries on yellow business cards!)
    --

    --
    Xenu loves you!