Subject: [TLS] Un-deprecating everything TLS 1.2

From: Michael D'Errico <[email-masked]>
Date: Sun, 4 Oct 2020 11:39:07 -0400

Hi,

I'm pretty sure TLS 1.3 is completely broken.  Can we
please stop deprecating things that TLS 1.2 uses and
make them all Recommended again?

Mike

---

From: "Salz, Rich" <[email-masked]>
Date: Sun, 4 Oct 2020 22:02:52 +0000

Mike,

I suggest you make sure you understand the analyses (plural) that have been done.  You are very far in the minority here. Even some folks who say "we don't need these features," but nobody else has said "this is not secure."

This is not to say that the RFC could not be improved, and gain clarity.  There is a 1.3 update RFC likely to be adopted by the WG soon, and if you find things unclear in 8446, opening issues could help.

---

From: Christopher Patton <[email-masked]>
Date: Mon, 5 Oct 2020 07:21:28 -0700

A couple pointers for getting started:

   1. Check out Dowling et al.'s recent analysis. Published a month or so
   ago, it's the most recent proof of security of the full handshake (also
   includes PSK modes): https://eprint.iacr.org/2020/1044
   2. Check out Paterson and van der Merwe's survey of the body of papers
   that helped to shape TLS 1.3. It also overviews the myriad attacks against
   TLS 1.2 and below that catalyzed a more proactive design approach for 1.3:
   https://link.springer.com/chapter/10.1007/978-3-319-49100-4_7

If you're unable to download the second (2.), the same paper appears in a
slightly different form in van der Merwe's PhD thesis.

No analysis is perfect, but so far, 1.3 appears to be far superior to
1.0-1.2.

Best,
Chris P.

---

From: Michael D'Errico <[email-masked]>
Date: Mon, 5 Oct 2020 17:47:39 -0400

> A couple pointers for getting started:

Thank you for providing these links!  I'm going through
the first one now and will note that it does not even
mention the HelloRetryRequest message.  So while I am
confident there has been quite a bit of study of a
ClientHello -> ServerHello handshake, there may not
have been much study of ClientHello1 -> HelloRetryRequest
-> ClientHello2 -> ServerHello handshakes.

I'm especially concerned about the fact that a "stateless"
server does not even remember what the ClientHello1 or
HelloRetryRequest messages were when it receives the
second ClientHello.  Load-balanced data centers seem to
do this based on some of the discussion I've had this
week.

The protocol handles the missing ClientHello1 message by
replacing it with hash-of-ClientHello1, but then you're
supposed to rely on the client to tell you this value in
its ClientHello2.  Even if nothing funny is happening,
how is the (stateless) server supposed to put the
HelloRetryRequest message in the Transcript-Hash?  Where
does it get this value from if it's not also somehow in
the "cookie" (which is how the client reminds the server
of hash-of-ClientHello1)?

And how would you put the HelloRetryRequest message into
the cookie extension when the cookie itself is a part of
the HelloRetryRequest?

Just trying to imagine the code I'd have to write to do
this correctly makes my head spin:

   0)  [disable "TCP Fast Open" so I don't do lots of
       processing without knowing there's a routable
       address associated with the client]

   1)  receive ClientHello1

   2)  generate HelloRetryRequest message without cookie

   3)  package ClientHello1 and HelloRetryRequest-minus-
       cookie into a data structure, encrypt + MAC to
       create a cookie

   4)  insert the cookie into the HelloRetryRequest,
       remembering to update the length of the extensions

   5)  send HelloRetryRequest (with cookie) to client

   6)  erase all memory of what just happened!!!

   7)  receive ClientHello2

   8)  ensure it has a cookie extension (well I should
       at least remember the fact that I already sent a
       HelloRetryRequest and not be completely stateless,
       right?  Otherwise the client may be able to send
       many ClientHelloN's without a cookie)

   9)  check MAC on the cookie and if it's valid, decrypt
       it to determine the contents of ClientHello1 and
       the HelloRetryRequest (without cookie) messages

   10) MAKE SURE ClientHello2 is valid according to what
       was received in ClientHello1 (RFC 8446 has a list
       of things a client is allowed to do; I would want
       to check all of them, so a hash of ClientHello1
       is inadequate in my opinion).  This seems to be a
       necessary thing to do even for stateful servers.

   11) Recreate the actual HelloRetryRequest message
       that was sent to the client by putting the cookie
       into HRR-minus-cookie (in the same place within
       the list of extensions as was already done in step
       4, but since we threw it away, do it again)

   12) Hash the ClientHello1 and add this hash to the
       Transcript-Hash along with the HelloRetryRequest
       message

And I didn't even handle the possibility of replay.........

Can a cryptographer (I don't claim to be one) please take a
few moments to look at the possibilities for a server which
doesn't implement step 8 and allows multiple ClientHello's
without a cookie on the same connection?  Or a server that
doesn't put the entire ClientHello1 into the cookie and can
not check whether ClientHello2 is conformant to the list of
allowed changes?  Or a server that has to maybe "guess" the
content of HelloRetryRequest based on ClientHello2 since it
just sent hash-of-ClientHello1 in the cookie?  And if it
guesses wrong and the Transcript-Hash ends up different
from the client, the peers will not be able to communicate
(denial of service to legitimate clients).

Implementers -- how do you put a HelloRetryRequest message
into the Transcript-Hash if you are "stateless" and threw
it in the bin along with ClientHello1?

Mike

>  1. Check out Dowling et al.'s recent analysis. Published a month or
>     so ago, it's the most recent proof of security of the full
>     handshake (also includes PSK modes): https://eprint.iacr.org/2020/1044
>  2. Check out Paterson and van der Merwe's survey of the body of
>     papers that helped to shape TLS 1.3. It also overviews the myriad
>     attacks against TLS 1.2 and below that catalyzed a more proactive
>     design approach for 1.3:
> If you're unable to download the second (2.), the same paper appears 
> in a slightly different form in van der Merwe's PhD thesis.
>

---

From: Christopher Patton <[email-masked]>
Date: Mon, 5 Oct 2020 19:00:45 -0700

I agree that the HRR code path is hard to reason about, but I don't really
see an attack here. Is it your contention that the HRR code path leads to
an attack not accounted for by existing proofs?

I don't think this is likely. One way to think about this problem is as
follows [1]. Given an attacker that exploits the HRR code path, can you
efficiently construct an attacker that exploits a version of the protocol
without the HRR code path implemented? If the answer is "yes", and if we
assume the protocol is secure *without* the HRR code path implemented (as
asserted by a proof of security, say), it must be case that the protocol is
also secure *with* the HRR code path implemented.

Although I haven't studied this problem specifically ---  Dowling et al.
appear to address this problem, if only implicitly --- my intuition is that
the answer is "yes". The reason, loosely, is that the HRR code path doesn't
appear to depend on any ephemeral or long-term secret key material used by
the server for the core handshake. In particular, it doesn't depend on the
server's key share or signing key. This means that the adversary can
"simulate" any computation involving the HRR code path in its head, without
interacting with a real server. This observation ought to yield the
reduction I described above. Perhaps the spec is vague here, but if you
study any one of the high quality implementations that exist (openSSL,
boringSSL, NSS, Go's crypto/tls just to name a few), it won't be hard to
convince yourself that the HRR code path doesn't depend on secrets used in
the core handshake.

Chris P.

[1] https://eprint.iacr.org/2020/573

---

From: Michael D'Errico <[email-masked]>
Date: Tue, 6 Oct 2020 16:11:18 -0400

On 10/5/20 22:00, Christopher Patton wrote:
> I agree that the HRR code path is hard to reason about, but I don't 
> really see an attack here. Is it your contention that the HRR code 
> path leads to an attack not accounted for by existing proofs?

I have a concern that yes, there may be a way to
attack a TLS server via the HRR code path that
may not be possible without using HRR.  I am
hopeful that I'm wrong about this, but as a non-
cryptographer it would be difficult to come up
with any kind of proof.

Specifically, I am thinking that a client can
trick a server to use its ECC private key to do
an operation using the wrong curve, the wrong
point, or maybe something else.  See the pseudo
code I wrote below.   Step 10 is where the server
should be checking that the second ClientHello is
valid based on what it originally sent in the
first ClientHello.

RFC 8446 implies that you should check ClientHello2
vs. ClientHello1 because if this wasn't necessary
then why is there a list of allowed modifications?

But then it also says you can throw away CH1 and
just send the client a hash of it, rely on the
client to send it back (once), and not check
whether the second ClientHello is properly similar
to the first one (since the server doesn't even
retain it).

Can a malicious client send in its second Client-
Hello an invalid combination of EC point, curve,
cipher suite, etc. (that a server maybe doesn't
even check because there's a cookie extension in
there as well) and then use the result to discern
the key?  How many handshakes does the client need
to make to get the private key if I'm right?  One?

I've avoided spelling this out because it seems
potentially serious, and there was the weekend,
but it's Tuesday now, and I have been hopeful that
I haven't been just ignored and everyone has been
disabling TLS 1.3 and/or fixing their code, etc.

Please just tell me why I'm wrong and I'll feel
better since we won't have to malign another cute
furry animal.

Mike

> I don't think this is likely. One way to think about this problem is 
> as follows [1]. Given an attacker that exploits the HRR code path, can 
> you efficiently construct an attacker that exploits a version of the 
> protocol without the HRR code path implemented? If the answer is 
> "yes", and if we assume the protocol is secure *without* the HRR code 
> path implemented (as asserted by a proof of security, say), it must be 
> case that the protocol is also secure *with* the HRR code path 
> implemented.
>
> Although I haven't studied this problem specifically --- Dowling et 
> al. appear to address this problem, if only implicitly --- my 
> intuition is that the answer is "yes". The reason, loosely, is that 
> the HRR code path doesn't appear to depend on any ephemeral or 
> long-term secret key material used by the server for the core 
> handshake. In particular, it doesn't depend on the server's key share 
> or signing key. This means that the adversary can "simulate" any 
> computation involving the HRR code path in its head, without 
> reduction I described above. Perhaps the spec is vague here, but if 
> you study any one of the high quality implementations that exist 
> (openSSL, boringSSL, NSS, Go's crypto/tls just to name a few), it 
> won't be hard to convince yourself that the HRR code path doesn't 
> depend on secrets used in the core handshake.
>
>
> Chris P.
>
> On Mon, Oct 5, 2020 at 2:47 PM Michael D'Errico <[email-masked] 
> <mailto:[email-masked]>> wrote:
>

---

From: Michael D'Errico <[email-masked]>
Date: Tue, 6 Oct 2020 17:52:23 -0400

[Resending this with a better Subject line. --Mike]

On 10/6/20 16:11, I wrote:
>> as follows [1]. Given an attacker that exploits the HRR code path, 
>> can you efficiently construct an attacker that exploits a version of 
>> the protocol without the HRR code path implemented? If the answer is 
>> path implemented (as asserted by a proof of security, say), it must 
>> be case that the protocol is also secure *with* the HRR code path 
>> implemented.
>>
>>     > A couple pointers for getting started:
>>
>>     >  1. Check out Dowling et al.'s recent analysis. Published a 
>> month or
>>     >     so ago, it's the most recent proof of security of the full
>>     >     handshake (also includes PSK modes):
>>     https://eprint.iacr.org/2020/1044
>>     >  2. Check out Paterson and van der Merwe's survey of the body of
>>     >     papers that helped to shape TLS 1.3. It also overviews the
>>     myriad
>>     >     attacks against TLS 1.2 and below that catalyzed a more
>>     proactive
>>     >     design approach for 1.3:
>>     > https://link.springer.com/chapter/10.1007/978-3-319-49100-4_7
>>     >
>>     > If you're unable to download the second (2.), the same paper
>>     appears
>>     > in a slightly different form in van der Merwe's PhD thesis.
>>     >
>>     > No analysis is perfect, but so far, 1.3 appears to be far
>>     superior to
>>     > 1.0-1.2.
>>     >
>>     > Best,
>>     > Chris P.
>>
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Christopher Patton <[email-masked]>
Date: Tue, 6 Oct 2020 16:11:28 -0700

> > better since we won't have to malign another cute

I've told you already why I believe you're wrong here. At this point, it
won't do much good to continue posting about this list on the list. My
suggestion to you is to study the problem offline, and If you find an
attack and can demonstrate the works, then bring it back to the list. It
would also be helpful to look at implementations in order to understand how
others have interpreted the HRR code path. I bet this would clear up many
of your questions.

Chris P.

---

From: Nick Harper <[email-masked]>
Date: Tue, 6 Oct 2020 16:11:54 -0700

> > valid based on what it originally sent in the

A server is going to do its EC private key operation on a key_share value K
from the client. It should be a value from ClientHello2, but let's assume
that it comes from any ClientHello. I posit that if a client causes a
server to use K as the client's public value in an ECDHE computation on a
handshake that involves HRR, the client could also cause the server to use
K in the ECDHE computation without using HRR. From this, I conclude that if
this leads to some vulnerability, this implies the ECDHE algorithm (or its
implementation), not the TLS handshake, is flawed.

Suppose a server sends ClientHello2 with a cookie to a server, and the
server deduces from ClientHello2 that the client supports groups G_1, G_2,
... G_n for (EC)DHE and the client has provided key shares K_1, K_2, ...
K_m that the client might wish to use with one of those supported groups.
Suppose the server picks supported group G_i and key share K_j and performs
an ECDHE operation with that combination (even though it might not be a
valid pairing, e.g. the group G_i is Ed25519 and the key share K_j is for
P256). The client could have just as easily had the server perform this
operation by sending a single ClientHello (i.e. on a fresh connection, with
no cookie) containing a supported groups list with only G_i and a key share
list with only K_j. If the key share doesn't match the group, the client
can lie in the KeyShareEntry and say that it does.

> > then why is there a list of allowed modifications?

I am not aiming to provide a complete explanation to this question. Some
modifications to the ClientHello can't be allowed. For example, the cipher
suite can't be changed between ClientHello1 and ClientHello2 because that
could mean a different PRF for the transcript hash, which needs to be
computed starting with ClientHello1. Other modifications must be allowed,
because the client needs to be able to send a key_share in ClientHello2
that wasn't present in ClientHello1. It's possible that some future TLS
extension might affect cipher suite selection, so for future compatibility
it seems like a good idea to require other extensions to stay the same
between ClientHello1 and ClientHello2. Because some modifications are
needed and some can't be allowed, a good spec should list what is and isn't
allowed. The list of allowed modifications makes sense as it's limited to
things affected by HRR and nothing else (unless a future extension present
in the HRR allows more modifications).

---

From: Michael D'Errico <[email-masked]>
Date: Tue, 6 Oct 2020 22:13:19 -0400

> path leads to an attack not accounted for by existing proofs?

I know that it may lead to denial-of-service
for a legitimate client.  That's a big deal, but
I was more worried that there might be a bigger
problem with ECC, and I'm glad to hear that you
and Nick Harper say it's just fine (or at least
that we're no worse off than we are by trusting
ECC in version 1.2).

I'm still very concerned that everything 1.2- and
non-ECC is being thrown in the trash.

To see what I mean about denial of service, a
"stateless" server implemented according to the
way RFC 8446 describes is not going to have the
actual HelloRetryRequest message it sent to the
client.  I don't know what is done to solve this
problem, but apparently a lot of people have
implemented stateless-HRR so they must have done
something to either guess this value, or maybe
their code is not actually stateless.  If they
are guessing the value of HRR based on the 2nd
ClientHello received, and they guess wrong, and
the client puts a different value of HRR in its
own Transcript-Hash, then the handshake will
fail and a legitimate client will be denied
service.

Note that the pseudo code I wrote in the quoted
message below (steps 0 thru 12) does a lot more
than what RFC 8446 implies you should do so that
the server does have access to both the original
ClientHello1 message and the HelloRetryRequest
message.  It seems like a lot of wasted effort
for very little gain (if any, maybe it's worse
in every respect - memory use, processing time,
latency, bandwidth...).

Even then, it's not going to work as well as just
making a "stateful" (non-stateless?) server.

A data center with load-balancing can probably use
their distributed database like this to do a non-
stateless HRR transaction:

    - [disable "TCP Fast Open" so your database
      doesn't fill up with a bunch of crap]

    - receive ClientHello1

    - ask database for a (long-enough) randomish
      unpredictable value to be used for a cookie

    - create a HelloRetryRequest message with the
      cookie and commit ClientHello1 & HelloRetry-
      Request messages to the database using the
      cookie as the key

    - reply to the client with HelloRetryRequest
      after the database has finished storing
      the messages and the process can terminate

later....

    - if a new ClientHello arrives containing a
      cookie, ask the database for ClientHello1
      and HelloRetryRequest messages which
      correspond to the cookie key, using an
      atomic retrieve-and-delete function so the
      cookie can only be used once

    - if the key isn't in the database, then
      the cookie was fake, or it was already
      retrieved by another database client (replay
      prevented), or maybe it was too old and got
      expunged, so generate an error and close the
      connection

    - if the database does return the messages,
      then you can continue the handshake, make
      any comparisons between the two ClientHello
      messages you decide are important, and you
      also have the actual HelloRetryRequest
      message that the server sent to the client
      which you can put into the Transcript-Hash

[Note: the pseudo code above and in the original
quoted message below may not be complete!]

> case that the protocol is also secure *with* the HRR code path 

I'm not quite sure I understand this reasoning.
Proof by contradiction?  HelloRetryRequest is a
new message flow not present in any version of
TLS before 1.3.  Sorry if I'm missing something.

I appreciate all of the time you and everybody
else are putting into these issues!

Mike

---

From: Michael D'Errico <[email-masked]>
Date: Tue, 6 Oct 2020 22:25:33 -0400

On 10/6/20 19:11, Nick Harper wrote:
> I conclude that if this leads to some vulnerability, this implies the 
> ECDHE algorithm (or its implementation), not the TLS handshake, is flawed.

Thank you for the analysis!

Mike

---

From: Michael D'Errico <[email-masked]>
Date: Tue, 6 Oct 2020 22:41:06 -0400

Just want to clarify what I meant by "It" below
where I said, "It seems like a lot of wasted effort
for very little gain"

"It" refers to "stateless HRR", not the pseudo
code I wrote.  Even though I proof read the whole
message several times I missed this...

Mike

On 10/6/20 22:13, I wrote:
> [....]

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 7 Oct 2020 22:20:24 +0300

On Tue, Oct 06, 2020 at 10:13:19PM -0400, Michael D'Errico wrote:
> > really see an attack here. Is it your contention that the HRR code path
> > leads to an attack not accounted for by existing proofs?
> 

If implemented properly, it will never lead to denying a legimate
client.
 
> non-ECC is being thrown in the trash.

Because actually proving security of any practical cryptography is far
beyond current capabilities of open cryptography, the way security of
crypto is judged today is from attempts to break it.

ECC has been subject to this for ~35 years, and natural prime curves
(which include P-256, P-384, P-521, Curve25519 and Curve448) are second
to none in how well those have fared.

RSA and finite-field discete-logs have fared MUCH worse in ~45 years.

And there is no tradeoff between security and performance: Using ECC
instead of RSA/DH gives massive performance improvement.

This is not to say there will not be major challenges in future: If
large quantum computers can be built, ECC is toast (along with lots
of other stuff), and one needs new crypto, which is a necressarily a lot
less secure.

And regarding TLS 1.2, it is a mess:

- There is an extension to prevent attacks from having server confuse
  initial handshake and renegotiation.
- There is an extension to prevent attacks from failing to include
  exchange keys into master secret.
- Diffie-Hellman group negotiation is completely broken. To prevent
  attacks, clients must either disable DHE or tolerate handshakes with
  some servers failing.
- Signatures fail to include handshake type. The endpoints can disagree
  about handshake type, leading to attacks.
- Session ticket mechanism is pretty totally insecure.
- Static RSA uses insecure encryption (and is not forward-secure).
- Blockmodes use mac-then-pad, leading to timing attacks. There is
  extension to fix this, but pretty much nobody implements it.
- The MTI ciphersuite is insecure.
- You think EXPORT and single-DES have gone the way of dodo, >20
  years after being proven completely insecure? Unfortunately no.
- Limited extensibilty due to middlebox threat.
- Adding post-quantum cryptography is not feasible.

It is in practice impossible to implement TLS 1.2 securely. The best
one can do is some approximation with multiple unimplemented features
that is approximately secure.

Then there are non-security issues with TLS 1.2. Like ciphersuite
negotiation being petty much impossible to implement correctly due
to coupling between encryption and certificates.

> fail and a legitimate client will be denied

Have function cookie_to_hrr(c,cs,grp) that turns a cookie c into
HRR message, and is pure function of the cookie.

Then:

Without cookie:

1) Receive ClientHello without cookie.

2) Figure out ciphersuite cs and group grp to use.

3) Compute invariant partial hash of Client Hello.

4) Serialize state, including full client hello hash, cs and grp in
   cookie (no need to include the invariant hash).

5) Use MAC to authenticate the cookie, including the invariant hash.
   
   OR

   Use MRAE to encrypt and authenticate cookie, including the invariant
   hash in associated data.

6) Use cookie_to_hrr(c,cs,grp), send result to client and abort.

With cookie:

1) Receive ClientHello with cookie.

2) Compute invariant partial hash of Client Hello.

3) Authenticate the cookie, and decrypt it if it is encrypted. If
   authentication fails, abort. Important: There is an attack if
   this is not done!

4) Read full client hello hash, cs and grp from cookie.

5) Inject client hello hash to transcript.

6) Use cookie_to_hrr(c,cs,grp), and inject result to transcript.

7) Add inject second client hello to transcript.

8) Figure out other connection parameters besides ciphersuite and
   group, and continue handshake.

This can be proven to always work.

-Ilari