Replayed signature requests don't consume ODIS quota

[codyborn]

Signers shouldn't deduct quota when an address + blinded phone number pair has been seen before (regardless of timestamp).

• Make blinded phone number generation deterministic by DEK (random blinded number makes it hard to know it was the same request in the future)

• Ignore timestamp when deciding if it's a replay

• [x] Update this thread once deployment is completed

• [x] Update metrics per this comment

[nategraf]

Make blinded phone number generation deterministic by DEK (random blinded number makes it hard to know it was the same request in the future)

I have a concern with this approach in that it removes forward secrecy from blinded requests in the case of the DEK becoming compromised. One solution to this, which would still allow for replays, is to use ephemeral keys for blinding that are rotated on a regular basis (e.g. every day). Other rules can also be used for this, and obviously doing regular key rotation at the DEK layer would help with this, although that would be much more difficult to implement.

[codyborn]

Glad you're thinking about this @nategraf. If the DEK is compromised and the attacker could figure out which phone numbers the user queried, then they'd be able to query the them for free with ODIS. Assuming the user had 100 contacts, the attacker would be able to save (100/2*$.001) 5 cents, which compared to the loss of the DEK and other encrypted data, is negligible. Were there other concerns that you had with regard to the forward secrecy?

[nategraf]

Glad you're thinking about this @nategraf. If the DEK is compromised and the attacker could figure out which phone numbers the user queried, then they'd be able to query the them for free with ODIS. Assuming the user had 100 contacts, the attacker would be able to save (100/2*$.001) 5 cents, which compared to the loss of the DEK and other encrypted data, is negligible. Were there other concerns that you had with regard to the forward secrecy?

My main concern is actually that the attacker would get the user's list of queried phone numbers (i.e. their contact list) from the blinded requests. Its also worth noting they would not need to query ODIS again if they have access to the blinded responses. I agree that the value of this as a target is fairly small compared to other concerns, so I am not saying we absolutely shouldn't do this, but whenever it is possible to preserve forward secrecy, we should, so I wanted it to be considered here.

[alecps]

I'm a little unclear what the specific concerns are here since the DEK is used in a few ways in this replay handling proposal. @nategraf I would value your feedback on the PR for these changes if you have a chance or would like to look at the actual implementation. I can try to resolve some ambiguity here also:

• This scheme uses the DEK for both matchmaking and signing
• For matchmaking, the DEK signature is verified. That is, a user must sign with their DEK to perform matchmaking and access to a user's DEK does allow you to query that user's matches as many times as you'd like. The user can rotate their DEK and this will remain the case (TODO: I hadn't thought of this until now, but I can add the change to make this possible).
• For signing, the client is free to provide whatever blinding factor they see fit (default is a random seed). We will recommend that Valora use something deterministic (like the DEK) as this will give user's the ability to query numbers they've queried before without spending quota. As @codyborn mentioned, the cost for an attacker to do this without compromising the user's DEK is negligible. Either way, ODIS cannot tell whether the client blinded the phone number with a DEK or a random seed.

[nategraf]

Either way, ODIS cannot tell whether the client blinded the phone number with a DEK or a random seed.

So this is the part that is not true. If given a blinded request, where the blinding factor is derived from the DEK, and the DEK, it is possible to unblind the request and crack the hash-to-curve (SHA256 hash) to get the requested phone number. When implemented in Valora, and what we recommend to developers in general, it would be beneficial to use an ephemeral key for this purpose, which is discarded when no longer needed.

[codyborn]

Either way, ODIS cannot tell whether the client blinded the phone number with a DEK or a random seed.

I think what Alec is saying is that it makes no difference from ODIS's side, as long as ODIS doesn't know the blinding factor.

which is discarded when no longer needed

The user would want to keep the blinding factor as long possible so that they can query their contacts' pepper without consuming quota. We can rotate the blinding factor, but we'd still want to keep track of the old ones somehow. This might defeat the purpose since they can still be leaked.

[nategraf]

I think what Alec is saying is that it makes no difference from ODIS's side, as long as ODIS doesn't know the blinding factor.

From an implementation standpoint on ODIS, this is definitely true. I raise this here because the suggestion is to have the ODIS client (e.g. Valora) use the DEK. I want to make sure this is considered by the client implementation, so maybe this is not the right place for that concern, but I didn't want to have this be lost.

The user would want to keep the blinding factor as long possible so that they can query their contacts' pepper without consuming quota. We can rotate the blinding factor, but we'd still want to keep track of the old ones somehow. This might defeat the purpose since they can still be leaked.

Certainly. Old blinding factor keys would need to be deleted to gain any benefit. It's true that the should be kept around for some time, but probably not forever. I would imagine that ODIS outputs should be cached by the client, instead of the client querying ODIS every time. Additionally, I imagine that ODIS will not store the record of previous requests forever, and so after a certain amount of time they would end up needing to pay for the request again anyway. Do we know how long we intend to keep client request records for facilitating this feature?

[alecps]

Thanks for the feedback @nategraf. I've created a ticket to continue this discussion https://app.zenhub.com/workspaces/cap-sprint-board-60059934ed9c6f000e5594f6/issues/celo-org/celo-monorepo/8313

[alecps]

This change has been merged and will be closed once the release is finished and the metrics are updated as described above