Re: [Cfrg] Mishandling twist attacks
Watson Ladd <watsonbladd@gmail.com> Fri, 28 November 2014 17:22 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 A04F11A008A for <cfrg@ietfa.amsl.com>; Fri, 28 Nov 2014 09:22:20 -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 9wc1i32AtJoz for <cfrg@ietfa.amsl.com>; Fri, 28 Nov 2014 09:22:17 -0800 (PST)
Received: from mail-yk0-x236.google.com (mail-yk0-x236.google.com [IPv6:2607:f8b0:4002:c07::236]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A0EF11A002F for <cfrg@irtf.org>; Fri, 28 Nov 2014 09:22:17 -0800 (PST)
Received: by mail-yk0-f182.google.com with SMTP id 131so3142351ykp.13 for <cfrg@irtf.org>; Fri, 28 Nov 2014 09:22:17 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=lKGj6CR3On4GkbV5fogsNWQT+khwKI2D5uklwnN0lTs=; b=mmekLkV5xeSSqRsXvsxYmZIyYTnZVA4mUUMmJ7Jqbs2gz/xkOQqqxTCyUxYbW0iGeD DY0j7hNrp+bashsPAGobkUA2Cb8D5byumPlQ2MTbZC1XrtMZk0m6BaiuIdz/OY0bNXFN mqdytJOocHvfvznICb3dkWG00G/LzzBA0BngPVVFgOVmrbsS5CWa80qA7Do2yJi9ySLs iJjws6dOOyQZzctFA+DpHrqoGGdTHTyMUD814cz3wCOhyYDwSD/5lvDOk1BmcJ3jDeUX yvY43IdtyfCVGnyD9e2wDEwolU9TCc0tabKo9FtXoBrBsIa0k+G7nOQE77rkz4ijQX67 o7Ng==
MIME-Version: 1.0
X-Received: by 10.170.89.130 with SMTP id g124mr37155385yka.24.1417195336894; Fri, 28 Nov 2014 09:22:16 -0800 (PST)
Received: by 10.170.195.21 with HTTP; Fri, 28 Nov 2014 09:22:16 -0800 (PST)
In-Reply-To: <20141128014059.26622.qmail@cr.yp.to>
References: <20141128014059.26622.qmail@cr.yp.to>
Date: Fri, 28 Nov 2014 09:22:16 -0800
Message-ID: <CACsn0cm4OBZX9RqV0nuT7547h+4e2_X3qgButJ+sdZDvG+65Ww@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: text/plain; charset="UTF-8"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/-IgqKzqcMdnzbLpd09u4J892Im8
Subject: Re: [Cfrg] Mishandling twist attacks
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, 28 Nov 2014 17:22:20 -0000
On Thu, Nov 27, 2014 at 5:40 PM, D. J. Bernstein <djb@cr.yp.to> wrote: > Two slight variants of Curve25519 were considered and rejected in the > Curve25519 paper. Apparently there's now a proposal to revive one of > those variants. Here are all three curves for comparison, including > names for the two variants so that I can refer to them: > > Curve25519: y^2 = x^3 + 486662x^2 + x mod 2^255-19 > FuschiaBikeShed: y^2 = x^3 + 464586x^2 + x mod 2^255-19 > PinkBikeShed: y^2 = x^3 + 358990x^2 + x mod 2^255-19 > > The proposal, specifically, is to use PinkBikeShed. The core argument > for this is that 358990 is smaller than 464586 and 486662. > > Perhaps I should emphasize that---when security is equal---the ultimate > arbiter is performance, not any preconceived notion of smallness. My > impression is that the ASIC costs of Curve25519 are marginally smaller > than the ASIC costs of PinkBikeShed and FuschiaBikeShed, after careful > optimization, because of the nicer bit pattern in 486662. Larger gaps in > sizes of constants often produce more noticeable slowdowns in software, > but I haven't found any platforms where 358990 is faster than 486662. > > But performance isn't the main topic of this message. There are much > more important reasons---security reasons---to reject PinkBikeShed. The > purpose of this message is to carefully explain one of those reasons. <snip> > > One can of course blame the implementors for not checking whether the > input point has order 8. One can blame the standards for not warning > people about twist attacks. One can blame the protocols for multiplying > by 4 for this particular curve rather than 8. But a competent curve > designer, instead of blaming everybody else for a predictable problem, > will simply eliminate the problem by choosing a better curve. What exactly is wrong with telling everyone to multiply by 8, not 4, even if the cofactor is 4? > > For Curve25519, the twist cofactor divides the curve cofactor, and this > problem disappears. What the standards say to do, namely multiply by the > curve cofactor, is wrong for PinkBikeShed but correct for Curve25519. > The numerical details are spelled out in the "Small-subgroup attacks" > section of the Curve25519 paper. > > This wasn't my only reason for rejecting PinkBikeShed. The Curve25519 > paper mentions a less important reason that allowed a much shorter > summary and that, as a historical matter, came first. I didn't bother > writing down a comprehensive critique of PinkBikeShed, and didn't > imagine that anyone would ever try to revive that curve. > > ---Dan So if we add this requirement to have the curve have larger cofactor then the twist, then we still get E-521, and we will get Curve25519 at the low end. It seems to me like we should make this change to the generation method, and run it on 2^389-21 to get the intermediate size curve. Sincerely, Watson Ladd
- Re: [Cfrg] Mishandling twist attacks Watson Ladd
- [Cfrg] Mishandling twist attacks D. J. Bernstein
- Re: [Cfrg] Mishandling twist attacks Michael Hamburg
- Re: [Cfrg] Mishandling twist attacks Alyssa Rowan
- Re: [Cfrg] Mishandling twist attacks Samuel Neves
- Re: [Cfrg] Mishandling twist attacks David Leon Gil
- Re: [Cfrg] Mishandling twist attacks D. J. Bernstein
- Re: [Cfrg] Mishandling twist attacks Ilari Liusvaara
- Re: [Cfrg] Mishandling twist attacks Lochter, Manfred
- Re: [Cfrg] Mishandling twist attacks D. J. Bernstein
- Re: [Cfrg] Mishandling twist attacks Lochter, Manfred
- Re: [Cfrg] Mishandling twist attacks Watson Ladd
- Re: [Cfrg] Mishandling twist attacks Lochter, Manfred
- Re: [Cfrg] Mishandling twist attacks Watson Ladd