

Cryptome DVDs are offered by Cryptome. Donate $25 for two DVDs of the Cryptome 12andahalfyears 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, eyeballseries.org and iraqkillmaim.org, and 23,100 (updated) pages of counterintelligence 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. 
18 November 2007
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 articleIf 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/bugattack.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
ListArchive:
<http://www.chiark.greenend.org.uk/pipermail/ukcrypto/>
Date: Sat, 17 Nov 2007 23:41:54 +0100
> http://cryptome.org/bugattack.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 overclocking and undercooling, 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
RSAbased 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
RSACRT 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^em, 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.