From: Derek Atkins <warlord@MIT.EDU>
Date: Fri, 15 Dec 1995 03:18:16 +0800
To: hallam@w3.org
Subject: Re: Kocher's RSA attack
In-Reply-To: <9512141640.AA22375@zorch.w3.org>
Message-ID: <199512141815.NAA26051@toxicwaste.media.mit.edu>
MIME-Version: 1.0
Content-Type: text/plain


> Further to Roger's comments that modular multiplies in software probably do
> not allow the timing attacks.

I must disagree, software implementations of RSA can and probably do
allow the timing attacks.  It all depends on the modexp implementation.
Most implementations that I know of, when performing an x^y mod n will
require a squarings and b multiplies, where a is the number of bits in
y and b is the number of 1-bits in y.

You iterate through the bits of y.  For each bit you square x, and if
the bit is 1 you multiply it into an accumulator.  Paul's attack can
determine if this multiply is done or not, given perfect timing
conditions, in 2 ciphertexts per bit.  This CAN happen in software,
and it does in implementations like RSAREF.  In fact, I'm fairly sure
that PGP's MPILib would be subject to this attack if it weren't for
all the other randomness involved in PGP.

The point is that just because an implementation is in software does
not mean you should be sloppy in your protections against this attack.

We should change implementations, both in software and hardware, to
defeat this attack.  Making operations run in constant time seems to
be the best way to defeat this attack.

Yes, we should also look at other possible attacks.  Covert channels
in a workstation environment are important, but they have nothing to
do with Paul's particular attack.  It would be interesting to see how
one could use covert challens to gain the timing information needed to
make this attack, howver.  I have a few ideas.

-derek