[Cryptech Core] modexp optimization plans (was: Re: teleconf?)

[Peter Stuge]

Rob Austein wrote:
> > > 4.2 Implement support for short exponent. Currently the size of the
> > > exponent is ignored. This means that an operation with a public exponent
> > > (such as 65537) takes as long time as if the exponent is as big as the
> > > modulus. This fix is easy to do and will drastically reduce the time to
> > > do operations with short exponents.

What are the numbers?


> > It also introduces a timing artefact based on input data. Like
> > operation skippin I think this needs to be configurable, if possible
> > at all.
> 
> Er, at least for RSA, the short public exponent is, um, public, and
> it's pretty obvious which operations use the public exponent and which
> ones use the private exponent, so letting it run fast for the public
> exponent doesn't leak anything your adversary didn't already know.

Are you sure? I'm not thinking of leaking public material.

Would the same size-dependent optimization not be used for private
operations? Would that require duplicating some logic? The suggestion
reads "Implement support for short exponent." and does not mention
the difference between public and private.

If not that's of course good, but this is still one of those things
where one binary bit (use variable-time or constant-time core) is all
it takes to make the hardware leak private material. Very easy to
slip in. That's why I would like it to not be possible in the first
place.

I seem to remember more secure and slow being prefered over less
secure and fast at one meeting.

It's fine that infrastructure operators pay for fast. I think it's
important not to force everyone to be less secure because of that.


//Peter