Clearing cache digests

[Eric Rescorla <[e-mail]>]

The draft says:

   As a result, clients MUST mitigate for this threat when the user
   attempts to remove identifiers (e.g., "clearing cookies").  This
   could be achieved in a number of ways; for example: by clearing the
   cache, by changing one or both of N and P, or by adding new,
   synthetic entries to the digest to change its contents.

   TODO: discuss how effective the suggested mitigations actually would
   be.

Except for "clearing the cache", my initial impression is that the answer
to "how effective" is "not very", except for very naive uses of the cache
as an identifier.

Consider that the general structure of this mechanism is that the client
gives the server an oracle which answers the question "do you have document
X" with false positive rate 2^-P. This implies that the server can use the
cache as a cookie B of length N bits by creating N resources R_1, R_1 ...
R_N and then to store the cookie:

- If B_i == 1 then store R_i
- Otherwise don't

You then query for the cookie in the cache the same way. This has an
epsilon error probability but you can correct for that by storing N + delta
bits and using an error correcting code.

So, my claim is that any mechanism that retains the information in the
cache digest will allow for tracking, even if you change the way it is
encoded (e.g., changing N, P).

-Ekr