Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:20
Mike Rosing (eresrch@msn.fullfeed.com)
Thu, 8 Oct 1998 09:08:40 -0500 (CDT)
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 :-)
I can get into more details if you like. In general a timing attack
is pretty damn hard to get useful info out of an ECC, but with enough
examples you can begin to get limits on how many key bits are in use.
What makes it even more difficult is that the time of an add is the
same as the time of a subtract, to within a few clock cycles. So the
attacker doesn't know if the key pattern is 1,0,0,0,1,0,0,0,-1,... or
1,0,0,0,-1,0,0,0,1,... All she knows is that at least 3 bits are set,
(the first one is always set) and by the number of doubles what the
length of the key is.
The bottom line is yes, theoretically a timing attack is possible.
However, you need twice as much data, and possibly more, to learn
anything useful. And it's trivial to defend against if you want to.
Patience, persistence, truth,
Dr. mike
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:20