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

[Dan Brown <[e-mail]>]

Recovering y at end of Montgomery ladder is something I heard about from Scott Vanstone, so it is likely published.

Tried to work it out: no square roots needed, but possibly a field inversion is.  Got a mess, which probably simplifies, especially in projective coords.

Can look later this week.


Sent with BlackBerry Work (www.blackberry.com)
________________________________
From: Phillip Hallam-Baker <[e-mail]>
Sent: Nov 9, 2019 5:24 PM
To: "Riad S. Wahby" <[e-mail]>; Mike Hamburg <[e-mail]>
Cc: [e-mail]
Subject: Re: [Cfrg] Efficient side channel resistance for X25519..

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]<mailto:[e-mail]>> wrote:
Phillip Hallam-Baker <[e-mail]<mailto:[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<https://urldefense.proofpoint.com/v2/url?u=https-3A__ia.cr_2015_673&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql-UonsW647lYqnsrbXizKI6MgkEw&m=tooJhXe_ybLT_tIp0s35eL4sVAb9UGVyN4oJJ_h5dyk&s=KRqHlQU2mVms-dWMP1Sjm7xFmnl6Nk-6lIiqOWu-lNE&e=>), 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

----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.