[1683] in cryptography@c2.net mail archive
Re: Kocher timing attacks revisited
daemon@ATHENA.MIT.EDU (Eric Young)
Thu Oct 2 19:58:29 1997
Date: Fri, 3 Oct 1997 09:09:49 +1000 (EST)
From: Eric Young <eay@cryptsoft.com>
To: "Perry E. Metzger" <perry@piermont.com>
cc: cryptography@c2.net
In-Reply-To: <199710022157.RAA28094@jekyll.piermont.com>
On Thu, 2 Oct 1997, Perry E. Metzger wrote:
> Are people using countermeasures for these methods yet, or are they
> still ignoring them?
I'm still sort of ignoring them. I use a 5 bit sliding window when
doing my r=a^b%m. This means that I actually don't ever do a multiply
by 0, but rather 'slide' over them. This means that timing information
will probably indicate how many sequences of 0 there are in various
locations, but it is more ugly than that. The only information I've
seen on Kocher's attack was against a simple 'one bit at a time' r=a^b%m.
Even using a 4 bit fixed window, there is now only 1/16 that a multiply would
be skipped, and this would only indicate 4 0 bits, not 'one' bit at a
time.
I'm probably missing something obvious, but I have my doubts about how
effective this type of attack is against the more non-trivial a^b%m
implemetations. I do feel guitly about this :-).
On the other hand, I have looked at putting blinding in, but I kept on
balking because it was hard to do effiecently while supporting multi-threaded
applications in my library. (I would be updating the multiplyer via the
a=a*a%m, a^-1 = a^-1 * a^-1 % m system, which would require consitancy if
several threads were trying to update the 'RSA' data structure at the same
time). Anyway, I thought there was a software patent on blinding? (not that
I care :-)
eric
