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

Rene Struik <rstruik.ext@gmail.com> Sun, 10 November 2019 16:36 UTC

Return-Path: <rstruik.ext@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id C5AFE120170 for <cfrg@ietfa.amsl.com>; Sun, 10 Nov 2019 08:36:54 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Status: No, score=-1.997 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, 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 (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id QBWLuGFdX2q2 for <cfrg@ietfa.amsl.com>; Sun, 10 Nov 2019 08:36:52 -0800 (PST)
Received: from mail-qk1-x733.google.com (mail-qk1-x733.google.com [IPv6:2607:f8b0:4864:20::733]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DCD7B12004C for <cfrg@irtf.org>; Sun, 10 Nov 2019 08:36:51 -0800 (PST)
Received: by mail-qk1-x733.google.com with SMTP id m16so9243559qki.11 for <cfrg@irtf.org>; Sun, 10 Nov 2019 08:36:51 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:to:cc:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-language; bh=sPFh/Dq1tRxrVoAzRB+iU140w2mLhupl8QvyHSie54k=; b=Ca3UyZxMvFgBDqCCOtxdP3dGxQcaIuXrKXBy57kpFYQ197yPp8sKFVZIo97IzGUL2s DD1L372Y9BionXXZmcQ7zp+mHDpVo7JWBnCglkIvvVAA6prV9mN7OpaKfzNEjBDVuDV2 7pNES5LGte/KX2DZpEQZOKBrU+K0ulKSuOAJbBfltkQujva6uCsGP9cJDCrRjEnC4Kua dFEqaHbIDKGdTqjxEZ2iUOUsN77A/qBOFAXLMhMK5ApU8xKtK91pSh9UKB/6B++yoE4Z /X92w4NX8kCM2a+KIABp3lYQuI+xDzjyQh75JZ2QORZA1jw2I0398U4hz9BplVnyuY8/ XSwQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=sPFh/Dq1tRxrVoAzRB+iU140w2mLhupl8QvyHSie54k=; b=RUQv0hnBySx3udx5nHA2OSoG3nqkOi35yAV0Uz54/rXjO1ib+fguWQBxXtZgN9tgnZ hSKybBa0dikjEg2rdzXcapIfEuUhbW3R4pXYk6wgKVKk+4onf9UxGwHFNrmRoDp9meDC HYmv8q72PE5EaC7wgDFa/A6VN3gTKKcQdBITqttVPXyOMxrBrRbuaML4zAt8BSZ4/GvT CPiMoTtGwiJwx1KwC9NtLJCcvv45gcM+Gy8SvNooyficOmTCy3WM9od0whBqr7HNe1Xb yZHWdVgsy3d1aGwV8ikLdG/KZWBdGIStMA+mJMq8k3ad4ULUXVPj5pvp8diHicDuTlrk aK6Q==
X-Gm-Message-State: APjAAAV+4ByjnJX6tR7BkLXynwRT+Tqb3co2BI4KfOlxGir5cZWo44Tx WC1y1oc6s4w5qYnGA6LZbG3jZf6T
X-Google-Smtp-Source: APXvYqzCQKozYKwKV+b9toVJOW8B864tmA11L2SyP4ifidmfqdoCi5wekBI21Xuluidw3mRCI5MvYg==
X-Received: by 2002:a37:bc3:: with SMTP id 186mr6554715qkl.196.1573403810665; Sun, 10 Nov 2019 08:36:50 -0800 (PST)
Received: from ?IPv6:2607:fea8:69f:fa3a:fc5f:12b:d173:619a? ([2607:fea8:69f:fa3a:fc5f:12b:d173:619a]) by smtp.gmail.com with ESMTPSA id k29sm5571179qtu.70.2019. (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 10 Nov 2019 08:36:49 -0800 (PST)
To: Phillip Hallam-Baker <phill@hallambaker.com>, "Riad S. Wahby" <rsw@jfet.org>, Mike Hamburg <mike@shiftleft.org>
Cc: cfrg@irtf.org
References: <CAMm+LwiB6cpcnb_gpfXueU-A5w=jJ-4U5hhH_xkH5ERx1budoQ@mail.gmail.com> <20191109190705.j4b7chrjfev3lwig@positron.jfet.org> <CAMm+LwhRA3zTMdMM0U-qbC47i80LF8PyN9hX3bzVy_kddHisCw@mail.gmail.com>
From: Rene Struik <rstruik.ext@gmail.com>
Message-ID: <f47fc518-a005-9546-d84f-971617351921@gmail.com>
Date: Sun, 10 Nov 2019 11:36:45 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.9.1
MIME-Version: 1.0
In-Reply-To: <CAMm+LwhRA3zTMdMM0U-qbC47i80LF8PyN9hX3bzVy_kddHisCw@mail.gmail.com>
Content-Type: multipart/alternative; boundary="------------26DB75CB73662D2573502564"
Content-Language: en-US
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/9ZHmsCcIY9t1OA3OYqJr0uKprWw>
Subject: [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: Sun, 10 Nov 2019 16:36:55 -0000

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 = 

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]).


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

I hope this helps.


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), 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
> https://www.irtf.org/mailman/listinfo/cfrg

email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363