Kurt Seifried, [email protected]
About 25 years ago the US NBS (National Board of Standards, renamed to NIST) put out a call for an encryption algorithm, unfortunately back then there wasn't a whole lot of public cryptography going on (they mostly worked for the NSA). Another call was put out in the federal register to which IBM responded with a algorithm called "Lucifer". This is where things get interesting. Originally Lucifer used a 128 bit key, however after the NSA got involved the key length was reduced to 56 bits, making it 4,722,366,482,869,645,213,696 times easier to brute force the key (2^72). This is rather interesting because it made it possible for the EFF to design and build a custom chip that had one purpose, to brute force DES keys. For less then $250,000 they engineered, and manufactured a machine that could run through the entire 56 bit key space in a matter of days (less then 5 days on average). This was accomplished by a small public effort and completed in January of 1999. This is especially interesting since the NSA is many years ahead of public cryptographic efforts (the NSA is the worlds largest employer of mathematicians). People realized that DES on it's own was secure against casual attackers, but not against a reasonably determined attacker, so 3DES was created, basically 2 56 bit keys are used to encrypt the data, first the A key, then the B key, then the A key again. This makes the resulting effort required to brute force it exponentially higher, unless there is some fundamental flaw in DES it probably isn't possible to brute force it. This of course creates a new problem, the resulting encryption and decryption is extremely slow and computationally expensive. NIST responded to this several years ago by calling for a replacement for DES, the AES (Advanced Encryption Standard), which has now been chosen and announced.
AES
AES must be faster, stronger and cheaper to implement then DES. It had to be fast when implemented in software, and small so it could be implemented in hardware (token cards/etc). It has to be highly resistant to attack since like DES it will be in service for a long time (to put it in perspective UNIX measures time in seconds since 1970, the "epoch"). After a lengthy process of many submissions it was whittled down to 5 finalists. At this point these algorithms are reasonably safe, they have been analyzed in great detail, and while some concerns have been found in most cases they are minor or easily solved (i.e. using more rounds). The algorithm chosen was Rijndael.
So what exactly are the differences between these various algorithms? In general they are all capable algorithms, however various trade offs are required. If you want the algorithm to be fast and secure it'll be more expensive to implement in low end hardware. MARS is extremely fast on high end hardware and most computers, but requires a much higher gate count then the other algorithms being considered for use on smartcards. The cost of implementation on smartcards and so forth is an important factor in choosing the AES finalist since the number of smartcards and other small devices that will be deployed using AES is significant (tens of millions over the next decade or two). At the same time the algorithm must be able to encrypt and decrypt many gigabits/second (imagine several thousand clients or sites connecting to a large site such as a central office). As network encryption becomes increasingly common (IPSec is just starting to take off) the need for an algorithm that can be implemented in hardware and is extremely fast is critical, especially since this algorithm will be in use for a long time.
MARS
MARS is from IBM, and surprisingly enough is not the one most similar to the original DES. MARS is designed with reasonably high end hardware in mind and is extremely fast. This means that for implementation on smart cards it will require about 70,000 gates, quite a bit more then the other candidates. On a 200mhz Intel Pentium Pro IBM claims that MARS can handle 65 megabits/sec, and with a custom hardware chip containing ~393,000 gates it will be able to handle 8 gigabits per second. MARS also supports keys from 128 to 448 bits, larger then some of the other candidates.
Serpent
Serpent is an international effort between Cambridge University, Haifa Israel and University of Bergen, Norway. Serpent is basically an improved version of DES, while not as sexy as other algorithms it is based on extremely well understood principles and has withstood a lot of analysis (20+ years). Serpent supports key sizes from 40 bits to 256 (I'm not sure if it supports larger keys but the documentation I have read does not seem to indicate it). Compared to other AES candidates Serpent is relatively "slow", they estimate 14.7 megabits/sec on a Pentium 200, significantly slower then MARS. However with dedicated hardware requiring around 100,000 gates, unfortunately no numbers on speed were given.
RC6
RC6 is from RSA laboratories, one major difference between it and other AES candidates is that it does not use look up tables, significantly reducing it's size (an important factor for smartcards). Unfortunately RC6 appears extremely slow when compared to others, an implementation written in assembly language on a Pentium 200 it would encrypt and decrypt at just over 12 megabits/sec, even slower then Serpent. However because of it's use of simple operations a hardware based implementation should be capable of over a gigabit per second, while this is more then sufficient for most current applications it could prove to be a problem in 10 years. RC6 also supports keysizes larger then 256 bits.
Rijndael
Rijndael was designed by a Dutch bank that handles a lot of ATMs, and it shows a lot of bias in this regard. Rijndael's size on 8 bit processors is quite impressive, code length is just over 1k, and ram requirements are 52 bytes when using a 256 bit key (less for smaller keys). The numbers they provide for speed on a Pentium 200 are rather odd, with ANSI C they claim 27 megabits/sec with a 128 bit key, and 19.8 megabits/sec with a 256 bit key. Using Visual C++ however the numbers increase by about 250%, 70.5 megabits/sec with a 128 bit key, and 51.2 megabits/sec with a 256 bit key. Unfortunately I have not been able to find any information on the number of gates needed to implement this algorithm in hardware, nor any performance figures, but from the general design and speeds on a Pentium it sounds like it would compare favorably to the other candidates.
Twofish
Twofish is an American effort, primarily by Counterpane Systems (Bruce Schneiers company, currently moving into managed security services). Twofish supports key sizes over 256 bits, and is extremely fast, producing 90 megabits/sec on a Pentium 200 (although the keysize associated with this is not mentioned). On smart cards it requires just over 2k and can be implemented in as little as 14,000 gates, larger implementations of up to 80,000 gates being faster. The numbers for a dedicated piece of hardware with 30,000 gates running at 150 MHz claim 1.2 gigabits/sec, using more gates and high clock speeds faster speeds can be achieved. Like most of Bruce Schneiers work it is "clean", they did not try to "push the envelope", sticking to reasonably tried and true methods, and allowing for various safety margins.
As far as speed goes it looks like MARS and Twofish are well ahead of the rest, and MARS appears to be the only one with support for keys larger then 256 bits (which counts in it's favor for "future proofing" in my opinion). Serpent is enviable because of it's basic design, using DES as it's base it uses extremely well prooven techniques. Rijndael and RC6 both look very attractive for smart cards, however they may not scale to well to high throughput situations, especially using 256 bit keys. The choice of Rijndael is reasonable given that none of these algorithms are "perfect" (to gain speed you trade off size, and so on). Hopefully no-one will find any significant problems in it since it looks like we'll be using this for the next few decades.
Reference links:
http://csrc.nist.gov/encryption/aes/
http://www.tml.hut.fi/~helger/aes/kenneth.txt - aes test results
http://csrc.nist.gov/encryption/aes/round2/NSA-AESfinalreport.pdf - hardware encryption test results
http://www.eff.org/descracker/ - Deep Crack
Last updated 7/7/2002
Copyright Kurt Seifried 2002