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:

"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. "

No comments: