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

From: Gregory Maxwell <[email-masked]>
Date: Thu, 17 Oct 2013 14:09:06 -0700

With the recent concerns about the integrity of the NIST specified ECC
curves many protocols are looking to non-NIST alternatives for their
EC crypto needs.

Is anyone considering using Curve3617 in OpenPGP? The case for the
design approach is made at http://safecurves.cr.yp.to/ and is
generally pretty compelling.

[Arguably for OpenPGP use it would be nice to see a ~1024 bit curve
produced with the same engineering methodology: for most uses of
OpenPGP performance is not a major limitation (1024 bit ECC could be
adequately fast on an embedded device) nor are 128 bytes more of
signature data, but long term security is... Index calculus results in
security that scales similar to integer factoring, so there is an
argument that even unknown breakthroughs that render common ECC
insecure would simply be reducing it to RSA like security.]

Along those lines, has there been any proposal for supporting a merkle
signature scheme for long term master identity keys?  For a master
identity key that delegates signing a finite (but potentially large)
amount of reuse is not problematic at all. Relatively large signatures
are not problematic in many applications, and these signatures would
have nicely orthogonal security to discrete log based cryptosystems
and are strong against quantum computers.  (And regardless how much of
a threat you personally consider quantum computers on the time scales
you consider relevant, FUD related to them "oh but the XYZ has QC's
see this dwave hype, no reason to use crypto at all" is harmful to the
public.)

---

From: Jon Callas <[email-masked]>
Date: Thu, 17 Oct 2013 18:37:58 -0700

> generally pretty compelling.

Andrey would know best, but my reading of RFC 6637 leads me to think that all you need is an OID for the curve and you're golden.

We're going to be using Curve3617 for Silent Circle as a replacement for P-384.

> insecure would simply be reducing it to RSA like security.]

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.

	Jon

---

From: Gregory Maxwell <[email-masked]>
Date: Fri, 18 Oct 2013 00:20:38 -0700

> 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.

---

From: Werner Koch <[email-masked]>
Date: Fri, 18 Oct 2013 09:24:56 +0200

> Andrey would know best, but my reading of RFC 6637 leads me to think that all you need is an OID for the curve and you're golden.

Right.  I plan to make Ed25519 the default in GnuPG - 256 bit ECC is a
good replacement for the current defaults - eventually other curves will
be added as well.  One drawback with rfc6637 is that we can't yet use
compressed points.  This is a minor drawback because introducing this
latter would still allow to keep on using the same keys.

Salam-Shalom,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

---

From: Gregory Maxwell <[email-masked]>
Date: Fri, 18 Oct 2013 00:57:25 -0700

On Fri, Oct 18, 2013 at 12:24 AM, Werner Koch <[email-masked]> wrote:
> This is a minor drawback because introducing this

Beyond the obvious doubling the size of the keys for no increase in
security (and that implementers often make mistakes and do things like
fail to validate the points, which I guess isn't an issue for ed25519
as it is twist secure), it would make it gratuitously incompatible all
the existing (esp fast constant time code) implementations which work
on the X coordinate alone.

Thats unfortunate, if not the end of the world.

---

From: Werner Koch <[email-masked]>
Date: Fri, 18 Oct 2013 10:29:22 +0200

> on the X coordinate alone.

Nope.  First, there is no released OpenPGP implementation with ECC yet.
Second, there is no incompatibiliy because it is still the same point
and actually it is faster to use because there is no need for
uncompressing.  Note also that compressing is an old technique which is
is simply not used because in the Weierstrass form it is patented (till
next year).

Salam-Shalom,

   Werner

---

From: Gregory Maxwell <[email-masked]>
Date: Fri, 18 Oct 2013 01:42:11 -0700

On Fri, Oct 18, 2013 at 1:29 AM, Werner Koch <[email-masked]> wrote:
> uncompressing.

Not so at least for ECDH, e.g. the implementation in curve25519 uses a
multiplier that really does work on the X coordinate alone. For other
curves (which are not twist secure), generally time spent
uncompressing is not to much slower than the sqrt needed to check that
the point is on the curve.

---

From: ianG <[email-masked]>
Date: Fri, 18 Oct 2013 11:50:11 +0300

On 18/10/13 10:20 AM, Gregory Maxwell wrote:

> ....   In these applications, when

Excellent and complete argumentation.  I don't necessarily agree with 
the statements, but I applaud the full presentation!

iang

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 18 Oct 2013 10:07:23 -0700

> Nope.  First, there is no released OpenPGP implementation with ECC yet.

One could google for "pgp command line with ecc support" and see a few 
hits. I clearly recall working on one product that was released.

> is simply not used because in the Weierstrass form it is patented (till

http://tools.ietf.org/html/draft-jivsov-ecc-compact-00 is based on a 
year 1986 method. You need an unambiguous definition for the DSA (not ECDH).

---

From: Werner Koch <[email-masked]>
Date: Mon, 21 Oct 2013 13:14:14 +0200

> hits. I clearly recall working on one product that was released.

I would not count beta versions as "released" ;-). In any case, it does
not matter because the used curve does not matter RFC-wise.

Salam-Shalom,

   Werner