Some important things come to mind: 1.) It isn't necessary to try an exhaustive search to prove that the hardware multiplier works correctly. Hardware multipliers multiply by shifting and adding; the failure mode would be one of failure to shift, or failure to add. The code to test every bit in two 64 bit multiplies is probably less than a thousand lines of C code, and involves far fewer operations than an exhaustive search. Testing the integer units in a modern CPU would fall well within the time constraints required by a typical cryptosystem implemented on a PC.
2.) The simplicity of integer hardware is such that the design can be formally proven with a minimal amount of effort. I'm inclined to say that it might take a competent engineer a week; an outstanding engineer could probably do it in a day. Given the emphasis most engineers place on getting it right the first time, and the triviality with which multiplication is implemented in hardware, it is quite likely that an engineer who couldn't correctly design a multiplier would also be unable to get their processor to work at all. The dispatch and retirement units of a modern CPU are far more complicated that a multiplier, and it seems the industry has no problem with this challenge. 3.) A cryptographer suspicious of his CPU can always multiply and divide the old-fashioned way, with a series of bit shifts and additions. Of course, there's always the possibility that the CPU itself is compromised; how does anyone know that Intel didn't put secret NSA backdoors in the CPU? One can do a lot with 135 million transistors. Ken Thompson's Reflections on Trusting Trust is very relevant here. Best Regards, Nathan Crawford -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of ' =JeffH ' Sent: Saturday, November 17, 2007 1:25 PM To: [email protected] Subject: fyi: Adi Shamir's microprocessor bug attack From: John Young <[EMAIL PROTECTED]> Subject: Adi Shamir's microprocessor bug attack To: [EMAIL PROTECTED] Date: Sat, 17 Nov 2007 09:50:31 -0500 (GMT-05:00) Adi Shamir's note on a microprocessor bug attack on public key cryptography featured in the NY Times today: http://cryptome.org/bug-attack.htm The NYT report: http://www.nytimes.com/2007/11/17/technology/17code.html ---------- Research Announcement: Microprocessor Bugs Can Be Security Disasters [reformatted to 64 cols single-spaced] Adi Shamir Computer Science Department The Weizmann Institute of Science Israel 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. We now describe the basic idea of the new attack. We assume that the RSA decryption (or signature generation) is using the Chinese Remainder Theorem (CRT) which speeds up the operation by a factor of 4 compared to naive implementations, that each multiplication of big operation by a factor of 4 compared to naive implementations, that each multiplication of big numbers proceeds by breaking them into the largest words which can be handled by the native multiplier in that microprocessor (typically 32 or 64 bits), and that all pairs of such words from the two numbers will be multiplied in some order. Knowing the target's public key n, the attacker can easily compute a half size number c which is guaranteed to be between the two secret factors p and q of n. For example, a number c which is the square root of n (rounded to the nearest integer) always satisfies p<c<q, and any number close to c is also likely to satisfy this condition. The attacker now chooses a message m which is equal to c, except that two low order words in it are replaced by a and b, and submits this "poisoned input" to the target PC. The first step in the CRT computation is to reduce the input m modulo p and q. Due to its choice, m will be randomized mod the smaller p, but remain unchanged mod the larger q. The next step in RSA-CRT is always to square the reduced inputs mod p and q, respectively. Since a and b are unlikely to remain in the randomized value of m (mod p), the computation mod p is likely to be correct. However, mod q the squaring operation will contain a step in which the word a is multiplied by the word b, and by our assumption the result will be incorrect in at least one bit. Assuming that the rest of the two computations mod p and q will be correct, the final result of the two exponentiations will be combined into a single output y which is likely to be correct mod p, but incorrect mod q. The attacker can then finish off his attack in the same way as the original fault attack, by computing the gcd of n with y^e-m, where e is the public exponent of the attacked RSA key. With very high probability, this gcd will be the secret factor p of n. This completely breaks the security of this key. How easy is it to verify that such a single multiplication bug does not exist in a modern microprocessor, when its exact design is kept as a trade secret? There are 2^128 pairs of inputs in a 64x64 bit multiplier, so we cannot try them all in an exhaustive search. Even if we assume that Intel had learned its lesson and meticulously verified the correctness of its multipliers, there are many smaller manufacturers of microprocessors who may be less careful with their design. In addition, the problem is not limited to microprocessors: 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. As we have demonstrated in this note, even a single (innocent or intentional) bug in any one of these multipliers can lead to a huge security disaster, which can be secretly exploited in an essentially undetectable way by a sophisticated intelligence organization. --- end --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
