[Cryptech Core] modexp optimization plans

[Rob Austein]

At Mon, 22 Jun 2015 15:56:01 +0200, Peter Stuge wrote:
> Joachim Strömbergson wrote:
...
>> Are you suggesting that all operations should fake a max size modulus
>> (8192) and always do that many operations.
> 
> Right, I think that should be the default.
> 
...
>>>> One could further optimize to find the MSB one of the exponent and
>>>> set the size to that. And then you could end up with data
>>>> dependent execution time.

Not sure it's worthwhile, but it occurred to me that, at least for
RSA, the nominal size of the operands to each ModExp operation will be
fairly obvious to anyone who has the public key and understands the
algorithm.  An attacker who knows the length of the public key will
know the size of the operands to the CRT operation, the size of the
operands in the RSA blinding factor calculation, and so forth.  What
they won't know is the exact bit pattern, and that's what we want to
be careful not to leak via timing variations.

So I think it would be OK to let the C code tell the API, eg, that the
nominal size of the exponent is 1024 bits, and that it need not
pretend that it's 8192 bits; the core must be careful not to leak
timing information that would betray anything further about those 1024
bits, but I doubt it's worth paying a huge speed penalty to hide the
nominal size when an attacker already knows it.

Note that passing the nominal size to the core as an argument is
different from scanning for the MSB, as the latter does potentially
leak information about the bit pattern.

Disclaimers:

- I am not a cryptographer, much less a cryptanalyst, so maybe there's
  an attack lurking here.  But I don't see it.

- This argument assumes that the attacker knows the public key.  I
  think this is the usual assumption when doing this sort of analysis
  for public key cryptography, but of course there may be special
  cases where this assumption does not apply.