"With the increasing word size and sophisticated optimizations of multiplication units in modern
microprocessors, it becomes increasingly likely that they contain some undetected bugs.
This was demonstrated by the accidental discovery of the obscure Pentium division bug
in the mid 1990's, and by the recent discovery of a multiplication bug in the Microsoft
Excel program. In this note we show that if some intelligence organization discovers (or
secretly plants) even one pair of integers a and b whose product is computed incorrectly
(even in a single low order bit) by a popular microprocessor, then ANY key in ANY
RSA-based security program running on ANY one of the millions of PC's that contain this
microprocessor can be trivially broken with a single chosen message. A similar attack can be
applied to any security scheme based on discrete logs modulo a prime, and to any security
scheme based on elliptic curves (in which we can also exploit division bugs), and thus almost
all the presently deployed public key schemes will become vulnerable to such an attack. "
Sunday, November 18, 2007
Shamir says public key cryptography vunerable
Adi Shamir (the "S" in RSA) says increasing complexity of modern microprocessor chips is almost certain to lead to undetected errors, which make RSA based cryptographic security programs on these microprocessors vunerable to attack. From Shamir's note: