Re: ECC and timing attacks

Anonymous (nobody@replay.com)
Thu, 8 Oct 1998 20:01:43 +0200

• Next message: Bruce Schneier: "CAST RFC"
• Previous message: Nicholas Charles Brawn: "one-way hash's"
• In reply to: Mail System Internal Data: "DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA"
• Next in thread: Tim Dierks: "Re: ECC and timing attacks"

Dr. Mike Rosing writes:

> On Thu, 8 Oct 1998, Lucky Green wrote:
>
> > Is anybody here aware of timing attacks against ECC? Are there theoretical
> > reasons why timing attacks will or will not work with ECC?
>
> I looked at this last year. Yes, timing attacks will work. In the
> expansion of a multiply you double, then perform one of (add, subtract,
> nop). Now, all a timing attack can tell you is the number of
> add/subtracts versus number of zeros, so it's less information than
> you get from an integer exponentiation expansion. However, the cure
> is simple: do a dummy add instead of a nop, and the time to perform
> a multiply will be constant. Slow, but constant :-)

You are underestimating the power of Kocher's timing attack. See
http://www.cryptography.com/timingattack.html.

The timing attack tells you more than the number of add/subtracts
vs number of zeros. It is far more subtle and clever than that.
It unpeels, one step at a time, each iteration, determining whether it
is an add/subtract versus a nop. Error correction mechanisms are used
to determine whether the previous guesses were correct.

Furthermore, doing a dummy add does not fix the timing attack. That is
analogous to doing a dummy multiply in the classic attack on modular
exponentiation, and Kocher remarks in section 9,

: (Note: Always performing the optional Ri = (si · y) mod n step does not
: make an implementation run in constant time, since timing characteristics
: from the squaring operation and subsequent loop iterations can be
: exploited.)

It may also be possible to distinguish adds from subtracts, if the timing
of those operations is different for some data values. (This will depend
on the details of the ECC algorithm.)

The correct solution is to use blinding, as James Donald described.

• Next message: Bruce Schneier: "CAST RFC"
• Previous message: Nicholas Charles Brawn: "one-way hash's"
• In reply to: Mail System Internal Data: "DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA"
• Next in thread: Tim Dierks: "Re: ECC and timing attacks"