Re: [openpgp] Curve3617 in OpenPGP? Beyond rfc6637.

Gregory Maxwell <gmaxwell@gmail.com> Fri, 18 October 2013 07:20 UTC

Return-Path: <gmaxwell@gmail.com>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id AC8D621F958A for <openpgp@ietfa.amsl.com>; Fri, 18 Oct 2013 00:20:47 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Level:
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, NO_RELAYS=-0.001]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id AbqlXg2WrWrK for <openpgp@ietfa.amsl.com>; Fri, 18 Oct 2013 00:20:46 -0700 (PDT)
Received: from mail-lb0-x22b.google.com (mail-lb0-x22b.google.com [IPv6:2a00:1450:4010:c04::22b]) by ietfa.amsl.com (Postfix) with ESMTP id 7C63721F83E2 for <openpgp@ietf.org>; Fri, 18 Oct 2013 00:20:43 -0700 (PDT)
Received: by mail-lb0-f171.google.com with SMTP id x18so1302423lbi.2 for <openpgp@ietf.org>; Fri, 18 Oct 2013 00:20:38 -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 :content-type:content-transfer-encoding; bh=wPgHDAWaqiqa0l3LxPHxi5QxDoIiMk/DN/hMFWykyC8=; b=N2FG0KJ2bXYG0RHjSHmHbCTYspaeyXCJaklQ2ljraLg2tP1n/RmOW3hye4peC0Y1NA 9dK/gpvSOm7ElLfeFGeUVL0wOravln4lb9gRCRHuACTAWL1mxrSCEuDA5V61TQGJ9Gl+ MZ3S70jZ2eoh90V3fCyrpAsfvyKjLtMaYRckfPpX5QJz1LUY9yfCocqO09+pQd5MtJcm 2oNMcKLotEBBEnPmMyGXvTeIUZJSCKMWGfdig/ghxOHNJT6VdW+xUvGbFi+JXbbuYVG0 ugMZ38ng83TMrDuP10kziTNJpjWmDwFu2kFAAJVwPb9/ZA6l+Z2wnkxVVg70cUpU6hzq oMZg==
MIME-Version: 1.0
X-Received: by 10.112.14.3 with SMTP id l3mr609538lbc.27.1382080838458; Fri, 18 Oct 2013 00:20:38 -0700 (PDT)
Received: by 10.112.89.72 with HTTP; Fri, 18 Oct 2013 00:20:38 -0700 (PDT)
In-Reply-To: <CBE39208-C436-4145-A645-10380145F200@callas.org>
References: <CAAS2fgRG2AbZsz_4aF33Pd167M4-6=-73WAAgxTAjLMdoGNLeQ@mail.gmail.com> <CBE39208-C436-4145-A645-10380145F200@callas.org>
Date: Fri, 18 Oct 2013 00:20:38 -0700
Message-ID: <CAAS2fgRZCS9y9LOG62fG5NOyz_DA8bek5L-rWMrhXrAt4EKLUA@mail.gmail.com>
From: Gregory Maxwell <gmaxwell@gmail.com>
To: openpgp@ietf.org
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [openpgp] Curve3617 in OpenPGP? Beyond rfc6637.
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>, <mailto:openpgp-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/openpgp>
List-Post: <mailto:openpgp@ietf.org>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>, <mailto:openpgp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 18 Oct 2013 07:20:47 -0000

Jon Callas <jon at callas.org> wrote:
> Why ever would you want a 1Kbit curve? Sure, arguably, but please make the argument. As it is, Curve3617 is more than one really needs. I'm genuinely interested.

The fastest method for solving the discrete log problem in finite
fields is index calculus. It is not known to be applicable to the
elliptic curves we use for cryptography (or obviously we wouldn't be
using them), modifications of the technique are applicable to
super-singular curves / extension fields and where applicable they
have sub-exponential scaling similar to the number field sieve for
factoring. While it's not believed that there can exist a
straightforward adaptation currently-believed strong curves, if one
were to be discovered it would render any of the common sizes
practically insecure.

It would be terrible indeed to migrate to ECC only to end up with keys
no more secure than 512 bit RSA.

But by comparison to performance in other groups a of size to around
1024 bits but leave the crypto system secure in practice even if index
calculus could be directly applied.

(Sorry for delay in responding, but I spent a little while googling
around to see if I was the only person thinking like this. I found a
number of things, the most amusing an old post of Bruce Schneier's:
"Realize, though, that someday -- next year, in ten years, in a
century -- someone may figure out how to define smoothness, or
something even more useful, in elliptic curves. If that happens, you
will have to use the same key lengths as you would with conventional
discrete logarithm algorithms, and there will be no reason to ever use
elliptic curves. "
https://www.schneier.com/crypto-gram-9911.html#EllipticCurvePublic-KeyCryptography
)

For many personal communications applications involving end to end
encryption— though certainly not all— speed is only an issue if you're
talking about hundreds of milliseconds, bandwidth is an issue only if
you're talking about tens of kilobytes.  In these applications, when
we're talking about long term security for _unspecified applications_
(meaning, we should assume the cryptosystem is life critical and the
attacker is state level, because we've not specified an application
that excludes these parameters) then it is seem obviously prudent to
use more of the available speed and bandwidth budget to increase
security.

The next question for that should be _how_ to go about increasing the
security.  One answer would be to pair up an orthogonal asymmetric
cryptosystem, but all the abelian hidden subgroup problems seem to
share a common fate— improvements in discrete log tend to result in
factoring improvements.  For signatures merkle signatures might fit,
but for encryption the asymmetric cryptosystems which appear unrelated
all have overheads which probably do take us outside of the available
budget.

But a larger curve would not. Nor would it impose a very large
implementation or design complexity overhead. Nor would it be so
expensive that it would be unduly burdensome to users who don't want
it when they are forced to interact with it (as 250kbyte McEliece +
ECDH public key would)   And it may well provide additional security
against currently unknown risks.

As a design principle, if the user has bandwidth and cpu to spare— it
would be quite sad to see his security fail simply because the
software didn't care to offer a maximally conservative option.

Failing to have a solid "I don't care about the speed/size, crank my
security to 11" option also creates a great market opportunity for
non-standard cryptography which turns out to be snake-oil "crank it up
to 11 (mod 10)", and increases the risk that users fail to use
encryption at all because they are too easily convinced by FUD that
the cryptography isn't strong.