Subject: [TLS] KeyUpdate and unbounded write obligations

From: David Benjamin <[email-masked]>
Date: Thu, 18 Aug 2016 04:29:19 +0000

Amusingly, Keith and I appear to have crossed mid-air in our respective
requests to change KeyUpdate, so this will be a fun collision. Mine is a
tad larger of a change I'm afraid.

We've currently implemented KeyUpdate in our in-progress TLS 1.3 code, but
we've for now ignored the requirement for the receiver to send KeyUpdates
to catch up with the sender. It appears that honoring that will cause
significant problems.

A TLS stack does not know much of the read/write patterns of the
higher-level application. It must handle all kinds of flows, so a dumb
filter is ideal. Some TLS APIs are even structured around this. Rather than
consume and provide a socket interface, they encrypt and decrypt buffers,
leaving transport business to the consumer. (And socket-based APIs are
often used as if they were filters using buffers for sockets.)

We may then have transport reads progress faster than transport writes, or
the write channel may not even be driven most of the time. (This isn't that
contrived. Unpipelined HTTP/1.1 never reads and writes in parallel. HTTP/2
may not have any response to write. Or perhaps it is processing a request
while an earlier response is still being written.) The receiver can then
accrue KeyUpdate obligations unboundedly. When the write channel is active
again, it has to dump all those out as unbounded write overhead. This is
rather a mess. There should be a tight bound (one, if not zero) on
KeyUpdate obligations.

I'm unclear on exactly what parts of KeyUpdate the WG finds important, so I
haven't written a concrete PR yet. But here is roughly the fix I have in
mind:

Sending one KeyUpdate and 1,000 in a row morally should be the same. But
both ends share a KeyUpdate track, so any forward secrecy goals require
matching generations. So branch client-write and server-write first and
have two KeyUpdate ladders starting at client_traffic_secret_0 and
server_traffic_secret_0.  (Note bidi KeyUpdate is asynchronous, so
implementations had to store separate read and write traffic secrets
anyway.) As a small bonus, we can lose the client/server split from traffic
key calculations (7.3), having branched at traffic secret already.

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:

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

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.

---

From: Keith Winstein <[email-masked]>
Date: Thu, 18 Aug 2016 00:30:03 -0700

I think it's probably possible to make everybody happy here.

I appreciate the need to avoid allowing the other side to create an
unbounded deferred write/compute obligation. I also think it's
valuable to preserve the ability for "either side to force an update
to the entire connection," and obviously I think it's valuable for the
initiating side to get an ack that that has happened (hence PR
#426/#580).

To mitigate the unboundedness issue, what would you think about this option:

1) Keep everything the same as the current draft, but
2) Add this text: "An implementation MUST NOT advance its current
sending generation to be greater than its current receiving generation
plus one."

That would be it. If an implementation reads a KeyUpdate that attempts
to advance the receiving generation to be greater than the sending
generation plus one, it may abort because the other side has behaved
in an invalid manner.

I think this eliminates any unbounded deferred write obligation. The
KeyUpdates would still be asynchronous, but after sending one, an
implementation would not be able to send another until it received one
from the other side -- and whether that KeyUpdate is triggered by its
own KeyUpdate, or generated independently, wouldn't matter. (Of course
we also want our PR #580 to be able to resolve that ambiguity, but
these can be basically orthogonal issues.)

-Keith

On Wed, Aug 17, 2016 at 9:29 PM, David Benjamin <[email-masked]> wrote:
> requests to change KeyUpdate, so this will be a fun collision. Mine is a tad
> larger of a change I'm afraid.
>
> we've for now ignored the requirement for the receiver to send KeyUpdates to
> catch up with the sender. It appears that honoring that will cause
> significant problems.
>
> leaving transport business to the consumer. (And socket-based APIs are often
> used as if they were filters using buffers for sockets.)
>
> rather a mess. There should be a tight bound (one, if not zero) on KeyUpdate
> obligations.
>
> matching generations. So branch client-write and server-write first and have
> two KeyUpdate ladders starting at client_traffic_secret_0 and
> problem) generation-based bidirectional KeyUpdate sync. Depending on what we
> want out of KeyUpdate, I can imagine a few options:
>
> - 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.)
>
> preceded by KeyUpdate. This is simple but needs an ad-hoc timeout to prevent
> ping-ponging.
>
> 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
>
> of side protocols. The application gets to make assumptions about read/write
> flows and knows in which contexts what is and isn't allowed.
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 18 Aug 2016 11:53:07 +0300

> initiating side to get an ack that that has happened (hence PR

That wouldn't work very well in highly asymmetric situations. One
could add rule that allows rekeys in excess of that limit if RSN is
above some threshold. Such RSN thresholds would greatly slow down
KeyUpdate spam (e.g. reaching 2^32 takes 84GB at minimum).

Also, for DTLS, one would need limits like this to avoid exessive key
updating.

-Ilari

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 18 Aug 2016 12:08:02 -0500

On 08/17/2016 11:29 PM, David Benjamin wrote:
> 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).

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

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

-Ben

---

From: David Benjamin <[email-masked]>
Date: Thu, 18 Aug 2016 17:26:37 +0000

On Thu, Aug 18, 2016 at 1:08 PM Benjamin Kaduk <[email-masked]> wrote:

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

> 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

---

From: Keith Winstein <[email-masked]>
Date: Thu, 18 Aug 2016 11:21:10 -0700

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 <[email-masked]> wrote:
>> 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.)
>>
>>
>> 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.
>>
> 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
> 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
>

---

From: David Benjamin <[email-masked]>
Date: Thu, 18 Aug 2016 18:55:46 +0000

Yeah, something of this sort should work. I'm fuzzy on P2 and especially
unconvinced by P3, so I default to preferring less mechanism than more, but
I'm certainly wrong a lot of the time and am not totally clear on which
properties the WG cares about.

As you say, it's not particularly invasive to get all of them. I'd be even
happier if the bound were zero instead of one, but one is fine.

> greater than its current_receive_generation plus one."

It seems desired_minimum_receive_generation can only be
current_receive_generation or current_receive_generation + 1. In that case,
a boolean should be sufficient and saves 7 bytes.

Nit: Do you really need that large of a generation number? DTLS renego only
ever let you count 2^16 epochs. Not that it matters.

> generation plus one, the receiver SHOULD abort."

Nit: Probably should explicitly say to fail with illegal_parameter or so.

> what we
> limits
> option
> the
> (as
> observer
> prevent
> read/write
> button
> why

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 18 Aug 2016 14:03:46 -0500

I am also fuzzy on P2 and P3, but don't have any complaints with this
strawman scheme.

-Ben

On 08/18/2016 01:55 PM, David Benjamin wrote:
> Yeah, something of this sort should work. I'm fuzzy on P2 and
> especially unconvinced by P3, so I default to preferring less
> mechanism than more, but I'm certainly wrong a lot of the time and am
> not totally clear on which properties the WG cares about.
>
> As you say, it's not particularly invasive to get all of them. I'd be
> even happier if the bound were zero instead of one, but one is fine.
>
> On Thu, Aug 18, 2016 at 2:21 PM Keith Winstein <[email-masked]
> <mailto:[email-masked]>> wrote:
>
> current_receive_generation or current_receive_generation + 1. In that
> case, a boolean should be sufficient and saves 7 bytes.
>
> Nit: Do you really need that large of a generation number? DTLS renego
> only ever let you count 2^16 epochs. Not that it matters.
>  
>
>     On Thu, Aug 18, 2016 at 10:26 AM, David Benjamin
>     <[email-masked] <mailto:[email-masked]>> wrote:
>     > On Thu, Aug 18, 2016 at 1:08 PM Benjamin Kaduk
>     <[email-masked] <mailto:[email-masked]>> wrote:
>     >>
>     message,
>     consumers
>     > [email-masked] <mailto:[email-masked]>
>     <https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_tls&d=DQMFaQ&c=96ZbZZcaMF4w0F4jpN6LZg&r=sssDLkeEEBWNIXmTsdpw8TZ3tAJx-Job4p1unc7rOhM&m=m-n-dkd-wF37KiHIqOGfyN5xdXjgH0rP2DWgl0TuMsU&s=wB9yc-0REcOSwU6RiqznQhLiGu9b2ip4eUHGh4m7FZg&e=>
>     >
>

---

From: Adam Langley <[email-masked]>
Date: Thu, 18 Aug 2016 12:10:48 -0700

> case, a boolean should be sufficient and saves 7 bytes.

Given that simplification, is there a purpose for current_receive_generation?
It seems that scheme might be equal to a "please_echo" flag.

Cheers

AGL

---

From: Jim Schaad <[email-masked]>
Date: Thu, 18 Aug 2016 12:13:37 -0700

> -----Original Message-----
> From: TLS [mailto:[email-masked]] On Behalf Of Keith Winstein
> Sent: Thursday, August 18, 2016 11:21 AM
> To: David Benjamin <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [TLS] KeyUpdate and unbounded write obligations
> 

If you are not getting any traffic back, it seems that this might a problem.
P1 + P3 causing P4.  Unless you are willing to not know the difference
between traffic getting lost and traffic being processed.

Jim

> 
> 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.
> 
> 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:
> KeyUpdate. An implementation MAY request that the other side update its
send
> keys by increasing the desired_minimum_receive_generation. An
> "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."
> >> 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.)
> >>
> >>
> >> 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
> >> 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).
> >
> >
> > 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.
> >
> > 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.
> >>
unless we
> truly need this.
> >> (KeyUpdate is right now a *required* feature, so simplicity should be
> >> 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.
> >> 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
> >

---

From: Keith Winstein <[email-masked]>
Date: Thu, 18 Aug 2016 12:20:21 -0700

Yes, you need current_receive_generation, or something like it, to get
P3. This is the subject of our PR #426/580.

-Keith

On Thu, Aug 18, 2016 at 12:10 PM, Adam Langley <[email-masked]> wrote:
> Given that simplification, is there a purpose for
> current_receive_generation? It seems that scheme might be equal to a
> "please_echo" flag.
>
>
> Cheers
>
> AGL

---

From: Adam Langley <[email-masked]>
Date: Thu, 18 Aug 2016 12:42:47 -0700

> P3. This is the subject of our PR #426/580.

The KeyUpdate messages are encrypted and thus sequenced with all the
application data. Apart from the Heartbeat message (TLS 6520), which has
not been significantly used in TLS (I think), we've never worried about a
TLS-level ack before.

PR 426 wants a way to retrospectively disclose keys to middleware and wants
to make sure that the receive side is no longer going to trust those keys
before doing so. Having spoken to several vendors of these products in the
past and tried to persuade them to accept read-only access I don't think we
should alter TLS's design for that unless there's a novel argument about
why they would ever accept it. (Because they won't. Their competitive
interest is to have as many "features" as possible, many of which would
require modifying traffic.)

Cheers

AGL

---

From: Keith Winstein <[email-masked]>
Date: Thu, 18 Aug 2016 13:36:05 -0700

Okay, this is a different question -- whether P3 is a valuable property or not.

I made the case for this in my Monday thread[1] and in my Berlin
presentation[2].

[1] https://www.ietf.org/mail-archive/web/tls/current/msg20787.html

[2] https://www.ietf.org/proceedings/96/slides/slides-96-tls-3.pdf

I'm happy to make the case for P3 here again but didn't want to hijack
David's thread. My claim here was that there are some simple designs
that satisfy everybody and grant P1+P2+P3+P4, and that David's
concern's and my concerns are "basically orthogonal issues."

===

On the value of P3, I think you're giving us a crimped reading. We
gave three use cases in Berlin and in my email:

- An embedded device may wish to fully rotate the session keys before
going to sleep.

- A paranoid device might fully rotate the session keys before closing
the session. (If confirmation is absent, the device might use a
higher-level mechanism to forcibly log out all open sessions from that
user.)

- An endpoint that wishes to permit a read-only virus scanner or IDS
will want to fully rotate the session before sharing the directional
keys with the middlebox.

On this last use case, I agree that incumbent IDS vendors may not be
eager to support it. But adoption would probably come from a different
direction. IoT devices today forbid anybody, including a middlebox
controlled by the device owner, from auditing their own traffic and
seeing what the devices are sending and receiving. (Unlike a browser,
they don't let the user add a private CA cert to be able to MITM.) In
my conversations with IoT device vendors, some expressed interest in
allowing device owners to grant read-only access to themselves. I
really do think this would be a good thing.

Unlike Heartbeat, we are not talking about an ack that would be
generated by something, and we're not really talking about altering
TLS's design. We're talking about piggybacking one field in a protocol
message that is going to be sent anyway, where the message (KeyUpdate)
is new in TLS 1.3 anyway.

As I said, it is orthogonal to David's issues here. Yes, it is
possible to get P1+P2+P4 by themselves -- P3 has to live or die on its
own merit. But it is really just one piggyback field to get it.

-Keith

On Thu, Aug 18, 2016 at 12:42 PM, Adam Langley <[email-masked]> wrote:
> application data. Apart from the Heartbeat message (TLS 6520), which has not
> been significantly used in TLS (I think), we've never worried about a
> TLS-level ack before.
>
> should alter TLS's design for that unless there's a novel argument about why
> they would ever accept it. (Because they won't. Their competitive interest
> is to have as many "features" as possible, many of which would require
> modifying traffic.)
>
>
> Cheers
>
> AGL

---

From: Adam Langley <[email-masked]>
Date: Thu, 18 Aug 2016 14:26:45 -0700

> gave three use cases in Berlin and in my email:

I think I was because I hadn't seen your Berlin presentation. But I'm still
going to hijack this thread and ask you to expand on some of these points
so that I understand your motivation :)

> going to sleep.

I imagine the argument here goes:

1) Sleep is good because it saves power.
2) To sleep we need to power down (and erase) most memory.
3) So to keep a TLS connection across sleep/wake secrets have to be saved
to flash, but that's hard to erase so we don't want to expose keys that
were used to encrypt traffic.

For that I see why one needs KeyUpdate to be echoed: as the embedded
device, you want the peer to rotate keys so that you can write only fresh
keys to flash. On wake you want the other side to rotate again so that the
keys in flash were only used to authenticate a new KeyUpdate.

But why do you need the other side to have confirmed that it has erased
your keys? I think you only care that it echos your KeyUpdate messages
promptly.

> higher-level mechanism to forcibly log out all open sessions from that

The worry here is that a peer might be seized and subject to a cold-boot
attack to lift the TLS connection keys? So if you don't hear from it every
$x seconds you'll log it out?

Again does the confirmation here help? What if you send a KeyUpdate and
receive a change password request? The peer might well have sent it before
receiving your KeyUpdate, or maybe it was seized and will just choose not
to echo your KeyUpdate.

(I might well be misunderstanding the details here.)

> really do think this would be a good thing.

If they have a channel to the user where they are sending a stream of old
keys, couldn't they just mirror the plaintext of the connection to keep
things simple? I guess you worry about a device that's cooperative enough
to put in the effort to have their audit channel but lies about the
plaintext?

Cheers

AGL

---

From: Keith Winstein <[email-masked]>
Date: Thu, 18 Aug 2016 17:18:13 -0700

On Thu, Aug 18, 2016 at 2:26 PM, Adam Langley <[email-masked]> wrote:

> going to hijack this thread and ask you to expand on some of these points so
> that I understand your motivation :)

Fair enough. :-)

> 3) So to keep a TLS connection across sleep/wake secrets have to be saved to
> flash, but that's hard to erase so we don't want to expose keys that were
> used to encrypt traffic.

Yeah, our reasoning follows yours and goes a little further:

4) I don't know when I'm going to wake up again.
5) I don't want a subsequent compromise of me *or* the other side to
reveal prior plaintext from the session.
6) Because I'm going to sleep, it's now or never to make sure the
session keys aren't retained.
7) Therefore, I'd like to make sure both sides have ratcheted forwards
before I go to sleep.

> For that I see why one needs KeyUpdate to be echoed: as the embedded device,
> you want the peer to rotate keys so that you can write only fresh keys to
> flash. On wake you want the other side to rotate again so that the keys in
> flash were only used to authenticate a new KeyUpdate.
>
> But why do you need the other side to have confirmed that it has erased your
> keys? I think you only care that it echos your KeyUpdate messages promptly.

Agreed, P1+P2 is sufficient if the device only cares about making sure
*it* is not going to leak keying material (that can reveal prior
plaintext) if there is a compromise during sleep. You need P3 if you
are also concerned the peer might be holding on to an old key.

> $x seconds you'll log it out?

Probably nothing that elaborate.

The device is concerned that after the session is over (from its
perspective), the server might get compromised, and the attacker reads
the key for a long-dormant session out of the server's /dev/mem, and
uses it to decrypt prior ciphertext.

One approach is that the device should make sure to close every
session with a secure bidirectional close, where the server actually
confirms that the session is dead in both directions. But TLS does not
have a secure bidirectional close. (Even when used, close_notify only
promises there will be no more data in *that* direction.)

However, the device can try to guarantee that both sides have
ratcheted past all the keys that could reveal prior plaintext.

> Again does the confirmation here help?

The confirmation is the way for the device to know that the server has
read its request to ratchet the client-to-server traffic key forwards.
(And the idea would be, if the device doesn't get that confirmation
and really wants it, it may have to raise a warning and handle this at
the application layer -- e.g. by opening a new session to the server
and issuing a "kill all sessions" command.)

> What if you send a KeyUpdate and receive a change password request? The peer
> might well have sent it before receiving your KeyUpdate, or maybe it was seized and
> will just choose not to echo your KeyUpdate.

Sure, there's nothing you can do if the peer gets compromised while
important keys still live on it. But the idea here is for the device
to be able to make sure the keys get ratcheted after all the data is
sent but before there can be a later compromise. Basically
approximating (some of) the semantics of an actual secure
bidirectional close.

> things simple? I guess you worry about a device that's cooperative enough to
> put in the effort to have their audit channel but lies about the plaintext?

Right, exactly. (Ideally, the device doesn't even know it's being
audited until the user logs in to the Web UI and says, "okay, now,
ratchet the session and then share the old keys with this auditor that
I am going to introduce you to, so it can decrypt some earlier
ciphertext I've been capturing." So we don't want a parallel channel
and we don't even want the device to have to know about the audit
beforehand.)

-Keith

---

From: Adam Langley <[email-masked]>
Date: Fri, 19 Aug 2016 11:05:32 -0700

> 7) Therefore, I'd like to make sure both sides have ratcheted forwards

I don't think that a device can ensure that the other side doesn't get
compromised. Even if it rotates keys, there are plenty of ways that a well
meaning implementation could fail to erase them: copying GCs, swap,
hibernation, coldboots, even hypervisor tricks like moving VMs between
machines.

And I don't think the device can ensure that the keys that it writes to
flash aren't used to protect sensitive data without application-level
support. Consider a device that does a KeyUpdate and gets a KeyUpdate in
reply before sleeping. However, just after echoing the KeyUpdate, the other
side says "oh, and by the way, here are the battle plans...". Those plans
would be encrypted with keys that the device just wrote to flash. So there
has to be an application-level concept of "we're rotating keys now because
I'm going to sleep. These keys are only for authenticating another
KeyUpdate when I wake, don't send me anything." Once you have an
application-level concept like that then you don't need an special
KeyUpdate ack system at the TLS level because the KeyUpdate messages are
sequenced with the application data already.

> ratcheted past all the keys that could reveal prior plaintext.

So you're worried that the server might not notice that a device has closed
a connection and so keep the keys in memory? Why didn't it notice? Because
an attacker cut the communication? If so, couldn't the attacker cut
communication just before the KeyUpdate and achieve the same thing?

Or are you assuming that we can't trust an implementation to erase keys
when a connection closes, but it will erase them for a KeyUpdate or a
bidirectional close? If so, I don't see why that's clearly true. It could
be true in practice, but I suspect that many implementations will do the
same thing in both cases. (And that, even if they try, they might not be
able to securely erase the keys because of swapping etc.)

> and issuing a "kill all sessions" command.)

That suggests that you're worried about an active attacker cutting
communications. But why would such an attacker let you open a new session?

> and we don't even want the device to have to know about the audit

I think that this is the most interesting case. I would like to think that
IoTish devices would care this much about doing the right thing, although I
suspect we're more likely to get more fodder for Matthew Garrett (
https://mjg59.dreamwidth.org/43486.html).

I would still tend towards not including the generation because I don't
believe that it's going to be used. But if, in a blaze of optimism, people
think it will, I'm not going to be too upset.

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 19 Aug 2016 22:29:50 +0100

On 19/08/16 19:05, Adam Langley wrote:
> I think that this is the most interesting case.

And for me, the dodgiest, by far. The scope for an "auditor"
(what is that?) actually being an attacker is IMO way too
high to consider standardising that kind of feature and any
idea that it'd involve informed consent of someone seems to
me fictional.

I'd be opposed to that fwiw, as an individual participant.

As an AD, I'd look excruciatingly closely at the process for
demonstrating that there's a real WG and IETF consensus for
that kind of feature and that its potential for conflicting
with other BCPs and well established IETF positions is very
carefully considered.

S.

---

From: Keith Winstein <[email-masked]>
Date: Fri, 19 Aug 2016 20:35:10 -0700

> hibernation, coldboots, even hypervisor tricks like moving VMs between

Sure. This is true of every forward-secret mechanism -- I don't think
KeyUpdate is unique. As you probably know better than me, the hope of
PFS is that key deletion (of the keys that can decrypt the ciphertext)
happens in the window after the ciphertext is received and before the
keys are compromised. But obviously it's different to have a protocol
that supports PFS vs. actually deleting the keys.

> side says "oh, and by the way, here are the battle plans...".

Sure, you're right about new data that the server sends on its own
initiative after a ratchet. You do still protect all the data that was
sent in the prior epoch.

> Those plans
> I'm going to sleep. These keys are only for authenticating another KeyUpdate
> when I wake, don't send me anything."

Obviously, in the real world the mechanism is much more useful if it
works with typical unmodified webservers and TLS terminators. If I
wanted to build my own application-layer protocol, I wouldn't be here.
(Mosh *has* a secure bidi close...)

> Or are you assuming that we can't trust an implementation to erase keys when
> a connection closes, but it will erase them for a KeyUpdate or a
> bidirectional close?

I send you a close_notify, and you send me a close_notify. Have you
stopped trusting input from my key? Have you deleted my key? There's
no way for me to tell. That's the worry. If I send you a KeyUpdate,
and you increment your receive_generation and tell me, then I know you
SHOULD have deleted the prior key. That's the most I can really ask
for.

-Keith

---

From: Keith Winstein <[email-masked]>
Date: Fri, 19 Aug 2016 20:40:12 -0700

> idea that it'd involve informed consent of someone seems to

I appreciate the sensitivity of this issue to the WG. My read of your
email is that there's a concern that by standardizing a protocol
mechanism that allows a node to learn when its own KeyUpdate has
happened, the WG would imply approval of features that permit
the bad kind of eavesdropping. Here's why I don't think that's the case:

Our PR is for a piggyback integer field to provide security property
P3: "An implementation can learn that its request to rekey its
outgoing traffic has been read by the other side."

KeyUpdate is an *instruction* to the other side: "please update my key
in a forward-secure manner." We think some implementations will want
to know that the instruction has been carried out. And there's an easy
opportunity to do that here as a piggyback, without any extra protocol
messages.

A node will naturally care more about forward secrecy, and
confirmation of a forward-secure ratcheting event, the more it has
reason to suspect the keys might later be exposed to a third party. In
Berlin, I described three escalating cases: the (1) node going to
sleep, (2) node closing a connection without a mechanism for secure
bidi close, and (3) node that itself intends to release keys to a
read-only auditor after a ratchet is complete.

By "read-only auditor," we mean a curious person or security
researcher who owns an IoT device and wants to know what the heck it
is sending out of their house, where the device doesn't want to allow
its owner to add trusted certificates for an MITM. (This describes
most such devices today.)

Obviously I think it's valuable to make this mechanism available for
IoT device manufacturers. Having talked to several manufacturers, I'm
cautiously optimistic that some would use this. But the WG doesn't
have to take a position on this. These use cases are up to
implementers. There's nothing stopping an implementer today from
releasing session keys, or allowing complete MITM, as is the case in
the browser context with user- or admin-installed root CA
certificates. The TLS WG hasn't opined on these either.

To restate: Property P3 allows a node to learn that its KeyUpdate
instruction has actually happened, which in our view is useful and a
strict benefit over the status quo. It's also orthogonal to the issue
of unbounded write obligations raised in this thread.

-Keith

---

From: Subodh Iyengar <[email-masked]>
Date: Tue, 23 Aug 2016 18:47:32 +0000

For people that currently use keyupdates or who are planning to use key updates, which layer are you planning to trigger a key update? Would the TLS implementation itself trigger the update or would the application trigger it? For renegotation, I believe it was mostly triggered by the application. 

For the use cases you mentioned Keith, they seem to be specific to application triggered key updates, i.e. key updates do not mean anything to the TLS layer apart from I got a key update and I must change keys. The fact that other side has thrown away it's key is only meaningful to the higher layer protocol. I imagine protocols like HTTP would not add these semantics, and these semantics would be added to very specific IoT protocols? Would the scope of the auditor be defined as a part of that protocol, or does it need to be defined as a part of TLS?

If key update is an application triggered mechanism, does the generation identifier need to be an integer to be understood by the TLS layer or could it also be an opaque identifier sent by the application. It would be much simpler not to have to deal with the requirements of consistency at the TLS layer and would make the API simpler.

Subodh
________________________________________
From: TLS [[email-masked]] on behalf of Keith Winstein [[email-masked]]
Sent: Friday, August 19, 2016 8:40 PM
To: Stephen Farrell
Cc: Adam Langley; [email-masked]
Subject: Re: [TLS] KeyUpdate and unbounded write obligations

-Keith

_______________________________________________
TLS mailing list
[email-masked]
https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_tls&d=DQICAg&c=5VD0RTtNlTh3ycd41b3MUw&r=h3Ju9EBS7mHtwg-wAyN7fQ&m=dPWRCHpTfdtxfXYBMZF__UyOa7wszKFnA6criwmMDHI&s=E7sRstn6vNQHPiX3CXAa6BbWSWtMW7VKtN4f3yblZ5U&e=

---

From: Judson Wilson <[email-masked]>
Date: Tue, 23 Aug 2016 22:45:07 -0700

>
>
> For the use cases you mentioned Keith, they seem to be specific to
> application triggered key updates, i.e. key updates do not mean anything to
> the TLS layer apart from I got a key update and I must change keys. The
> fact that other side has thrown away it's key is only meaningful to the
> higher layer protocol. I imagine protocols like HTTP would not add these
> semantics, and these semantics would be added to very specific IoT
> protocols? Would the scope of the auditor be defined as a part of that
> protocol, or does it need to be defined as a part of TLS?
>
>
It makes more sense to have the TLS layer disseminate information about
which keys are in use, rather than have the higher layer try to infer it.
Conceivably, either endpoint can cooperate with a user to by giving the
user the keys that are no longer in use on the channel. (Endpoints can
already do this, but without any guarantee that the keys are not in use.)
With the very small piggyback that Keith proposed, a client application
could get an assurance which keys are no longer in use, without any changes
on the server side. TLS termination devices, load balancers, reverse
proxies, and HTTP servers would all be compatible without any further
changes - the format on the wire would be unchanged.

I also believe that we all agree that adding a full auditing spec is far
beyond the scope of TLS. However, with this small change to KeyUpdate,
there might be opportunities to add such a feature to IoT devices without
having to re-engineer the front end of a cloud application - the wire
compatibility is a really nice feature in this regard. An IoT device could
possibly be compliant with some future auditing spec while using plain-old
HTTP and TLS 1.3 in the cloud.

If key update is an application triggered mechanism, does the generation
> identifier need to be an integer to be understood by the TLS layer or could
> it also be an opaque identifier sent by the application. It would be much
> simpler not to have to deal with the requirements of consistency at the TLS
> layer and would make the API simpler.

I don't think this introduces any kind of consistency issues at the TLS
layer.  The receiver simply needs to keep count of the receive key
generation, and put this number (or even a numerically smaller one) in any
subsequent outgoing KeyUpdate.

It would also be sufficient to transmit a boolean indicating whether the
KeyUpdate message is an initiating message, or a response message (I am
omitting some details), but that would not work well with mitigating this
multiple KeyUpdate backlog issue which is the original topic of this thread.

On Tue, Aug 23, 2016 at 11:47 AM, Subodh Iyengar <[email-masked]> wrote:

> For people that currently use keyupdates or who are planning to use key
> updates, which layer are you planning to trigger a key update? Would the
> TLS implementation itself trigger the update or would the application
> trigger it? For renegotation, I believe it was mostly triggered by the
> application.
>
> For the use cases you mentioned Keith, they seem to be specific to
> application triggered key updates, i.e. key updates do not mean anything to
> the TLS layer apart from I got a key update and I must change keys. The
> fact that other side has thrown away it's key is only meaningful to the
> higher layer protocol. I imagine protocols like HTTP would not add these
> semantics, and these semantics would be added to very specific IoT
> protocols? Would the scope of the auditor be defined as a part of that
> protocol, or does it need to be defined as a part of TLS?
>
> If key update is an application triggered mechanism, does the generation
> identifier need to be an integer to be understood by the TLS layer or could
> it also be an opaque identifier sent by the application. It would be much
> simpler not to have to deal with the requirements of consistency at the TLS
> layer and would make the API simpler.
>
> Subodh
> https://urldefense.proofpoint.com/v2/url?u=https-3A__www.
> ietf.org_mailman_listinfo_tls&d=DQICAg&c=5VD0RTtNlTh3ycd41b3MUw&r=
> h3Ju9EBS7mHtwg-wAyN7fQ&m=dPWRCHpTfdtxfXYBMZF__UyOa7wszKFnA6criwmMDHI&s=
> E7sRstn6vNQHPiX3CXAa6BbWSWtMW7VKtN4f3yblZ5U&e=
>

---

From: Keith Winstein <[email-masked]>
Date: Wed, 24 Aug 2016 16:01:45 -0700

Hi Subodh,

Interesting points.

On the form of the generation identifier: The draft does already
specify the generations as integers (traffic_secret_N, N+1, etc.), and
the semantics of a KeyUpdate are that when you receive one, you
increment the generation of the receive key. So the proposed
"receive_generation" field is really just echoing the generation
number back. I could imagine a different system where the KeyUpdate
instead includes an opaque identifier, and the receiving
implementation is then supposed to echo back the most recent opaque
identifier that it got. That would also provide Property P3, and so I
would be totally fine with it. But now we're talking about adding
*two* fields to a KeyUpdate (the sender's opaque identifier, and also
an echo of the most recently received opaque identifier), instead of
one field, so I'd be surprised if there were more consensus around
this alternate approach!

On the API that a TLS implementation would expose: Obviously the WG
doesn't have to specify this, but here are three APIs I could imagine:

(1) No change to current APIs. The TLS implementation itself triggers
KeyUpdate when it wants to (e.g. per recommendation on when the
underlying cipher wants to be rekeyed), but doesn't expose this to the
application.

(2) Fire-and-forget. The TLS implementation exposes a
`rekey_session()` function, which initiates a KeyUpdate. [If we adopt
the proposal described earlier in this thread, maybe there's a boolean
parameter about whether to request a reciprocal rekey from the other
side...]

(3) Fire-and-later-check. The TLS implementation exposes #2 above, but
also `tls_session_generations()`, which returns a pair of integers
giving the current sending and receiving generations.

Any application we might want to build can be built on top of #3.

Cheers,
Keith

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 25 Aug 2016 07:23:44 +0300

> one field, so I'd be surprised if there were more consensus around

The generations are not specified as integers. It is just some abstract
sequence (nowhere in protocol is that generations are integers used).

And echoing identifiers doesn't work. The key updates can cross in
flight, so neither is after one another.

> underlying cipher wants to be rekeyed), but doesn't expose this to the

The intended application of KeyUpdate is mostly this, with optional
knobs controlling the frequency of rekeying.

> parameter about whether to request a reciprocal rekey from the other

Due to design, one can't do a reciproal rekey.
 
> Any application we might want to build can be built on top of #3.

Nope, the KeyUpdate is designed to deal with arbitrary latency in
order to fully decouple the direction (any coupling there would lead
to API problems, which apparently are more major than I initially
thought).

And if that is combined with request-response protocol, if you just
send a KeyUpdate without application data, the response will NEVER
come.

-Ilari

---

From: Keith Winstein <[email-masked]>
Date: Thu, 25 Aug 2016 12:31:53 -0700

> sequence (nowhere in protocol is that generations are integers used).

The current draft requires that upon receipt of a KeyUpdate, "the
receiver MUST update their receiving keys and if they have not already
updated their sending state up to or past the then current receiving
generation MUST send their own KeyUpdate prior to sending any other
messages."

This requires the generation counts to be comparable for inequality.
Implementations will have to keep track of the generations, or the
difference between them, in an integer counter. (How else would you do
it?)

> Due to design, one can't do a reciproal rekey.

Hmm, there must be some misunderstanding. In the current draft,
*every* time a node receives KeyUpdate #N (rekeying the incoming
direction), it MUST reciprocate by rekeying its outgoing direction
unless it has already sent at least N KeyUpdates. Current text: "This
mechanism allows either side to force an update to the entire
connection."

> to API problems, which apparently are more major than I initially

Not quite sure what you're disagreeing with. Our proposal is also
designed to deal with arbitrary latency. It's a field piggybacking on
the otherwise-unmodified KeyUpdate messages.

-Keith

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 28 Aug 2016 10:53:14 -0700

I'd like to close this discussion if we can.

I'd prefer to keep things as simple as possible here and from that
perspective, I think any indicator from side A to side B that it wants a
key change over and above the KeyUpdate is extra complexity. I do, however,
want to retain the property that one side can ask the other one to rekey
[0]. I believe we can get this by modifying the rule in the spec by treating
a run of KeyUpdates as a single generation.

Specifically.
"Upon receiving a KeyUpdate, the receiver MUST update its receiving
keys. If the receiver has sent any data records since receiving the
last KeyUpdate it MUST also increment its min_send_generation counter
by 1. Otherwise, the min_send_generation MUST remain unchanged. Prior
to sending a record, if min_send_generation is greater than the
current sending generation, the sender MUST first send a KeyUpdate."

This still leaves open the question of whether we should advertise the
current
receiving generation or have two ladders, but I believe those are
orthogonal to
David's issue. Does anyone see a reason why this won't work?

-Ekr

[0] My reasoning here is that it allows implementations who learn about new
limits for a cipher or are otherwise more conservative than their peer to
get more aggressive updates even if it's the other side doing most of the
sending.

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 28 Aug 2016 21:41:06 +0300

> current sending generation, the sender MUST first send a KeyUpdate."

Timing- and propagation-wise, it looks workable (also, could be done
with two flags[1], no need for counter).

Yes, this causes lots more desync between sides, but existing
mechanism needed to cope with that already.

However, one problem: Because both sides take their keys from one
ladder, if one side is behind the other, one can extract past keys
of other side from the one that is behind (running separate ladders
in both directions[2][3] would fix this).

[1] Specifically:
- last_tx_key_update: Was the last record I sent a KeyUpdate?
- next_tx_key_update: Will the next record I send be a KeyUpdate?

[2] Any current implementation likely already has per-direction
traffic secrets (at least mine certainly does). 

[3] Allowing multiple steps at once would open things up for DoS
attacks.

-Ilari

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 28 Aug 2016 11:50:27 -0700

> in both directions[2][3] would fix this).

Yes, I agree separate ladders would fix this. I don't necessarily object to
this
change, but I'm not sure it's that big a deal either, because you really
only get
into this case when there's a big asymmetry in sending rate, so much that
one side wants to send multiple updates before the other side has sent
any data at all.

Note: it's also possible to avoid the rollback problem with the existing
single-ladder system: when you send a key update you compute:

traffic_secret_N+1
read_key_N+1
write_key_N+1

You then discard traffic_secret N, write_key_N, but key read_key_N, so if
you
are M updates ahead of the other side, you have M read keys outstanding,
but these cannot be used to produce the write keys. However, this probably
isn't simpler than just running two ladders if we think this is important.

-Ekr

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 29 Aug 2016 20:30:05 +0300

> > with two flags[1], no need for counter).

I tried to implement this, and probably got it wrong somehow:

Test setup consisists of multi-Gbps stream in one direction and fairly
slow one in another. Very low latencies. Also, TLS stack can't do new
flights.

1) The fast stream eventually (~5min) reaches the rekey threshold,
   triggering a KeyUpdate.
2) The other side receives the KeyUpdate. Since last record it sent
   was not KeyUpdate, it marks KeyUpdate to be sent.
3) The slow stream transmits something. Since KeyUpdate is pending,
   it is sent, along with something else (so last record is not a
   KeyUpdate.
4) The fast sender receives the KeyUpdate. Since last record it
   sent was not a KeyUpdate (it has sent more data since) it
   schedules a KeyUpdate to be sent.
5) Almost immediately new data arrives, and since KeyUpdate is pending,
   it is sent, along with something else (so last record is not a
   KeyUpdate).
6) Goto 2.

The result is ping-pong of KeyUpdate's that starts as soon as one side
sends one (at rate determined by the send rate of the slower peer,
which still can be pretty high).

-Ilari

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 29 Aug 2016 10:32:52 -0700

> which still can be pretty high).

Did you use the "flags" approach or the generation approach, since it seems
like in the latter approach, at that point it would be in send=2, recv=1 and
it wouldn't update.

-Ekr

---

From: Adam Langley <[email-masked]>
Date: Mon, 29 Aug 2016 11:11:12 -0700

> one side wants to send multiple updates before the other side has sent

I think that cases where there's a big asymmetry in sending rates are
in the majority.

> isn't simpler than just running two ladders if we think this is important.

That works but I agree that splitting the ladders is nicer and I think
that we should do that.

Cheers

AGL

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 29 Aug 2016 12:15:08 -0700

> I think that cases where there's a big asymmetry in sending rates are

Well, it has to be more than just asymmetric in terms of traffic volume,
but I take
your point.

> That works but I agree that splitting the ladders is nicer and I think

I'm fine with that. Unless someone objects soon I'm going to prepare a PR
to do this
along with the rule above (both changes are required).

-Ekr

---

From: Russ Housley <[email-masked]>
Date: Mon, 29 Aug 2016 18:06:29 -0400

Eric:

> Yes, I agree separate ladders would fix this. I don't necessarily object to this
> change, but I'm not sure it's that big a deal either, because you really only get

I can think of many situations where one side sends a lot more data than the other.

> You then discard traffic_secret N, write_key_N, but key read_key_N, so if you

That seems to work.  However, I think that splitting the ladders seems to marry well with the many situations where one side sends a lot more than the other.  So, I suggest that we split the ladders.

Russ