Re: [Cfrg] Montgomery ladder and field operations (was: Re: Efficient side channel resistance for X25519..)

Mike Hamburg <mike@shiftleft.org> Tue, 12 November 2019 16:15 UTC

Return-Path: <mike@shiftleft.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 2D60912008B for <cfrg@ietfa.amsl.com>; Tue, 12 Nov 2019 08:15:23 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=shiftleft.org
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id wl2PMA1rt5Kz for <cfrg@ietfa.amsl.com>; Tue, 12 Nov 2019 08:15:20 -0800 (PST)
Received: from astral.shiftleft.org (vpn.shiftleft.org [54.219.126.124]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 211BA1208F4 for <cfrg@irtf.org>; Tue, 12 Nov 2019 08:15:20 -0800 (PST)
Received: from [192.168.0.11] (unknown [73.162.216.15]) (Authenticated sender: mike) by astral.shiftleft.org (Postfix) with ESMTPSA id 3E44F3B6; Tue, 12 Nov 2019 08:15:19 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=shiftleft.org; s=sldo; t=1573575319; bh=F0gI+VieDxeWyylIsO8CplywGjo79jjfum/SBXlJqJw=; h=From:Subject:Date:In-Reply-To:Cc:To:References:From; b=R8klAWRyoBiY+mDpwMrS6nBEoC63EJvr43PX3BtF/hgW0M2fr+lJeGcKalsW9J1kW zlurmvRCWu6e5LyuLqB1CVoWOOpdutfT2/O3aCLQ/kc6IWby6klaRqK3H4RRMhTRSh R7X3O6x01rFFSxfL9WB0lE5QQSy7++nWg0YYCcI8=
From: Mike Hamburg <mike@shiftleft.org>
Message-Id: <E4DA46BE-2659-4E40-9163-F818A46F8DC0@shiftleft.org>
Content-Type: multipart/alternative; boundary="Apple-Mail=_55777563-6FD4-484C-A3B2-A3D52477A9D9"
Mime-Version: 1.0 (Mac OS X Mail 13.0 \(3601.0.10\))
Date: Tue, 12 Nov 2019 08:15:18 -0800
In-Reply-To: <f47fc518-a005-9546-d84f-971617351921@gmail.com>
Cc: Phillip Hallam-Baker <phill@hallambaker.com>, "Riad S. Wahby" <rsw@jfet.org>, cfrg@irtf.org
To: Rene Struik <rstruik.ext@gmail.com>
References: <CAMm+LwiB6cpcnb_gpfXueU-A5w=jJ-4U5hhH_xkH5ERx1budoQ@mail.gmail.com> <20191109190705.j4b7chrjfev3lwig@positron.jfet.org> <CAMm+LwhRA3zTMdMM0U-qbC47i80LF8PyN9hX3bzVy_kddHisCw@mail.gmail.com> <f47fc518-a005-9546-d84f-971617351921@gmail.com>
X-Mailer: Apple Mail (2.3601.0.10)
X-Virus-Scanned: clamav-milter 0.101.4 at astral.shiftleft.org
X-Virus-Status: Clean
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/IVoJ7xFCvmlNOITnQ0UHuXVMs0o>
Subject: Re: [Cfrg] Montgomery ladder and field operations (was: Re: Efficient side channel resistance for X25519..)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 12 Nov 2019 16:15:23 -0000

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 <rstruik.ext@gmail.com>; wrote:
> 
> 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/ <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 11/9/2019 5:23 PM, Phillip Hallam-Baker wrote:
>> 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 <rsw@jfet.org <mailto:rsw@jfet.org>> wrote:
>> Phillip Hallam-Baker <phill@hallambaker.com <mailto:phill@hallambaker.com>> 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://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
>> 
>> 
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org <mailto:Cfrg@irtf.org>
>> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
> 
> -- 
> email: rstruik.ext@gmail.com <mailto:rstruik.ext@gmail.com> | Skype: rstruik
> cell: +1 (647) 867-5658 | US: +1 (415) 690-7363