Kocher's RSA attack

I read Kocher's paper, but I question its applicability.  One of his
premises is that the time of a modular multiplication varies with
the data.  I've checked my code for modular multiplication, and
the clock cycles to execute don't depend on the data at all.  The
same instructions get executed, and assuming the processor has a
hardware multiply, they take the same time.

When I timed the modular multiplication, I was able to detect some
slight variation, but I attribute this to cache misses, as the variance
with the same data was the same as the variance with different data.

Apparently RSAREF has modular multiplies which vary significantly
with the data, but I maintain this is not necessary.

A good test case for his analysis might be to pull a secret key
from a smart card.  If, say, the Capstone chip modular multiplication
has some timing anomalies, this might be a good way to defeat the
Fortezza card.

Roger Schlafly

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

On the internet the randomness introduced by the network probably hides
the timing of the cryptography. I say probably because I am at a conference
and have not got the maths texts to hand. I would guess however that
Shanon's paper on communications bandwidth and some empirical results on
the timing characteristics of the network would allow one to demonstrate that
the attack is infeasible.

On the other hand the attack is quite likely to work against some smart
cards. In particular there are many which do not have specialized modular
multiplication facilities. These use software to implement bignum arithmetic. 
Since smartcards also tend to be slow processors the arithmetic may well have been speeded up with the type of optimisation
been speeded up in an RSAREF type manner.

A conclusion which might be reached is that smartcards should in future contain 
contain a timer which is started at the beginnin of every cryptographic
operation and a delay loop introduced to ensure that the time taken is always
the same. The alternative of attempting to ensure that equal processing is
spent on each cycle threatens an infinite regress into second and third order
effects, eg frequency of page faults. Covert channel analysis is bad enough
as it is.

Perhaps we should concentrate on the question of how the timing attack bight be used
in a workstation environment. Here covert channels are very relevant - with the
proviso that we do not have a process concealment problem but a security 
partitioning problem. Consider the problem of a cryptographic file store where
the users do not have access to a private key used to make files accessible.

I suggest that we attempt to break out these attacks into categories, label 
the categories and produce a companion guide to the attack paper describing its
system level implications. I beleive that such a task is best done in 
a collaborative medium such as this list. We need as many people as possible to
consider the possible attack modes. Nobody is likely to think of them all.

	Phill

> 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