Mathematical Police Find Security Bug

When you buy a gadget online or check your bank balance electronically, your computer encodes your messages using a mathematical algorithm. The difficulty of breaking these encryption algorithms prevents digital onlookers from stealing your credit card numbers or reading your bank statement. One of the creators of the most venerable such code, the RSA algorithm, has recently warned that if your computer’s processing chip contains a flaw that makes it perform a miscalculation, it’s possible that an attacker could break the codes in your computer and spill your digital secrets.

“Even a single innocent or intentional bug … can lead to a huge security disaster, which can be secretly exploited in an essentially undetectable way by a sophisticated intelligence organization,” Adi Shamir of the Weizmann Institute in Israel wrote in a recent research note. “Almost all the presently deployed public key schemes will become vulnerable to such an attack.” Shamir created the RSA algorithm in 1977 with Ronald L. Rivest at the Massachusetts Institute of Technology and Leonard M. Adleman of the University of Southern California in Los Angeles.

The flaw that Shamir has identified is not known to appear in any of the chips now being produced. In 1994, however, another researcher found just such a design flaw in the Intel Pentium chip. That embarrassment has led Intel and other leading manufacturers to be especially careful about the design of their chips. But since many small manufacturers also produce chips, and because chip design has become almost unimaginably complicated, chances are high that such a flaw could creep in at some point, notes Shamir.

Protecting against the newly discovered vulnerability is not difficult, cryptographers say, as long as computer manufacturers, cryptographers, and users of cryptographic systems become aware of the potential danger. Shamir wrote his research note to generate such awareness.

Public-key encryption algorithms use two “keys”: one is a publicly known pair of numbers, and the other is a secret number. If Alice wants to send an encrypted message to Bob, she first looks up his public key. Next, she encodes her message as a number, a process that is simplified by the fact that computers use 0s and 1s to store messages. Finally, she performs a particular mathematical operation on her numerical message using Bob’s public key. The result is the encoded message.

After encoding the message, even Alice herself can’t deduce her original message from the result. The only way she could get it back would be to use Bob’s private, secret key, which has been devised to allow him to restore Alice’s encrypted message to its original, readable form through another series of mathematical operations.

Encryption algorithms are also useful for verifying a person’s identity online. Suppose Alice is about to transfer money into Bob’s account, but she’s worried someone else may be impersonating him. She can give Bob a test: her computer will create a random message, encrypt it using Bob’s public key, and ask him to decrypt it using his private key and send it back to her. If the decrypted message matches the one she sent, she will know she’s really talking to Bob. This process is called “authentication.”

Suppose, though, that the chip in Bob’s computer makes a miscalculation while decrypting the message. Then when Alice gets the message back, the result won’t match what she started with. The authentication will fail—but that’s not the worst part.

Cryptographers realized a decade ago that when Alice gets the message back with the botched decryption, she can use some tricks from number theory to figure out Bob’s private key. That would allow her to read all his encrypted correspondence or impersonate him in the future, unbeknownst to him.

For a long time, cryptographers weren’t too worried about this. Such an attack could only work if Bob’s computer chip made a miscalculation. To force such a miscalculation, an attacker would have to physically possess Bob’s computer and manipulate its operation. That would be nearly impossible to do with a computer, but the finding did raise some concern that a stolen smart card could be open to such an attack.

Occasionally, a chip might make computational errors on its own, as happened in 1994. But cryptographers considered such errors extremely difficult to exploit, because they could occur only in computations that are very rarely performed. If a chip makes a miscalculation frequently, the manufacturer will almost certainly notice and reject it before it makes its way into a computer.

Therefore, when Alice asks Bob to verify his identity, his decryption process will perform the bad computation only once in a blue moon. Odds are very high that Bob’s slightly faulty computer will decrypt Alice’s test message correctly and Alice won’t be able to get Bob’s private key.

But now, Shamir has found that Alice could get around that problem using a “poisoned input.” If she knows what error the chip will make, she can send a cleverly designed message that will force Bob’s computer to perform the problematic computation during decryption, revealing Bob’s key. Shamir calls this technique a “bug attack.”

Happily, it’s not too hard for Bob to protect himself against a bug attack if he suspects that Alice might be trying to attack him in this way when she sends him a request for authentication encrypted with his public key. He could decrypt her test message normally, and then re-encrypt it using his public key. If he doesn’t get the same encrypted message that Alice sent, he will suspect the problem, destroy the incorrectly decrypted message, and refuse to respond to Alice’s request for authentication. Many modern encryption software packages perform this check already, though some users turn off the feature to speed up the encryption process.

What makes a bug attack especially dangerous is that it could be inflicted on many computers simultaneously from a remote location. If the faulty chips were to find their way inside banks, governments, or other high-security places, an attacker could do an enormous amount of damage very quickly.

“This illustrates in a very crisp way what makes security so difficult,” says Paul Kocher, president of Cryptography Research, a San Francisco consulting firm. “There’s this assumption in cryptography that every other part of the system is working perfectly, every processor and every chip and every Internet transaction. Very often, those assumptions aren’t correct.” And when they’re not, it can cause problems.

But Kocher also points out that there are many known ways of attacking computer systems, and an attacker will choose the easiest way. It would be difficult to plant or detect a design flaw in a computer chip, so it’s not the most likely technique for a malicious person to use.

Kocher compares computer security with protecting a house from burglars. “If there’s a bad lock on the front door and a window that’s wide open, the window is the way [a burglar is] going to go in,” he says. “But if you’re trying to figure out what issues need to be mitigated to make the whole house secure, the door is certainly on the list.”

---

If you would like to comment on this article, please see the blog version.