[1686] in cryptography@c2.net mail archive
Re: Kocher timing attacks revisited
daemon@ATHENA.MIT.EDU (Eric Young)
Fri Oct 3 11:46:16 1997
Date: Sat, 4 Oct 1997 00:26:06 +1000 (EST)
From: Eric Young <eay@cryptsoft.com>
To: Bill Stewart <stewarts@ix.netcom.com>
cc: cryptography@c2.net
In-Reply-To: <3.0.3.32.19971002215319.006a89c8@popd.ix.netcom.com>
On Thu, 2 Oct 1997, Bill Stewart wrote:
> 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.
For r=a^p%m
given a window size of 3 bits, precalculate values for
001 a%m
011 a*a*a%m
101 a*a*a*a*a%m
111 a*a*a*a*a*a*a%m
Then given a p value of
1001100101110101 we will use the following 'windows'
1 222 33344 555
or
001
011
101
011
101
We sqr-mod the running total from left to right and at the correct
points, multiply by the pre-calculated values when the exponent bitmap
matches.
This system mostly pays off on larger exponents.
> One way to blind this is to do
> if (bit k is odd) r = r*t %m ; else dummy = dummy*t %m
Given r=a^p%m, you can do mul-mod with a blinding value on the
input number a. After the a^p%m, you multiply with the inverse value %m
to give the origional result back.
The expensive part is calculating the inverse of the original value where
A * A^-1 === 1 mod m.
Since we don't want to keep on using the same blinding multiplier, we
need to change this value every now and then, and a nice simple way to
do this is
A2 = A*A mod m
A2^-1 = A^-1 * A^-1 mod m
Potentially this gives blinding (because it changes the input value by
a 'random' value), with minimal cost (2 extra sqr-mod, but for a 1024 bit
number we are already doing 1024 of them). The squaring of the blinding
value is a cheap way of making it different each time, and since the original
value was 'random', the subsequent values are not predictable.
The hassle for me is
making this all work with treads without using locking (which is bad) and
without changing the SSLeay RSA API :-). I would prefer not to have
seperate blinding and thread-safe blinding options.
eric (who has just convinced himself to put blinding in..... :-)
