branch prediction analysis
Modern microprocessors have facilities to gather statistical information about how branches in a program are taken.
Quite a bit simplified: the reason for this is, that these processors execute their instructions in a rather long pipeline, and thus if an instruction is finally performed the next couple of instructions are already waiting prefetched, decoded and sometimes already executed out of order.
Now if the instruction in question is a branching instruction (like an “if” or the conditional of a loop in a highlevel programming language) then the processor is in trouble: there are two possible sequences of instructions it can prefetch and decode in the pipeline depending on the outcome of the (conditional) branching instruction. This is roughly like tossing a coin. If the processor bets on the wrong branch, it has to dump all the prefetched and decoded instructions, clear its pipeline and start over. This costs time and energy (you decide which is the worse of it). The (partial) solution to this misery is branch prediction.
There are several levels of branch prediction – modern processors of course are using the most advanced ones. On a very basic level one can analyse for example that 85% of the conditional branching backwards in the code (like jumping back in a loop) are taken (60% for the forward branches). Using this knowledge is some progess but not enough. Then one can invent a branch prediction buffer (BPB) that stores for each branching wether it was taken or not. The next step stores more bits per branch and then one can even do multi level prediction algorithms that correlate different branches etc.
The RSA algorithm is a very common public key encryption algorithm. Since it is widely used, it is under close observation of cryptologists and several attac scenarios have been proposed (and Peter Shor showed, that a quantum computer could break the code in polynomial time).
Now Onur Acıicmez , Cetin Kaya Koc, and Jean-Pierre Seifert showed in a recent paper that the use of only one branch prediction (BP) unit might a threat for RSA as well. Close analysis of the BP unit of a parallel running (spy) process can recover most of the bits of a secret key during one run of the encryption algorithm (and that way for example crack a 512 bit key in a couple of miliseconds)
(found on physorg.com strangely without reference on the paper)