GREASE ESNI extensions are easily distinguished from real ones

[davidben]

The draft has provisions for GREASE ESNI extensions, per "Do not stick out". However, this is not very effective if an attacker can distinguish a GREASE ESNI extension from a real one.

#154 tried to address this, but it doesn't work if the (public) ESNI record is known. There's also a simpler attack: replay the ClientHello with one byte of ciphertext corrupted. ESNI currently distinguishes key mismatch from decrypt failure, with the latter resulting in an alert. We can fix that by saying decrypt failure should behave like key mismatch. This still leaves record_digest.

The natural fix is to drop record_digest in favor of trial decryption. The cost is the server must perform a DH operation per known key. The number of keys the server needs depends on its DNS TTLs and key rotation. (I think it's 1 + ceil(dns_ttl / time_between_rotation), plus some leeway[*].)

Instead, we can keep a key name, but make the space dense. Suppose we replace it with a B-bit "key phase". The server picks a random starting key phase. Then, each time it rotates the keys, it increments the phase, with wraparound. The server then gets 2^B keys for free. If it needs more, it still needs trial decryption but gains a 2^B multiplicative factor in the cost. On the flip side, an individual GREASE extension with a random key phase has a 1/2^B chance of colliding with a particular ESNI key.

I'm not sure we actually need that many live keys, so B = 2 is probably plenty. Or even B = 1 if we say you should just rotate slower than your DNS TTL.

[*] Note the robustness mechanism means that server doesn't need to cover all clients with stale keys. The retry is expensive, so the server still needs to cover almost all of them, but it can cut off the long tail.

[davidben]

Mostly a note to myself for the actual PR: the draft should also discuss padding of the EncryptedExtensions message.

[ekr]

I think we really need to go back to first principles here and ask what it is we are trying to accomplish. First, it's public information whether a given server supports ECHO, so if an attacker wants to know that, it can mostly just ask [there is some complexity around getting candidate names, but note that you can always get the public name from the SNI value and any real attacker will see a lot of non-ECHO traffic and so will know a bunch of SNI values].

What's not public information is whether a given connection uses ECHO. The attacker might not know this either because:

1. It knows that the server is ECHO-supporting.
2. It has a limited view of just the connection and isn't willing to do do the work of trying to determine if the server is ECHO-supporting.

In case (1) I would also expect that the attacker is not going to go to the trouble of doing probe connections, as determining if the server is ECHO supporting is easier. This leaves us with the case where the attacker knows that the server is ECHO supporting and that the client knows about ECHO (otherwise it couldn't generate GREASE) but doesn't know if the client is actually doing ECHO. Do we expect there to be a lot of clients like this? Why not just do ECHO?

[chris-wood]

As per today's call, we're going to revisit the GREASE threat model and then reconvene if further work is needed.

[chris-wood]

I'm moving to closes this issue as resolved by #235. If we need to do something against connection blocking adversaries, perhaps we should look into MASQUE for that.

[chris-wood]

Closing for now. @davidben, please re-open if you still think we should address this!