Re: fyi: Adi Shamir's microprocessor bug attack
James A. Donald wrote: James Muir wrote: > Can anyone think of a deployed implementation of RSA > signatures that would be vulnerable to the attack > Shamir mentions? Hashing and message blinding would > seem to thwart it. As I said, public key encryption has long been known to be weak against chosen plaintext and chosen cryptotext - so protocols have long been designed to prevent this sort of attack. If they are not so designed, they were known to be weak before this attack was discovered. I completely agree with you. Good public key cryptography should be designed to resist chosen message attacks. This has been a standard part of cryptographic theory since the 80s. But this is an implementation attack, and real world implementations don't necessarily follow all the rules of cryptographic theory. If you or anyone else happened to know of a single real-world implementation of RSA signatures that is vulnerable to this fault attack, then that might give some justification for the incredible media coverage it has received. I can't think of any, and my feeling is that this announcement has been over-hyped (and presented without proper perspective). -James - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: fyi: Adi Shamir's microprocessor bug attack
James Muir wrote: > Can anyone think of a deployed implementation of RSA > signatures that would be vulnerable to the attack > Shamir mentions? Hashing and message blinding would > seem to thwart it. As I said, public key encryption has long been known to be weak against chosen plaintext and chosen cryptotext - so protocols have long been designed to prevent this sort of attack. If they are not so designed, they were known to be weak before this attack was discovered. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: fyi: Adi Shamir's microprocessor bug attack
' =JeffH ' wrote: From: John Young <[EMAIL PROTECTED]> [...] Research Announcement: Microprocessor Bugs Can Be Security Disasters [...] 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) Does somebody know if, in case of a discrete log scheme, this would result in an attack using one chosen message (like for RSA), or would the attack be similar to the one described by Boneh, DeMillo and Lipton for Schnorr's identification protocol and require O(n log n) executions? - Christian - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: fyi: Adi Shamir's microprocessor bug attack
' =JeffH ' wrote: > 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 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 micropr
Re: fyi: Adi Shamir's microprocessor bug attack
Perhaps I'm missing something, but real-world RSA implementations are not vulnerable to this because they implement RSA blinding to prevent timing attacks (which prevents a magic a * b fault from being exploited deterministically) or verify the signature after creation (which protects against random faults, a very good idea anyway). Something can't be "new" and "big" if it's been addressed in GnuPG, Crypto++ and others years ago. 8-P - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: fyi: Adi Shamir's microprocessor bug attack
' =JeffH ' wrote: 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 Can anyone think of a deployed implementation of RSA signatures that would be vulnerable to the attack Shamir mentions? Hashing and message blinding would seem to thwart it. Incidentally, in the 2001 Boneh-DeMillo-Lipton paper they do mention the Intel floating point division bug. -James - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
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
