Why are stateless reset tokens 16 bytes long?

[marten-seemann]

We chose the stateless reset token to be 16 bytes long, but I don't remember the reason. It matches the tag size of the AEADs we use, although, as @kazuho points out in #2006 (comment), this might not be true for all TLS cipher suites.

In general, the probability for an attacker to correctly guess a stateless reset token is 2^(-token length). It seems like a 64 bit token would be sufficient to provide protection against an attack like that. Using a shorter token would make rotating connection IDs significantly cheaper.

[kazuho]

If the concern is about the overhead of the Stateless Reset Token field of the NEW_CONNECTION_ID frame, the other option might be to make the field optional. I am not sure why the field is mandatory, even though not all endpoints are required to send Stateless Resets.

Conveniently, once #2006 gets merged, the Length field of the Stateless Reset Token field would be the only field we use a 8-bit encoding for Connection ID Length. We can change it to a 4-bit encoding for consistency, and will have 4 bits to encode flags...

[mikkelfj]

Due to birthday problem a reset could affect the wrong connection with a real world probability if it is too short. Especially when servers do not coordinate and when state is lost between reboots.

[marten-seemann]

@mikkelfj: I don't see how the birthday problem comes into play here.
Let's run some numbers. Assume a cluster that is serving 1 million (≈ 2^20) connections at the same time, each of them using 16 (2^4) connection IDs at the same time. To have a chance of 1 millionth (≈ 2^-20) to disrupt a random connection of those, an attacker would have inject 1 million packets.

[kazuho]

Generally speaking, I prefer having the same level of protection for resets as we have for other types of injection; i.e. I think we should use a token that is as large as the AEAD tag.

I am not sure if there is a reason strong enough to shorten the token; after all, QUIC v1’s model is to use a stable CID rather than rotating very frequently, therfore the overhead does not matter.

[martinthomson]

@kazuho's reasoning is what drove the decision here. It might be the case that 16 octets is overkill, but there isn't a huge advantage in shaving this down. The cost isn't significant.

[ekr]

I think the real question is whether they are too small. If you build them with self-encryption, you might want more room.

[martinthomson]

Self-encryption isn't useful here. Self-encryption of a connection ID, sure, but the producer and consumer of a stateless reset token are different.

[kazuho]

Kind-of related, but by rereading #1041 I notice that a Stateless Reset is considered valid even for packets that arrive from a non-validated path (see section 10.4.1).

Is that intentional? Or should we limit the detection of Stateless Resets to packets that arrive from a pre-validated path?

I ask this because the current design of CID allows 2^18*8 of space to identify a connection (because CID is generated by the endpoint that uses it to identify the connection), whereas a stateless reset token only provides 2^8*8 space (because token is generated by peer and therefore be suspected to birthday attacks.

[martinthomson]

It is intentional. Even if 2⁶⁴ was insufficient, I don't think that it's that bad. Birthday bounds only come into play when you want to kill one connection from many. That is, you are willing to send 2⁶⁴ packets and there are 2⁶⁴ connection IDs live. Standard DoS mitigation techniques probably start to apply before the birthday bound is threatened.

[kazuho]

Thank you for the clarification. Makes sense to me.

[ekr]

Oh, yes, sorry. Long day and I was thinking retry token.

…

On Sun, Nov 25, 2018 at 7:35 PM Martin Thomson ***@***.***> wrote: Self-encryption isn't useful here. Self-encryption of a connection ID, sure, but the producer and consumer of a stateless reset token is different. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2018 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABD1ofWDKDVXAo3LxuvusAVxuhL46Rjcks5uy2F7gaJpZM4YnRg3> .

[dtikhonov]

Time to close this bug? The question has been answered.

[martinthomson]

Yep.