[Cfrg] How rigid is rigid enough?

David Leon Gil <coruus@gmail.com> Thu, 08 January 2015 06:49 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 87B0B1A885A for <cfrg@ietfa.amsl.com>; Wed, 7 Jan 2015 22:49:40 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.7
X-Spam-Level:
X-Spam-Status: No, score=0.7 tagged_above=-999 required=5 tests=[BAYES_50=0.8, 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 X_jebuokFYbL for <cfrg@ietfa.amsl.com>; Wed, 7 Jan 2015 22:49:38 -0800 (PST)
Received: from mail-ie0-x22a.google.com (mail-ie0-x22a.google.com [IPv6:2607:f8b0:4001:c03::22a]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2FF201A887B for <cfrg@irtf.org>; Wed, 7 Jan 2015 22:49:38 -0800 (PST)
Received: by mail-ie0-f170.google.com with SMTP id rd18so8043058iec.1 for <cfrg@irtf.org>; Wed, 07 Jan 2015 22:49:37 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:from:date:message-id:subject:to:content-type; bh=Z3E02v7EAKGynLXguMLI6wHx2jeV5Twv/RnlzieHHOo=; b=nS0K57aWjVJ9hjFLkeDKUgTuuAVXWwcWdOSP/4Bawwqp0tg9ja63l/0p57wyRLmajf plgohburdgsRkeyfuHeNhunIkw3XRaxoC7ytDkzN5SrRWlSKfAcTPKV1HN7hjCcelFW9 GJZCTYuqbdrodQhtIaOFoiADHj2Um14xatzCCZp+zI7j1t+9eqRpETCKGA8fWFpsiHQF KnO5Geoq95cbK2MmEFr9bSnT2zX/a4Qh2IRHr/ED9O3n7uFOsxDRFT9mGQBBBVRE2qyS rVg3KBuzuupdkyNfnZInj1dc+4xXYT5OgFFEqy0LwWDyI3hG0dcY+CSEniC6YZikljzi 02JQ==
X-Received: by 10.50.117.68 with SMTP id kc4mr26446695igb.25.1420699777270; Wed, 07 Jan 2015 22:49:37 -0800 (PST)
MIME-Version: 1.0
Received: by 10.107.132.211 with HTTP; Wed, 7 Jan 2015 22:49:16 -0800 (PST)
From: David Leon Gil <coruus@gmail.com>
Date: Wed, 07 Jan 2015 22:49:16 -0800
Message-ID: <CAA7UWsVi+TszTYxKd4KSGYNryV24Bq+0FpxN2GO5LWA5khdqjg@mail.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/LQIyeCFGgoROzsx_UBf9cjlsS-A
Subject: [Cfrg] How rigid is rigid enough?
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: Thu, 08 Jan 2015 06:49:40 -0000

# How rigid are rigid curves?

(About 138 reasonable choices of curve for the range 2^300
to 2^521.)

## Rigid fast primes in the range 2^300 to 2^521

Mersennes:
  2^521 - 1       == 3 mod 4   M521

(Granger-Scott have presented a fast algorithm for platforms where
the number of limbs is too small for FFT-based multiplication to
be efficient.)

A minimal Crandall is a prime of the form:

  2^n - c, !E c' < c : is_prime(2^n - c)

Crandalls are fast when log2(c) <<< limb_bits. If we want a Crandall
that's fast on any platform, this effectively restricts us to c < 32.
(LCD platform: JavaScript, where bignums typically use 12/24 limbs.)

Crandalls:
  2-bit:
    2^336 -  3    == 1 mod 4
    2^452 -  3    == 1 mod 4   C452 (???)

  4-bit:
    2^321 -  9    == 3 mod 4
    2^322 - 11    == 1 mod 4
    2^338 - 15    == 1 mod 4

  5-bit:
    2^414 - 17    == 3 mod 4   C414 (djb)
    2^444 - 17    == 3 mod 4
    2^468 - 17    == 3 mod 4
    2^488 - 17    == 3 mod 4
    2^379 - 19    == 1 mod 4
    2^389 - 21    == 3 mod 4   C389 (rr?)
    2^413 - 21    == 3 mod 4
    2^489 - 21    == 3 mod 4
    2^324 - 23    == 1 mod 4
    2^369 - 25    == 3 mod 4   C369 (???)
    2^383 - 31    == 1 mod 4   C383 (NUMS)
    2^401 - 31    == 1 mod 4
    2^495 - 31    == 1 mod 4

Define an `m`-splitting `Ridinghood` as a prime of the form:

    2^n - 2^(n/2) - 1, n|2 /\ (n/2)|2^m

There is at most one Ridinghood per `n`. (And these are,
in fact, extremely rare primes.)

(Michael Hamburg has described how multiplication modulo these
primes can take advantage of their Karatsuba-friendly shape.)

Ridinghoods:
  5-splitting:
    2^448 - 2^224 - 1 == 3 mod 4  R448 (mh)
  4-splitting:
    2^480 - 2^240 - 1 == 3 mod 4  R480 (mh)
    2^416 - 2^208 - 1 == 3 mod 4
  1-splitting:
    2^322 - 2^161 - 1 == 3 mod 4
    2^450 - 2^225 - 1 == 3 mod 4

So, in total: 22 plausible fast primes. (There are really
fewer than this, even; some of these are not sufficiently
larger than 2^255-19 to be interesting.)

## Minimal-cost curve parameters and corresponding basepoints

Minimal curve parameters. Let `c(x)` be a cost function, and
choose the value of a free parameter `x` such that there
does not exist another `x' != x` with `c(x') <= c(x)`.

Safe curves. Set `c(x) == \inf` if `#E/h` and `#Et/ht` are
not prime, or if some set of safety criteria are not
satisfied. (Insert SafeCurves criteria here.)

Choosing basepoints. Choose the unique point of order `#E/h`
whose single-coordinate representation in the chosen curve
model is minimal in value.

Choosing curve parameters. Suppose that we want an Edwards
curve; so we have a cofactor != 1. Choose the cofactor to
be minimal consistent with safety. Then:

    q == 1 mod 4: h = 8, ht = 4
    q == 3 mod 4: h = 4, ht = 4

Curve form and parameter, *x*:
- Proposed:
  BLE form, a=-1: d
  BLE form, a=+1: d
  Montgomery form: A
- Possible:
  Weierstrass, a=-3: b
- For mathematicians, mainly:
  Legendre form: lambda
  j-invariant

Cost functions, *c(x)*:
  - Proposed:
    min(x)
    min(abs(x))
  - Possible:
    min( (hamming(x), x) )

Am I missing any plausible proposals?

This gives 6 proposed methods of choosing Edwards curves.
Several of these are always equivalent up to isogeny, but for
the choice of basepoint.

# How rigid is rigid enough?

One way we might answer this is by asking whether there are any
cryptographically interesting properties of curves that we know of
that occur with probability on the order of 1/132.

There's at least one, now historical, example:

Only about 1/50 prime-order Weierstrass curves at this
bitlength is twist-secure. (See, e.g., traces for the prime
Salinas384; available at https://github.com/coruus/sally)

(Or, had CFRG then been in the business of choosing curves,
there would have been -- assuming that the CFRG process
is an effective means of selecting a curve uniformly at random
-- a < 0.2% chance of getting P384 right.)

So...is rigidity good? Yes. Do we know that a "rigid" choice
is, in fact, rigid enough to prevent an adversary from selecting
a curve with a chosen, cryptographically interesting property?
. . . . ?

Perhaps we can now hope -- with all of our problems for the
moment solved -- for an end to the rigider-than-thou holy wars,
and a return to collaborating to make ECC safer.

- dlg