This paper outlines simple branch prediction analysis attack against the RSA decryption algorithm.
At the core of RSA decryption is a loop over all bits of the secret key number d. When the bit 1 there is other code executed than when the bit is 0. The CPU branches on a different bit.
A spy process can be run on the CPU which measures the branch cache of the CPU by flooding the cache with branches and measuring the time it takes. When the sequentially running secret process doing RSA decryption makes a different branch (1 instead of 0) it can be noticed in a change of execution time on the spy process’s branches.
In this way quite a lot of secret bits can be derived.
There are some clear buts:
- You must be able to insert a spy process on the computer itself and it should know exactly when the RSA process runs.
- To attain clear readings, there shouldn’t be other processes claiming too much CPU time.
- The spy and CPU process should run on the same physical processor and preferably at the same time (dual core)
An easy fix would be to allocate a whole processor for the RSA decryption time, so no process can spy. Another option would be to add noise in the Branch Prediction Buffer, but that would result in a performance loss.