[TLS] TLS 1.3 ECC Private Key Compromise? (was Re: Un-deprecating everything TLS 1.2)

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

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

On 10/6/20 16:11, I wrote:
> 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 
>> 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.
>>
>
> _______________________________________________
> TLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tls