Cryptographer Warns that Math Errors in Computer Chips Could Be a Global Security Risk

Noted Israeli cryptographer Adi Shamir (the "S" in RSA Security and the middle one in the picture at right) has made an obvious, but nonetheless important, observation about the security problems that would ensue should a math error be found in any widely used computer chip.

Such an error could allow intelligence agencies and industrial spies to crack messages protected by public key cryptography. It could also allow hackers to break the protections in software used for e-commerce.

The New York Times's John Markoff says Shamir made the observation in a research note he sent to cryptographer colleagues recently.

Shamir's observation isn't new. A division error found in Intel's Pentium microprocessor in the mid-90s first raised the specter of serious computational problems caused by buggy chips -- though that particular problem wasn't considered widespread and Intel claimed that it would affect spreadsheet users only once every 27,000 years. But given the greater reliance on cryptography these days in regular business correspondence and e-commerce transactions, the kind of bug Shamir describes -- which is only hypothetical at this point -- would be far more serious.

Shamir's note is all the more remarkable, a cryptographer says in Markoff's story, because it suggests that Shamir's own RSA algorithm could be vulnerable.

Mr. Shamir wrote that if an intelligence organization discovered a math error in a widely used chip, then security software on a PC with that chip could be “trivially broken with a single chosen message.”

Executing the attack would require only knowledge of the math flaw and the ability to send a “poisoned” encrypted message to a protected computer, he wrote. It would then be possible to compute the value of the secret key used by the targeted system.

With this approach, “millions of PC’s can be attacked simultaneously, without having to manipulate the operating environment of each one of them individually,” Mr. Shamir wrote.

The research note is significant, cryptographers said, in part because of Mr. Shamir’s role in designing the RSA public key algorithm, software that is widely used to protect e-commerce transactions from hackers.

“The remarkable thing about this note is that Adi Shamir is saying that RSA is potentially vulnerable,” said Jean-Jacques Quisquater, a professor and cryptographic researcher at the Université Catholique de Louvain in Belgium.

Shamir notes that laws governing trade secrets prevent users of such chips from being able to verify that the chips were made correctly.

“Even if we assume that Intel had learned its lesson and meticulously verified the correctness of its multipliers,” Shamir wrote in his note, according to the Times, “there are many smaller manufacturers of microprocessors who may be less careful with their design.”

Photo: Ron Rivest, Adi Shamir and Len Adelman/RSA Security