Alvaro VidelaRead my Thoughts. Follow my Leads.

You don’t roll your own crypto

March 2 2014

Imagine you enter a contest organized by the National Institute for Standards and Technology (NIST), where the goal is to design a new encryption standard to replace DES and Triple-DES. Some of the contestants? The RSA, IBM, Deutsche Telekom and Counterpane (a team lead by Bruce Schneier). Would you think you stand a chance of winning? I know I wouldn’t, but a Belgian team composed by Joan Daemen and Vincent Rijmen beat the other teams with their submission: Rijndael, the system that was later to be come the new Advanced Encryption Standard (AES).

The book The Design of Rijndael has a very fascinating first chapter where the authors describe the selection process proposed by the NIST to chose the new AES, from which I would like to share here some facts that are quite interesting. They prove, that you don’t roll your own crypto.

Note that I don’t claim to know the stuff I’m presenting here, or be an expert in cryptography, I’m just learning about this topic and I thought it would be interesting to share this story. I’ve also added a list of books at the bottom, that are the ones I’ve been using to learn about it.

The selection process

The selection process for AES started in 1997 and it was open, anyone could submit and entry as long as the entry met the requirements:

The designers should provide:

The security and evaluation of the submissions was not going to be made by NIST, but by the cryptology community. Anyone could have commented on the entries and send their papers back to the NIST.

As you can see from the requirements, this wasn’t a contest for hobbyists, it required serious effort and knowledge. This meant that many proposal got filtered out simply by these requirements.

From the start something quite cool happened, a team called Cryptix decided to provide Java implementations for all ciphers and the KAT and MCT tests. Here we can see the community working together to achieve a common goal.

Round One

Another interesting fact from the selection process was that it happened in the open, together with conferences about security that gathered most of the researchers interested in the topic.

The cryptology community mounted different kinds of attacks and tried to analyze the different candidates. Then people will send submissions to be presented at the conference. The main topics of analysis were:

Security

This was the most important category, no news about it. Some candidates already showed some theoretical design flaws at this stage. Later the book develops the math behind AES and one can see that one doesn’t design an encryption algorithm over some beers. This might seem obvious, but still people keep designing their own encryption.

Costs

Here the evaluation was two fold. First, algorithms should be free of royalties as mentioned above. Also contestants were not allowed to exercise patents over other people’s ideas. The second part was the analysis of computational costs, program size, memory usage, and so on.

Algorithm Difficulty

Here the algorithms were analyzed on how easy was to implement them for different platforms. From 8-bit micro-controllers to dedicated hardware, like encryption/decryption at one gigabit-per-second rates.

They were also interested in key-agility, that is, how easy it is to setup new keys for the algorithm.

Finally, simplicity played an important role: how easy it is to implement the algorithm and make sure that the implementation is correct.

Selecting the Five Finalists

Fast forward to 1999, where the second AES conference was held in Rome. Here papers presented crypto-attacks, cipher cross-analysis and algorithm observations. Were you ever afraid of code reviews? Well, imagine the whole cryptology community reviewing your code. If your code survives the process, then there’s must be something good in it. At this point it was shown that Magenta, the entry by Deutsche Telekom didn’t satisfy the security requirements imposed by NIST. Another algorithm called DEAL was know to not satisfy the security requirements, and another paper demonstrated that an algorithm called HPC had weaknesses.

An example that shows how important peer review is in this kind of situations was a paper presented by a researcher that wasn’t member of any of the contestant teams. This person analyzed the performance of the algorithms on Pentium Processors, showing that Rijndael was among the five fastest algorithms.

Another person presented a paper comparing the security strength of the presented algorithms, showing that there was a big margin between them, prompting for this detail to be taken into account when making a choosing and algorithm. There was an algorithm called SERPENT that was slow, but it had a high margin of security.

Other papers focused on how the algorithm performed in 8-bit and 32-bit processors. Some algorithms didn’t even fit into the smaller architectures. Again, Rijndael was one of the best algorithms in this category.

At the end of the conference there was a workshop where the five finalists were announced:

Round Two

At this stage NIST made another call for papers discussing the finalist algorithms. In this case even the NSA took part, sending several performance simulations that were done for the finalists. On the area of cryptographic attacks there were no breakthroughs, since none of the finalist showed any weaknesses that would disqualify them from the competition. On the area of hardware implementation, Rijndael performed well again.

The aforementioned results were presented at a conference in New York City, in April 2000, ending with a questionnaire to the attendants to vote for their favorite algorithm. Rijndael was voted the public’s favorite.

The Selection

On October of the same year, the NIST announced that Rijndael would become the new AES without any modifications. The NIST published a report were it made the announcement, saying about Rijndael:

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 low memory requirements make it very well suited for restricted-space environments, in which it also demonstrates excellent performance. Rijndael’s operations 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 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 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.

Conclusion

I hope you found this story as interesting as I found it when I read it for the first time. For me the take away from it is that while it might be useful to create our own cipher algorithm for education purposes, we should never attempt to create one to be used in production. Also, please don’t publish them. Somebody will use them. I’ve seen how people have tried to use in production complete jokes such as gifsockets. We could see that teams like the people from Deutsche Telekom had created algorithms that weren’t’ secure enough according to the selection criteria. Also, the eyes and scrutiny of world’s cryptology experts are a better safety net than what we might think is safe. As they say on TV: don’t try this at home, kids.

As I said before, this is based on Chapter 1 from the book The Design of Rijndael. It’s a quite small book that describes the mathematical background behind AES, its design and implementation.

Books

In case you want to learn more about the subject, here are some books I’ve been studying:

blog comments powered by Disqus