[Cfrg] tcpinc: session ID unlinkability

[Kyle Rose <[e-mail]>]

I got some great feedback from the last question. Thanks to everyone, and
especially to Natanael, who helpfully provided a convincing argument that
uniqueness of the session ID even against adversary-as-endpoint is
sufficient for endpoint authentication (i.e., that secrecy and even
unpredictability of the session ID are not required).

Now for the second inquiry...

The TCP-ENO draft (https://tools.ietf.org/html/draft-ietf-tcpinc-tcpeno-04)
says:

"Unless and until applications disclose information about the session ID,
all but the first byte MUST be computationally indistinguishable from
random bytes to a network eavesdropper."

I don't think this is actually the property we want. It's really okay, for
instance, if the first K>=1 bytes (for some constant K) are predictable as
long as they do not impact the security of the system (see my previous
question in the "endpoint authentication and session ID privacy" thread),
and as long as they cannot be used to violate privacy, e.g., by enabling
tracking of clients or interesting classes of clients. (In the case of
tcpcrypt, the first byte of the session ID is the ENO suboption
representing the negotiated key exchange mechanism, to ensure that
cross-protocol session ID attacks are not possible by putting session IDs
for different KEX mechanisms into disjoint spaces.)

Conversely, it's not okay for the first byte to be used to encode something
interesting about the user in the clear (e.g., user agent), because that
could be used by a passive observer to track clients.

Furthermore, as discussed in the previous question, we really do need these
session IDs to be unique even when one endpoint is an adversary.

I'm struggling with how to phrase this whole thing. So my first question
is: what property/properties do we actually want here?

Daniel Franke's draft for the NTS project has a very similar requirement,
as I noted on this thread:

q( Section 6.1.6 should list required properties of cookies; in particular,
something like "To prevent tracking of clients, a cookie issued by a server
will be repeated at most once by the client in plaintext; therefore, all
cookies issued by a server must be constructed in such a way that, even in
large numbers, they cannot be correlated to specific clients by an observer
not in possession of the keying material used to create them." Basically,
to a third-party, the cookies must be cryptographically indistinguishable
from each other with respect to the input data they represent. A
cryptographer might be able to come up with some precise language to
describe this. )

http://lists.ntp.org/pipermail/ntpwg/2016-August/003014.html

An answer here might be generally useful, maybe even to the point of a BCP
for these kinds of cookies. (Heck, there might even be one that I don't
know about.)

Furthermore, some protocols may require most of the bits to be
unpredictable, but even that's not quite right: what's really needed is
enough entropy (say, >= 256 bits) over the totality of the session ID. If
you take a 512-bit session ID and bias each bit slightly toward 0, I
imagine you've still got more than enough entropy.

So my second question is: do we need to capture this, or should we simplify
and say that each session ID should have at least 256 bits that are
computationally indistinguishable from random?

Kyle