Cryptography And Quicksand

A basic question about cryptography that we pretend is not there.

Victor Shoup is one of the top experts in cryptography. He is well known for many things including a soon to be released book that is joint with Dan Boneh on, what else, cryptography; and the implementation of many of the basic functions of cryptography.

Today I want to talk about my recent visit to the Simons Institute in Berkeley where I heard Victor give a special lecture.

This lecture led to an interesting question:

How do we know if a crypto function is correctly implemented?

Before I discuss this let me report that this summer the institute is running an excellent program on cryptography. It was organized by Tal Rabin, Shafi Goldwasser, and Guy Rothblum. While I just visited for a short time last week, it seems to be an incredibly well run program, with much of the thanks going to Tal. Tal added social interaction as part of the program, about which more below. The institute director, Dick Karp, told me he thought these additional social activities were wonderful and they helped make the program so enjoyable and productive.

Victor’s Talk

Victor gave his special talk on mostly known—to experts—results in basic cryptography. His talk was well attended, well structured, and well delivered. He made three points during the talk that were striking to me:

• He wrote all of the operations used in his talk using “additive” notation. Most crypto systems use some abelian group as the base of operations, of course some use more than one. Usually these groups are written using multiplicative notation: . Victor switched this to . This is of course not a major difference, but it had some nice properties. Also, for those of us who are comfortable with the usual notation, it made us have to rethink things a bit.
• He repeatedly made the comment that while many of the provable methods he presented where fast enough to be practical, they were not used. He essentially said that provable methods seemed to be avoided by real system builders. As you might image this was not a welcome comment to the group that consisted mostly of researchers who work in cryptography. Oh well.

• He also made another point: For the basic type of systems under discussion, he averred that the mathematics needed to describe and understand them was essentially high school algebra. Or as he said, “at least high school algebra outside the US.” This is not a negative point: there is nothing wrong with the systems requiring only simple operations from algebra. Deep mathematics is great, but not necessary to make a great cryptographic system.

A Question

Kathryn Farley, a researcher in performance arts, was at Victor’s talk, since she was also in town. She could not stay for the entire 90-minute lecture—she left after about one hour for another appointment. Later that day we talked and she said she had thought about asking a question to Victor, but not being an expert in cryptography, was unsure if her question was naive or not. I asked her what it was and she replied with the question atop this post. To say it again:

How do we know if a crypto function is correctly implemented?

I told her that it was, in my opinion a terrific question, one that we often avoid. Or at best we assume it is handled by others, not by cryptographers. I immediately said that I have discussed this and related questions before here and I still am unsure what can be done to be ensure that crypto functions are correctly implemented.

Suppose that is claimed to return a random number: of course it is a pseudo-random number generator (PRNG). Lets assume that it claims to use a strong PRNG method. How can we know? We can look at the code and check that it really works as claimed, but that is messy and time consuming. Worse it defeats the whole purpose of having a library of crypto functions.

A nastier example: Suppose that uses the following trick. If the date is before January 1, 2016, it will use the correct strong generator. If the date is later, then it will use a simple PRNG that is easy to break. Further it makes this happen in a subtle manner, which is extremely hard to detect by code inspection. How would we discover this?

The Tea Party

Friday at the institute was “The Tea Party.” At the end of the day all were invited to be outside near the institute’s building, and join in eating, drinking, and playing a variety of games.

The food was quite impressive—much better than the standard fare that we see at most university gatherings. It was also well attended, which probably is related to the quality of the food.

Kathryn and I were there. And it was a perfect time and place to ask some of the cryptographers about her question. We got several answers, most of which were not very satisfying. I will list the answers without directly quoting anyone—protecting the innocent, as they say.

Some said that the issue was not about crypto, but about software engineering. So it was someone else’s issue.

Some were more explicit and said that software engineers should use verification methods to check correctness.

Others said that the code should be checked carefully by making it open source: basically relying on the “crowd” for correctness.

None of these methods is foolproof. Which raises the question: how can we actually be sure that all is well?

Some Ideas

I was not very happy with any of the answers that we got. I would suggest that this correctness problem is special and because it is about crypto systems it may have approaches that work that do not work for arbitrary code.

Here are some ideas that perhaps can be used: I think they are just examples of what we may be able to do, and welcome better ideas.

Property Testing:

Many crypto functions satisfy nontrivial mathematical properties, which is quite different from arbitrary code. Consider RSA. One could check that

And the same with the decode function. This doe not imply correctness, but a failure would mean the code is incorrect.

Version Testing:

If the code is critical one could in principle implement the function twice, or more times. This is best done by different vendors. Then the outputs would be checked to see if they are identical. Note since crypto functions usually operate over finite fields or rings, there is no rounding errors. Thus, the different implementations should get identical values.

Note this is a standard idea in software engineering—see this. The key assumption is that different versions should have different errors. This appears not to be the case in practice, but the method still has something behind it. Wikipedia says: -version programming has been applied to software in switching trains, performing flight control computations on modern airliners, electronic voting (the SAVE System), and the detection of zero-day exploits, among other uses.

Check No State:

A crypto function should be a function and have no state. The date “attack” I gave earlier shows that functions should be forced to not be able to create any state. I believe that it may be possible to “sandbox” the code of a alleged function so that it cannot keep any state. This obviously makes the date trick impossible.

Open Problems

How do we be sure that crypto functions are correctly implemented? I suggest simply that cryptographers should start to view this issue as another type of attack that can be used against their system. Perhaps viewed this way will lead to new ideas and better and more secure systems.