### Re: [Cfrg] A note on how to (pre-)compute a ladder

Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx> Tue, 04 April 2017 01:11 UTC

Return-Path: <francisco@cs.cinvestav.mx>

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 DF1021293F4
for <cfrg@ietfa.amsl.com>; Mon, 3 Apr 2017 18:11:41 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -1.902

X-Spam-Level:

X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001,
RP_MATCHES_RCVD=-0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001,
URIBL_BLOCKED=0.001] autolearn=ham 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 r9IPkIl0VpL8 for <cfrg@ietfa.amsl.com>;
Mon, 3 Apr 2017 18:11:39 -0700 (PDT)

Received: from delta.cs.cinvestav.mx (delta.cs.cinvestav.mx [148.247.102.21])
(using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id EA1FB1252BA
for <cfrg@irtf.org>; Mon, 3 Apr 2017 18:11:38 -0700 (PDT)

Received: from localhost (localhost [127.0.0.1])
by delta.cs.cinvestav.mx (Postfix) with ESMTP id E7E825C206F;
Mon, 3 Apr 2017 20:11:23 -0500 (CDT)

X-Virus-Scanned: amavisd-new at cs.cinvestav.mx

Received: from delta.cs.cinvestav.mx ([127.0.0.1])
by localhost (delta.cs.cinvestav.mx [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id f7s5x4uBQW5K; Mon, 3 Apr 2017 20:11:22 -0500 (CDT)

Received: by delta.cs.cinvestav.mx (Postfix, from userid 1507)
id 69CE05C2098; Mon, 3 Apr 2017 20:11:22 -0500 (CDT)

Received: from localhost (localhost [127.0.0.1])
by delta.cs.cinvestav.mx (Postfix) with ESMTP id 04EDE5C206F;
Mon, 3 Apr 2017 20:11:22 -0500 (CDT)

Date: Mon, 3 Apr 2017 20:11:22 -0500 (CDT)

From: Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx>

To: Peter Dettman <peter.dettman@bouncycastle.org>

cc: cfrg@irtf.org

In-Reply-To: <badf4370-ee06-7312-0a94-ffd3a6df40ff@bouncycastle.org>

Message-ID: <alpine.LFD.2.02.1704031956300.14799@delta.cs.cinvestav.mx>

References: <CAHOTMVKHA-yJR1oCyPtUp4-aJVc3dTdyxQHNo4xqnJt0hU6jVQ@mail.gmail.com>
<CAMm+Lwgm8XzTBarZ1eFePTZGORorBJAeF7brDkhWGQKQVT0LPQ@mail.gmail.com>
<CAMm+LwggT_AVv=KjzM1r=6UnkeK+g8zkticXFBDQ0cUXs_PP0A@mail.gmail.com>
<CAHOTMVLHPFyi2VWpv85hrZ1MoXqeHYUv52wkMxjj3xp5B4V1cw@mail.gmail.com>
<CAMm+Lwgfk1=yEJSbZbaZLvF5k5k66VVSx6MzKLM+DbUV7Ls6Xw@mail.gmail.com>
<CAHOTMVK1gYrFiwd8f8zf2zPXYyCorp+jixkcY5FLhfHfv0NkWw@mail.gmail.com>
<CAMm+LwjeZdR=ZGX0topN2w6P12jEmR-TQ8M9+anyETj43nbiqg@mail.gmail.com>
<CAHOTMVL2e2UjVX6VKgHUbOHrb-gsU8kn_cxY1FdNrnj29cki9g@mail.gmail.com>
<alpine.LFD.2.02.1703291804030.8996@delta.cs.cinvestav.mx>
<badf4370-ee06-7312-0a94-ffd3a6df40ff@bouncycastle.org>

User-Agent: Alpine 2.02 (LFD 1266 2009-07-14)

MIME-Version: 1.0

Content-Type: MULTIPART/MIXED;
BOUNDARY="-141290138-2003453357-1491268282=:14799"

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/L0nSpuczWCYiwu08IyAc0FK7fOI>

Subject: Re: [Cfrg] A note on how to (pre-)compute a ladder

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.22

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, 04 Apr 2017 01:11:42 -0000

Hi Peter, Thank you very much for your feedback! Please see below for our interlined comments. Cheers, The authors On Fri, 31 Mar 2017, Peter Dettman wrote: > Hi Francisco, > > Seems like a nice performance win for key generation with very little > extra effort over the variable-point ladder in RFC 7748. Thanks! > Would it be worth briefly addressing safe-error attacks? Yes, indeed. A preliminary analysis could go along the following lines. C safe-error attacks: The addition in [Alg. 4, Stp. 8] is not a dummy operation, but it is required for performing further R1 = R0 + R1 additions. Moreover, given that in the X25519 and X448 functions the most significant bit of the scalar k is always set k_(n-1) = 1, the last iteration of [Alg. 4] performs the addition R1 = R0 + R1 (with R2 = R0 - R1). As a result, a computational fault induced at any iteration in [Stp. 8] would produce an incorrect point Q. M safe-error attacks: let M0 and M1 be memory addresses. The "cswap" function guarantees that every iteration of [Alg. 4] performs the operation M0 <- R0 + M0 (with M1 = R0 - M0), where (M0, M1) contains (R1, R2) if k = 1 and (R2, R1) otherwise. Then, the attacker is only able to modify the blocks of M0, which is not sufficient to deduce the bits of the scalar k. Most probably, for hardware implementations other countermeasures should be taken, but they are similar to the ones applied on the classical Montgomery ladder. On the other hand, as pointed out in previous messages in this forum, the "cswap" function does not protect against every side-channel threat. Furthermore, as far as we know, the practical implications of safe-error attacks over the "cswap" function have not been studied yet. > At first glance Algorithm 4 appears to not involve R2 in the final > result, although it's made clear later in Algorithm 5 that both R1 and > R2 are used in every addition due to the choice of addition formula. You are right, the R2 is the difference R0 - R1. > Remark 2 at the end of 5.1 presents this as a minor performance > optimization, but fails to point out that it is needed to protect > against safe-error attacks. Using the improvements suggested by Peter Montgomery in his '87 paper, we have the following formulas: U3 <- Z2*((U1+Z1) + A*(U1-Z1))^2 U3 <- U2*((U1+Z1) - A*(U1-Z1))^2 with A = (U0+Z0) and Z0 = 1/(u-1), U0 = x*Z0. /* all operations pre-computed */ Here, the coordinates of R2 are used too. Consequently, the advantage of the formulas listed in Remark 2 is actually the savings of two field additions. > Regards, > Pete Dettman Thanks for the comments! > On 30/03/2017 8:00 AM, Francisco Rodriguez- Henriquez wrote: >> Dear CFRG community, >> >> We would like to draw your attention to our IACR pre-print entitled, >> >> "A note on how to (pre-)compute a ladder >> Improving the performance of X25519 and X448" >> >> https://eprint.iacr.org/2017/264.pdf. >> >> For the point multiplication computation Q = kP, this note describes a >> right-to-left version of the Montgomery ladder, which is amenable for >> pre-computing multiples of the base point P. By requiring very modest >> memory resources and a small implementation effort, it obtains noticeable >> performance improvements with respect to the RFC 7748 classical ladder >> procedure. >> >> We stress that our proposal fully complies with the RFC 7748 >> specification, in the sense that given any arbitrary secret keys of >> Alice and Bob, our ladder generates exactly the same public keys that an >> implementation of the RFC 7748 would output. >> >> As a way of illustration, in Appendix B of our note, we include a magma >> script, which given Alice and Bob private keys of RFC7748 Sec. 6.2, it >> computes the same public keys as specified in that document. >> >> We would be delighted to receive feedback (including sightings of typos) >> from the CFRG community. >> >> With best regards, >> >> Thomaz Oliveira, Julio López and Francisco Rodríguez-Henríquez >> >> >> _______________________________________________ >> Cfrg mailing list >> Cfrg@irtf.org >> https://www.irtf.org/mailman/listinfo/cfrg >> > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg >

- [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Aaron Zauner
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Dmitry Khovratovich
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Nadim Kobeissi
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Taylor R Campbell
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Phillip Hallam-Baker
- Re: [Cfrg] Interest in an "Ed25519-HD" standard? Tony Arcieri
- [Cfrg] A note on how to (pre-)compute a ladder Francisco Rodriguez- Henriquez
- Re: [Cfrg] A note on how to (pre-)compute a ladder Peter Dettman
- Re: [Cfrg] A note on how to (pre-)compute a ladder Peter Dettman
- Re: [Cfrg] A note on how to (pre-)compute a ladder Francisco Rodriguez- Henriquez
- Re: [Cfrg] A note on how to (pre-)compute a ladder Francisco Rodriguez- Henriquez
- [Cfrg] How to (pre-)compute a ladder [revised ver… Francisco Rodriguez- Henriquez
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Mike Hamburg
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Peter Dettman
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Antonio Sanso
- Re: [Cfrg] How to (pre-)compute a ladder [full C … Francisco Rodriguez- Henriquez
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Francisco Rodriguez- Henriquez
- Re: [Cfrg] How to (pre-)compute a ladder [revised… Francisco Rodriguez- Henriquez