Subject: [Cfrg] Backup ciphersuites in the event of an ECCpocalypse

From: Tony Arcieri <[email-masked]>
Date: Wed, 3 Jun 2015 16:27:56 -0700

This question was broached by people on the TLS mailing list who are
apparently already running off and implementing things. I think it actually
belongs here.

Some questions:

Should there be backup algorithms in the event of some revolutionary
innovation that breaks all known curves or all curves presently in use?

If both key exchange and signatures are moving to ECC, what should the
backups be, provided we think backups are a good idea?

My concern is people are already arguing that such backups are necessary
and trying to ship solutions without actually considering the practical
implications of an ECCpocalypse.

Some questions I expect might come up:

If ECC has failed, did FFDHE fail too?

How about RSA?

What do we predict will be assured working in 10 years time?

This is all speculation in which I don't particularly wish to indulge, but
if people feel like this sort of thing is necessary, I think the algorithm
selection should be driven by cryptographers, not people concerned with
RHEL5 errata.

-- 
Tony Arcieri

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 4 Jun 2015 00:33:10 +0000

> Should there be backup algorithms in the event of some revolutionary innovation that breaks all known curves or all curves presently in use?

No.  It is trying to solve a worry about the future with a hope.

How do you know a backup is any better?  And, if it is, why is it a backup and not the primary choice?

In the event of an ECCpocalypse, we'll fall back to EDH and RSA until the next new thing emerges.

	/r$

---

From: Adam Langley <[email-masked]>
Date: Wed, 3 Jun 2015 17:36:55 -0700

> innovation that breaks all known curves or all curves presently in use?

http://eprint.iacr.org/2014/599.pdf

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 3 Jun 2015 18:28:44 -0700

> http://eprint.iacr.org/2014/599.pdf

I completely agree that this is the direction we should be headed in...

-- 
Tony Arcieri

---

From: Tom Ritter <[email-masked]>
Date: Wed, 3 Jun 2015 20:38:43 -0500

> I completely agree that this is the direction we should be headed in...

Ditto.  I will also make the plug that if someone wants to work on a
new PQ KEX algorithm, and have a strong chance of it getting deployed
in a real system, come over and work on Tor.  We'd actually like
researchers to start designing just that, with an eye to implementing
and deploying it in the next several years.

-tom

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 3 Jun 2015 23:08:11 -0400

> http://eprint.iacr.org/2014/599.pdf

This is all just a plot to make me spend my 80s learning the math I gave up
on in my 20s when I decided recourse to category theory to make formal
methods tractable was trying way too hard.

I agree that if we do anything post ECC we should be looking at the lattice
stuff. But it does seem likely that they resist known methods of applying
QM techniques rather than being QM resistant.

Seems to me that if folk worry about ECC being broken they should be
trusting their keys to symmetric techniques.

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 3 Jun 2015 21:08:29 -0700

> In the event of an ECCpocalypse, we'll fall back to EDH and RSA until the

The proposed backup on the TLS list is FFDHE. While that solves the key
exchange problem, is that useful if we're using ECC certs?

-- 
Tony Arcieri

---

From: Yoav Nir <[email-masked]>
Date: Thu, 4 Jun 2015 08:11:40 +0300

Rolling out RSA certificates is something that CAs have some experience with.

> On Jun 4, 2015, at 7:08 AM, Tony Arcieri <[email-masked]> wrote:
> 
> On Wed, Jun 3, 2015 at 5:33 PM, Salz, Rich <[email-masked] <mailto:[email-masked]>> wrote:
> The proposed backup on the TLS list is FFDHE. While that solves the key exchange problem, is that useful if we're using ECC certs?
> 
> -- 
> Tony Arcieri
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Johannes Merkle <[email-masked]>
Date: Tue, 16 Jun 2015 17:15:04 +0200

> No.  It is trying to solve a worry about the future with a hope.

We have the scenario of someone building a quantum computer. In this case, not only ECC is broken but RSA and FFDH, too.
Although I can't imagine that this will happen soon, it's better to be prepared.

> How do you know a backup is any better?  And, if it is, why is it a backup and not the primary choice?

There are many schemes believed to be resistant to quantum computers, including hash-based signatures where the security
can be based on any secure hash function.
https://datatracker.ietf.org/doc/draft-huelsing-cfrg-hash-sig-xmss/
https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/

Of course, almost all Post-quantum schemes have very large keys making them not the primary choice today.

-- 
Johannes

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 16 Jun 2015 15:22:39 +0000

> We have the scenario of someone building a quantum computer. In this case,
> not only ECC is broken but RSA and FFDH, too.

Trying to build seems more accurate.

> Although I can't imagine that this will happen soon, it's better to be prepared.

If they succeed then everything's broken.

We clearly have enough problems trying to get good solid crypto deployed now.  We should spend our (meager, finite) efforts there.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 16 Jun 2015 15:32:47 +0000

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Johannes Merkle
> Sent: Tuesday, June 16, 2015 11:15 AM
> To: Salz, Rich; Tony Arcieri; [email-masked]
> Subject: Re: [Cfrg] Backup ciphersuites in the event of an ECCpocalypse
> 
> We have the scenario of someone building a quantum computer. In this
> case, not only ECC is broken but RSA and FFDH, too.
> There are many schemes believed to be resistant to quantum computers,
> including hash-based signatures where the security can be based on any
> secure hash function.

Minor correction: hash based signatures (such as the Huelsing and McGrew proposals above) have large signatures; the McGrew proposal has quite small public keys, and the Huelsing has reasonable sized ones.

---

From: Kurt Roeckx <[email-masked]>
Date: Fri, 19 Jun 2015 00:50:44 +0200

> backups be, provided we think backups are a good idea?

I think there are various people who would like to keep the
communication confidential for a long time.  So I think they would
be most interested in having a key exchange (and encryption) that
is likely to survive a long time.  I think the key exchange is the
most likely weak point.  So I think there are people that don't
look it as a backup but want to already start using it.

The paper Adam pointed to at least looks interesting for those
people, but I'm not sure how ready that is.  I have a feeling it
still requires more research.

But I think that the people who (think that they) need it is such
a minority and that we have more important things to do that it
currently shouldn't be a priority for us to look at it.

I'm wondering if there are estimates for how long things like RSA,
DDDHE, ECDHE and so on will still be usable.

Kurt