RFR(L): 8069539: RSA acceleration

Andrew Haley aph at redhat.com
Mon May 11 16:15:42 UTC 2015


On 05/11/2015 04:37 PM, Florian Weimer wrote:
> On 05/08/2015 07:19 PM, Andrew Haley wrote:
> 
>>> Do we want to add side-channel protection as part of this effort
>>> (against timing attacks and cache-flushing attacks)?
>>
>> I wouldn't have thought so.  It might make sense to add an optional
>> path without key-dependent branches, but not as a part of this effort:
>> the goals are completely orthogonal.
> 
> I'm not well-versed in this kind of side-channel protection for RSA
> implementations, but my impression that algorithm changes are needed
> to mitigate the impact of data-dependent memory fetches (see
> fixed-width modular exponentiation). 

RSA can be done with no key- (or data-) dependent timing.  No Chinese
Remainder Theorem optimizations, no addition chains, no optimized
division.  Just do everything.  Even when the result of a
multiplication is not needed, do it anyway.  This really easy to do:
just delete all of the optimizations (and therefore most of the code)
in oddModPow, leaving only a simple kernel and a much slower
algorithm.

> But maybe the necessary changes materialize at a higher level,
> beyond the operation which you proposed to intrinsify.

They absolutely do.  The algorithm I propose to intrinsify has almost
no key-dependent timing whatsoever unless the multiplication
instruction itself has an early-out optimization.  And there's not
much anyone can do about that.  (Well, almost: it may be necessary to
do an extra subtraction to normalize the result of the Montgomery
multiplication, and this is data-dependent.  I suppose it would be
possible to do the subtraction anyway, and throw it away if needs be.)

It would make more sense to use one of the techniques to prevent
timing attacks by using blinding functions.  See e.g. Timing Attacks
on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems,
Kocher 1995.

But really it seems inappropriate to me to piggyback this conversation
on top of a completely different subject, RSA acceleration.  Let's
continue it elsewhere.

Andrew.


More information about the hotspot-compiler-dev mailing list