Re: [Cfrg] ECC reboot (Was: When's the decision?)

Alyssa Rowan <akr@akr.io> Thu, 16 October 2014 18:29 UTC

Return-Path: <akr@akr.io>
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 1138D1A7018 for <cfrg@ietfa.amsl.com>; Thu, 16 Oct 2014 11:29:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_HELO_PASS=-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 F8A3u5ogbojM for <cfrg@ietfa.amsl.com>; Thu, 16 Oct 2014 11:29:52 -0700 (PDT)
Received: from entima.net (entima.net [78.129.143.175]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9B5681A8032 for <cfrg@irtf.org>; Thu, 16 Oct 2014 11:29:51 -0700 (PDT)
Message-ID: <54400E9F.5020905@akr.io>
Date: Thu, 16 Oct 2014 19:29:51 +0100
From: Alyssa Rowan <akr@akr.io>
MIME-Version: 1.0
To: "cfrg@irtf.org" <cfrg@irtf.org>
References: <D065A817.30406%kenny.paterson@rhul.ac.uk>
In-Reply-To: <D065A817.30406%kenny.paterson@rhul.ac.uk>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/Jkbp6JyDKfDJfD7NhIhs4y3bZ4o
Subject: Re: [Cfrg] ECC reboot (Was: When's the decision?)
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, 16 Oct 2014 18:29:54 -0000

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

On 16/10/2014 17:08, Paterson, Kenny wrote:

> Our first task should be to finalise the requirements that we will
> use to guide the selection process. I think we are close, with a
> couple of outstanding issues:

Alright, so let's try to get things in high gear and argue those out…?

> 1. Amount of "wiggle room" that should be permitted.

Broadly: I think what we're aiming for is probably one faster/strong
curve, and one stronger/fast curve.

Given the strong preferences of some to minimise the number of curves,
it looks to me like ­≈384 is almost-definitely dropped, leaving us
with something near ≈256 and something near ≈512.

We seem to be in agreement that wiggle room on ≈256 would include
fields of 2^255-19 as well as 2^256-189 in scope.

For the paranoid-strong, performance-second ≈512, 2^512-569 very
obviously falls within scope.

I put forth that 2^521-1 also falls within scope. It's not very far
away, and it's a true Mersenne prime rather than a pseudo-Mersenne,
and they do not grow on trees - no others fall near our criteria (the
next lowest is 2^127-1 which is way too small, and the next biggest is
2^607-1). They are very attractive - attractive enough for 4 (?)
independent research groups to independently arrive on E-521, and
SECG/NIST to have independently picked the same prime years ago for
secp521r1.

[Previous discussion countering this point: Sean Parkinson @ RSA
suggested stepping over a power of 2 is "only going to hurt
performance in the future". Phillip Hallam-Baker also thought anything
that is not less than a clean multiple of a power of two "may cause
severe performance hits on future architectures", mentioning 512-bit
memory buses on graphics cards?! - although I'm not convinced that's
actually primarily relevant to an implementation of a high-strength
curve. We will, of course, evaluate performance of contenders in Phase
II, future architectures can be more-or-less anything that works well,
and performance implications usually aren't anything like so obvious…
Aren't Mersennes actually particularly _good_ performance-wise?]

I put forth that 2^414-17 and 2^448-2^224-1 might fall outside "wiggle
room" there, although I do so very reluctantly as I think it's a shame
to exclude them on that basis if they have otherwise nice properties,
and they do seem to have very good performance for their strength.

> 2. A more nuanced set of hardware requirements.

See other thread.

> So here's a proposal for a new schedule which I believe to be
> feasible: 24/10/14 (1 week from now): we finalise requirements,
> including hardware requirements.

Optimistic? One way to find out. <g>

> 31/10/14 (2 weeks from now): we agree on whatever benchmarking
> system we're going to use for performance measurements. (Right now,
> supercop seems like the front runner to me.)

Consider this an early +1 to SUPERCOP.

> 30/11/14 (6 weeks from now): we deliver our recommendations to the
> TLS WG.

Let's give it a try!

- -- 
/akr
-----BEGIN PGP SIGNATURE-----

iQIcBAEBCgAGBQJUQA6fAAoJEOyEjtkWi2t6U8gQAJG9FmifkdZs2QQv+2gB8o2w
fWdo6FztDHIyGaUTaOLzHdKhs7+3Ts7ozH2S418zNYNZ3rHbpi68iXxg57ekAeMo
c8Nncog1ryB1K7s3BW38BZltcX2ceJrNv5Y33HEf6JwhG8lYyHDeiuSDuShXRi/B
yv/UiI5uR+JmFR7kD4LDtgIB/uaNBCL4SUjIfWb1PrFe9+Y+b9boElnarDUcDifO
RL1BbwiRuLAGKQCpfaw27dV86PxhCIGMj7aIP7xraBCVuSC6tFITY05H4MMZ85RE
5DSdDHcrKIcKm4bv3teLj3G4V6TUjJf7JW8ubhNQiicbN4isqumny8ZCWKLu1zRC
U9CQF0oRvTLGTwIYOI6UD8+dhZ6vL2ckjIDKoSZ6vss6cwNTjSkHnR1wAnstqL8T
YVOJsGj1Dth64AFpNjMRsoHEVSaU6m64QuANNBchynqOSpB9+F1EsJjpSwMk4jkU
ejkRf7b73HRus6I9AwuQeZzubUQ8gqqs5t6xxM3+YMjtTlRa5ymvfaGJFA8MeKNA
8PpuiZOmWC6PKA4L7Cd3d6lKm7YZhGQBtqGVuJB83xzomDOoNQBPDLhHF8V8zXil
4avghhLlZNwWoKFcNlc46MGK7KBSu5fqrMN0hqhz+TkUKou3eTgXLAXiXReXJ/6L
YzVvRl8bzJNkeTRar6Zp
=9Y7p
-----END PGP SIGNATURE-----