[Cfrg] Montgomery yet again (was Re: Adoption of draft-agl-cfrgcurve-00 as a RG document)
Watson Ladd <watsonbladd@gmail.com> Fri, 09 January 2015 15:37 UTC
Return-Path: <watsonbladd@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D02311A01C6 for <cfrg@ietfa.amsl.com>; Fri, 9 Jan 2015 07:37:13 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 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, SPF_PASS=-0.001] autolearn=ham
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 QlFbuxARrwVA for <cfrg@ietfa.amsl.com>; Fri, 9 Jan 2015 07:37:10 -0800 (PST)
Received: from mail-yh0-x22b.google.com (mail-yh0-x22b.google.com [IPv6:2607:f8b0:4002:c01::22b]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 86C501A00FC for <cfrg@irtf.org>; Fri, 9 Jan 2015 07:37:10 -0800 (PST)
Received: by mail-yh0-f43.google.com with SMTP id z6so4395728yhz.2 for <cfrg@irtf.org>; Fri, 09 Jan 2015 07:37:09 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:cc:content-type; bh=pbvvpm1HFljwycBPMQxTku3pdfwAu3CEcf3Bd385+4M=; b=hgyV0NuOhLM6Df4ovbu5Xy9WwMDy/xYCcxdwTj6ehIBABGpzVlMD3m3mbZWp+RihJU sJyjPFmKfuZijmgEogp3lhV8xOypvyf9O5JK8cd9HWKiCXfIIYiORibOtiwWBnuWVT/C HDa71NqTfcvi+BVcGS0j6zlL9vy1FPSkc75sssP/FvuOH+v91KhAxGil88x0QPwzG19L ab8DOM7Pf5iGzWWnQXlWmn/lsyzBAOk6A+bCb9QfV5g6qyhtuo5BCxyhcK+Hs0A77+5+ mjbOoxf7Y4gwQ2f7ijc9udduRJUi1ZKcmgWVJ3Hv8H0uzSxrydjQ2Jnf7Srly12bDfeg XbCw==
MIME-Version: 1.0
X-Received: by 10.236.18.168 with SMTP id l28mr11662161yhl.172.1420817829740; Fri, 09 Jan 2015 07:37:09 -0800 (PST)
Received: by 10.170.207.6 with HTTP; Fri, 9 Jan 2015 07:37:09 -0800 (PST)
Date: Fri, 09 Jan 2015 10:37:09 -0500
Message-ID: <CACsn0cnqc-iHZuS7w6=G5zXM6u3MNWQNN7cgdBf5TkbPhB8LWA@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Joppe Bos <joppe.bos@nxp.com>
Content-Type: text/plain; charset="UTF-8"
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/VTxcfz36Q3pOM65IXfTjFyYVDlg>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: [Cfrg] Montgomery yet again (was Re: Adoption of draft-agl-cfrgcurve-00 as a RG document)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 09 Jan 2015 15:37:14 -0000
(Replace this email with the discussions had in May on teleconference, and over this summer as shown in "Progress on curve recommendations for TLS WG", http://www.ietf.org/mail-archive/web/cfrg/current/msg04760.html and the ensuing discussion. The last note is from http://www.ietf.org/mail-archive/web/cfrg/current/msg04966.html. If you've read these, you don't need to read this email ) On Fri, Jan 9, 2015 at 8:59 AM, Joppe Bos <joppe.bos@nxp.com> wrote: > Hi all, > > The current version of the draft contains methods for parameter selection > (section 6) and a single recommended curve (section 7). > IMO the natural approach would be to first agree upon a parameter selection > procedure (one draft) and subsequently, when a large portion of the > community agrees that this selection procedure is sound, use this procedure > to select new curves (another draft). Currently, we are changing the > selection procedure to match an existing curve. If we want curve25519 > because it is fast and widely deployed then we should state this clearly and > refrain from modifying the selection procedures because this might have a > negative impact on the potential selection of curves in the future. How does the existence of a selection procedure that gives Curve25519 and particular choice of an isogeny equal "changing the selection procedure to match an existing curve?" In fact, there are good reasons to favor the particular twist security criteria and use the given isogeny in any case. > > Please find below some comments on the current version of the draft. > > Section 7: > - The specification of the parameters is done either in formula form (p), in > decimal (d) or a formula + hexadecimal (order). Maybe use the same notation > (e.g. either decimal or hexadecimal) everywhere to avoid confusion? > - For completeness it might be good to give the corresponding (short) > Weierstrass form of the curve(s). Not sure why we want forms that won't be used. I agree we should explain the isogeny in more detail. > > Section 8-10: > These sections are curve25519 specific, this should be stated much clearer. > > Section 8: > As far as my understanding goes there was no consensus on the wire format of > field elements. > This section states that "when transmitting field elements in the > Diffie-Hellman protocol below, they MUST be encoded as an array of bytes, x, > in little-endian order". Maybe some notation got confused here, what is this > x-coordinate? The only x defined are on the Edwards curve while I think here > the Montgomery curve is meant (the u-coordinate from section 7). This should > be fixed or stated clearer to avoid confusion. Good catch! > > Section 9: > - It is not entirely clear to me why such low-level details are provided in > this draft. Is it expected from the CFRG to deliver implementation details > for algorithms or just a specification of curves plus related info (such as > wire formats)? If we want to provide such low-level details then why not > also state how to implement the field arithmetic? Paul Lambert argued that we need implementation details, and I think he's right. Field arithmetic is going to look different on 32 and 64 bit platforms, and on some architectures might be very strange. Maybe it's worth it: I don't have strong feelings one way or the other. I do agree that side-channel free algorithms may be worth presenting, particularly as the textbook algorithms are not. > - Why is only the approach based on the Montgomery ladder stated in this > section? There is nothing wrong with the Montgomery ladder but it is not the > best solution for all reasonable definitions of best. The implementer has > the choice, as stated before on this list, to compute DH on (for instance) > the corresponding Edwards or Weierstrass curve. Currently it looks as if the > CFRG recommends to use the Montgomery ladder for all scenarios; something > we know is suboptimal in terms of performance for higher security levels. > Moreover, imagine the scenarios where people use (twisted) Edwards curves > for signatures. Then implementing DH using the Montgomery ladder implies > managing code for both the Montgomery and the twisted Edwards curve and, > following the reasoning expressed by some people on this list, a larger code > base implies more room for errors which implies a less secure approach. > - This ladder implementation defines the usage of cswap ("due to the > existence of side-channels in commodity hardware"). Although this adds some > protection this algorithm is not secure in many realistic threat models > (e.g. in hardware security). To me, it looks quite arbitrary to just protect > against one type of attack and not against a whole range of other > side-channel attacks. The threat model should depend on where the > implementation will be used and therefore it is up to the implementer to > make the appropriate design decisions and introduce the adequate > countermeasures. While the hardware threat model is "realistic", I don't see why we should ignore settings in which cache-based and timing-based attacks are of concern and DPA isn't, and I don't see why we should remove information about protections that are adequate to this setting, because they aren't for all settings. The setting this algorithm is designed for is rather common. Implementors are free to ignore it if they have the understanding and need for a more appropriate algorithm for their setting. Right now many implementations are not side channel secure at all. We keep hearing about the implementor having to do this and that and the other thing, and it's all their fault when it doesn't work. Well, has anyone bothered to check if the implementor can do the job? I have, and the results are pretty ugly. We should err on the side of providing more assistance and guidance rather than chuck the plans over the wall, and come back to investigate the damage. There are real risks with using twisted Edwards form for DH that don't exist for ECDSA style signatures, or signatures that send r and s instead of R and s in Schnorr. As for complexity, we are discussing whether or not an additional 20 lines of code (if that!) will make maintenance more difficult. Certainly, more test vectors and the like will need to be added, but that's true anyway for signatures and DH. I'm surprised that this argument is getting made: OpenSSH has adopted Curve25519 and Ed25519, without worrying about the increased code size. Likewise, implementors of TLS libraries haven't raised this as a major concern. It's true that x-coordinate only DH isn't compatible with some protocols like HMQV, but these are rather uncommon. Sincerely, Watson Ladd > > Best regards, > > Joppe > > -----Original Message----- > From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Alexey Melnikov > Sent: Monday, January 05, 2015 8:15 PM > To: cfrg@irtf.org > Subject: [Cfrg] Adoption of draft-agl-cfrgcurve-00 as a RG document > > This message starts 2 weeks adoption call (ending on January 19th 2015) on: > > https://www.imperialviolet.org/cfrgcurve/cfrgcurve.xml > > as the starting point for the CFRG document which describes an algorithm for > safe curve parameter generation for a particular security level and also > recommends a specific curve (2^255-19) for the 128-bit security level. > > Please reply to this message or directly to CFRG chairs, stating whether you > support (or not) adoption of this document. If you do not support adoption > of this document, please state whether you support adoption of any > alternative document or whether you want a particular change be made to the > document before adoption. > > Chairs ask not to reiterate previously expressed technical opinions or > arguments. But clarifying questions on the adoption call are welcome. > > While making your decision, please keep in mind > > http://www.ietf.org/mail-archive/web/cfrg/current/msg05813.html > > Alexey, > On behalf of CFRG chairs. > > P.S. Editors of draft-black-rpgecc-01 and > draft-turner-thecurve25519function-01 can become co-editors of the adopted > document, if they choose to do so. Email chairs directly if you are willing > or not willing to do so. > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > http://www.irtf.org/mailman/listinfo/cfrg > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > http://www.irtf.org/mailman/listinfo/cfrg > -- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin
- [Cfrg] Montgomery yet again (was Re: Adoption of … Watson Ladd
- Re: [Cfrg] Montgomery yet again (was Re: Adoption… Paul Lambert