Subject: [Cfrg] Security consequences of E-521

From: Watson Ladd <[email-masked]>
Date: Thu, 12 Feb 2015 22:19:04 -0800

Dear all,

It seems many people are suggesting that P-384, despite widespread
use, is too small, and 2^448-2^224-1 is too-funny looking. So, we
should use 2^521-1 instead. But what they haven't considered are the
actual consequences of this choice for people who actually need to
ensure that busy websites stay up and serve users, without spending a
fortune on servers, and the actual security gains.

It's clear that in the TLS context, ECDH keys have a longer lifetime
than the keys used to secure the PKI. Recovering a key that can be
used to sign new certificates is bad, but it's pointless if we've
already migrated the root certificates in response to predicted
weaknesses. This is why 512-RSA doesn't threaten the security of TLS
connections today, even if there were roots that used it. By contrast,
past data sent over a channel encrypted with 512-RSA could be stored,
and today decrypted.

Right now the proposal appears to be a highly efficient Curve25519
ECDHE exchange, with roots and possibly intermediate certificates
using a ludicrously oversized E-521. This will be adequate security
for almost all data. But the root certificate doesn't need to be so
large.

However, what if we think we have data that is more sensitive? Then a
choice to only recommend E-521 leads to a very serious 4x reduction in
the number of key exchanges that a given set of servers can perform,
and thus is less likely to be adopted then a smaller, still secure
curve. In the event of a supposed cryptanalytic breakthrough, this is
likely to slow migration.

The performance impact is even worse than this. As TLS 1.3 is
currently envisioned, every server needs to carry out not just one,
but two exponentiations per client due to the use of online
signatures. It's likely that leaf certificates thus use the smaller
key sizes, thus making optimizations based on batching dependent on
roots.

Clients are already having difficulty verifying three signatures over
P384. Why make it even harder? Note that if the leaf certificate uses
the same signature scheme as the root, and all intermediates, and that
scheme enables batchable verification, much higher performance is
possible.

It's undisputed that AES-256 is much easier to attack then E-521.
Adding bits to the prime beyond the level where AES-256 becomes easier
to attack is pointless: it depends on assuming cryptanalytic
breakthroughs which are extremely unlikely.

Proponents of E-521 for PKIX roots: is there any reason why the
currently used P-384 is insufficiently secure? Do you think that when
the NSA recommends P-384 for Top Secret data, they are being
insufficiently paranoid? And why should easily replaceable
certificates be regarded as less important than the data they
supposedly protect?

Sincerely,
Watson Ladd

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 13 Feb 2015 20:06:52 -0800

> past data sent over a channel encrypted with 512-RSA could be stored,

What about a government/ISP that wants to decrypt all the traffic of its
citizens/users, including for server certs issued outside the country?

If one recovers a private key of an intermediate CA that issues server
certs, or forges the signature over that or higher level cert in the chain,
from that point he can be an active man in the middle without the need to
break ECDHE.

This is a more efficient attack without the need to store ciphertext. CA
certificates have longer lifetime and represent a single target.

> key sizes, thus making optimizations based on batching dependent on

It makes sense that the end-entity cert uses the same or a bit weaker curve
as ECDHE, but there is benefit to have at least as strong CA certs.

One note is that ECDHE in TLS, being negotiated online, is relatively easy
to upgrade. In particular, the mechanism is already there to offer weaker
version (for compatibility) along with the current stronger version.
Compare this with SMIME encryption: there is no infrastructure to have two
encryption keys to the same effect (but OpenPGP supports multiple subkeys).
Same for CA certs.

> scheme enables batchable verification, much higher performance is

In practice the validity of CA certs can be cached, but it looks like the
server cert issuing CA should be strong and the client will incur the cost
to validate the signature by that (last) issuing CA.

> certificates be regarded as less important than the data they

Top level CA certificates are not as easy to replace. They must be in
hardware. I think we won't see quick changes for these regardless of new
the curve.

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

---

From: Watson Ladd <[email-masked]>
Date: Sat, 14 Feb 2015 11:22:54 -0800

> certificates have longer lifetime and represent a single target.

If you think one discrete logarithm on Curve25519 is feasible today,
you should be against its deployment at all.

CA certificates do not have a longer lifetime: data that is encrypted
with Curve25519 or P256 remains vulnerable to future cryptanalysis
forever, while one cannot attack authentication retroactively: if I
break the key of a certificate retired because of cryptanalytic
advances, it doesn't help. But if I have an encrypted message, future
attacks are still useful to decrypt it.

> as ECDHE, but there is benefit to have at least as strong CA certs.

What is that benefit?

> version (for compatibility) along with the current stronger version. Compare
> this with SMIME encryption: there is no infrastructure to have two

Looking at the certificates in my laptop trust store, I see four
distinct Digicert CA certificates, each with different hash and
signature algorithms. Looking at actual TLS deployments, I see means
provided and used to handle having multiple possible algorithms for
signatures.

> to validate the signature by that (last) issuing CA.

But that's exactly my point: authentication isn't vulnerable to future
cryptanalytic attacks, while encryption is. Meanwhile, the client and
the server pay the cost because the CA wants a big number to show off
to its customers.

> hardware. I think we won't see quick changes for these regardless of new the
> curve.

You'll notice that when Diginotar and Turktrust happened, the
certificates were invalidated within days. If we think that 384 bit
ECC is weaker than expected, we will have ample time for certificates
to expire and ones using other algorithms to be issued. By contrast,
we cannot take back encrypted data and reencrypt it with a more secure
algorithm.

I also don't understand this migration argument. Sure, if we wake up
tomorrow to a new Claus Diem paper introducing an effective
index-calculus for genus 1, we've got a problem: we've got to change
every cert. But the much bigger problem is that all data encrypted
with Curve25519 is now readable by an attacker: that's not fixable.

Sincerely,
Watson Ladd

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

---

From: Kurt Roeckx <[email-masked]>
Date: Sun, 15 Feb 2015 23:31:10 +0100

> attacks are still useful to decrypt it.

One of the things I've been wondering about is wether we need to
same strength for authentication, integrity and confidentiality.
I think that in the case of TLS both authentication and integrity
don't need to be as strong as the confidentiality.

If you look at the performance as seen by the server, I would
argue that the strenght of the CA certificates doesn't matter
much, it's the EE certificate's I would care about since that's
the only key used by the server.  If the CAs want to use a
stronger key for the CA certificates I think it has little impact
on the server.

I would like to point out that according to the CA/Browser forum's
baseline requirements the lifetime of an EE certificate is maximum
39 months with an exception to 60 months (5 years).  I currently
see no need to have EE certificates that are stronger than then
128 bit level.

Looking at the validity periods of the root CAs the most seem to
be in the 20-30 year range.  So I can understand that they might
think they need something stronger if it needs to be valid that
long and still expect to use it then.  But I have a feeling that
in 30 years 128 bit would still be considered strong enough for
authentication but that for confidentiality the 128 bit might get
close to what we think that at that time is sufficient.

Kurt

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 15 Feb 2015 15:22:32 -0800

> attacks are still useful to decrypt it.

I have no problem with your reasoning about retroactively breaking the 
ECDH. A couple of notes, though.

The strength of ECDH employed should depend on the future value of the 
information it protects. Curve25519 is too strong to encrypt stock 
market trading information. National secrets get declassified. There is 
almost always an expiration when you are too late to break the ECDH.

The need to store all the traffic and then break each connection appears 
as fairly expensive, which means that there may be cheaper methods to 
collect this information (e.g. from the corresponding servers).

>> as ECDHE, but there is benefit to have at least as strong CA certs.

Let's say, as you advocate, we have RSA 512 bit CA certs in the chain 
and we worry about government monitoring its citizens.

That delayed decryption on ECDH works the best when the attacker knows 
the two peers. If the attacker doesn't know these peers, he is forced to 
store all the traffic between the members of a large group (e.g. between 
citizens / servers), and this is inefficient.

There is an alternative for an attacker: break one RSA 512 cert, install 
a proxy in front of relevant servers, and from this point monitor the 
communication in clear.

The attacker needs to store all encrypted traffic until he broke the 
chain. After this, the attacker trades off massive storage and 
per-connection computations with a single computation.

> we cannot take back encrypted data and reencrypt it with a more secure

An upgrade to a new curve will be slower than regeneration of a cert for 
the same curve.

> with Curve25519 is now readable by an attacker: that's not fixable.

I don't know if there is a good solution for confidentiality in regard 
to future decryption. Most information doesn't need stronger than 
Curve25519 and it would be bad to have performance penalty for that 
plaintext.

There is a need for "paranoid" security too.

There may be a place for intermediate strength choice, but this will 
make people wanting fewer options unhappy.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 15 Feb 2015 15:38:42 -0800

> The strength of ECDH employed should depend on the future value of the
information it protects. Curve25519 is too strong to encrypt stock market
trading information. National secrets get declassified. There is almost
always an expiration when you are too late to break the ECDH.
> Let's say, as you advocate, we have RSA 512 bit CA certs in the chain and
we worry about government monitoring its citizens.

Did I ever advocate that? No. Your example only works if we believe Curve
25519 is breakable today, in which case we shouldn't use it at all.

Notice that the NSA is spending billions of dollars on exactly this.

>>> version (for compatibility) along with the current stronger version.
Compare
the same curve.

Yes, but we'll have much more of a warning.

> I don't know if there is a good solution for confidentiality in regard to
future decryption. Most information doesn't need stronger than Curve25519
and it would be bad to have performance penalty for that plaintext.
> There is a need for "paranoid" security too.

Why not a 1024 bit ECC prime then?

>
> There may be a place for intermediate strength choice, but this will make
people wanting fewer options unhappy.

As Ilari pointed out 384 is already strong enough. This argument assumes
cryptanalysis that breaks 384 effectively but not 521. This is at odds with
actual practice today, and the many decades of analysis of ECC security.

The performance impact of certificates is much larger then that of ECDH.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 15 Feb 2015 19:04:19 -0800

> stronger key for the CA certificates I think it has little impact

The server is only half the equation. Clients have to verify that all
signatures presented in the chain are valid, and there are at least
two (root and intermediate) that the server doesn't control. Clients
are likely to be less powerful than servers. Already P384 is a real
pain. Better choices of prime can mitigate this, but it's clear that
2^379-19 or 2^389-21 are much better than 2^521-1 for speed. (There is
also the question of ECDSA vs a batchable scheme, which can also
change the tradeoff).

> close to what we think that at that time is sufficient.

Let's assume that an 80 bit computation is feasible today. Then
Moore's law tells us that the same cost can pay for a computation with
two more bits every three years. Then 45*3/2=69. So Curve25519 will
need to be retired in 70 years. By contrast P384 is good for 168
years. Is a century and a half enough time?

Of course, someone could invent a general purpose quantum computer
before that time, and indeed is likely to. But E-521 isn't
significantly stronger with regards to Shor's algorithm.

Sincerely,
Watson Ladd

---

From: Kurt Roeckx <[email-masked]>
Date: Mon, 16 Feb 2015 19:07:28 +0100

> also the question of ECDSA vs a batchable scheme, which can also

I was very explicit in talking about the server side, since the
client side is more complicated.  They might need to validate
alternative chains.  They should do OCSP/CRL tests.  They
might want to do DANE, and so on.  

I've seen people claim that on low end devices it might be slow.
But I would think that even the low end of what users buy now to
connect to a server is more than fast enough.

Please note that I'm not advocating the use of stronger
certificates, I'm not sure about the arguments against it.

> years. Is a century and a half enough time?

There is what is feasible today and what is the recommended
strenght.  I think 80 bit computations is feasible today, the
question is just how long it takes today.  As far as I know the
current recommendation is to use at least 112 bit, so 32 bit more.
That would also mean that in 30 years from now they both got 20
bit more and so 100 bit doable and 132 recommended as minimum.

The question is really is how long is enough.  And I think for
most of the things we do we don't actually care about it that
long.

Kurt