Re: [TLS] KeyUpdate and unbounded write obligations

Keith Winstein <keithw@cs.stanford.edu> Thu, 18 August 2016 18:21 UTC

Return-Path: <winstein@gmail.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 664B612D8F9 for <tls@ietfa.amsl.com>; Thu, 18 Aug 2016 11:21:55 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.598
X-Spam-Level:
X-Spam-Status: No, score=-2.598 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.001, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.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 ONk7f_jVmeFX for <tls@ietfa.amsl.com>; Thu, 18 Aug 2016 11:21:52 -0700 (PDT)
Received: from mail-yw0-x232.google.com (mail-yw0-x232.google.com [IPv6:2607:f8b0:4002:c05::232]) (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 64D7812D140 for <tls@ietf.org>; Thu, 18 Aug 2016 11:21:52 -0700 (PDT)
Received: by mail-yw0-x232.google.com with SMTP id r9so14687586ywg.0 for <tls@ietf.org>; Thu, 18 Aug 2016 11:21:52 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=hEjODIWCN4jatVVU2AR06q9OCG9pT95KQaOQcWcUVkU=; b=0osdHyeLZx4ahrGP7LgjtuJnWZN9T4SM3fTx5tT56iEu6MHajPhnyK9rBKIfh4VF7G 4JlZhFG4QUM+djeNZ0g/81O0ddXjegKE49Je/wX3jxngxNaW/UAS3xOYyTagoTAP4613 n8o5Xul7yW374vb7iN39bwz4X/Wip9KbDATErgEHiLbEk2XsthOj5xAIUwPPQ+8spN0G UvxByyw2iEnEH+iN77nROtGo+sV0kaQroQXJvRNndHXi+Xq0eq9JBukVNmhAU64UEthy ahUBRC6jNRJc03hc494kRBrzln5NiU/0pGKejqKqfA+BCoFXTfgZ18sGNN7PhGEVLNDG lVQg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc; bh=hEjODIWCN4jatVVU2AR06q9OCG9pT95KQaOQcWcUVkU=; b=YGX+ac2FXNjDnz5qlJy8TMkfy2ekvXzERK9oIVuviw8MmtSYRQxYlnM4sklW8p/3Kv Iplmd05xO3h2Ey1/RIh+xWqvsoZ8ejUNA5eTYG/r8H1yikD7yTxttDrm9oUYY7htp5pT B/MGGHazur2xr76efVqyFDfNr1aUtnsdGW812jqrIxQZvGDQxODlnDaaBN1Bh0SxojjU mcYdjYCCYWKkrJm0BY2cOomDgVMuTWAg3NcYX/0t9iQcQ3856CjuLHMi1MAksBEBzSPO rQ3PrWVkd9dLWh0MrAIgpUpi/A2NEhtjhDjQ9HF2dfr/CSRlUoZfJtEOPrJ7uqrUyKWi I3kQ==
X-Gm-Message-State: AEkooutXrOB78UpApzU16mRtulqbDc7RLN6YjmCPLypQI4JYXdKT3pSWP1pKpzTHemo8BLPScmI/IdNWQDMlzg==
X-Received: by 10.13.249.135 with SMTP id j129mr2981410ywf.267.1471544511213; Thu, 18 Aug 2016 11:21:51 -0700 (PDT)
MIME-Version: 1.0
Sender: winstein@gmail.com
Received: by 10.129.79.209 with HTTP; Thu, 18 Aug 2016 11:21:10 -0700 (PDT)
In-Reply-To: <CAF8qwaDfWdCCQpD8z8iY0BMJjbrf8qi-qf5X7mSe8m+hNZu-FQ@mail.gmail.com>
References: <CAF8qwaDgGHGmuBwhZEz9-=Ss2bfzNAYWfmnbMqQDxTQnMUpH7g@mail.gmail.com> <93086b3c-ca1b-4c37-67e1-efbf417a8b58@akamai.com> <CAF8qwaDfWdCCQpD8z8iY0BMJjbrf8qi-qf5X7mSe8m+hNZu-FQ@mail.gmail.com>
From: Keith Winstein <keithw@cs.stanford.edu>
Date: Thu, 18 Aug 2016 11:21:10 -0700
X-Google-Sender-Auth: 6U1JHddhLqu2kgy43EY9uSn27RI
Message-ID: <CAMzhQmPB0GXZzh+g=-TMmAp9HQxpZUPcht4zi3_K7WW_ouGg6A@mail.gmail.com>
To: David Benjamin <davidben@chromium.org>
Content-Type: text/plain; charset="UTF-8"
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/ww-lCkirPw5VNwwnc5D5rlnU7H4>
Cc: "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] KeyUpdate and unbounded write obligations
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.17
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: Thu, 18 Aug 2016 18:21:55 -0000

It sounds like there are four properties in play here:

P1: Either side can rekey its outgoing traffic whenever it wants.

P2: Either side can "force an update to the entire connection," i.e.
can ask the other side to rekey *its* outgoing traffic.

P3: A side can learn that P1 has been read by the other side.

P4: Neither side can cause the other to accrue an unbounded deferred
write obligation; in fact the maximum accruable deferred write
obligation is one KeyUpdate.

The current draft has P1 and P2 only.

My view: all four properties are important.

I've previously argued for the benefit of P3.

Re: P2, there seems to be some disagreement about the value. I think
it is -- one endpoint may well have knowledge (about the traffic or
its future susceptibility to compromise) that makes it want to ratchet
the session. Forward secrecy is not only valuable to the sender. I
don't think it's enough to recommend that each side rekey its own
direction occasionally.

I don't think it's a particularly hard design or implementation
challenge to get all four properties.

Here a simple explicit and verbose design as a straw-man, that gets
P1, P2, P3, and P4:

1) As David proposes, separate the tracks and have two KeyUpdate ladders.

2) Define KeyUpdate like this:

   struct {
       uint64 desired_minimum_receive_generation;
       uint64 current_receive_generation;
   } KeyUpdate;

Language: "An implementation MAY update its send keys by sending a
KeyUpdate. An implementation MAY request that the other side update
its send keys by increasing the desired_minimum_receive_generation. An
implementation MUST NOT set desired_minimum_receive_generation to be
greater than its current_receive_generation plus one."

"Upon receiving a KeyUpdate, the receiver MUST increment their
receiving generation by one. If the desired_minimum_receive_generation
is greater than its current send generation, the receiver MUST update
its send keys and send a KeyUpdate. If the
desired_minimum_receive_generation is greater than the current send
generation plus one, the receiver SHOULD abort."

-Keith

On Thu, Aug 18, 2016 at 10:26 AM, David Benjamin <davidben@chromium.org> wrote:
> On Thu, Aug 18, 2016 at 1:08 PM Benjamin Kaduk <bkaduk@akamai.com> wrote:
>>
>> On 08/17/2016 11:29 PM, David Benjamin wrote:
>>
>> However, we lose the "free" (really at the cost of this unboundedness
>> problem) generation-based bidirectional KeyUpdate sync. Depending on what we
>> want out of KeyUpdate, I can imagine a few options:
>>
>>
>> My recollection is that the only reason we have KeyUpdate is to avoid
>> going over the limit for amount of ciphertext encrypted in the same key
>> within our safety margin (recall the analyses debating whether such limits
>> would even be reachable for the ciphers currently in use, as well as the
>> disagreement as to what the safety margin should be).
>>
>>
>> - Don't. KeyUpdates are unilateral. Recommend in the spec to KeyUpdate
>> every N records or so and leave it at that. (I think this is the best option
>> on grounds of simplicity, assuming it meets the primary needs of KeyUpdate.)
>>
>>
>> If we're in a world where implementations are considering leaving out the
>> required "catch up" KeyUpdate, we may want to consider alternative options
>> to put in the spec that are easier to implement.  That is, we can write the
>> spec in various ways to get the functionality that both write directions get
>> the key updates needed to avoid the ciphertext limit, and we are reliant on
>> implementations to follow the spec in order to get that safety property.
>> So, given that we can only get the safety property if all implementations
>> follow the spec, why not just ... require implementations to track the
>> amount sent and rekey if it's too close to the limit?  That is consistent
>> with a unilateral/unidirectional KeyUpdate, and having per-connection
>> byte/record counters does not seem to be a huge overhead.
>>
>> Keeping the two write directions' keys independent would also avoid
>> conflict when the two peers disagree on how often a rekey is necessary (as
>> might happen if a resource-constrained device decided to not implement byte
>> counters and just rekey after every N records, which is "free" since you
>> need to track serial numbers anyway).
>
>
> Yup. If we say implementations SHOULD/MUST/whatever send KeyUpdates
> frequently and we're fine with just saying we rely on each sender to honor
> that w.r.t. their own send keys with little other fanfare, I think this
> option is the clear winner. We're already relying on the sender to not, say,
> exfiltrate all data somewhere nasty.
>
> There seemed to be other motivations for KeyUpdate (Keith's passive observer
> use case, I've heard some theories around one side knowing more about the
> cipher than another, etc.), so I left that alone for now. I'm not currently
> convinced by those use cases, but perhaps the working group feels
> differently. I'm reasonably confident splitting the key tracks is correct
> regardless, but I wasn't sure which KeyUpdate motivations were considered
> important and which weren't.
>
>>
>> - If you receive a KeyUpdate and didn't send one in the last N minutes
>> (where N minutes >>> 1 RTT), (optionally?) flag your next write to be
>> preceded by KeyUpdate. This is simple but needs an ad-hoc timeout to prevent
>> ping-ponging.
>>
>> - Variations on sticking a please_echo boolean in the KeyUpdate message,
>> generation counts, etc., to get synchronization with coalescing if we need
>> it. I would much prefer the simpler options unless we truly need this.
>> (KeyUpdate is right now a *required* feature, so simplicity should be a
>> priority. Rare use cases are what extensions are for.)
>>
>> Thoughts?
>>
>> David
>>
>> PS: We've seen this before with renego (I've seen many OpenSSL consumers
>> which lock up if the peer renegotiation), error alerts triggered on reads
>> (often they don't get sent), and close_notify (also don't get sent in
>> practice). Deviations from dumb filters are expensive.
>>
>>
>> Yes, simple is better.  Well, here at least :)
>>
>>
>> PPS: I'm wary of over-extending post-handshake auth for the same reason,
>> though I haven't had time to look carefully at the latest proposal yet.
>> Still, having TLS specify and analyze the crypto while lifting the actual
>> messages into application-level framing would be preferable for these sorts
>> of side protocols. The application gets to make assumptions about read/write
>> flows and knows in which contexts what is and isn't allowed.
>>
>>
>> Hmm, so [in the above proposal] that would involve the application doing
>> the byte/record counters and pushing a "give me a rekey packet now" button
>> when needed?  I am not sure that I'm comfortable moving "crypto sensitive"
>> code (well, sort-of) into the application, since many applications won't do
>> it.  Also, not all applications will have access to the record serial
>> number, as I understand it, and the formulas I remember for the ciphertext
>> limits involved both records and bytes.
>
>
> Sorry, that was unclear. That was more of a side comment to help explain why
> I have such strong visceral reactions to any post-handshake auth mechanisms
> since part of it is the same issue. I am not proposing we lift KeyUpdate to
> the application layer. I'm proposing we split the KeyUpdate tracks in two
> and do [insert preferred option here] w.r.t. the bidirectionality issue.
> Probably should not have mentioned it since it's mostly a distraction for
> this topic. I ramble a lot. :-)
>
> David
>
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>