Subject: [Cfrg] Summary

From: Kurt Roeckx <[email-masked]>
Date: Thu, 1 Jan 2015 15:49:26 +0100

Hi,

I'm new to this list and I've been reading the archive.  It's all
very unclear to me on what is really going on.  Could someone
please make a summary?  It should probably include:
- What are the things being worked on?  I understand that at least
  part is recommending things for use in TLS, but I guess there
  are also other things being worked on.
- What are the various proposals?  The IETF datatracker doesn't
  seem to known all proposals, and I think there are proposals
  that just don't have a document yet.
- Is there some document with requirements, and maybe a comparison
  of how the proposals meet the requirements?

Kurt

---

From: Watson Ladd <[email-masked]>
Date: Thu, 1 Jan 2015 10:50:49 -0500

>   are also other things being worked on.

The curves issue is really the big one, and the drastically overdue
one. I would suggest not trying to follow the discussion through the
archive.

>   that just don't have a document yet.

Good question: the answer is that at the 255 bit level, for ECDH the
current proposals are both Curve25519. But one uses the same basepoint
as existing code, and the other doesn't. This difference doesn't
affect security in any way. It's the only difference.

Above 255 bits, life gets more interesting. Assuming we want to use
X-coordinate Montgomery (sorry Mike) for ECDH and compressed Edwards
for sigs, we've got 3 or 4 different proposals for around 380, and 1
for 521.

-For 521 it's E521 as described on safecurves.cr.yp.to, the prime being 2^521-1
-2^389-21: I've not calculated the curve yet, but I think Ilari may have
-2^384-317: the NUMS proposal
-2^448-2^224-1: Goldilocks, which has extremely fast arithmetic due to
its shape.

We don't have exactly equivalent numbers for each of these: some
report scalar mult times, others arith times. But what we do know from
the recent batch of measurements is Goldilocks is about as fast as
2^384-17, and 2^389-21 is 8-9% faster than Goldilocks. 2^521-1 is
slower, but much bigger.

For signatures, NUMS proposes what I've called FrankenECDSA, and they
call ECDSA (but isn't really): doing ECDSA but with Edwards curves.
The other proposal is EdDSA, which is a Schnorr signature variant.
NUMS has been open to an additional signature algorithm, and we can
use ECDSA on an isomorphic Weierstrass curve if we really want. There
are some differences over which of the isogenous or isomorphic Edwards
curve to use, with NUMS using an isogenous one and the current Ed25519
an isomorphic one.

This is very different from the original NUMS proposal.

>   of how the proposals meet the requirements?

No. The chairs suggested making one, but then didn't. Part of the
problem is everyone was gaming the requirements to make their own
proposals look better.

Sincerely,
Watson Ladd

>
>
> Kurt
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Tanja Lange <[email-masked]>
Date: Thu, 1 Jan 2015 18:17:37 +0100

Dear Watson,
Thanks for the summary.

> -2^448-2^224-1: Goldilocks, which has extremely fast arithmetic due to
It's complicated to speak of proposals because there isn't a formal
procedure, but we sure would also like to see Curve41417 be considered.
There the prime is 2^414-17.

All the best
	Tanja

---

From: Christoph Anton Mitterer <[email-masked]>
Date: Thu, 01 Jan 2015 18:25:58 +0100

> -For 521 it's E521 as described on safecurves.cr.yp.to, the prime being 2^521-1
Is this going to be followed up?
I'd really love so see a trustworthy curve that has an extremely high
security margin... something like "as long as there are no quantum
computers and no other break through against the base paradigms is found
- no collected computing power will 'ever' be able to break this"...
that could be used in fields like OpenPGP... for long-term key signing,
where performance doesn't matter that much.

Cheers,
Chris.

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 1 Jan 2015 10:01:38 -0800

> On Jan 1, 2015, at 9:25 AM, Christoph Anton Mitterer <[email-masked]> wrote:
> 

Heh.  My alternative point encoding stuff is just an experiment.

> Is this going to be followed up?

Yes, at some point.

> where performance doesn't matter that much.

I agree.  That said, 521 bits is overkill for this.    For a 384-bit prime, you already need an amount of energy equal to many stars’ outputs over their entire lifetimes.  (The Universal Security paper would suggest about a million Sun-like stars, but I don’t recall what temperature they’re assuming the computation will take place at.)  Even in a science-fiction world where humanity is capable of such feats, it will not be worth snuffing stars to break your PGP key.

I consider every prime past 2^256, and certainly every prime past say 2^320, to be a hedge against limited math breakthroughs and not against faster computers.  So it’s really tricky to evaluate where to set the security levels.

Cheers,
— Mike

---

From: Kurt Roeckx <[email-masked]>
Date: Thu, 1 Jan 2015 20:03:32 +0100

> problem is everyone was gaming the requirements to make their own

I think it could be useful to have such a list.  Please note that
not all the requirements are of equal importance, some might be a
MUST and others might be nice to have.  The importance might also
change depending on the use, like TLS, SSH, PGP or X509.  Maybe
we can't agree on those levels, but I think a list a list could
be useful.

Kurt

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 1 Jan 2015 21:55:43 +0200

> -2^448-2^224-1: Goldilocks, which has extremely fast arithmetic due to

http://www.ietf.org/mail-archive/web/cfrg/current/msg05630.html

> curve to use, with NUMS using an isogenous one and the current Ed25519

Then there is ECDSA with Edwards public keys (which could be interpretted
as just another point format):

Replace 'r = x1 mod n'  by  'r = ((Y/X)^2 + (2-4d)/3) mod n' in both
generation and verification and calculate otherwise with Edwards curve.

-Ilari

---

From: Nico Williams <[email-masked]>
Date: Thu, 1 Jan 2015 22:38:28 -0600

> affect security in any way. It's the only difference.

If it's the only difference then picking Curve25519's generator is the
obvious way to go, since changing it would be a gratuitous change and
Curve25519 has seen wide deployment.

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Fri, 2 Jan 2015 10:43:29 -0500

> we can't agree on those levels, but I think a list a list could

We tried that exercise. The problem is that all these protocols use
only two things: signatures and ECDH (okay, ECIES, but that's ECDH+an
AEAD mode), and use separate keys for each. Even if they didn't, this
wouldn't in any way lead to a restriction on which primes to use, and
certainly wouldn't solve the problem of which generator to use.

If you go beyond this to consider implementations, then it turns out
that people actually want to change their implementations and
protocols to take advantage of better cryptography. The original NUMS
proposal had a rather ugly way to stuff the results in existing point
formats, but I don't remember much implementor enthusiasm for doing
that, and TLS 1.3 is being redesigned to accommodate non-Weierstrass
curves. (Why they need to wait for us, I can't remember: perfectly
possible to say "bytes go here") Brainpool wanted to use random primes
because of the details of their smartcards, but their claims that this
was necessary for side-channel security were wrong: extra performance
lets you do more blinding. Certainly now with NUMS being changed to
use the same formats as the alternative proposal, it's a moot point.

Had we dinged the NUMS proposal for the reasons it eventually was
modified, then yes, we would have solved a good deal of our problems.
But the current bikeshedding wasn't the issue we were originally faced
with, which were two or three rather different proposals. There's a
temptation, which I've indulged in, to think of ways we could have
done things differently: most crypto competitions don't have these
issues, for instance. But it's not really helpful with where we stand
now.

Sincerely,
Watson Ladd