Last week I discussed an attack in which an aggressive but non-privileged process running on one virtual machine can observe the execution path of another virtual machine sharing the same physical CPU core, and how that can lead to stealing an ElGamal private key.
There is an unexpected lesson here, regarding why it is probably a bad idea to write your own cryptographic code.
ElGamal computes a modular exponentiation xs mod N for encryption and decryption. The GNU general-purpose cryptographic library libgcrypt provides ElGamal functions among many others cryptographic building blocks.
The libgcrypt implementation uses a classic square-and-multiply algorithm for the exponentiation. The thing is, the term s in that operation is the private key. If you could observe the sequence of machine instructions used by the square-and-multiply algorithm, you would have the bit sequence of the key.
The attack described in the paper Cross-VM Side Channels and Their Use to Extract Private Keys is very impressive. They cannot simply observe the sequence of instructions run by the other virtual machine. What they do have are very noisy measurements of fragments of the overall sequence.
They use a multiclass support vector machine, a form of supervised machine learning, to extract noisy fragments. They then use a Hidden Markov Model to reduce the errors. This provides a large but still incomplete collection of fragments of the sequence. They then use a technique devised for a somewhat analogous problem, discovering similarities in the amino acid sequences of two proteins. They end up with most of the key — a brute-force search is still needed but they only have to try about 10,000 possible keys.
I did not see that coming! But what is the lesson?
It is very hard to write secure software, especially in the area of cryptography. Even if your code always provides the correct answer, it may do so in a way that a clever observer can obtain unexpected advantages.
There have been many cryptanalytic attacks that take advantage of timing or even power consumption. These are called side-channel attacks. They don’t go after flaws in the mathematics, they take advantage of unexpected information leakage. Here is one that uses CPU cache refill timing to derive instruction sequences and thus key fragments.
Now, I happily admit that the specifics of this case happen to argue against using the current standard implementation, at least in very specific circumstances. The paper suggests using a different algorithm for the exponentiation, such as the Montgomery ladder algorithm. But an important question is: would your programmers have thought about the relative dangers of the multiply-and-square versus Montgomery ladder algorithms?
I doubt it.
Re-implementing cryptographic building blocks can be useful in a university course. “Oh, so that’s how a Feistal network and a sponge function really work.” But given the subtlety of side-channel vulnerability and attacks, it seems very risky to rely on your own re-implementations.
Learning Tree’s Cloud Security Essentials course points out the difficulty of secure design, and the need to use trusted cryptography in the cloud.