Re: [tcpinc] Simultaneous open tie breaking

[Tero Kivinen <[e-mail]>]

David Mazieres writes:
> Tero Kivinen <[e-mail]> writes:
> 
> > I do not think the b bit is really going to work, and I agree with
> > others that we need proper tie-breaker to solve this issue.
> >
> > On the other hand I do not think we need to add large tie breaker to
> > the frame, we can most likely use something like very small tie
> > breaker and sequence numbers for tie-breaker. I.e. whoever has smaller
> > 8-bit (or 6-bit) tie breaker is winner,
> 
> This is doable, though adds complexity to implementations.  Should this
> tie-breaker be sent by every active opener (and therefore consume option
> space), or do you imagine that applications intending to use
> simultaneous open set an option to include the tie breaker?

I think tcpinc charter says we must work with unmodified applications,
so I think the default needs to be send it, but allow API call to
disable it. 

> > if the tie breakers are same, then we compare initial sequence
> > numbers, and whoever has smaller initial sequence number is the
> > initiator and other end responder.
> 
> I'm very uncomfortable using sequence numbers.  In our initial tests for
> tcpcrypt we found sequence numbers got modulated.  If I recall OpenBSD
> does this by default when operating as a NAT, and I'm not even sure
> there's a way to disable it.  Same for timestamp.

The reason I want to use sequence numbers, is that in that case we can
make the tie-breaker so small, that it does not waste too many bits on
the wire.

Also as tie-breaker is only needed in the simultaneous opens, and
simulatenous opens with NATs in the middle are not that common. In
that case you need some kind of protocol to find out the external NAT
IP and port number before you can even start to do simultenous
connect, and those external protocols might also fix one of the
endpoints to be active opener and another to be passive listener, even
when the actual connection is done as simultaneous open.

> > After that we just need to have rules specifying how we pick up the
> > protocol from two ordered list. The most simple solution would be to
> > just say we take initiators list, remove all of the protocols not in
> > the responders list, and then take first item from initiators list
> > that is also supported by responder.
> 
> ENO currently does the mirror of this, letting the responder's list
> determine priority.  The logic was that passive openers tend to need to
> support higher numbers of connections per second, and so may need to
> steer choices towards options with better hardware acceleration,
> etc.

That is fine too. 

> Is your choice of the initiator's list just arbitrary, because you think
> we should just settle on one of the two lists and happened to say
> initiator?

Yes it is arbitrary. I picked it up, as that is what most of the other
protocols use, i.e. initiator/client presents list of supported
ciphers, and responders/server pick first it supports. This is for
example how secure shell works. 

> Or is there an argument to favor the initiator's list over
> the responder's?

Usually servers are configured to allow everything to maximize
interoperability, but clients might be configured to only support
things that they want to use. Also with mobile clients connecting to
the servers, the server might have much more computing power to
calculate things than client.

Anyways either order is fine. 

> > I.e. the negotiation would be (with same tie breaker selected randomly
> > in both ends):
> >
> > A->B(0x9453f454) SYN: Tie breaker=33; I can speak Z, Y
> > B->A(0x434945e5) SYN: Tie breaker=33; I can speak X, Y, Z
> >
> > As tie breaker is same, we will check sequence numbers, and as B has
> > smaller he is the winner, and both ends know this. Following the rules
> > above, the protocol to be used is Y.
> >
> > There are of course some middleboxes who do mess up with sequence
> > numrbers. To detect this we want to tell the result of the exchange to
> > both ends:
> >
> > A->B(0x9453f455) ACK: We are using protocol Y
> > B->A(0x434945e6) ACK: We are using protocol Y, I am initiator
> 
> This is going to add significant complexity to the protocol, including
> some cold code paths that are likely to be weakly tested in some OS
> distributions.

I do not think it will add that much as this is already done when
there is no simulatenous connection, i.e. the SYN-ACK will pick one
protocol, i.e. it will say "We are using protocol Y" anyways. The
final ACK does not need to repeat that information, but doing so will
have some benefits, as it makes it easy to understand which protocol
we are talking and if there are key exchange related messages they are
related to that protocol. 

> If we are going to add another round of exchanges anyway, though, why
> not do the tie-breaking there?  We could keep the single b bit as is
> (for applications that want to work it out), and then add a
> variable-length tie-breaking phase.  E.g.,
> 
>     A->B:  SYN ENO<Z, Y>
>     B->A:  SYN ENO<X, Y, Z>
>     A->B:  ACK ENO<Breaker 0x29892a863ce5>
>     B->A:  ACK ENO<Breaker 0xdb636b5918a2>
> 
> Here B is chosen as virtual responder because it has a higher
> tie-breaker, and at this point the protocol proceeds as usual.

Then we cannot have any key exchange protocol related messages in the
tcp handshake, and the whole key exchange needs to be done in after
the 3-way handshake. This is fine also, but it will add round trip.

I.e. if we do not know which one is initiator, we cannot pick the
protocol, thus we cannot have those messages in the ACKs. 

> Yet another possibility is hashing the options list and comparing.
> 
> Before settling on something, I'd like to get a sense of whether people
> think it's okay to ask applications to signal their intent to use
> simultaneous open, or whether it's important for TCP-ENO to enable
> encryption for existing, unmodified applications that use simultaneous
> open.  Those two options put us down different paths.

By our charter, I think we need to work with unmodified applications,
but we can provide API to allow optimizations and other things later.

> > Also if application will know it will NEVER do simulatenous opens
> > (like web server, or web client), it can do setsockopt that will
> > disable the Tie breaker option from the option list, saving byte or
> > two.
> 
> Obviously a passive opener never needs to include the tie-breaker.  But
> this sounds like you want active openers to include a tie-breaker by
> default, but want to enable them to opt out of it to save option space.

Yep. And this is why I think using very small (6-bit?) tie-breaker and
sequence number is good compromize. 

> My personal feeling is that it's unfortunate to waste option space and
> add all this complexity to deal with such a fringe case.  But it's not a
> strong feeling and I'm happy to modify ENO to suit the option of the
> working group.
> 
> But... I might have an idea for how to make this work that isn't so bad.
> Let me try something based on sorting the option lists and adding a
> variable-length tie-breaker option.  I think that might allow
> simultaneous open to work out of the box without adding too much
> complexity, and would allow people trade-offs in terms of option space
> consumed vs. failure probability.

I do not tihnk the tie-breaker needs to be variable length, it can be
fixed length, and it can be quite short.
-- 
[e-mail]