Subject: [tcpinc] Why the protocol asymmetry?

From: Bryan Ford <[email-masked]>
Date: Wed, 4 Nov 2015 14:52:54 +0900

Following up on my comment in the tcpinc meeting, I’m worried that both tcpinc proposals, as well as the TCP-ENO design, are baking in an assumption 
that there “need” to be asymmetric passive-active or A-B roles - and introducing a lot of complexity in the process - whereas a much simpler and cleaner alternative might be simply to remain more design-consistent with TCP by consistently treating the endpoints’ roles symmetrically.

A symmetric protocol definition certainly seems to be a feasible option for tcpcrypt, as discussed below, and as far as I can tell would only simplify the tcpcrypt protocol.  A symmetric definition might not really be an option for USE-TLS merely due to the goal of historical compatibility with (and reuse of) TLS, which does have asymmetry baked in fairly fundamentally.

Outlining how I envision tcpcrypt might be made purely symmetric, and what the implications are (i.e., how that would simplify the protocol):

- The most obvious simplicity benefit is that the protocol needs no special mechanisms in order to make TCP simultaneous open work.  In particular, the tie-breaking (or whatever else it should be named) feature definitely adds complexity, which could be eliminated entirely from tcpcrypt (and perhaps made optional in TCP-ENO).

- The tie-breaking mechanism obviously carries a risk of failure - i.e., if both sides choose the same role they have to “fail open” back to unencrypted communication.  Which I admit is not completely a deal-breaker since we’re talking about opportunistic encryption in the first place, but it still adds both protocol complexity and behavioral unpredictability that makes me sad.

- The first place role-asymmetry comes into the tcpcrypt spec itself is negotiation, section 3.3, where "the last spec identifier in the SYN segment of host B” is the winner.  It’s easy to create a symmetric but still deterministic version of this.  For example: (1) each endpoint sends in its ENO SYN packet a list of spec identifiers in ascending preference order; (2) from each list take the LAST spec-identifier that also appears in the other list; and (3) the spec-identifier chosen is the numerically largest of those two.  This approach has the nice properties that (a) whenever both parties happen to agree on the “most preferred” spec that they both support, they’ll always get that one; and (b) if they do disagree, they’ll tie-break by picking the one that is probably most “recent/modern” of the two, assuming spec-identifiers tend to get assigned over time from lower to higher numbers.  At any rate, no A/B roles needed to achieve consensus.

- Key exchange (sec 3.4): each party sends the other an init packet of identical form init = {INIT_MAGIC, sym-cipher-list, N_me, PK_i}, where “me” is A for the A->B message and is “B” for the B->A message.  They use the two sym-cipher-lists to pick one deterministically and symmetrically in the same fashion as for spec-identifier agreement above.  

- The two parties now compute two directional pre-master secrets (PMSs) and one undirectional PMS.  Party A computes its directional PMS_A based on param_A := { “directional”, eno_A, eno_B, init_A, init_B }, and computes its other directional PMS_B based on param_B := { “directional”, eno_B, eno_A, init_B, init_A }.  Party B computes the same directional PMSes only with A and B swapped (i.e., each has a PMS_me_to_you and a PMS_you_to_me).  Both parties compute the undirected PMS, call it PMS_U, based on param_U := { “undirected”, min(eno_A, eno_B), max(eno_A, eno_B), min(init_A, init_B), max(init_A, init_B) }, for appropriate “min”/“max” functions representing pretty much any total-ordering (e.g., lexicographic order) on eno-lists and init-packets.  The tcpcrypt protocol itself will mainly (perhaps exclusively) use the directional PMSes, but the undirected PMS might be useful to provide an undirected session identifier (perhaps alongside directed session identifiers) to applications.

- Now the session secrets are similarly computed directionally but otherwise in the same way as they currently are: e.g., party A computes ss_AtoB[0] := PRK_AtoB and ss_BtoA[0] := PRK_BtoA; party B performs exactly the same computations but with A to B swapped.  ss_AtoB[i] is used form master keys mk_AtoB[j] which are used to encrypt and integrity-protect traffic flowing from A to B, while ss_BtoA[i] is used to form master keys mk_BtoA[j] which are used to encrypt and integrity-protect traffic flowing from B to A.  But again this is fully symmetric, so neither party knows or cares whether it is “A” or “B”; it just thinks of “me to you” and “you to me” session secrets and traffic flows.

- The re-keying mechanism and most of the rest of the tcpcrypt spec, as far as I can tell, is unaffected by a change to symmetric behavior (except obviously for the collapse of INIT1 and INIT2 into INIT, etc).

So again, it feels to me like this all would strictly simplify the protocol, make it more consistent with TCP’s symmetric design style, and would make TCP simultaneous open “just work” with no extra tie-breaking complexity or attendant risks of fail-open.  Is there an identifiable reason the current asymmetric behavior is necessary or even advantageous?

Thanks
Bryan

---

From: David Mazieres <[email-masked]>
Date: Wed, 04 Nov 2015 03:50:54 -0800

Bryan Ford <[email-masked]> writes:

> So again, it feels to me like this all would strictly simplify the
> protocol, make it more consistent with TCP’s symmetric design style,
> and would make TCP simultaneous open “just work” with no extra
> tie-breaking complexity or attendant risks of fail-open.  Is there an
> identifiable reason the current asymmetric behavior is necessary or
> even advantageous?

Well, first, it's not at all clear that the new protocol will be
simpler.  For example, how does session resumption work with two session
IDs?  Having two session IDs could also make things a lot more
complicated for applications.  E.g., if you are storing session IDs in
logs to compare after the fact, do you now have to store two session
IDs?  If you are using voice authentication, do you now have to read two
large hex numbers over the phone?  If you are using PAKE authentication
as in the original tcpcrypt paper, do you have to authenticate two
session IDs?

Second, just because currently we are using ECDHE does not mean that we
always will be.  E.g., the NSA "suite B" has deprecated elliptic curve
crypto for top secret documents.  Who knows what this means--it could
mean ECDHE is insecure, it could be some sort of weird reverse
psychology, or it could be that we need all new curves.  Nonetheless, if
it turns out we want a TCPINC option to use RSA, then again there will
be an inherent asymmetry in the key exchange.

Third, the working group has been unable to identify a good application
of simultaneous open that A) would benefit from tcpinc, and B) is harmed
by the current b bit mechanism.  Simultaneous open is much trickier to
use in practice than in theory, with a result that it is usually a last
choice anyway.  Often the P2P apps doing it have their own encryption.
And on top of that, often the connection has to be brokered in some way
that makes it easy to assign the b bit.

I've actually spoken to two different people who have basically told me
the same thing, that they managed to get simultaneous open working but
didn't end up using it in their product because it was too finicky.  The
only use case in the wild we have identified is ICE in firefox, and then
it is only used if UDP does not work, and would want to disable tcpinc
anyway.  By contrast, there's plenty of RSA use in the wild.  And
someday we may want post-quantum options.  So even if the current TCPINC
drafts are exclusively ECDHE, I'd be uncomfortable forever ruling out
public key encryption, whether by RSA or post-quantum lattice-based
ciphers.  Oh, and even if we move to DH over Zp, RSA becomes an
attractive option for server performance.

David

---

From: Kyle Rose <[email-masked]>
Date: Thu, 5 Nov 2015 09:15:49 +0900

> IDs?

As Bryan indicated, you could introduce a bidirectional PMS from which
a bidirectional SID could be derived. If there is more than one key
exchange (see below), order the outputs of the key exchange
lexicographically, and use that as the PMS.

> Having two session IDs could also make things a lot more
> complicated for applications.

I don't know that there's any particular reason to have unidirectional
SIDs, only a way to construct a single SID in a way that does not
depend on designating either end of the connection as A or B.

> always will be.

If you're using RSA, both sides could encrypt a secret and then order
the two lexicographically to make the PMS. Of course, you'd have to
agree to use RSA or ECDHE in advance, but you're already doing that
via TCP-ENO.

> by the current b bit mechanism.

Sure. All the above having been said, I don't know how much effort
should be put into supporting simultaneous open; my instinct, however,
is to support it transparently if it doesn't overly complicate
matters. I don't think these changes overly complicate the protocol.

Kyle

---

From: David Mazieres <[email-masked]>
Date: Thu, 05 Nov 2015 10:44:31 +0900

> depend on designating either end of the connection as A or B.

But then how do you do authentication?  You need a way of saying thing
slike, "this end of this connection speaks for this user," which means
you need to name the connection and the end.  It might help if someone
re-did the examples from the API document under the proposed symmetric
scheme.

> agree to use RSA or ECDHE in advance, but you're already doing that

But you don't want both sides to encrypt a secret--you only want one
side to encrypt a secret with RSA.  Otherwise you are potentially adding
another round trip time in the normal case, not to mention expending a
lot of unnecessary CPU time that can limit connections per second on a
busy server.

> matters. I don't think these changes overly complicate the protocol.

I think we are all in favor of supporting it transparently if that can
be done so for free.  But if doing so potentially means adding round
trip times, or preventing public key encryption from being used for key
exchange, or making application-level implementation of authentication
trickier, then we have to make a trade-off.

Section 6.1 of the ENO document lays out four levels of TCP-SO support
and picks one of them.  We are open to arguments for other design
points, but it would require either A) demonstrating a need for
transparent simultaneous open, or B) demonstrating (via working out
packet flows) that the cost would be negligible.  So far, proposals have
all done at least one of the following undesirable things:

  * Consume a lot of option space even in the normal (three-way
    handshake) mode of operation, by including a tie breaker in every
    active open SYN,

  * Prevent use of public key encryption in future specs (by requiring
    symmetry),

  * Add extra round trips and CPU time (by requiring twice the number of
    public key ciphertexts),

  * Complicate the API on top of which applications will implement
    authentication by getting rid of roles and adding extra
    uni-directional session IDs, and/or

  * Require each encryption spec to devise its own means of coping with
    simultaneous open, again dirtying the application-level abstraction.

In my opinion, none of those trade-offs is worth it.  But if I'm missing
something and there's a cheap way of getting transparent simultaneous
open (what we call level 4 in the ENO draft), then I'd love to hear it.

David

---

From: Bryan Ford <[email-masked]>
Date: Sat, 7 Nov 2015 13:41:55 +0900

> re-did the examples from the API document under the proposed symmetric

There are two simple ways of handling authentication, in this scenario, depending on whether and how much you care about distinguishing “which endpoint is which” in the process.

If you DO care about distinguishing the endpoints: authenticate based on an ordered pair of the session identifiers or (based on a hash of that ordered pair if you care about its size).  For example, if A and B are the participants involved and we call the two directional session IDs “AtoB” and “BtoA”, then A authenticates its end by signing the (optionally hashed) ordered pair {AtoB, BtoA}, and B authenticates its end by signing the (optionally hashed) ordered pair {BtoA, AtoB}.

If you DON’T care about distinguishing the endpoints: as Kyle suggests, just lexicographically sort the AtoB and BtoA session IDs, and either authenticate that pair or a hash of it if you care about size.  Then both endpoints are simply saying, “I attest that one of the endpoints of this session speaks for me”, without saying which one.  This can sometimes be desirable: e.g., some [partially-]deniable authentication protocols depend on precisely this property.  If you are one of the parties (e.g., A), you presumably know who you are and only care about verifying who the other party is.

I don’t have a strong position on which of these approaches is better, but it seems nice that the symmetric protocol design makes either or both of them trivial to accomplish, which may depend on the needs and requirements of the application.

> lot of unnecessary CPU time that can limit connections per second on a

Where would this create an extra round-trip?  To me everything seems exactly the same in terms of round-trips.  In the client/server “common case” scenario:

1. A (client) RSA-encrypts a secret S_A and sends it to B as part of its INIT packet.

2. B (server) RSA-encrypts a secret S_B and sends it to A as part of its INIT packet.  B now already has all the information it needs to construct a joint master secret: e.g., it uses the ordered pair {S_A,S_B} to form the master secret for the AtoB direction, and uses the distinct ordered pair {S_B,S_A} to form the master secret for the BtoA direction.  B can start using this master secret immediately to start encrypting and sending data to A without waiting for further communication from A.  Exactly the same as in the ECDH case.

3. A (client) finally receives B’s encrypted S_B decrypts it, and can now compute the same two master secrets and start sending encrypted data to B.  Again, exactly as if A had been waiting for an ECDH public-key from B with which to do DH key exchange.

Of course, if A wants to send encrypted data to B from the very first message (#1 above) it needs to play “zero-round-trip” games just like TLS 1.3 presumably using state cached from a previous session, but that’s another topic and seems like it still would work the same way whether based on ECDH or a pair of RSA-encrypted secrets.

Regardless, I’m not suggesting that we “should” bother specifying or implementing the RSA variation unless the WG feels it’s worth the trouble - but at any rate it seems like the option is there and presents no additional difficulty beyond ECDH.

> trickier, then we have to make a trade-off.

I’m still waiting to hear how the symmetric design makes anything trickier, either for tcpcrypt itself or for the application using it. ;)

> all done at least one of the following undesirable things:

I think it may be reasonable to keep the "tie-breaker bit” or something equivalent in the TCP-ENO specification, because some protocols we might want to negotiate with it (e.g., TLS) may have baked-in assumptions about a passive/active asymmetry.  But if the two endpoints both support and happen to decide on tcpcrypt, it would be nice if they simply never needed to use the tie-breaker bit for anything, and hence don't have to run the risk of things breaking even in the (however potentially rare) case of simultaneous open.  The fact that other protocols break TCP’s symmetric model doesn’t mean that yours needs to break it as well. ;)  

And I think it’s more important for tcpcrypt not to break TCP’s model precisely because tcpcrypt is (rightly) positioned as something readily implementable in the kernel basically as an extension to the TCP stack itself.  Creating another user-space protocol with baked-in passive/active asymmetry like TLS would not be inconsistent with existing practice (e.g., TLS), but creating a protocol intended for kernel-space implementation with such a baked-in asymmetry assumption would be a much bigger divergence from the tradition of kernel-space TCP extensions.

> open (what we call level 4 in the ENO draft), then I'd love to hear it.

How to do that seems pretty clear to me, but perhaps I need to go do a more thorough reading of the TCP-ENO draft and suggest specific text.  I’ll try to do that as soon as I have a moment.

Cheers
Bryan

---

From: David Mazieres <[email-masked]>
Date: Fri, 06 Nov 2015 22:05:45 -0800

Bryan Ford <[email-masked]> writes:

> There are two simple ways of handling authentication, in this
> scenario, depending on whether and how much you care about
> distinguishing “which endpoint is which” in the process.

Exactly.  The fact that applications currently have to chose between
multiple ways of doing this means they may get it wrong.  Whereas having
a session ID and a role is pretty simple.

Big picture, the goal is that we will basically get TCPINC right, which
means most vulnerabilities will arise out of misuse of the API.  So we
really want to keep it as simple as possible.

> Where would this create an extra round-trip?  To me everything seems
> exactly the same in terms of round-trips.  In the client/server
> “common case” scenario:
>

And where did A get B's public key?  By that point an asymmetric
protocol would probably have allowed B to send data.  Besides, why pay
the price of two RSA decryptions when you only need one?

> And I think it’s more important for tcpcrypt not to break TCP’s model
> precisely because tcpcrypt is (rightly) positioned as something
> readily implementable in the kernel basically as an extension to the
> TCP stack itself.

But how is TCP's model symmetric?  Simultaneous open is this weird
fringe case that didn't even work until we had NATs and firewalls to
suppress SYNs that would otherwise trigger RST packets.  Even now it
basically only works through particular kinds of NATs.  We can barely
seem to find any examples of its use in practice.  Other than that, TCP
is full of asymmetries on both the connection setup and shutdown.
Someone with more historical perspective can correct me if I'm wrong,
but it doesn't appear as though symmetry was a particular design goal of
TCP.

> How to do that seems pretty clear to me, but perhaps I need to go do a
> more thorough reading of the TCP-ENO draft and suggest specific text.
> I’ll try to do that as soon as I have a moment.

I think the best way to work through these things is with packet flow
diagrams.  For example, if your symmetric RSA example looks something
like this:

  A -> B:  SYN(ENO)
  B -> A:  SYN-ACK(ENO)
  A -> B:  (ENO) PKA
  B -> A:  PKB, {NB}_PKA
  A -> B:  {NA}_PKB
  A -> B:  data
  B -> A:  data

Then it takes 2.5 round trips before B can send any data to A (using
keys derived from NA, NB, PKA, PKB), vs. 1.5 in the simpler protocol
where the session keys are derived from just PKA and NB (plus probably
some other nonces not shown):

  A -> B:  SYN(ENO)
  B -> A:  SYN-ACK(ENO)
  A -> B:  (ENO) PKA
  B -> A:  {NB}_PKA
  B -> A:  data
  A -> B:  data

The other major advantage of the second (asymmetric) diagram is that it
supports very high connection rates at the passive opener, because with
low exponents RSA encryption can be much faster than decryption.  So the
crypto for the symmetric RSA protocol isn't "just" twice as expensive on
the server, but on my machine about 33x more expensive.  The discrepancy
grows linearly with modulus size, too, since decryption is O(n^3) and
encryption O(n^2).

David

---

From: Bryan Ford <[email-masked]>
Date: Sat, 7 Nov 2015 15:26:25 +0900

To follow up on specific ways to evolve the TCP-ENO spec to make it compatible with symmetrically-designed protocols like TCP could be (and IMO should be for consistency with TCP and to avoid breaking simultaneous-open):

- Section 2, Introduction: insert “, if needed by the negotiated protocol,” somewhere appropriate in bullet 6 at the very end of this section.

- Section 3.1: Simply document this role-defining function as an optional capability of TCP-ENO negotiation, and move this section somewhere later - e.g., just after (or into a subsection of) the current section 3.3, where the spec defines the suboption containing the tie-breaker bit.  Then the currently-specified general sub option (the one with high-nibble of 0) would in turn become optional in general; required only when at least one of the listed encryption-scheme specs requires the tie-breaking functionality and/or the application-aware (aa) bits.

- Section 3.2: the basic ENO-presence rules during handshake rules already don't seem to depend on the passive/active role distinction.  In particular, the ENO option presence rules in the section paragraph of section 3.2 seem to be perfectly symmetrical already; the only asymmetry assumption that suggests itself is the way in which the text starting “Depending on whether a host…” elaborates on those rules.  And that can be fixed trivially simply by clarifying how the rules work in the (perhaps rare) simultaneous-open case, i.e., by adding a third bullet-point that looks something like:

	* If both endpoints play the active role, e.g., in the case of TCP simultaneous-open, then each endpoint will first send a SYN packet (without the ACK flag set) containing ENO options; then upon receiving the other endpoint’s SYN packet, each endpoint will send an ACK packet containing an empty ENO option in order to confirm receipt of the other endpoint’s ENO options.

- The “negotiated spec” paragraph needs to be adjusted as I proposed in my earlier E-mail: e.g., from each list of supported specs, take the last spec from each list that is present in both lists, and if they are different, just choose (say) the numerically higher one, instead of choosing the one proposed by host B.

- Just delete the paragraph that start “When possible, host B SHOULD send only one spec identifier…”

- Change wording slightly here and there in 3.2.1 “Handshake examples” to avoid unnecessarily implying an assumption of active/passive asymmetry.  (The examples can still use asymmetry and refer to active/passive sides in the cases where, like the first, the roles are clearly defined in the example scenario - but just make it clear that those roles are associated with those specific examples.)

- Section 3.4: simply redefine the transcript as being a directional pair of transcripts, one containing the (two) ENO-options one endpoint sent (#s 1-2 in the current spec), the other containing the (two) ENO-options the other endpoint sent (#s 3-4 in the current spec).  These may then be used directionally as I already proposed in the tcpcrypt protocol, or undirectionally by sorting them either lexicographically or via the tie-breaker mechanism (needed only for negotiated protocols that need the tie-breaker).  That is, when the symmetric version tcpcrypt is negotiated via ENO, endpoint A takes the two ENO-transcripts (AtoB, BtoA) and uses them in that order to derive the AtoB master key, and uses the two ENO transcripts in the opposite order (BtoA, AtoB) to derive the BtoA master key.  When TLS is negotiated via ENO, each endpoint takes the two ENO-transcripts and sorts them into A/B roles via the tie-breaker rules, resulting in the same effective behavior as what the ENO spec currently defines in the #1-4 list.

- Section 4.1 should similarly be generalized to allow for both directional and undirected session IDs to be passed to applications.  The cleanest way to do this is probably simply to specify that any spec MUST provide three session IDs to the application: (a) an undirected session-ID, (b) a “me-to-you” session ID, and (c) a “you-to-me” session ID.  The spec must arrange that both application endpoints receive the same undirected session-ID (a); that each endpoint’s “me-to-you” session ID (b) is identical to the other endpoint’s “you-to-me” session ID (c); and that all of these session-IDs are unique with overwhelming probability.  The application can then use whichever of these session IDs are most convenient for the application protocol: asymmetric application protocols might be more likely to use (a) while symmetric protocols might be more likely to use (b) and (c), but that’s the application’s concern.

Those are the only significant changes I see that would be needed to enhance TCP-ENO to support both symmetric and asymmetric use.  Did I miss anything important?

Now for two issues that my closer read-through brought up, which are at least partially orthogonal to the symmetric-mode support:

1. The current section 3.1 doesn’t really state clearly where the “p” bit comes from in Figure 4.  It’s not included in the general sub option specified in section 3.3, so I assume each endpoint is supposed to “infer” both its own p-bit and the other endpoint’s p-bit.  Presumably it’s easy for each endpoint to decide the value of its own p-bit, but how does each endpoint determine the intended value of the other endpoint’s p-bit?  For example, if I consider myself an active opener (p=0), then do I decide that the other endpoint’s p-bit is a 1 if the first TCP packet I get from them is a SYN-ACK, and decide the other endpoint’s p-bit is a 0 if the first packet I get from them is a SYN without an ACK (presumably indicating a simultaneous open)?  If so, I see a problem with race conditions.  For example, my SYN (without ACK) reaches my partner but his SYN (without ACK) gets dropped on its way to me.  The next packet he sends me (e.g., a retransmission) will be a SYN-ACK, because he is by then aware of my SYN.  But he’ll correctly perceive my p-bit to be 0, and thus go into tie-breaker mode, whereas I’ll think his p-bit is a 1 because I saw a SYN-ACK first, and horrible confusion ensues.  Perhaps it would be better to avoid risk of such confusion simply by deleting the ‘z’ bit from the sub option packet and instead just including an explicit ‘p’ bit right next to the ‘b’ bit?

2. Section 3 currently specifies that only one variable-length sub option per ENO option is allowed, but that multiple ENO options can be used if needed to contain multiple variable-length ENO sub options.  I understand the tradeoffs discussed in section 6.4 but frankly the current solution makes my skin crawl. :)  I think the ENO spec should be defined such that it should never, ever be necessary to have more than one ENO option in a single packet.  This doesn’t necessarily mean adding a whole extra byte to every variable-length sub option.  Two possible ways to avoid that are: (a) when v=1, use the next 3 bits to choose from a few possible sub-option lengths: e.g., 0,1,2,4,8,16,32,64.  A sub option that needs 5 bytes gets encoded with 3 padding bytes (oh well).  (b) when v=1, use the next bit (u?) to encode whether this is the “last” suboption (u=0) or not-the-last suboption (u=1).  When u=1 (a non-last suboption), the bottom 6 bits encode the length of this (non-last) sub option, and the sub option itself is coded starting in the next byte with v=1,u=0.  This approach would be just as space-efficient as the current proposal in the presumably common case of only one variable-length sub option, and would add one extra byte of overhead (for the v=1,u=1 length byte) for each *additional* variable-length option encoded before that last option.

Cheers
Bryan

---

From: Bryan Ford <[email-masked]>
Date: Sat, 7 Nov 2015 15:57:23 +0900

> the price of two RSA decryptions when you only need one?

A sends it to B in its INIT message (and vice versa).

And yes, it costs two RSA decryptions instead of just one, but you also get a potentially important benefit from this cost: namely the ability to obtain PFS from RSA-based key exchange.  In particular, both the RSA key A sends to B and the key B sends to A could now be short-term RSA public keys used only for key agreement, with the users’ long-term (possibly RSA, possibly something-else) keys used only for signing the session IDs generated via key agreement.  Just like ECDH achieves PFS, and just as symmetrical.

All this is moot, of course, if we decide RSA isn’t really interesting or necessary for tcpcrypt (which seems like a reasonable position).  But if we do want RSA, then I think RSA with PFS would definitely be better in today’s world than RSA without PFS and I would argue worth the cost, independent of whether it is embodied in a symmetric or asymmetric protocol design.

> but it doesn't appear as though symmetry was a particular design goal of

It is symmetrical in that each endpoint has the same set of choices available to it and follows the same state machine (defined by Figure 6 in RFC793).  It might well be most commonly used in an asymmetrical fashion (with the “passive” endpoint following a slightly different path through the TCP state machine than the “active” endpoint), but it can also deal cleanly with the case where two endpoints happen to express interest in talking to each other at about the same time, forming a single connection with two active openers (the simultaneous-open case).  I always liked that property not just because it’s (sometimes) useful for NAT traversal, but conceptually, e.g., for P2P protocols where peers want to keep “a connection” open with each other for gossip or whatnot (and would rather have just one symmetric connection, not one in each direction).  Admittedly this symmetry is not fundamentally essential and it’s always possible to design applications or P2P protocols that build on asymmetric transport (or encrypted-transport) protocols by adding appropriate tie-breaking functionality.  But given that TCP (as well as UDP) already have a long-established tradition of role-symmetry in the transport protocol design, it just feels cleaner to preserve it in a TCP extension like tcpcrypt.  Especially when preserving role-symmetry makes the protocol simpler and cleaner, as I think it does.

> some other nonces not shown):

OK, I see how this very RSA-encryption-specific optimization can shave off a round-trip in the asymmetric case.  But:

(1) It clearly doesn’t provide PFS and doesn’t work for ECDH, which is probably the current state-of-the-art we want to be focusing on anyway.

(2) If you want to shave off one round-trip, there are probably cleaner and more general ways of doing it, e.g., the way TLS 1.3 is doing it.  Namely, the client caches the server’s PKB from the last session, and starts the next session by optimistically assuming PKB hasn’t changed, in which case the client send its (possibly fresh) PKA and compute a shared secret using the server’s last-known PKB.  This works equally well for either ECDH or RSA and allows for forward-secrecy beyond PKA/PKB refresh epochs.  (In the RSA case, the client sends PKA,{NA}_PKB to the server in its first data round-trip, and can commence sending encrypted payload data with it immediately.)

(3) If you really, really want to do the RSA-specific single-RTT key-exchange hack above, you still CAN do it as a special-case optimization within an otherwise-symmetrical version of the tcpcrypt protocol.  That is, on startup, IF the RSA suite was negotiated, then look at the TCP-ENO tie-breaking bits and IF there’s a clear “winner”, the A side initiates the abbreviated key-exchange protocol you described above; otherwise both endpoints fall back on the more general key-exchange.  But frankly, I wouldn’t bother, given the other alternatives available and the fact that we’re talking about RSA.

> grows linearly with modulus size, too, since decryption is O(n^3) and

OK - if you really care about hyper-optimizing RSA key exchange, I won’t try to stop you, and that can be done in multiple ways as discussed above.  But designing the entire structure of tcpcrypt around this one tiny optimization of a nearly-obsolete encryption algorithm just doesn’t sound like a great tradeoff to me. :)

Bryan

---

From: David Mazieres <[email-masked]>
Date: Sat, 07 Nov 2015 00:32:55 -0800

Bryan Ford <[email-masked]> writes:

> And yes, it costs two RSA decryptions instead of just one, but you
> also get a potentially important benefit from this cost: namely the
> ability to obtain PFS from RSA-based key exchange.  In particular,
> both the RSA key A sends to B and the key B sends to A could now be
> short-term RSA public keys used only for key agreement, with the
> users’ long-term (possibly RSA, possibly something-else) keys used
> only for signing the session IDs generated via key agreement.  Just
> like ECDH achieves PFS, and just as symmetrical.

The PFS situation is identical whether you do one or two RSA
decryptions.  Either way you have to erase an RSA key when your
connection ends or is rekeyed.  Given the cost of generating RSA keys,
it might be better to erase them every two minutes instead of exactly
when the session ends.  That's why the charter requires forward secrecy
but not *perfect* forward secrecy.

> All this is moot, of course, if we decide RSA isn’t really interesting
> or necessary for tcpcrypt (which seems like a reasonable position).
> But if we do want RSA, then I think RSA with PFS would definitely be
> better in today’s world than RSA without PFS and I would argue worth
> the cost, independent of whether it is embodied in a symmetric or
> asymmetric protocol design.

It's not RSA so much as any form of public-key encryption vs. just
Diffie-Hellman key exchange.  If we ever need to move to post-quantum
crypto, it will most likely be with public key encryption (such as
lattice-based ciphers) rather than Diffie-Hellman.  Also, if we ever
decide that elliptic curve cryptography is problematic and favor DH over
Zp, then RSA may be competitive again.  (I do think it more likely that
RSA will fail before discrete log, but we shouldn't bet the future
security of the Internet such conjectures.)

> It is symmetrical in that each endpoint has the same set of choices
> available to it and follows the same state machine (defined by Figure
> 6 in RFC793).

Well, in that sense ENO is symmetric as well, because you have the same
state machine on both sides.

> But given that TCP (as well as UDP) already have a long-established
> tradition of role-symmetry in the transport protocol design, it just
> feels cleaner to preserve it in a TCP extension like tcpcrypt.

I reject the assertion that TCP has a long-established tradition of
role-symmetry, except in the sense that ENO is symmetric (both hosts use
the same state machine).  How about this:  Show me a tcpdump of a
simultaneous open by an application that you did not write yourself,
without transiting a firewall/NAT you specifically configured yourself
for the purposes of the experiment, and then we'll talk.

BUT, and this is the point, I think it's highly likely that even if you
do demonstrate such an application, it will A) already be encrypting
traffic, and/or B) provide a trivial way of assigning roles (e.g., the
TCP stack might not know its own public IP address/port, but the
application might, in which case you can just sort by <IP, port>).

Given that there are very realistic scenarios in which future encryption
specs will want to employ public-key encryption, and there are very real
concerns that application-writers can misuse APIs, I don't think we can
justify penalizing public-key encryption and complicating APIs without a
concrete example of an application that would benefit.

> Especially when preserving role-symmetry makes the protocol simpler
> and cleaner, as I think it does.

I also disagree about making the protocol simpler.  Also, even if you do
think the protocol is simpler, the API is more complicated, and that is
likely to be the biggest source of errors.

> OK, I see how this very RSA-encryption-specific optimization can shave
> off a round-trip in the asymmetric case.  But:
>
> (1) It clearly doesn’t provide PFS and doesn’t work for ECDH, which is
> probably the current state-of-the-art we want to be focusing on
> anyway.

Whether or not it provides PFS just depends on when you erase the RSA
key.  Having two RSA decryptions won't help the PFS situation.  There's
an efficiency argument where DH can justify PFS, while with RSA you
might want to reuse keys for two minutes.  But that argument is entirely
separate from the question of whether ENO is symmetric or not.

> (2) If you want to shave off one round-trip, there are probably
> cleaner and more general ways of doing it, e.g., the way TLS 1.3 is
> doing it.  Namely, the client caches the server’s PKB from the last
> session, and starts the next session by optimistically assuming PKB
> hasn’t changed, in which case the client send its (possibly fresh) PKA
> and compute a shared secret using the server’s last-known PKB.

This is could be problematic for server farms if SKB is secret.  It also
burns gratuitous CPU time.  Plus, if you are really connecting to the
same server, you should use session resumption.

On the other hand, given that PKB is not used for security, how about
picking some 512-bit modulus, publishing both the modulus and its
factorization in the RFC, and saying all passive openers MUST use that
one modulus (so only with two active openers would you not).  Then
you'll never miss in the cache!

Now you could use different PKB on different servers, or use a modulus
larger than 512 bits, but then you'd have more cache misses and more
cost on the server for no benefit.  Do you really still think yours is a
simpler and cleaner design?

> (3) If you really, really want to do the RSA-specific single-RTT
> key-exchange hack above, you still CAN do it as a special-case
> optimization within an otherwise-symmetrical version of the tcpcrypt
> protocol.  That is, on startup, IF the RSA suite was negotiated, then
> look at the TCP-ENO tie-breaking bits and IF there’s a clear “winner”,
> the A side initiates the abbreviated key-exchange protocol you
> described above; otherwise both endpoints fall back on the more
> general key-exchange.  But frankly, I wouldn’t bother, given the other
> alternatives available and the fact that we’re talking about RSA.

We're talking about any key *exchange* (or transport), as opposed to key
*agreement*.  We might not be using RSA or ECDH in 30 years, but ideally
ENO can still negotiate whatever ciphers people need.

> OK - if you really care about hyper-optimizing RSA key exchange, I
> won’t try to stop you, and that can be done in multiple ways as
> discussed above.  But designing the entire structure of tcpcrypt
> around this one tiny optimization of a nearly-obsolete encryption
> algorithm just doesn’t sound like a great tradeoff to me. :)

Well, the 33x is for RSA.  But if you look at some of the post-quantum
algorithms on http://bench.cr.yp.to/results-encrypt.html, like
ntruees787ep1, it's still up to a factor of two cheaper to encrypt than
decrypt.  And obviously that's in addition to the factor of two you are
already paying for the gratuitous extra encryption/decryption, and the
extra round-trip latency (because you wouldn't be doing key negotiation
in the first place if you hit in the cache).

It seems ridiculous to rule out efficient use of public key encryption,
including post-quantum crypto, which may well be important someday, in
favor of simultaneous open, which already basically works with ENO,
would likely never be used with ENO anyway, and will grow even less
relevant with IPv6 adoption.

But as I said, cut and paste me a tcpdump and we'll talk.  It may be
that in a more specific context of an application that needs this we can
find something that will satisfy you and not add gratuitous cost to the
protocol and complexity to the API.

David

---

From: Bryan Ford <[email-masked]>
Date: Sat, 7 Nov 2015 20:49:31 +0900

Hi David,

I don’t have anything against public-key encryption, and there are various ways it can be (efficiently) implemented in either a symmetric fashion or as a “special-case asymmetric optimization” as discussed already, so I’m not going to address all your individual points about that.  Just...

> likely to be the biggest source of errors.

One important and readily measurable it will make the protocol simpler (at least in the purely symmetric version) is by simplifying the control flow of any implementation.  In most software complexity metrics, number of if-statements and other control flow cases play a major role.  The symmetric tcpcrypt design I proposed, as far as I can tell, removes all the “if” statements of the form “if I am in the A-role do this” or “if I am in the B role do that”.  I’m sure there are some number of those in your tcpcrypt implementation(s); I don’t know how many but maybe you can tell me. :)  As far as I can tell, the symmetric design removes all those if-statements, and adds no other essential ones that I can think of.  Can you point out any conditionals or special-cases that the symmetric design requires and the asymmetric design does not?

> relevant with IPv6 adoption.

I’m not remotely proposing to rule out efficient use of public key encryption.  As I said already, if you want it (which is fine), it can easily be added as a special-case, optional asymmetric optimization that gets activated when both parties support it and happen to agree on who is A and who is B (which will be most of the time).  But if it doesn’t work, it simply falls back to the slightly-less-optimized symmetric method.  You get your efficient use of public key encryption, and we avoid breaking TCP’s role-symmetry or simultaneous open.

B

---

From: [email-masked]
Date: Sat, 07 Nov 2015 10:10:54 -0800

Bryan Ford <[email-masked]> writes:

> - Section 2, Introduction: insert “, if needed by the negotiated
> protocol,” somewhere appropriate in bullet 6 at the very end of this
> section.

That bullet says, "so as to name each end of a connection for encryption
or authentication purposes."  So what if it's needed for authentication?

> 	* If both endpoints play the active role, e.g., in the case of
> 	TCP simultaneous-open, then each endpoint will first send a SYN
> 	packet (without the ACK flag set) containing ENO options; then
> 	upon receiving the other endpoint’s SYN packet, each endpoint
> 	will send an ACK packet containing an empty ENO option in order
> 	to confirm receipt of the other endpoint’s ENO options.

The reason I'm asking you for tcpdump output or at least an "A->B"-style
packet flow diagram is that this isn't how simultaneous open works, yet
it's easy to convince yourself that stuff like this works when you don't
go through the trouble of creating and staring at a packet flow diagram.

TCP-SO requires two SYNs followed by two SYN-ACKs.  Any realistic
scenario involves a stateful firewall or NAT dropping one of the two SYN
segments; otherwise, whoever connected first will get an RST segment and
abort the connection.  Hence, the SYN-ACK must contain the same ENO
option as the SYN.  Moreover, an overwhelming faction of the time
exactly one end of the TCP connection will know that this is a
simultaneous open, while a small fraction of the time you will get
"lucky" and both ends will receive SYNs without ACK.

Consider how weird it is that we've wasted so much time emailing about
TCP-SO when we don't even share a basic understanding of how the
mechanism works.  I conjecture this is because TCP-SO essentially
doesn't exist in the wild.  Since we can't observe it, we make up
strange theories about how it works or how it might be useful.  With no
empirical basis, these theories do not provide useful guidance for the
design of TCP-ENO.

> - The “negotiated spec” paragraph needs to be adjusted as I proposed
> in my earlier E-mail: e.g., from each list of supported specs, take
> the last spec from each list that is present in both lists, and if
> they are different, just choose (say) the numerically higher one,
> instead of choosing the one proposed by host B.

I think it's a little weird to favor higher code points.  It effectively
makes RAW mode an impractical implementation technique for servers with
well-defined spec preferences.  But while I'm adamant about not
complicating the API, if you solve the API problem, RAW mode is
something I would at least consider changing or getting rid of.

> send only one spec identifier…”

Why?  First it's a SHOULD, not a MUST.  Second, it seems even more
important now that code points reflect some kind of weird priority that
almost certainly doesn't capture anyone's preferences.  Finally, there's
plenty of precedent for even stronger restrictions dating back at least
to RFC1323 ("Furthermore, an extension option will be sent in a
<SYN,ACK> segment only if the corresponding option was received in the
initial <SYN> segment.")  I'm not saying I agree with RFC1323, just that
TCP's supposedly symmetric design hasn't really been symmetric since the
early 1990s.

Okay, I'm not even going to address two transcripts issue, because A) if
you solve the API problem the solution to the transcript will follow
naturally, and B) I think this whole thread is a giant waste of time
until we have a concrete example of TCP-SO use that could benefit from
TCPINC.

Also, to reemphasize the API point, if there's any application using
TCP-SO that could benefit from TCPINC, it's probably a peer-to-peer
application.  And that style of symmetric application is precisely the
kind most likely to be tricked into thinking it has connected to itself.
So roles are especially important in peer-to-peer applications.  (In
other settings, the application will know if it was an active or passive
opener, but the API ROLE calls are still necessary so that people can
implement "idiot-proof" authentication libraries that don't rely on
getting this information properly from the application.)

David

---

From: Kyle Rose <[email-masked]>
Date: Sun, 8 Nov 2015 20:11:02 +0900

chair^

I don't think this has been a waste of time at all. Even if we decide
to make no changes, the discussion has brought forth a number of
interesting considerations not necessarily limited to SO, including
that of how tcpcrypt will perform in a world of quantum-resistant key
exchange.

member^

> a session ID and a role is pretty simple.

What exactly is the issue here? You mentioned a client being tricked
into thinking it has connected to itself, but I think I need you to
spell out the worry here. In my earlier post, I was thinking it was
sufficient for an application to know it is (at least) one end of a
session identified by a particular SID, but I'm perfectly willing to
believe I'm missing something subtle here.

> but it doesn't appear as though symmetry was a particular design goal of

Yeah, I am worried we're expending too much mental energy on SO
itself. But part of the reason I'm glad it was brought up is that I
still have no real idea what the TCP establishment thinks about the
expendability of SO considerations. I'd hate to put a lot of work into
something and have the tsv AD or IESG remand it because it turns out a
lot more people care about SO than we currently guess. That having
been said, my suspicion is that it won't be a problem if the naive
failure mode for an unmodified SO-based app, both endpoints of which
support TCPINC, is to fall back to unencrypted TCP. I can believe they
would have a problem with a failure mode in which SO applications fail
to connect.

Kyle

---

From: David Mazieres <[email-masked]>
Date: Sun, 08 Nov 2015 12:08:27 -0800

> believe I'm missing something subtle here.

An example of something I'm involved with that obviously doesn't use
TCPINC but might well if it were widely available is stellar-core
(www.stellar.org).  It uses a peer-to-peer overlay network to multicast
messages, with pairwise authentication to make sure you are talking to
the nodes you think you are talking to (as opposed to random people who
might try to DoS you).  You also hear your own messages, a bit like the
loopback interface.  If you didn't have roles and just signed session
IDs, you'd need some other logic to make sure that you really are
talking to yourself.  Otherwise, anyone could just throw your
authentication signature back in your face.

Now since the system doesn't use simultaneous open, you could use the
active/passive opener status as the role.  But this makes it harder to
abstract away authentication.  Ideally, in the long-term we would have
libraries for authentication where you just hand the library a file
descriptor and credentials and everything works, including the case of
simultaneous open if that's ever used.

The more general point is that domain separation is extremely important
in the use of digital signatures and MACs, and having explicit roles
make it harder for people to mess that up.

> would have a problem with a failure mode in which SO applications fail

Yes, that's why we chose point 2 on the four-point scale that arose out
of the last TCP-SO discussion on the mailing list:

        https://tools.ietf.org/html/draft-ietf-tcpinc-tcpeno-00#section-6.2

I think given the present discussion, I might revise points 3 and 4 to
say it would either require a tie-breaker, or place the onus of role
assignment on encryption specs, thereby potentially incurring additional
computation or round trips.

David

---

From: Bryan A Ford <[email-masked]>
Date: Sat, 21 Nov 2015 19:02:03 -0800

I never saw any response to my Nov 6 E-mail on "specific ways to evolve
the TCP-ENO spec".  I would especially like to hear any of the spec's
authors address these particular concerns at the end of the E-mail,
especially the first, which seems like a potentially significant
protocol bug:

On 11/6/15 10:26 PM, Bryan Ford wrote:
>Now for two issues that my closer read-through brought up, which are
>at least partially orthogonal to the symmetric-mode support:
>
>1. The current section 3.1 doesn’t really state clearly where the “p”
>bit comes from in Figure 4.  It’s not included in the general sub
>option specified in section 3.3, so I assume each endpoint is supposed
>to “infer” both its own p-bit and the other endpoint’s p-bit.
>Presumably it’s easy for each endpoint to decide the value of its own
>p-bit, but how does each endpoint determine the intended value of the
>other endpoint’s p-bit?  For example, if I consider myself an active
>opener (p=0), then do I decide that the other endpoint’s p-bit is a 1
>if the first TCP packet I get from them is a SYN-ACK, and decide the
>other endpoint’s p-bit is a 0 if the first packet I get from them is a
>SYN without an ACK (presumably indicating a simultaneous open)?  If
>so, I see a problem with race conditions.  For example, my SYN
>(without ACK) reaches my partner but his SYN (without ACK) gets
>dropped on its way to me.  The next packet he sends me (e.g., a
>retransmission) will be a SYN-ACK, because he is by then aware of my
>SYN.  But he’ll correctly perceive my p-bit to be 0, and thus go into
>tie-breaker mode, whereas I’ll think his p-bit is a 1 because I saw a
>SYN-ACK first, and horrible confusion ensues.  Perhaps it would be
>better to avoid risk of such confusion simply by deleting the ‘z’ bit
>from the sub option packet and instead just including an explicit ‘p’
>bit right next to the ‘b’ bit?
>
>2. Section 3 currently specifies that only one variable-length sub
>option per ENO option is allowed, but that multiple ENO options can be
>used if needed to contain multiple variable-length ENO sub options.  I
>understand the tradeoffs discussed in section 6.4 but frankly the
>current solution makes my skin crawl.   I think the ENO spec should be
>defined such that it should never, ever be necessary to have more than
>one ENO option in a single packet.  This doesn’t necessarily mean
>adding a whole extra byte to every variable-length sub option.  Two
>possible ways to avoid that are: (a) when v=1, use the next 3 bits to
>choose from a few possible sub-option lengths: e.g.,
>0,1,2,4,8,16,32,64.  A sub option that needs 5 bytes gets encoded with
>3 padding bytes (oh well).  (b) when v=1, use the next bit (u?) to
>encode whether this is the “last” suboption (u=0) or not-the-last
>suboption (u=1).  When u=1 (a non-last suboption), the bottom 6 bits
>encode the length of this (non-last) sub option, and the sub option
>itself is coded starting in the next byte with v=1,u=0.  This approach
>would be just as space-efficient as the current proposal in the
>presumably common case of only one variable-length sub option, and
>would add one extra byte of overhead (for the v=1,u=1 length byte) for
>each *additional* variable-length option encoded before that last >option.

Thanks
Bryan

---

From: David Mazieres <[email-masked]>
Date: Sat, 21 Nov 2015 21:20:40 -0800

> especially the first, which seems like a potentially significant

We will attempt to address the technical points in the next draft of the
TCP-ENO spec.

David