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

Nick Harper <nharper@google.com> Tue, 06 October 2020 23:12 UTC

Return-Path: <nharper@google.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 129FC3A1575 for <tls@ietfa.amsl.com>; Tue, 6 Oct 2020 16:12:10 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -17.599
X-Spam-Level:
X-Spam-Status: No, score=-17.599 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, ENV_AND_HDR_SPF_MATCH=-0.5, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, USER_IN_DEF_DKIM_WL=-7.5, USER_IN_DEF_SPF_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=google.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 84G2oxceUn2t for <tls@ietfa.amsl.com>; Tue, 6 Oct 2020 16:12:06 -0700 (PDT)
Received: from mail-oo1-xc35.google.com (mail-oo1-xc35.google.com [IPv6:2607:f8b0:4864:20::c35]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9F3603A1540 for <tls@ietf.org>; Tue, 6 Oct 2020 16:12:06 -0700 (PDT)
Received: by mail-oo1-xc35.google.com with SMTP id w7so153966oow.7 for <tls@ietf.org>; Tue, 06 Oct 2020 16:12:06 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=/g8PjCi6VddZnhwukmO4EJJao70+V7fAvGn3d3wTZeI=; b=gOrguqMSQ5F3eM+8UoYLrIV6fEmnPNWTEQixG0toRroGGDim6QSYGtBU8YW++6ypQb iEMqnf8GbzGov1EIOnTpkTkF91dgXDRTpN58IZcZHLemhA3ivXgyr3YwdVKb2cU9dm4Q B6HhoeLrBBeZpi1EZdDbluqKDs3xXigx8N2peGLJalOlndGQCh/XHyRvEPISqyWIXXls csX6peBGLa7X960JErp95gDn8zIo4BLATZBUa6RCoHV5TM7ERZEt/f11B5Psf9QvQoLg EKp0rkCqtik7/2UIqVm1r3baXCw04XLZ/26hR3y1f8LexWCfMdAs8KV+vnbLNt1LB8it XpXQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=/g8PjCi6VddZnhwukmO4EJJao70+V7fAvGn3d3wTZeI=; b=od8hahPhwY5wdcbsW+m4pdkEfGLR64CWvm95Fa1hSFbEokWFUQ4e2qKKSAOvHYTX2+ VTB5SVNCMigavfVCins6UEm9+Yjf4mUgHzfUGxzM4X7DvEswtfSGO6LWunaImAaUDao+ Yezv6o32pt0pWTDTTGiTweI3cC/a0nbl1VUWdMnYq5aSiAb4ZHRdy4AV7sqpeRDpzpzt L4J81GUv/LSD4LbtT6xqu04A+fr1osvDnMi0UjDpjoxPXGQTn4cfHUlODH9gH7M1CJch sk3E2PtOl3UVte6nHjQFnKqyTBGgpK9X7hddfpCkXVl59KbXbZKdE0gAXDgHbitbiyN2 w6Gw==
X-Gm-Message-State: AOAM532+74N0JgVC0Jsv+NNsXEb5HQmO68+/yDot4oJW6Q1kVERUDp5p 3tCN1nfS7YrJTqk6aJqbVakZh3Od/M+bC1BQR5IzPw==
X-Google-Smtp-Source: ABdhPJyw1Cf7GF4mquWCw+lFhe7cgI6z8OBRDoZFj0WAFlRInrYcziwRrwwJSdthpNy4k5kzGXBstftKlo4/pd1JVLU=
X-Received: by 2002:a4a:ad05:: with SMTP id r5mr268967oon.37.1602025925270; Tue, 06 Oct 2020 16:12:05 -0700 (PDT)
MIME-Version: 1.0
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> <2c875954-e068-1c59-9eb7-f45dd68e61db@pobox.com>
In-Reply-To: <2c875954-e068-1c59-9eb7-f45dd68e61db@pobox.com>
From: Nick Harper <nharper@google.com>
Date: Tue, 06 Oct 2020 16:11:54 -0700
Message-ID: <CACdeXiJ7tFmFm+ioqa-rZxuY8jq6V_2OnmuVOOzZCrm8bORO4w@mail.gmail.com>
To: Michael D'Errico <mike-list@pobox.com>
Cc: "<tls@ietf.org>" <tls@ietf.org>
Content-Type: multipart/alternative; boundary="00000000000032cee705b108baf4"
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/76lQLRB3aZ7_qgsopiZ33XvzN-E>
Subject: Re: [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 23:12:17 -0000

On Tue, Oct 6, 2020 at 2:52 PM Michael D'Errico <mike-list@pobox.com> wrote:

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

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.

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

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

> >
> > 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
>
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>