Why I like RC5 and RC6, Part 3
In Part 1 I talked about how great RC5 was, in Part 2 I discussed the major complaint against RC5 and the attempt to overcome that complaint in RC6. Now let's compare these two algorithms to other ciphers.
First up, DES. You might be thinking, "DES is broken, it's old, it's a bad cipher." Actually, DES was never broken, the only problem was that it used a 56-bit key, and computers got so fast it was possible to do a brute-force on a 56-bit key in 24 hours. That is, the algorithm is still strong, it's the key that's weak.
Incidentally, the 56-bit limit on the key size is artificial, imposed by the US National Security Agency to make it easier to break. The NSA doesn't like other people to have the ability to keep secrets, so they would rather no one used encryption. However, they knew that they couldn't stop it, that people would use encryption. Hence, they chose to direct the development of DES as a standard. That way, if people were going to encrypt, they could make sure people used the algorithm they wanted them to use. And they made sure it had this 56-bit key.
So how does RC5 compare to DES? It's faster (20 to 80 times faster), smaller (20 times smaller), has a variable round count (more rounds for more security), and much easier to analyze. As for analysis, here's an interesting story about DES. The original algorithm (called Lucifer) used various tables of values, called "S-boxes". There are 16 of them, each with 64 32-bit numbers like 0x00108000 or 0x20101004. During encrpytion, the algorithm performs XOR operations with different values in the tables, table entries determined based on the key and input data. However, the NSA suggested some changes to the tables. At the time, no one outside the NSA knew why the proposed tables would be better, but the change was made. Years later, someone in the industry came up with an attack called differential cryptanalyis. It turned out that DES with the old tables was susceptible to the attack, but with the new, NSA tables, it was secure.
Companies that wanted keys bigger than 56 bits had to use DESX or TripleDES if they wanted to follow the standard. Those who were willing to use a non-standard algorithm used RC2, IDEA, Cast, Safer, and Blowfish (there were others, but these were the leaders). But RC5 was the next generation beyond all these algorithms. It was faster, smaller, and used less memory. It also did not use S-boxes. Other algorithms followed the DES model and had these look-up tables. But now people were thinking, "How do we know the S-boxes are good? After all, we know that there can be bad tables, look at DES." In the late nineties, RSA Data Security was selling RC5 to companies that liked its speed and size. Companies making small devices, such as cell phones or other hand held equipment, especially liked it. We even were able to put it onto a pacemaker (that project never went through, but we were able to do it).
The main problem with RC5 now was that it was patented. Anyone who wanted to use it had to pay RSA. Because DES, TripleDES, and other algorithms were free, you could write the code yourself or sometimes even find Open Source code. Why pay for something when you could get the competition for free? Trust and support might be reasons, but the main reason people paid for RC5 was the speed and size. If they simply couldn't afford more than a few hundred bytes of code size or memory, RC5 was about the only game in town.
The next hurdle was AES. The US government declared a competition: submit your algorithm and we'll choose one to replace DES. There were 15 original applicants, narrowed down to 5: RC6, Rijndael, Serpent, Mars, and Twofish.
The first question might be, why not simply update DES to use bigger keys? Remember, the algorithm itself was never broken, it was still strong, it was the key size that was the problem. Well, that's pretty much what Rijndael is. The actual DES algorithm is so slow, a version that simply uses bigger keys would never win. But researchers Rijmen and Daemen, developed an algorithm that updated the DES model of XOR operations based on S-boxes. They also supplied good mathematical evidence to show that the S-boxes were secure. It was much faster.
Researchers from around the world examined all five algorithms. One thing came through among all independent researchers: RC6 was much smaller in code size and memory usage, and almost universally significantly faster than all the other algorithms. Someone found an issue with the RC6 key table, but that was resolved. Others were upset that RC6 "barely" exceeded the security requirements, whereas the others were way over the bar. Then there was the multiply. Those testing the algorithms on Smart cards found RC6 very slow on those cards that did not have a fast multiply. Finally, people who build chips pointed out that making an RC6 chip would not be as easy as making a Rijndael chip (a chip that has the algorithm built in, rather than a sequence of instructions, the algorithm is performed on the chip).
In my opinion, the complaints were not that important. "Barely cleared the security bar?" That's just stupid. If the requirements were to have a cipher that has security level 500 (a made-up number for illustrative purposes only), and RC6 has level 510 but the other algorithms have level 620 – 740, so what? You need 500, you have 500. If you don't think 500 is enough, then set the bar to 600. RC6 will be 22 or 24 rounds instead of 20 and be 610. But then the detractors would say, "Well, 610 barely clears the bar, so that's not good enough." OK, then make the bar 700, or 800 or 1000, or 1,000,000 or 500 quintillion. Add more rounds and the algorithm will meet the requirement. But you can't say, "You must meet this minimum requirement, but what I really want is for you to meet minimum + extra."
That's like saying, "You must be at least 4 feet 5 inches tall to ride this roller coaster," then denying someone who is 4 feet 6 inches because they just barely met the minimum. If 4 ft 6 is too small, then make 4 ft 7 the minimum. But then someone 4 ft 8 barely meets the min, so make the min 4 ft 9. And so on until the min is 8 ft tall and no one rides.
The multiply? As Rivest pointed out, the idea of AES was to be the algorithm for the next 20 years, not for just the year 2000, and all chip makers, including Smart card chip makers, were either now, or very soon going to be, making chips with fast 32-bit multiplies, regardless of the AES selection.
The algorithm in hardware? That will account for less than 1/100 of 1% of the usage of the algorithm. You're saying that you want to deny 99.99 % of the users of the algorithm the advantages of RC6 so that .001% of the users get something better? And it's not like the alternative was all that much better. RC6 got an A- from the hardware designers, Rijndael got an A.
However (and this is the big however), some of the other algorithms (including Rijndael) did not have those complaints. In other words, the drawbacks to RC6 were small (in my opinion invalid), but other algorithms had virtually no drawbacks. Well, they all had one drawback: size and speed.
In the end, Rijndael was chosen as the AES algorithm. In my opinion here's why.
1. The patent. None of the other algorithms had any intellectual encumbrances at all. The developers of all the other algorithms had relinquished all intellectual property rights, whether the algorithm was selected or not. RSA said they would relinquish IP rights only if RC6 were selected. Too many people just didn't want to have even a hint of IP issues.
2. Size was no longer important. One of the big advantages of RC6 was not seen as important. Where Rijndael would be about 15,000 bytes of code size plus memory, RC6 was less than 1,000. But 15K on even a cell phone or other constrained device was soon to be no issue.
3. Speed was not as important. Chips are getting so fast that a "slow" algorithm will still be fast enough. If you need 12,000 bytes per second, and with RC6 you get 100,000 and with Rijndael you get 30,000, how much does it really matter?
4. Trival complaints. RC6 had some perceived drawbacks (the multiply, etc.), which generally wouldn't be real issues. But when you need to make a decision between two very good things, the insignificant or even invalid complaints might be the only thing you have to differentiate.
5. New vs. old. The main component of RC6 is the data-dependent rotation, an idea almost 20 years younger than DES. In the crypto community, age is often better. The longer something has been around and studied, and survived in good shape, the more confidence it inspires and the less likely someone is willing to switch. Because Rijndael uses the same philosophy of DES, some will always feel it is the "safer" choice.
So I like RC5 best because it is so fast, small, and elegant. No matter what system you're using, with computers smaller and faster is always better. Small and fast can never hurt and sometimes help. Big and slow can sometimes hurt you. And you don't have to sacrifice security for the elegance.
RC6 solves the rotate count issue, but I still like RC5 better because I don't think the rotate count issue is a real problem. It's solved by adding more rounds, each of which is much faster than an RC6 round. As Terence Spies says, "Throw rounds at it."