There are a number of cryptographic problems for which we don't yet have good solutions. However, there are many problems for which good cryptographic solutions do exist. For example, we have good solutions to most of the basic problems of cryptography: encryption, message authentication, digital signatures, key exchange and identification. Despite this, there is an incredibly frustrating phenomenon that keeps repeating itself: even when standard off-the-shelf cryptographic solutions exist, actual implementations are very often wrong. As with any software error, the source of these mistakes can be in the design and/or in the implementation. (Of course, there are many cases where implementing a secure solution is very difficult and very tricky; I am not referring to these cases.)

Looking at some of the implementation errors, I get the feeling that they often occur as a result of the combination of the following two facts: First, cryptographic constructions are incredibly sensitive and mild seemingly benign modifications render them insecure. Second, there are no clear instructions on how a given task should be implemented. Sure, there are plenty of books out there that explain what a block cipher is and what the different modes of operation are, but they don't give an exact description of what should be done in order to encrypt a file on disk. Since the security of implementation cannot be checked by standard quality assurance techniques, the combination of the above is a disaster (without clear instructions, the chances of getting an implementation right is actually very small).

In order to try to improve this state of affairs, one of the themes of this blog is going to be to provide CRYPTO RECIPES that will consist of an exact step-by-step description of how to solve a given problem. I would like to invite recipe orders on any topic relating to cryptography. If you have to implement something and you don't have an exact description of how to do it, I would be happy to hear about the problem and respond. (If you can describe the context that it arose, that would also be nice but there is no obligation.)

For this first post, I will just give one example that shows how tricky it can be to work without an exact recipe. RSAES-OAEP is the new PKCS#1 standard for encrypting with RSA. It is essentially a complex form of padding that is provably resistant against adaptive chosen-ciphertext attacks. Such attacks are arguably unrealistic. However, at CRYPTO'98 Daniel Bleichenbacher demonstrated such an attack on PKCS padding for RSA that could be carried out against an SSL server. Bleichenbacher's attack is a form of chosen-ciphertext attack and, very loosely speaking, works in the following way. An attacker first captures a target ciphertext and then applies multiple transformations to it. Each transformation is then sent to the server and the attacker wishes merely to know if the plaintext that lies behind the transformed ciphertext has valid PKCS padding or does not. This information is of course supplied by the server in the form of an error message. Amazingly, Bleichenbacher showed that this is enough to actually break the original ciphertext open! The RSAES-OAEP standard provably resists such attacks and is therefore recommended for all network encryption. The issue that I wish to raise here is one pointed out by James Manger at CRYPTO 2001. In RSAES-OAEP the padding is checked upon decryption and no action is taken if it is incorrect. However, Manger pointed out that there are actually two distinct types of errors (a possible error in the integer-to-octets conversion and subsequent padding errors). Interestingly, if the server provides different error messages for the different types of errors (something that is very likely), then a Bleichenbacher-type attack is once again possible (and in fact the attack in this case is far more efficient and can easily be carried out in real life).

I think that this example clearly demonstrates just how delicate cryptographic implementations can be. I would like to conclude by comparing implementing cryptography to baking bread. Everyone knows that even the most amateur cook can successfully modify the recipe when cooking a pot roast. However, when it comes to bread, unless you are an expert, you had better follow the exact recipe. The same is true of crypto.