Subject: Re: [Cfrg] [TLS] A la carte handshake negotiation

From: Michael Hamburg <[email-masked]>
Date: Thu, 23 Jul 2015 13:15:14 -0700

> On Jul 22, 2015, at 7:50 PM, Peter Gutmann <[email-masked] <mailto:[email-masked]>> wrote:
> 
> Kyle Rose <[email-masked] <mailto:[email-masked]>> writes:
> 
>> In that case, we should dispense with any larger key sizes and recommend
>> exactly one per algorithm, and vary only on algorithm. Adopting this would
>> simplify things even further by reducing the cipher set list by an order of
>> magnitude.
> 
> Yup.
> 
>> Sadly, I'm guessing there are numerological requirements in various standards
>> and regulations that make it necessary to keep both AES-128 and AES-256
>> around, for example. There are also a ton of existing 2048-bit RSA keys that
>> aren't going anywhere for a while.
> 
> You could just say "anything over 1536 bits, 1536 or 2048 recommended", which
> would deal with both.
> 
>> I'm also skeptical of statements like "Using any known technology it's
>> unlikely that humans can ever get beyond about 2^^100 operations", because
>> that's true exactly up until it isn't.
> 
> Right, but if you're going to use that argument then AES is breakable until it
> isn't, you can't find SHA-256 collisions until you can, quantum crypto can be
> broken by whoever you're afraid of, and so on.

But I think that’s his point.  That’s why SHA-512 and AES-256 exist, not to mention
ChaCha and Camellia and GOST, and why several groups are looking at
post-quantum signatures and key exchange.  That’s why some users will want to
use them, and why it’s reasonable for TLS to support them in cipher suites.
Requiring the minimal secure crypto will be seen as dangerous, especially because 
computers are pretty fast and using a stronger cipher doesn’t cost very much.

Personally, I don’t think matching exact cipher strength levels always makes sense.
Going from AES-128 to AES-256 gives a 40% slowdown in the fastest, most
hardware-accelerated part of the system, but going from the matching RSA-3072
to RSA-15360 gives probably a 60x slowdown in the slowest part.  But having
ciphersuites which are balanced in terms of “do extra effort, get an extra hedge
against a breakthrough” makes sense.

> One thing we've become pretty good at doing is taking current progress on
> breaking crypto and mapping out what'll happen in the future, to the point
> where there have been zero sudden breaks of properly-designed algorithms (DES,
> AES, IDEA, SHA, RSA, DH, and so on), ever.  In every case we've been able to
> see, from a long way off, what's in store.

I don’t agree.  While MD5 and small-characteristic discrete log were considered
somewhat sketchy before they were broken, they were both considered acceptable
right up until they were broken wide open.

Consider discrete log in particular.  Numbers below are from
https://www1.lip6.fr/~pierrot/papers/DLogSurvey.pdf <https://www1.lip6.fr/~pierrot/papers/DLogSurvey.pdf>

As of 2011, the record for discrete logs in prime fields was 530 bits, set in 2007
using 20k CPU hours.  For tiny-char it was 613 bits, set in 2005 using 26k CPU
hours.  For medium characteristic it was 556 bits, set in 2005 with only 200 CPU
hours.  For comparison, RSA-768 was factored in 2009, but using ~17M core
hours.  No major progress had been made on tiny-characteristic since the
function field sieve in 1999, though Joux had made advances for small- and
medium-characteristic in 2006.  Tiny-characteristic discrete log systems are
considered questionable for general use, but acceptable for pairings, and are
about as popular as BN curves.

As of 2014, the attacks on tiny-char are quasipolynomial time, and 9234-bit
discrete log has been broken.  Perhaps more relevantly, a 1303-bit pairing
group (3^(6*137)) was broken in sub-1k CPU hours.

Or perhaps algorithms which got suddenly broken were not “properly designed”
in the first place.  For the record, do you think binary elliptic curves have
acceptable security properties?  Would it be “proper design” to use them today,
eg in a hardware product where the acceleration matters?  Are the attacks on
them more or less realistic than XSL attacks on AES?  If binary curves are not
acceptable, then what about endomorphisms, or hyperelliptic curves / Kummer
surfaces?  Hindsight is 20/20.

> And to see what's in store for PKCs, you can't use the computers used by
> mathematicians/numerologists, which all have infinite amounts of
> zero-cycle-time memory, but the ones that actually exist in the real world.
> For a 1024-bit RSA key that's around 40 terabytes of memory for the final
> step, and a 1280-bit key would require roughly a petabyte of RAM, all in a
> single machine or a single-machine equivalent (a standard distributed cluster
> won't work because of interconnect latency problems).  So you'd need to
> dedicate the entire Tianhe-2 to breaking a single 1280-bit key (I don't know
> how its memory architecture will affect performance, I just chose the world's
> most powerful supercomputer because that happens to be barely enough to attack
> a 1280-bit key, so I'm not sure how many years of time you'd need).

And then a small improvement to factorization and a small improvement to computer
design, and we’ll realize that actually you can break a million such keys in a batch in
6 months.  Then we’ll wonder how long China and NSA and whoever else have
known this, and how long they’ve been exploiting it.

> Or you could just backdoor the server, which is what'll actually happen to
> anyone who wants to get in.  Heck, just the interest on the power bill for the
> Tianhe-2 (if you assume the computer itself comes for free) would be enough to
> bribe most of the maintenance staff to plug in a trojan USB key for a minute
> or two while they're cleaning.

See LOGJAM, where the authors conclude that it’s reasonable to believe that NSA
can use precomputation to break 1024-bit finite field discrete log, and that they may
have been doing it for years.  Instead of or in addition to compromising servers and
backdooring RNGs.

Or maybe they haven’t, who knows?  But some conservatism is warranted here.

Cheers,
— Mike

> And if you really are concerned about China secretly building a second
> Tianhe-2 and using it to attack your mail server, just change your key once a
> year and you're OK.
> 
> Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 24 Jul 2015 09:56:27 +0000

Michael Hamburg <[email-masked]> writes:

>While MD5 and small-characteristic discrete log were considered somewhat
>sketchy before they were broken, they were both considered acceptable right
>up until they were broken wide open.

Uhh, that's wrong on both counts, MD5 has been known to be problematic since
Dobbertin's work twenty years ago (so it's only "considered acceptable" if
you've been living in a cave for at least the last fifteen years), and it's
not "broken wide open" even now, you can generate collisions under certain
circumstances, but not if some basic protective measures like randomisation
are used, and can't generate preimages at all.  It's been a slow (nearly) 25-
year slide, not a sudden break.

>small-characteristic discrete log

... as used in which (mainstream, standardised) security protocol?

>That’s why some users will want to use them, and why it’s reasonable for TLS
>to support them in cipher suites.

So far the only thing that backup cipher suites (or whatever you want to call
them, the also-rans that accompany the default cipher suite that's first on
the list) has given us is security vulnerabilities.  Lots and lots of security
vulnerabilities.  In over two decades of SSL and TLS use, we've never actually
needed them.

Peter.

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 24 Jul 2015 10:18:36 -0700

> On Jul 24, 2015, at 2:56 AM, Peter Gutmann <[email-masked]> wrote:
> 
> Michael Hamburg <[email-masked] <mailto:[email-masked]>> writes:
> 

I agree that it was considered concerning and that SHA-1 was recommended.  This was as much due to its size as to its cryptanalytic flaws.  There was a project to generate one with 2^64 work, right before a practical cryptanalytic attack was announced.

> ... as used in which (mainstream, standardised) security protocol?

I thought we were talking about algorithms, not protocols?  Anyway, this is getting pretty close to a “no true Scotsman” argument.  MD5 and RC4 were in widely deployed protocols that weren’t “properly designed”, and tiny-char discrete log was in systems which claimed to be production-quality and were considered properly designed, but weren’t widely deployed.

> vulnerabilities.  In over two decades of SSL and TLS use, we've never actually

The first on which list?  I’m seeing ECDHE-RSA-AES256-GCM-SHA384 at the top on my laptop, which seems like not a bad choice if the RSA and ECDHE are big enough.

I agree that cipher suite proliferation is a problem.  I’m just arguing that there should be a conservative cipher suite to accompany the “RSA-1536 should be enough for anyone” default.

— Mike