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