Re: Time-based cryptanalysis: How to defeat it?

At 10:56 PM 12/10/95 -0800, anonymous-remailer wrote:
>Assuming Alice is decrypting a secret message sent to her
>by Bob (on her very slow C64 ;), and Mallet is watching
>with a stopwatch in hand, hoping to determine Alice's secret
>key...

The modern equivalent of that very slow C64 is the smartcard/
electronic wallet.  Sounds like we'll have to implement them
very carefully....

>It would be good to place inside the decryption routines
>a timer (WELL PLACED!) that waits a random-number of cycles
>(based on key-strokes, mouse position, etc.) to defeat this
>type of cryptanalysis?

The most interesting detail in the paper, to me, was:

PK> Computing optional Ri+1 calculations regardless of whether the exponent 
PK> bit is set does not work and can actually make the attack easier;
PK> the computations still diverge but attackers no longer have to identify
PK> the lack of a correlation for adjacent zero exponent bits. 

My immediate reaction to the description of the timing attack on 
Diffie-Hellman had, of course, been to do precisely that :-)
#--
#				Thanks;  Bill
# Bill Stewart, Freelance Information Architect, stewarts@ix.netcom.com
# Phone +1-510-247-0663 Pager/Voicemail 1-408-787-1281

Bill Stewart writes:
> The most interesting detail in the paper, to me, was:
> 
> PK> Computing optional Ri+1 calculations regardless of whether the exponent 
> PK> bit is set does not work and can actually make the attack easier;
> PK> the computations still diverge but attackers no longer have to identify
> PK> the lack of a correlation for adjacent zero exponent bits. 
> 
> My immediate reaction to the description of the timing attack on 
> Diffie-Hellman had, of course, been to do precisely that :-)

I don't understand why Kocher's point is correct. For example, why do the
times diverge with the following modification of the modexp algorithm on
pg.2 of the abstract ?

	Algorithm to compute R = y^x mod n:
		Let R_0 = 1.
		Let y_0 = y.
		For i = 0 upto (bits_in_x - 1):
			Let M = (R_i * y_i) mod n.
			Let R_(i+1) = (bit i of x) * M  +
					(1 - (bit i of x)) * R_i.
			Let y_(i+1) = (y_i)^2 mod n.
		End.

(I suppose I should wait for the full paper....)

-Futplex <futplex@pseudonym.com>