Cryptome DVDs are offered by Cryptome. Donate $25 for two DVDs of the Cryptome 12-and-a-half-years collection of 47,000 files from June 1996 to January 2009 (~6.9 GB). Click Paypal or mail check/MO made out to John Young, 251 West 89th Street, New York, NY 10024. The collection includes all files of cryptome.org, cryptome.info, jya.com, cartome.org, eyeball-series.org and iraq-kill-maim.org, and 23,100 (updated) pages of counter-intelligence dossiers declassified by the US Army Information and Security Command, dating from 1945 to 1985.The DVDs will be sent anywhere worldwide without extra cost.

Google
 
Web cryptome.org cryptome.info jya.com eyeball-series.org cryptome.cn

18 November 2007

http://groups.google.com/group/cryptopp-users/browse_thread/thread/36194e2b9a52de7/d9ce17217cdbc797?hl=en&lnk=st&q=cryptome#d9ce17217cdbc797

From: "Wei Dai" <wei...[at]weidai.com>
Date: Sun, 18 Nov 2007 04:22:19 -0800
Local: Sun, Nov 18 2007 7:22 am
Subject: yesterday's NYT article

If you read yesterday's New York Times article at http://www.nytimes.com/2007/11/17/technology/17code.html (Shamir's paper that's referenced can be found at http://cryptome.org/bug-attack.htm), you might be interested to know that the RSA implementation in Crypto++ is already protected against this attack, even if a multiplication bug does exist in the CPU.

I'm not sure why neither the article nor Shamir's paper mention this, but it's been well known for some time that in order to protect against this kind of fault attack, after doing the RSA private key operation y=x^d mod n, one should check that the result is correct by verifying that x=y^e mod n. Crypto++ has done this since version 5.1.

From: Florian Weimer <fw[at]deneb.enyo.de>
To: ukcrypto[at]chiark.greenend.org.uk
Subject: Re: Adi Shamir's microprocessor bug attack
List-Archive: <http://www.chiark.greenend.org.uk/pipermail/ukcrypto/>
Date: Sat, 17 Nov 2007 23:41:54 +0100

> http://cryptome.org/bug-attack.htm

| We assume that the RSA decryption (or signature generation) is using
| the Chinese Remainder Theorem (CRT)

Some OpenPGP implementations have already added a signature verification step after signature generation, so that random bit errors do not expose the private key by mere accident.  With all that over-clocking and under-cooling, this seems to be a fairly relevant threat.

17 November 2007. Thanks to A. with permission of Adi Shamir.

News report: http://www.nytimes.com/2007/11/17/technology/17code.html

Research Announcement: Microprocessor Bugs Can Be Security Disasters

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

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.