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.