Re: [Cfrg] Efficient side channel resistance for X25519..

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

cc'd Mike himself in the hope he might take pity on us here... :-)

Seems to me that this should be possible. But the argument is a little more
abbreviated than I can follow.

" This means that it is enough to compute ±1/ √ au0u1u2. This will allow us
to determine av0/u0 to adjust the sign of the square root. It will allow us
to check whether av2/u2 is negative, in which case we should output 1/ √
au2 instead of p u2/a. Furthermore, the input point s0 is p u0/a, and the
modified Montgomery ladder state contains either √ au1 or √ au2, depending
on the last bit of the ladder. This allows us to compute p u2/a or its
inverse from the ladder state and 1/ √ au0u1u2 with no additional field
exponents. In the actual computation, u1 and u2 are given in projective
form, but this does not greatly complicate matters because the equations
are nearly homogeneous."

My implementation of the ladder already has these values...

                var x_3rt = (DA + CB);
                x_3 = (x_3rt * x_3rt).Mod(P);

                var z_3rt = (DA - CB);
                z_3 = (x_1 * (z_3rt * z_3rt)).Mod(P);

The paper suggests that the sign of the y point is somehow encoded there...
but how?



On Sat, Nov 9, 2019 at 2:07 PM Riad S. Wahby <[e-mail]> wrote:

> Phillip Hallam-Baker <[e-mail]> wrote:
> > I can make the code work but I am not a number theorist so if anyone
> could
> > help, I would appreciate it.
>
> This is more like a vague memory than a clear answer (sorry):
>
> In Mike Hamburg's Decaf paper (https://ia.cr/2015/673), Appx. B
> describes a method of recovering the y-coordinate while avoiding
> an extra square-root computation, essentially by remembering some
> intermediate values during the ladder computation.
>
> I haven't thought at all about whether a similar trick can be used
> in the non-Decaf context, but it might be worth taking a look.
>
> (As a general comment---and from your email, it appears we're in
> agreement---masking via randomization is good, but probably it's
> best to think of it as insurance: a masked implementation that's
> non-constant-time is toast in the face of randomness failures.)
>
> -=rsw
>