Re: [Cfrg] Mishandling twist attacks

David Leon Gil <coruus@gmail.com> Sat, 29 November 2014 02:35 UTC

Return-Path: <coruus@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 2FEB61A1BD6 for <cfrg@ietfa.amsl.com>; Fri, 28 Nov 2014 18:35:52 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 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, HTML_MESSAGE=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 9ALKM4YIl-Vc for <cfrg@ietfa.amsl.com>; Fri, 28 Nov 2014 18:35:49 -0800 (PST)
Received: from mail-ig0-x22e.google.com (mail-ig0-x22e.google.com [IPv6:2607:f8b0:4001:c05::22e]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E19021A1BC8 for <cfrg@irtf.org>; Fri, 28 Nov 2014 18:35:48 -0800 (PST)
Received: by mail-ig0-f174.google.com with SMTP id hn15so10640166igb.1 for <cfrg@irtf.org>; Fri, 28 Nov 2014 18:35:47 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:references:from:date:message-id:subject:to :content-type; bh=qP+ye82JvhvuJxUmPgqW4m+3cLywtqTHQMK5ucBvmaQ=; b=Wekz1udoe6iHqYVGJCKZzl8OC46zdtHs0CW7RNLTF5+TR1sngpOwTwTBjwPt56axSg FMN5oiF/YMzb8BrVlgit9/pstzblUUYcBjdiMDYg9Y7TG0ib/5ZqdQ945nIkjPB3iMdj 0vw85Vw/5EbuJmuvQQyup177VUy94R4d7DjpBqJX7dGY+4yUSkkim4TiLmbbU+Qm5tWm s78b+/WoYmcw0gbbu3Vp3L179WzCrAZAx6aShoYTCHXhyzdadQiEsZpf8gFf2xcpiJOt oesH62YY9ExaXoqpg6BKqy1DmDQHIhheKPi+9vxtg0YQFR76XnGynDxD9CR3hOLSlBTW DwFQ==
X-Received: by 10.107.35.83 with SMTP id j80mr4952444ioj.55.1417228547859; Fri, 28 Nov 2014 18:35:47 -0800 (PST)
MIME-Version: 1.0
References: <20141128014059.26622.qmail@cr.yp.to> <CACsn0cm4OBZX9RqV0nuT7547h+4e2_X3qgButJ+sdZDvG+65Ww@mail.gmail.com> <54791F31.2080400@dei.uc.pt>
From: David Leon Gil <coruus@gmail.com>
Date: Sat, 29 Nov 2014 02:35:47 +0000
Message-ID: <CAA7UWsVAcEHF4pkOQAtDqhBx=X+cZxFbNk0F6L5zTnCCx5SQ-g@mail.gmail.com>
To: Samuel Neves <sneves@dei.uc.pt>, "cfrg@irtf.org" <cfrg@irtf.org>, "dgil@yahoo-inc.com" <dgil@yahoo-inc.com>
Content-Type: multipart/alternative; boundary=001a1140c936294fa90508f63cb4
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/ZmHqoJwJo6oRi9BydTZvIS-WiAY
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: Sat, 29 Nov 2014 02:35:52 -0000

1. Very much agreed on 3 mod 4 primes; they are much more pleasant to work
with.

The most rigid solution is then to require, as Samuel proposes, the curve
and its twist to have equal cofactors.

----

2. The NUMS paper's approach to selecting curves was technically superior;
it is elegant and rigid.

(Provided that the complete Edwards curve with parameter d0 is used, of
course.)

----

However. Curve25519 is widely deployed. The benefits of changing curve
parameters is negligible. No new curves over 2^255-19, please. We have a
perfectly good one.

The likelihood of my adopting a new curve is not increased by CFRG's
meddling with good crypto.

--

(I have no opinions about Curve1174.)

David Leon Gil
Yahoo

(PS From a hot tub, on Thanksgiving vacation.)
On Fri, Nov 28, 2014 at 5:20 PM Samuel Neves <sneves@dei.uc.pt>; wrote:

> On 28-11-2014 17:22, Watson Ladd wrote:
> > What exactly is wrong with telling everyone to multiply by 8, not 4,
> > even if the cofactor is 4?
>
> If your protocol is tightly coupled with an elliptic curve, nothing wrong
> with that, I suppose. But schemes and
> protocols are often specified in terms of generic groups, where order and
> cofactor always exist, but the notion of twist
> security may not.
>
> > 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.
>
> All this bickering further convinces me that complete Edwards curves over
> 3 (mod 4) primes are the way to go:
>
>  - Square root computations are the simplest. 1 (mod 4) is too lenient, by
> the way: I don't think anybody is interested
> in computing square roots over 1 (mod 8) primes.
>
>  - Edwards curves over 3 (mod 4) primes can have both order and twist with
> cofactor 4.
>
>  - For users obsessed with speed, Mike Hamburg has described how to use an
> isogeny to get twisted Edwards-speed out of
> these curves [1].
>
> We already have an excellent candidate in this space, namely Curve1174
> over 2^251-9. E-521 is also such a curve. Since
> 2^389-21---which appears to be one of the nicest primes in that range (the
> other one being 2^379-19)---is also congruent
> to 3 (mod 4), it seems logical to keep things consistent and choose 3 (mod
> 4) primes for every work factor.
>
> [1] https://eprint.iacr.org/2014/027
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>