Slashdot Mirror
AES: Learn All About It
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:
- MARS (IBM) (their case)
- RC6 (RSA) (their case)
- Rijndael (their case) (how to pronounce it)
- Serpent (their case)
- Twofish (Counterpane) (their case)
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.
BibliographyI 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.
- NIST's main AES site is the place to start. It links to most of the technical information I linked to above.
- RSA's crypto FAQ has been around for many years, and the latest edition only gets better. Covers all sorts of ground on cryptography, both general and specific. If you're trying to learn more about crypto, this is the definitive place to go.
- SANS InfoSec has a good overview of the process and the finalist algorithms.
- A Cryptographic Compendium has a good AES section
- SecurityPortal has an excellent perspective on what AES means
- Everyone's favorite IT rag The Register has a solid overview of the process
- Bruce Schneier publishes a crypto newsletter through his company, Counterpane Internet Security. See especially the issues from May 15, 1998, March and August 15, 1999, and April and October 15 of 2000.
- Simon Singh's The Code Book provided some excellent background
Right now I believe that the NSA has given up on cracking ciphers, and is more interested in securing America's commercial transactions to protect them from info warfare. Besides, as one spook divulged somewhere that I don't recall, the NSA doesn't need to crack the encryption to monitor your communications. Most networks and operating systems are so insecure that, if they decide to monitor you, they can intercept your data long before it hits the wire.
-E
Send mail here if you want to reach me.
At which point AES would get renamed PES, the Previous Encryption Standard
Where if you don't "FES" up to what your key is, they'll have at you with rubber pipes...
If you're not part of the solution, you're part of the precipitate.
Calling the DES replacement AES is like naming a specific product "new" or "ultimate". Five years later it isn't new, and what are you going to call its replacement? "really ultimate, we mean it this time"?
Calling DES by its name now feels silly because the S is more or less false. Three decades from now we'll feel silly calling these algorithms AES, because our hardware will be able to crack 128-bit keys in eight seconds (while ripping mp3's, of course), and that hardly counts as "Advanced".
Still, I'm looking forward to Razjdxndawl. (I can pronounce it no problem, but heck if I can remember how to spell it.)
You cannot apply a technological solution to a sociological problem. (Edwards' Law)
Sure, AES is (almost certainly) more secure. But in your requirements phase, you presumably determined that DES provided sufficient security for your needs. You presumably determined that your VPN needed to keep data secure for approximately 24 hours and anything more secure was simply overkill.
The introduction of AES does not change this. Your data is still secure for about 24 hours against a custom-built DES cracking machine, longer against a general purpose attack.
I suggest you read Secrets and Lies so you can understand the tradeoffs in the computer security field.
--
Oceania has always been at war with Eastasia.
Not much to say here.
I noticed some links were bad. So, for your pleasure, look at http://www.nist.gov/aes
instead. It has all the links to everything.
In case anyone is wondering if there are any applications that use AES, the newest version of PGP do. I am not using any version past 6.5.8 due to the NAI/PRZ split that was noted here on Monday, but I thought I would make sure you all knew.
----------------------
Kurt A. Mueller
kurtm3@bigfoot.com
PGP key id:0x4FB5FB1D
Lawrence Lessig is my personal hero.
" SPECIAL NOTE - Intellectual Property
NIST reminds all interested parties that the adoption of AES is being conducted as an open standards-setting activity. Specifically, NIST has requested that all interested parties identify to NIST any patents or inventions that may be required for the use of AES. NIST hereby gives public notice that it may seek redress under the antitrust laws of the United States against any party in the future who might seek to exercise patent rights against any user of AES that have not been disclosed to NIST in response to this request for information."
-- Quoted from the NIST homepage
Its nice to know that someone thought this through and/or has been paying attention to recent events in the Patent arena.
This space for rent. All reasonable inquiries will be entertained at proprietors discretion.
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!
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!