kern/60889 - zero IP id change issues in 5.2RC2

[silby at silby.com]

> Richard Wendland wrote:

> Haven't read all of that yet.

>> It's important to remember that if fragmentation takes place, and a
>> fragment is lost, the other fragment(s) will wait for quite some time
>> in a re-assembly buffer (maybe up to 63 seconds).  While they are
>> waiting they are at quite some risk of being joined onto a fragment
>> from the next ip_id cycle if a lot of packets are flowing:

IMO, that's not really a "risk" anymore than packet loss is a risk.  If
two different IP packets are joined together, the subsequent TCP / UDP
checksum will be incorrect, and the packet will be dropped.  This is
equivalent to a packet being dropped by the network; if we can't handle a
few lost packets, then we have a big problem.

Now, on to likelihood.  Since IP IDs are per (IP source, dest) pair, let's
consider two computers talking together, and assume that all packets are
fragmented.  If all packets are received in order, then we could actually
get away with using the same ID over and over; each packet would be
removed from the reassmebly queue when the final fragment arrived, and the
next packet would create a new reassembly queue when its first fragment
arrives.

Assuming that some packet reordering occurs, but no packet loss, we're
still in good shape, and can get away with only as many IP IDs as we have
packets in flight.

Even if we have slight packet loss, there should still be very few
problems, as a collision in the 2^16 space will be unlikely if we have
only a few incompletely reassembled packets hanging around.

Of course, you can make the argument that if we have frequent packet loss,
collisions become a common occurance.  I agree... however, if you have
frequent packet loss, TCP will backoff to a lower transmission rate, add
delays, etc, which will help mitigate the problem.  And if you have an app
which keeps sending UDP packets at crazy rates which causes fragment loss
and the resulting collisions, well, your performance will already be so
bad that I doubt the additional few packets dropped due to collisions will
matter one bit.

So, to sum up my position on IP ID collisions: they cause no more problems
than random packet loss would, and hence are not something we need to
worry about much at all.

Now, on to what we should do...

> I have an idea how to something like this in an efficient manner.
> Have a global incrementing ip_id counter and a small fixed size
> hash table.  The hash is computed from faddr/fport (see tcp_hostcache
> for a good hash function).  The hash table contains seeds in every
> bucket which are refreshed periodically (every second or ten or
> whatever).  For an outgoing packet you take the global ip_id counter,
> increment it by one, take the result and XOR it with the seed in
> the apropriate bucket.  The chance of collisions is very low and
> you get the full 64k cycle (globally).  Or you can do it the other way
> around and have a counter in every bucket and a global seed.
> Need to think about which is actually better.
>
> --
> Andre

Could you just use the tcp host cache for this purpose?

The simplest solution I can think of is to use the host cache to provide
seperate IP ID sequences for hosts in the cache, and to use arc4random for
all other hosts.  This could result in a few collisions under certain
situations, but I think that is an acceptable risk.

If that requires extra host cache lookups, we could use the host cache
provided sequence space for TCP packets only (one sequence space for all
TCP sessions, of course), and arc4random for UDP / etc.

I had considered some sort of hash table type system as you propose above,
I came to the conclusion that it wouldn't be that much faster than
arc4random and would provide much less randomness.

Oh, I also wanted to reinforce a point Richard had made in his post on the
problems with our id = 0 change: randomization becomes _more_ important as
we move away from a global counter.  If we use the tcp host cache to
provide individual sequence spaces for TCP connections, we need to make
sure that we address all the other packets, or we will be increasing the
amount of information we're revealing.

Mike "Silby" Silbersack