Article 40176 of alt.security:
Ross Anderson wrote:

> Lenstra has a far simpler attack, which gets an ACK in the Bellcore paper. If
> you have an RSA signature S on the message M that is right mod p and wrong
> mod q, where the modulus n = pq and the public exponent is e, then p =
> gcd(n, M-S^e).

It's so simple once someone points it out.

[...]
> use clock or power glitches.
> If your smartcard is normally clocked at 5MHz, replace one of these pulses
> with four at 20MHz. The card will typically decode a wrong instruction -
> maybe one that isn't even in the microcode.

Good point, especially for Lenstra's method.  Since the modular
exponentiation requires so many instructions, a random instruction
which computes the wrong value is likely to introduce just the
sort of error the attack needs.  Corrupting a random memory
location is less likely to be helpful, since the exponentiation
takes a smaller fraction of memory.
 
> Given that RSA smartcards work out signatures mod p and mod q separately and
> then combine them using the Chinese remainder theorem, it is quite likely that
> you can get a wrong signature of the kind you need for Lenstra's attack.

Until I read this I hadn't considered the attack practical.  Now I think
we need to guard against it.  Since exponentiation by the public key is 
much faster than signing/encrypting with the private key (public keys
are 
usually small, like 3 or 2^16+1), the card can check that the public key
inverts private key operations, and still only add a small fraction of
the
run time.

Operations using long-term symmetric keys should probably also be 
re-checked.  This would double the required time, but such keys
are not typically used for bulk data encryption and don't account
for a large amount of time.

Is it worth double-checking session key operations?  I don't think
so.  We probably don't want to slow down bulk encryption, nor double
the amount of hardware we need.  Since these keys are only used for 
one session, it seems that the only data an attacker could recover 
is the data he's using for the attack.

--Bryan