Rate-Limited Tokens: Exclusive Key Ownership

Summary: A client may be able to provide different public keys to the Attester and Issuer, resulting in an incorrect computation of the OPRF.

Details:

According to my best reading of the draft, the client generates a blinded key request_key and uses it to generate a signature on the encrypted token request. The request_key is sent to the Issuer inside the encrypted InnerTokenRequest. Let me call this copy of the request_key rk1. The client also communicates this request_key and the corresponding request_blind to the Attester via a request header. Let me call this copy rk2. The Attester and Issuer both verify the signature on the encrypted token request; the Attester also verifies the correctness of request_blind with respect to rk2 and the client long-term public key.

The question I had: can the client specify a different request_key in the two places? If so, the OPRF computation will no longer be correct, which may allow you to get exceed the token rate limit. For this to work, you would need two different public keys such that the signature verifies correctly under both of them.

Preventing such a construction is not a standard property of signature algorithms. The closest I could find was in this paper:

The Provable Security of Ed25519: Theory and Practice Jacqueline Brendel, Cas Cremers, Dennis Jackson, and Mang Zhao https://eprint.iacr.org/2020/823 (also published at S&P 2021)

There they define a property called Malicious Strong Universal Exclusive Ownership (M-S-UEO) that says that the adversary cannot create two public keys k, k' and two messages m, m' such that Verify(m,k) = Verify(m,k') = True. This property is sufficient to prevent the above attack, though not strictly necessary, since in our case we also need for m = m'.

The paper proves that EdDSA is resilient to such attacks only if there is a check that avoids the small subgroup on Curve25519. Unfortunately, as the paper points out, RFC8032 does not specify such a check, though, e.g., libsodium implements it. Without the check, a small subgroup attack can be used for a relatively straightforward attack on M-S-UEO (as well as other key substitution attacks discussed in the paper). I have not checked whether this attack would work end-to-end in rate-limited tokens, but I suspect that subgroup confinement gives you a lot of attack freedom.

The other issue is that ECDSA is almost certainly not resilient to the kind of key substitution we are looking at here, since it doesn't bind the public key to the signature the way EdDSA does, and there are known key substitution attacks against DSA. Again, I have not checked whether an end-to-end attack would work, but I suspect it might.

Solution:

I think this attack can be addressed by making sure that the Attester and Issuer are using the same public key. A simple way to accomplish this would be to have the attester communicate its copy of request_key to the Issuer and then having the Issuer verify that the key inside the encrypted InnerTokenRequest matches the one from the Attester. A nice way to do this would be to include a cleartext request_key inside the TokenRequest structure and perhaps also including it in the signature.

tfpauly / privacy-proxy

Rate-Limited Tokens: Exclusive Key Ownership #217