Re: [Cfrg] Curve selection revisited

Robert Ransom <rransom.8774@gmail.com> Wed, 30 July 2014 09:36 UTC

Return-Path: <rransom.8774@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 DFA4A1B2A35 for <cfrg@ietfa.amsl.com>; Wed, 30 Jul 2014 02:36:14 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.75
X-Spam-Level:
X-Spam-Status: No, score=-1.75 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=no
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 6niDuyhY-o6o for <cfrg@ietfa.amsl.com>; Wed, 30 Jul 2014 02:36:13 -0700 (PDT)
Received: from mail-qa0-x236.google.com (mail-qa0-x236.google.com [IPv6:2607:f8b0:400d:c00::236]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A2D691A01C6 for <cfrg@irtf.org>; Wed, 30 Jul 2014 02:36:13 -0700 (PDT)
Received: by mail-qa0-f54.google.com with SMTP id k15so976933qaq.41 for <cfrg@irtf.org>; Wed, 30 Jul 2014 02:36:12 -0700 (PDT)
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 :cc:content-type:content-transfer-encoding; bh=YziIA/HyaxiHxQIcpKohrhInRkq8RWiLwsbBcgkfE/w=; b=wPT2qPTKBIGZ97zKe2o/zC8k0bEr0TmA9j7iF8N2fyHtbma9RpGuD2BJHM+KgQ9Fsg /tyvUboBm3Z2jUbflh0pygLk90/jOssc6KpvOIPgff76zKa1/TWQNXqdKu+gNRY9qyG3 gcMH68gVqKaTGv3oVPAWKW5sg7lVsaoZJWNHKe8YYrL6eJFKLEIyXOoH6TEhXDk2Piu1 YIAXmDbnxFJTJurHMtJDz7iKuFt4VRfFxvNBmNe9pPnhgShrGUWN/Mo+hRPJJL9i9USH cQisKP8X8Sq3AnQDGC3velKw5Or803wbpd4sAhloaMxApVGG+Nnttz0u5rx9DVv48RlZ BaTw==
MIME-Version: 1.0
X-Received: by 10.140.105.72 with SMTP id b66mr4558838qgf.30.1406712972581; Wed, 30 Jul 2014 02:36:12 -0700 (PDT)
Received: by 10.140.86.135 with HTTP; Wed, 30 Jul 2014 02:36:12 -0700 (PDT)
In-Reply-To: <53D89DB0.9020505@brainhub.org>
References: <CA+Vbu7xroa68=HOZtbf=oz7kK2EeUv_z1okpnjxHPR0ZtHD5cA@mail.gmail.com> <CFF7E184.28E9F%kenny.paterson@rhul.ac.uk> <53D2781B.8030605@sbcglobal.net> <CACsn0ckqFigWoH2+OOEHSd2VWPp8y6=m8H5OsFRyjXmjK7+m4w@mail.gmail.com> <CABqy+srxMNuG0AaQd0SaegHvZWgbW762EQq+iAHL_fbu6sOJJQ@mail.gmail.com> <53D420B3.10707@brainhub.org> <CABqy+so6JcL3drjXuiQfLhm-LPMOJuS9ES5Hyb1UQRhi-gV2jA@mail.gmail.com> <53D89DB0.9020505@brainhub.org>
Date: Wed, 30 Jul 2014 02:36:12 -0700
Message-ID: <CABqy+spEkd9BCwE3o+CyRDeN24TPvQBHoyY+VYr9eeK4dg6sPg@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Andrey Jivsov <crypto@brainhub.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/lkUdJIaSc4AGuqDOk7HJbbT1Id4
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Curve selection revisited
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: Wed, 30 Jul 2014 09:36:15 -0000

On 7/30/14, Andrey Jivsov <crypto@brainhub.org> wrote:
> On 07/29/2014 04:14 AM, Robert Ransom wrote:

>> Do you see any benefit of p = 2^256 - 189 over p = 2^255 - 19 that you
>> believe offsets the costs of switching to a different coordinate
>> field?
>
> They are :
> * aesthetics
> * it happened that square root of  p = 2^255 - 19 requires
> multiplication by a sqrt(-1) in half the cases when decompression is
> involved.
>
> Both are tolerable from aesthetics point of view IMO if we (effectively)
> standardize on p = 2^255 - 19. p = 2^255 - 19's slightly higher
> performance than 2^256 - 189 should balance *sqrt(-1) out.

What do you mean by “aesthetics”?  (My aesthetic sense may have been
warped by seeing how these fields are implemented -- 2^255-19 and
2^414-17 are quite pretty to me.)

As for the slightly more annoying square-root algorithm modulo
2^255-19, (a) that's *much* better than the P-224 field (already
IETF-approved as a TLS NamedCurve), and (b) that's better than having
a trade-off between using the a=-1 formulas (and saving 1M per scalar
limb in Edwards form) and having a complete formula available for
arbitrary points.  I think it's unfortunate that 2^414-17 is a 3mod4
field rather than a 5mod8 field.


> ( Compare this with 2^414-17, which won't be trivial to match with other
> algorithms. )

What do you mean by “match with other algorithms”?

If you're referring to ‘security level’:

* Stream-cipher keys are found by brute-force preimage search;
discrete logarithms in strong EC groups are computed by brute-force
collision search on the function m*P + n*Q.  The preimage-search
attack on a stream cipher can attack multiple target keys at the same
time at no extra cost, and its probability of finding any of the
target keys is linear in the number of operations performed.  The
discrete-logarithm attack targets a single key at a time (and cannot
find the first of multiple targets at reduced cost), and its
probability of finding the target key increases slower than linearly.
(See Dr. Bernstein's bruteforce paper for the engineering details of
preimage search, then see his ecc2k130 paper for the details of
discrete logarithms, though that paper targets a curve with
automorphisms.)  Thus, a curve group ‘at the n-bit security level’
should always be used with a stream cipher whose key is longer than n
bits.

* The only reason that people use AES keys shorter than 256 bits is
that NSA chose a cipher which uses more rounds (and is thus slower)
for longer keys.  If AES-256 ran at the same speed as AES-128,
everyone would rightly use 256-bit keys, regardless of the difficulty
of breaking the public-key algorithm used with it.


Robert Ransom