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

Dan Brown <danibrown@blackberry.com> Sun, 10 November 2019 14:56 UTC

Return-Path: <danibrown@blackberry.com>
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 D0C78120096 for <cfrg@ietfa.amsl.com>; Sun, 10 Nov 2019 06:56:41 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.798
X-Spam-Level:
X-Spam-Status: No, score=-1.798 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
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 9WpyTMGvyXp7 for <cfrg@ietfa.amsl.com>; Sun, 10 Nov 2019 06:56:39 -0800 (PST)
Received: from smtp-pg11.blackberry.com (smtp-pg11.blackberry.com [68.171.242.227]) (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 A0112120074 for <cfrg@irtf.org>; Sun, 10 Nov 2019 06:56:39 -0800 (PST)
Received: from pps.filterd (mhs401ykf.rim.net [127.0.0.1]) by mhs401ykf.rim.net (8.16.0.27/8.16.0.27) with SMTP id xAAEqs6Q027226; Sun, 10 Nov 2019 09:56:37 -0500
Received: from xct104cnc.rim.net (smtp-pop.rim.net [10.65.161.204]) by mhs401ykf.rim.net with ESMTP id 2w5skabe9x-1 (version=TLSv1 cipher=ECDHE-RSA-AES256-SHA bits=256 verify=NOT); Sun, 10 Nov 2019 09:56:36 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT104CNC.rim.net ([::1]) with mapi id 14.03.0415.000; Sun, 10 Nov 2019 09:56:35 -0500
From: Dan Brown <danibrown@blackberry.com>
To: "phill@hallambaker.com" <phill@hallambaker.com>, "rsw@jfet.org" <rsw@jfet.org>, "mike@shiftleft.org" <mike@shiftleft.org>
CC: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Efficient side channel resistance for X25519..
Thread-Index: AQHVlygo0okM68e5IkeAudIlID7HXqeDh0GAgAA29ACAAMGSLQ==
Date: Sun, 10 Nov 2019 14:56:35 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF501E82D65@XMB116CNC.rim.net>
References: <CAMm+LwiB6cpcnb_gpfXueU-A5w=jJ-4U5hhH_xkH5ERx1budoQ@mail.gmail.com> <20191109190705.j4b7chrjfev3lwig@positron.jfet.org>, <CAMm+LwhRA3zTMdMM0U-qbC47i80LF8PyN9hX3bzVy_kddHisCw@mail.gmail.com>
In-Reply-To: <CAMm+LwhRA3zTMdMM0U-qbC47i80LF8PyN9hX3bzVy_kddHisCw@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
Content-Type: multipart/alternative; boundary="_000_810C31990B57ED40B2062BA10D43FBF501E82D65XMB116CNCrimnet_"
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2019-11-10_03:, , signatures=0
X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 priorityscore=1501 malwarescore=0 suspectscore=0 phishscore=0 bulkscore=0 spamscore=0 clxscore=1011 lowpriorityscore=0 mlxscore=0 impostorscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1910280000 definitions=main-1911100149
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/KnRKzhM2m4pQ7iKLn4y5DotUkE4>
Subject: Re: [Cfrg] 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 14:56:42 -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 <phill@hallambaker.com>;
Sent: Nov 9, 2019 5:24 PM
To: "Riad S. Wahby" <rsw@jfet.org>;; Mike Hamburg <mike@shiftleft.org>;
Cc: cfrg@irtf.org
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 <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://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.