[tcpinc] tcpcrypt - Session resumption cache collision

["Black, David" <[e-mail]>]

Picking up this one comment from earlier discussion:

> > 3.4 "If key negotiation is compromised and yields two different
> > keys,...": This means collisions in SID[i](0..8) (72 bits) will result
> > in failed connections, which will lead to a frequency of something
> > like 1 out of every 2^36 connections wherever the session cache on the
> > passive opener cannot distinguish between different active openers. Is
> > this actually a problem? Not clear: should there be requirements
> > around how active and passive openers partition their session caches?
> > If naive clients or servers use one big pool, you can expect to see
> > this problem quite frequently at internet scale, with billions of
> > connections per second.
> 
> Well the frequency of collision depends on the size of your
> cache.  I guess you're saying that if you manage a cache for
> 2^36 active clients, then each new connection has
> probability of collision (2^36)/(2^72) = 2^(-36).
> Apparently we are supposed to have around 2^33
> internet-connected things this year, so perhaps this is a
> reasonable concern.
> 
> The motivation for the nine-byte SID prefix is to yield a
> multiple-of-four ENO length in the common case.  More
> comment on this tradeoff is welcome!

The quoted text is now in the security considerations section, but
this discussion is about Session ID collision on session resumption.

If there's a session ID 9-byte prefix collision resulting in a match to the
resumption cache, but the wrong saved keys, so the session can't
continue, the host that attempted resumption will need to retry
without asking for resumption.  This requires that host to realize
that the connection failed after what appeared to be a successful
resumption - I think a brief discussion of this is in order along with
a requirement to not retry resumption of a session that failed after
a resumption (never got any traffic from the other side that
decrypted correctly).  This only occurs on resumptions, not initial
connections.

Obviously, the size of the session cache affects the collision probability
on resumption, but 2^36 is a large cache - I'd expect much smaller
sizes of even the largest caches in practice.    There is a timeout here;
my initial sense is that the collision probability is small enough that this
is ok, but this could use some more careful thought.

Thanks, --David