Re: [TLS] Un-deprecating everything TLS 1.2

[Michael D'Errico <[e-mail]>]

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 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!]

> 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.

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


> 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
>
> On Mon, Oct 5, 2020 at 2:47 PM Michael D'Errico <[e-mail] 
> <mailto:[e-mail]>> wrote:
>
>     On 10/5/20 10:21, Christopher Patton wrote:
>     > 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:
>     > 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.
>