Chip bugs can lead to major security disasters

These bugs chips, which are becoming increasingly complex, would make RSA's public key encryption scheme vulnerable. Shamir told John Markoff, who first reported on the research note in the New York Times, that he had no evidence the attack he described has been used. Following is a portion of Shamir's research 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.

The new attack (which we call a "Bug Attack") is related to the notion of fault attacks discovered by Boneh, Demillo and Lipton in 1996, but seems to be much more dangerous in its implications. The original fault attack required physical possession of the computing device by the attacker, and the deliberate injection of a transient fault by operating this device in an unusual way (in a microwave oven, at high temperature, with high frequency clock, or with a sudden spike in the power supply). Such attacks are feasible against smart cards, but are much harder to carry out against PC's. In the new bug attack, the target PC can be located at a secure location half a world away, and the attacker has no way of influencing its operating environment in order to trigger a fault. In addition, millions of PC's can be attacked simultaneously, without having to manipulate the operating environment of each one of them individually.

Shamir also said that the potential problem isn't limited to processors from companies such as Intel and AMD.

Many cellular telephones are running RSA or elliptic curve computations on signal processors made by TI and others, FPGA or ASIC devices can embed in their design flawed multipliers from popular libraries of standard cell designs, and many security programs use optimized "bignum packages" written by others without being able to fully verify their correctness.