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

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 9 Nov 2019 13:03:48 -0500

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.

---

From: "Riad S. Wahby" <[email-masked]>
Date: Sat, 9 Nov 2019 11:07:05 -0800

> 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

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 9 Nov 2019 17:05:38 -0500

> non-constant-time is toast in the face of randomness failures.)

Thanks for the pointer. I agree that belt and braces is best. But in this
particular case we seemed to have gone for a not particularly reliable belt
and ignored the suspender option.

The other concern of course will be the possibility some troll has got a
'do it on the radio' type patent on Kocher's work of 25 years ago. We
should probably check into that.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 9 Nov 2019 17:23:46 -0500

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?

---

From: Dan Brown <[email-masked]>
Date: Sun, 10 Nov 2019 14:56:35 +0000

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 <[email-masked]>
Sent: Nov 9, 2019 5:24 PM
To: "Riad S. Wahby" <[email-masked]>; Mike Hamburg <[email-masked]>
Cc: [email-masked]
Subject: Re: [Cfrg] Efficient side channel resistance for X25519..

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."

                var x_3rt = (DA + CB);

                var z_3rt = (DA - CB);

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 <[email-masked]<mailto:[email-masked]>> wrote:

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.

-=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.

---

From: Rene Struik <[email-masked]>
Date: Sun, 10 Nov 2019 11:36:45 -0500

Hi Phil:

This follows directly from the addition laws:

Let P1:=(u1, v1) and P2:=(u2, v2) be distinct affine points of the 
Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the identity 
element. Then Q:=(u, v), where

     u + u1 + u2 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where 
lambda:=(v2 - v1)/(u2 - u1).

 From this, it follows that

     u*(u2-u1)^2=B*(v2-v1)^2-A*(u2-u1)^2 = 
B*(v1^2+v2^2)-2*B*v1*v2-A*(u2-u1)^2=-2B*v1*v2-u1*(u2^2+A*u2+1)-u2*(u1^2+A*u1+1).

It follows that if P=(u, v), P1=k*P=(u1, v1), and P2=(k+1)*P=(u2, v2) 
are distinct affine points of the Montgomery curve M_{A,B} and if v is 
nonzero, then the v-coordinate of P1 can be expressed in terms of the 
u-coordinates of P, P1, and P2, and the v-coordinate of P.

One can compute a square root of a nonzero square x in GF(q) and the 
inverse of a nonzero element y of GF(q) by first computing 
s:=1/sqrt(x*y^2)=1/(y*sqrt(x)) and then observing that t:=s*x*y=sqrt(x) 
and t*s=(+/-)1/y. Here, the (+/-)-sign is due to square roots being 
unique up to sign.

See also [1], where Appendices C.1, C.2, and C.3 give recovery rules for 
Weierstrass curves, Montgomery curves, and twisted Edwards curves, and 
where Appendices L.1 and L.2 give details for computing square roots and 
inverses (including "Montgomery's trick").

I added y-coordinate recovery in version 2 of [1] after you posed a 
similar question on the saag mailing list (Oct 3, 2018 [2]).

[1]https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/

[2] https://mailarchive.ietf.org/arch/msg/saag/x4rKzfOB3E7RKQceiGfxAUrFfDQ

I hope this helps.

Rene

On 11/9/2019 5:23 PM, Phillip Hallam-Baker wrote:
> " 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."
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Henry de Valence <[email-masked]>
Date: Mon, 11 Nov 2019 14:16:53 -0800

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

Section 4.3 of https://arxiv.org/pdf/1703.01863.pdf may be helpful.

Cheers,
Henry

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 12 Nov 2019 08:15:18 -0800

Hi all,

Sorry for the slow response, I haven’t been up to date on email and haven’t checked CFRG in a while.

The formulas for recovering a y-coordinate from the Montgomery ladder without square roots can also be found in my paper:

https://eprint.iacr.org/2012/309.pdf

Appendex A.3.  If you homogenize those formulas, IIRC you will get either DA+-CB terms, or something very similar.

Regards,
— Mike Hamburg

> On Nov 10, 2019, at 8:36 AM, Rene Struik <[email-masked]> wrote:
> 
> Hi Phil:
> 
> Let P1:=(u1, v1) and P2:=(u2, v2) be distinct affine points of the Montgomery curve M_{A,B} and let Q:=P1 + P2, where Q is not the identity element. Then Q:=(u, v), where 
> 
>     u + u1 + u2 = B*lambda^2 - A and v + v1 = lambda*(u1 - u), where lambda:=(v2 - v1)/(u2 - u1).
> 
>     u*(u2-u1)^2=B*(v2-v1)^2-A*(u2-u1)^2 = B*(v1^2+v2^2)-2*B*v1*v2-A*(u2-u1)^2=-2B*v1*v2-u1*(u2^2+A*u2+1)-u2*(u1^2+A*u1+1).
> 
> It follows that if P=(u, v), P1=k*P=(u1, v1), and P2=(k+1)*P=(u2, v2) are distinct affine points of the Montgomery curve M_{A,B} and if v is nonzero, then the v-coordinate of P1 can be expressed in terms of the u-coordinates of P, P1, and P2, and the v-coordinate of P.
> 
> One can compute a square root of a nonzero square x in GF(q) and the inverse of a nonzero element y of GF(q) by first computing s:=1/sqrt(x*y^2)=1/(y*sqrt(x)) and then observing that t:=s*x*y=sqrt(x) and t*s=(+/-)1/y. Here, the (+/-)-sign is due to square roots being unique up to sign.    
> 
> See also [1], where Appendices C.1, C.2, and C.3 give recovery rules for Weierstrass curves, Montgomery curves, and twisted Edwards curves, and where Appendices L.1 and L.2 give details for computing square roots and inverses (including "Montgomery's trick").
> 
> I added y-coordinate recovery in version 2 of [1] after you posed a similar question on the saag mailing list (Oct 3, 2018 [2]). 
> 
> [1] https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/ <https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/>
> [2] https://mailarchive.ietf.org/arch/msg/saag/x4rKzfOB3E7RKQceiGfxAUrFfDQ <https://mailarchive.ietf.org/arch/msg/saag/x4rKzfOB3E7RKQceiGfxAUrFfDQ>
> I hope this helps. 
> 
> Rene
> 
> 
>> On Sat, Nov 9, 2019 at 2:07 PM Riad S. Wahby <[email-masked] <mailto:[email-masked]>> wrote:
>> Phillip Hallam-Baker <[email-masked] <mailto:[email-masked]>> wrote:
>> In Mike Hamburg's Decaf paper (https://ia.cr/2015/673 <https://ia.cr/2015/673>), Appx. B
>> [email-masked] <mailto:[email-masked]>
>> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
> 
> -- 
> email: [email-masked] <mailto:[email-masked]> | Skype: rstruik

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 12 Nov 2019 12:38:33 -0500

Thanks,

It looks to me as if Algorithm 5 should do what I need. Though I will have
to work out the correspondence between Algorithm 4 and RFC 7748.

Probably not happening till I get back from Singapore.

On Mon, Nov 11, 2019 at 5:17 PM Henry de Valence <[email-masked]> wrote:

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