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
Still, past a certain point, you must consider practicality. While I'd love to chain Twofish and Rijndael together (Twofish is a Feistel cipher somewhat similar to DES, Rijndael is some other kind of beasty altogether, so it is unlikely that BOTH would be broke), the result would be less than half the speed of Rijndael. While this would be fine for a file encryption program, I wouldn't want to try it for encrypting a gigabit Ethernet network connection -- it'd suck my CPU to the toilet.
Past a certain point, you have to look past paranoia and decide: a) Just how secure the data needs to be (and against whom does it need to be secure), and b) what's practical to do, given current technology. I made the decision, when Rijndael was chosen as the Advanced Encryption Standard, that Rijndael alone provided adequate security for my purposes. Depending upon how sensitive your data is (and what happens if it is compromised), you may make a different decision. I'm sure that Bin Laden triple-encrypts everything, since failure of his encryption means that he dies. If the consequences of failure are death and imprisonment, of COURSE you should double or triple encrypt everything, regardless of the performance penalty. Otherwise, it's a more difficult analysis, and usually double or triple encryption doesn't buy you enough to outweigh the costs.
-E
Send mail here if you want to reach me.
You'll need to devise your own shell scripts to serve as a key manager etc.,this is a raw Unix component similar to 'dd', rather than a swiss-army-knife application like PGP.
-E
Send mail here if you want to reach me.
While not as fast as Serpent in hardware, Rijndael is pretty efficient, and doesn't demand too many gates. There should be no problem with encrypting a T1 using Rijndael even in software; in hardware it should be able to encrypt much fatter links, especially used in CTR mode (or OCB, IAPM etc) where you can do several block encrypts in parallel.
--
Xenu loves you!
I'm pretty sure RC6 had the smallest security margin of the five finalists.
Note that Bruce Schneier has also gone on record as saying that he does not believe any practically useful weakness against Rijndael will ever be discovered. Also, Rijndael gains a lot of strength from each round, so the security margin may be misleading; the Square based attacks stretch across quite a few rounds but they're very hard to extend.
--
Xenu loves you!
This piece didn't really seem all that complete since there were a couple of things that should have been mentioned. The first one was that the standard did not mandate just an 128-bit key length but also required key lenghts of 192- and 256-bits. An 128-bit block size was also required.
Secondly it should have been mentioned that Rijndael had the smallest "security margin" of the AES finalists. (At least I'm pretty sure it was the smallest, I don't have the papers here to confirm.) What this means is that out of the number of rounds (essentially iterations) of the cipher, it has proportionally the most broken of any of the finalists. While none of these represent real-life attacks they do give some indication of a confidence level for the future. Remember, as Bruce likes to say, "attacks always get better."
Finally it should be noted that this is only a standard for a block cipher so calling it a "encryption standard" is a little misleading. It would be nice also to have an official stream cipher standard and public key encryption standard.
I'm not entirely certain no cipher negotiation is a good idea. If Rjindael is ever cracked, it would be nice to be able to plug in another algorithm. Plus, Rjindael is fairly new, so older programs may not support it.
But, it does at least make an obvious default.
Citizens Against Plate Tectonics
hmm.. not according to Van Dale's dictionary.
[snip]
Schrijf een tussen-n als het eerste deel van de samenstelling:
niet op een e eindigt en een meervoud heeft op -en: bloemenmand, leeuwendeel
een persoon aanduidt en een meervoud heeft op -en: blindeninstituut, ziekenhuis
[snip]
(translation)
Use the extra 'n' when the first part of the compound word:
-doesn't end in 'e' and has a plural ending in 'en'
-denotes a person and has a plural ending in 'en'
koe ends in 'e', so no 'n'. koeieuier stands. Now I would like to hear Bush pronounce this.
//rdj
No one can understand the truth until he drinks of coffee's frothy goodness.
--Sheikh Abd-Al-Kadir, 1587
According to the Serpent WWW site, DES can encrypt 15 Mbit/sec on a Pentium 200; Serpent manages 45 Mbit/sec - three times faster, despite being much more secure! A great deal of effort went into optimising both Serpent and Rijndael for performance; I can't see the corresponding figure for Rijndael on their page, but I was told a few weeks ago that Serpent basically lost because it was slower than Rijndael... (Since this came from one of the guys who worked on the performance optimisations, I think he'd know!)
I'm currently doing an encryption project with Ross Anderson (one of the Serpent guys) as my supervisor. It's a public key system (RSA with 2048 bit keys). Unfortunately, I'm using DES for part of the project, which probably won't make him happy :-/
It's gonna take about 2 more years for them to crack RC5-64, but hey, let's get started on AES now! According to my rough calculations, it should take a mere 1,000,000,000,000,000,000,000 (that's 1^20) years to break at today's computing speed!
Unless we can get some time on the NSA's über-secret quantum computer and do it in a few minutes, that is.
:)
I guess he never heard of Quantum Computation.
I'd like to play Quake 21 (or Doom 15) in one of those babies
- IJ actualy represents an Y with two dots on top. It reads strange otherwise
- UI actualy reads as OU. For example UIT is read as the english word OUT (and means the same)
- The letter G can be read in two totally distinct ways: As the G of Going or as a gutural groan (nothing quite like it in any of the other languages i know). It all depends on the origins of the word: "garage" is G because it comes from the French, "gaan" is the gutural thing.
I expect this to be corrected in Dutch v2.0Best Regards,
A Dissatisfied User
What really sucks, is I just set up a VPN between offices using DES and now their is something new out. Oh well, back to the old drawing board.
Of course, that's just my opinion, I could be wrong.
Calling the DES replacement AES is like naming a specific product "new" or "ultimate".
I always thought the same thing about the "Very Large" qualifier in VLSI, or the V and U in VHF and UHF.
Five years later it isn't new, and what are you going to call its replacement?
I take your point about the name getting obsolete, but as an aside: AES will probably last longer than just 5 years. (DES lasted as a standard for a LONG time, much after most people thought it should have. Hopefully AES won't be thought of as weak for a long time.)
I've been playing with the perl API to the Rijndael encrytion scheme and have found it easy to use and speedy. The module is very new, and does cause a segfault it you feed it data of an improper length (instead of throwing an error), but it is interesting to experiment with this emerging technology. Read about the module here: http://search.cpan.org/search?mode=module&query=Ri jndael
Can't you give it another name ? (Propose it as a tweak !)
Dutch is a wonderful language. Currently we are debating about the names "Herfstvrucht", "Angstschreeuw" and "Koeieuier". Other suggestions are welcome of course. Derek Brown, Toronto, Ontario, Canada, proposes "bob".
If someone is passing you on the right, you are an asshole for driving in the wrong lane.
Who in their right mind is still using DES for anything important? I think the fact that it's been cracked a number of times puts me off from using it.
terradot, growing awareness
Better make sure RamBus doesn't join!
--
Top Most Bizarre/Disturbing Error Messages
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)
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!