Re: [Cfrg] Mishandling twist attacks

Watson Ladd <> Fri, 28 November 2014 17:22 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id A04F11A008A for <>; Fri, 28 Nov 2014 09:22:20 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 9wc1i32AtJoz for <>; Fri, 28 Nov 2014 09:22:17 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:4002:c07::236]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id A0EF11A002F for <>; Fri, 28 Nov 2014 09:22:17 -0800 (PST)
Received: by with SMTP id 131so3142351ykp.13 for <>; Fri, 28 Nov 2014 09:22:17 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; 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 with SMTP id g124mr37155385yka.24.1417195336894; Fri, 28 Nov 2014 09:22:16 -0800 (PST)
Received: by with HTTP; Fri, 28 Nov 2014 09:22:16 -0800 (PST)
In-Reply-To: <>
References: <>
Date: Fri, 28 Nov 2014 09:22:16 -0800
Message-ID: <>
From: Watson Ladd <>
To: "" <>
Content-Type: text/plain; charset=UTF-8
Subject: Re: [Cfrg] Mishandling twist attacks
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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 <> 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.
> 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

Watson Ladd