[Cryptech Tech] RSA Key Format

[Rob Austein]

On Tue, 12 Mar 2019 07:17:02 -0400, Pavel Shatov wrote:
...
> In that light I'm starting to think that my idea to offload the
> computation to STM32 is not that smart after all. Speaking of RISC-V,
> can it get us true constant-time operation?

In theory, constant time C code on a CPU should produce constant time
result unless the CPU is somehow attempting to be excessively clever.
In practice, of course, the answer is try it and measure the result.

With constant time C code one is always fighting the compiler, which
wants to help out by optimizing things in clever ways.  Certain tricks
can foil the compiler's attempt to help out, none of them are perfect,
but see ff_add() in sw/libhal/ecdsa.c for an example of using a
boolean value as an array index to keep the compiler from cleverly
optimizing out subtraction of the field modulus.

> I'm now looking into how to integrate blinding into the core. Suppose
> that our modulus is N = P * Q and the message to sign is M. When doing
> CRT, we do two "easier" exponentiations mod P and mod Q, but the
> message M is twice larger. So we have to first compute two new bases
> MP = M mod P and MQ = M mod Q. Now do I get it right, that what we
> want to do is we blind the original twice larger message M? In theory
> we can blind the two smaller bases separately. Okay, the latter may be
> a totally stupid thing, because I haven't worked out all the math
> details yet, just asking.

The first two times I read this, I thought it wouldn't work; on a
third try, I think it would, assuming constant time calculation of MP
and MQ.  Well, mostly.  Doing blinding this way would only protect
against side channel attacks on the exponentiation itself, it wouldn't
protect the rest of Garner's formula.  So this would require some
analysis to figure out whether the residual risks are something we
need to worry about.

Other opinions actively solicited, particularly from people who think
they understand the math.