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

[futplex@pseudonym.com (Futplex)]

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>