Timing Channel Threatens RSA Security
[11 Dec. 95] The New York Times reported that Paul Kocher,
a 22-year-old researcher who has worked as a computer security consultant
to several major software companies, has identified a significant attack
on the secuirty of the RSA public key encryption algorithm. From the
perspective of many Cipher readers, the attack is of particular interest
because it explits an inadvertent covert timing channel in the execution
of the RSA algorithm. Such covert timing channels have been a concern to
researchers for years, but they have typically been dismissed as
insignificant by most commercial vendors and, indeed, by many within the
INFOSEC community. The idea behind the attack is that by observing
closely the time it takes for the software executing the algorithm to
complete the many multiplications it requires, one can deduce significant
information about the factors involved in the multiplication, thereby
greatly limiting the size of the space that needs to be searched
to find the key. Details are available in a
message to the Cypherpunks mailing list and in a web page by Kocher. RSA Security
responded that the vulnerability could be closed, either by
padding the multiplication times or by randomizing them through a
technique called "blinding". Evidently neither of these techniques is
in place in current RSA implementations.