[1685] in cryptography@c2.net mail archive
Re: Kocher timing attacks revisited
daemon@ATHENA.MIT.EDU (Bill Stewart)
Fri Oct 3 11:42:14 1997
Date: Thu, 02 Oct 1997 21:53:19 -0700
To: Eric Young <eay@cryptsoft.com>
From: Bill Stewart <stewarts@ix.netcom.com>
Cc: cryptography@c2.net
In-Reply-To: <Pine.GSO.3.96.971003085458.21923B-100000@pandora.cryptsoft
.com>
At 09:09 AM 10/03/1997 +1000, Eric Young wrote:
>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. [...] The only information I've
>seen on Kocher's attack was against a simple 'one bit at a time' r=a^b%m.
How does your window system work? The usual approach, which Kocher attacks, is
r=1; t=a
t = t**2 %m
if (bit k is odd) r = r*t %m
which is efficient at exponentiation, though it may or may not
save time to only do the %m every few iterations.
One way to blind this is to do
if (bit k is odd) r = r*t %m ; else dummy = dummy*t %m
which at least covers the gross modmult time, though it may have more
subtle problems. It ought to do fine in your threaded environments
(except of course that it is doing 1/3 more modmults as cover.)
>Anyway, I thought there was a software patent on blinding? (not that I care :-)
Chaum's blinded signatures and ecash blinding stuff are patented;
this is a different application of modmults so it shouldn't be affected.
Thanks!
Bill
Bill Stewart, stewarts@ix.netcom.com
Regular Key PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
