Ross Anderson - Security Engineering

The usual real-world solution is optimal asymmetric encryption padding (OAEP), where we concatenate the message with a random nonce , and use a hash function to combine them:

In effect, this is a two-round Feistel cipher that uses as its round function. The result, the combination , is then encrypted with RSA and sent. The recipient then computes as and recovers as [213]. This was eventually proven to be secure. There are a number of public-key cryptography standards; PKCS #1 describes OAEP [995]. These block a whole lot of attacks that were discovered in the 20th century and about which people have mostly forgotten, such as the fact that an opponent can detect if you encrypt the same message with two different RSA keys. In fact, one of the things we learned in the 1990s was that randomisation helps make crypto protocols more robust against all sorts of attacks, and not just the mathematical ones. Side-channel attacks and even physical probing of devices take a lot more work.

With signatures, things are slightly simpler. In general, it's often enough to just hash the message before applying the private key: (mod ); PKCS #7 describes simple mechanisms for signing a message digest [1010]. However, in some applications one might wish to include further data in the signature block, such as a timestamp, or some randomness to make side-channel attacks harder.

Many of the things that have gone wrong with real implementations have to do with side channels and error handling. One spectacular example was when Daniel Bleichenbacher found a way to break the RSA implementation in SSL v 3.0 by sending suitably chosen ciphertexts to the victim and observing any resulting error messages. If he could learn from the target whether a given , when decrypted as (mod ), corresponds to a PKCS #1 message, then he could use this to decrypt or sign messages [265]. There have been many more side-channel attacks on common public-key implementations, typically via measuring the precise time taken to decrypt. RSA is also mathematically fragile; you can break it using homomorphisms, or if you have the same ciphertext encrypted under too many different small keys, or if the message is too short, or if two messages are related by a known polynomial, or in several other edge cases. Errors in computation can also give a result that's correct modulo one factor of the modulus and wrong modulo the other, enabling the modulus to be factored; errors can be inserted tactically, by interfering with the crypto device, or strategically, for example by the chipmaker arranging for one particular value of a 64-bit multiply to be computed incorrectly. Yet other attacks have involved stack overflows, whether by sending the attack code in as keys, or as padding in poorly-implemented standards.

While RSA was the first public-key encryption algorithm deployed in the SSL and SSH protocols, the most popular public-key algorithms now are based on discrete logarithms. There are a number of flavors, some using normal modular arithmetic while others use elliptic curves . I'll explain the normal case first.

A primitive root modulo is a number whose powers generate all the nonzero numbers mod ; for example, when working modulo 7 we find that = 25 which reduces to 4 (modulo 7), then we can compute as or which is 20, which reduces to 6 (modulo 7), and so on, as in Figure 5.17.

Thus 5 is a primitive root modulo 7. This means that given any , we can always solve the equation (mod 7); is then called the discrete logarithm of modulo 7. Small examples like this can be solved by inspection, but for a large random prime number , we do not know how to do this efficiently. So the mapping (mod ) is a one-way function, with the additional properties that and . In other words, it is a one-way homomorphism . As such, it can be used to construct digital signature and public key encryption algorithms.