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

Michael D'Errico <mike-list@pobox.com> Tue, 06 October 2020 21:52 UTC

Return-Path: <mike-list@pobox.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 47AF43A1505 for <tls@ietfa.amsl.com>; Tue, 6 Oct 2020 14:52:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=pobox.com; domainkeys=pass (1024-bit key) header.from=mike-list@pobox.com header.d=pobox.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id 32LH8GEy7m1Y for <tls@ietfa.amsl.com>; Tue, 6 Oct 2020 14:52:29 -0700 (PDT)
Received: from pb-smtp2.pobox.com (pb-smtp2.pobox.com []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 00C9C3A09C4 for <tls@ietf.org>; Tue, 6 Oct 2020 14:52:28 -0700 (PDT)
Received: from pb-smtp2.pobox.com (unknown []) by pb-smtp2.pobox.com (Postfix) with ESMTP id 6CA088535E for <tls@ietf.org>; Tue, 6 Oct 2020 17:52:26 -0400 (EDT) (envelope-from mike-list@pobox.com)
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=subject:to :references:from:message-id:date:mime-version:in-reply-to :content-type:content-transfer-encoding; s=sasl; bh=T9U3+LqN5f6C RWbT+ifPwK1wRmo=; b=tyJTPZDRjiRKWDcdyNHYObYjZ7DDDFVIqMwGVNEvSg2O orH3zs2rBhgPE/hRZQxKFvlNeNAxXlHJ0jJghsBHNkzKtMtOJKaIXNfLBsJ7JCbY Og4jW0kJYAwvdDKVODvg/zAdOy4cmOP/HI114MIXORFW5Y97r2aKayX6/ATlQ1A=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=subject:to :references:from:message-id:date:mime-version:in-reply-to :content-type:content-transfer-encoding; q=dns; s=sasl; b=qc782N pCn7t9aJmvUlBr1A9+Ztx2zRZYkNk3G6CNdjrMPI/HkHfMwZebfkgD6x04j32ioP EGPOeVzJtNwLwCj3Ac5i0vijaqhXtTu4x0o5sAdFTMtUx/Hkux/Z+kCyV/KfC5cR 9fwKMkK6/Z+MCQRbWgFi7JZyGN0rbvP3YPrE0=
Received: from pb-smtp2.nyi.icgroup.com (unknown []) by pb-smtp2.pobox.com (Postfix) with ESMTP id 64C588535D for <tls@ietf.org>; Tue, 6 Oct 2020 17:52:26 -0400 (EDT) (envelope-from mike-list@pobox.com)
Received: from MacBookPro.local (unknown []) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by pb-smtp2.pobox.com (Postfix) with ESMTPSA id 8E7C685358 for <tls@ietf.org>; Tue, 6 Oct 2020 17:52:25 -0400 (EDT) (envelope-from mike-list@pobox.com)
To: tls@ietf.org
References: <eb32ba5a-8ea7-efb7-584d-0d0521d16f59@pobox.com> <0E05019B-32FF-4A0C-9AB5-E25544CA952D@akamai.com> <CAG2Zi21fDe-i4VauFv1KZWsBoSyCwtsx4APPAw9ceMnL6ZWSnQ@mail.gmail.com> <8a468f58-2da1-ee81-9f21-f8c76255c988@pobox.com> <CAG2Zi23LMfFYDjhJ_cXniqSuNVWPuiBoB6St1nMiWLFnA-Wz_w@mail.gmail.com> <51a02fc4-92f9-93dc-c60c-bfeed505d74e@pobox.com>
From: Michael D'Errico <mike-list@pobox.com>
Message-ID: <2c875954-e068-1c59-9eb7-f45dd68e61db@pobox.com>
Date: Tue, 6 Oct 2020 17:52:23 -0400
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.13; rv:68.0) Gecko/20100101 Thunderbird/68.12.1
MIME-Version: 1.0
In-Reply-To: <51a02fc4-92f9-93dc-c60c-bfeed505d74e@pobox.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
X-Pobox-Relay-ID: 3893883E-081E-11EB-850C-74DE23BA3BAF-38729857!pb-smtp2.pobox.com
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/HZ58mobR-lJ1XYkEyJy_lr4-rJ4>
Subject: [TLS] TLS 1.3 ECC Private Key Compromise? (was Re: Un-deprecating everything TLS 1.2)
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 06 Oct 2020 21:52:31 -0000

[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 <mike-list@pobox.com 
>> <mailto:mike-list@pobox.com>> 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
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls