[Cfrg] Efficient side channel resistance for X25519..

[Phillip Hallam-Baker <[e-mail]>]

The X25519 spec appears to assume that the Montgomery ladder is sufficient
to avoid side channel timing attacks. This argument has never been a
convincing one. Modern compilers are designed for performance and there are
multiple layers of optimization.

My understanding of the deeper layers of the architecture makes me
profoundly skeptical as to the possibility of getting the timing exactly
right and even if we could, there is no (reliable) way of testing to see if
we did. And even if we did succeed, timing is no longer the only side
channel attack of concern, we now have ROWHAMMER and SPECTRE class attacks.

So until now, my approach has been to use the Edwards curves for key
agreement and signature. They allow me to use the Kocher style blinding
approaches. So instead of calculating s.P, I generate a random nonce r that
is different for every private key operation and calculate s1 = r mod Q, s2
= (s - s1) mod Q, where Q is the group order. I then calculate s1.P + s2.P
= s.P.

This approach is robust in that a side channel attack can only leak the
private key if both s1 and s2 are completely disclosed in a single
operation. The side channel isn't closed completely but all the approaches
publicly demonstrated to date are shut down (with the possible exception of
induced hardware errors).

So I would like a mechanism that allows me to efficiently extract the sign
bit of the Y coordinate from the Montgomery ladder. The way I am doing this
at present is a pretty horrible hack. I am effectively performing point
recovery guessing that the sign is positive (or even, same thing in a
modular field) then comparing with the other output from the Montgomery
ladder to see if I am right (one accumulator gives s.P and the other
s.(P+1)).

I can make the code work but I am not a number theorist so if anyone could
help, I would appreciate it.


Besides the protections against side channel attack, the same approach
allows for the type of techniques I have rebranded 'meta-cryptography' to
persuade people to take another look at them, threshold cryptography and
the like.

There is a MATHMESH BOF first thing on Monday in Singapore.