On Fri, 2018-01-12 at 08:53 +0000, Georg Koppen wrote:

Could you elaborate on the problem you see a bit? What exactly would be the attack scenario given edge1, edge2, ..., edgeN and why are DLEQ proofs not sufficient for that? What do you mean by "your edge public key"?

There is a secret scalar k used in CloudFlare's OPRF scheme which yields a public curve point K = g^k. https://blog.cloudflare.com/privacy-pass-the-math/ If different k are used for different clients then those clients are distinguished from one another later when using the tokens.

In batching the DLEQ proofs, they prove that all tokens within a batch share the same k, but the important question is:

How do you know if different users are given different K?

George said K was originally simply pinned in the Privacy Pass plugin, which works fine. It's hard to know if CloudFlare wants to keep it that way, maybe they're okay with sharing the secret k among many servers, or maybe they've no choice base on how Tor users move.

In general, CloudFlare's answer is an unspecified certificate transparency scheme. I'm nervous about nebulously saying certificate transparency here because it's problematic if CloudFlare starts using different k on different servers, which they might do if they want to protect k better.

I think short version for Tor Browser is: You can deploy Privacy Pass with a pinned K safely, but.. Anytime CloudFlare updates Privacy Pass, Tor Browser folk should check if they change handling of K. If they do, then any new scheme requires careful review. Ideally Tor Browser users should not independently update to any new CloudFlare version.

Jeff

p.s. We might ask if a purely local certificate transparency logs work: If Tor is anonymous, then CloudFlare cannot detect when the same users withdraws some new batch, so if they give this user a new K and their client remembers the old K then their client can detect this and raise an alarm.

I think this fails for several reasons: First, there are attacks on Tor, including attacks we believe many adversaries do not use due to cost, but Privacy Pass without an external certificate transparency magnifies these attacks effectiveness. Second, Tor is typically run in situations like Tails where its hard to persist a local certificate transparency log.

p.s.2 Any such scheme runs into this problem. In Taler, denomination keys face similar problems, except our tokens already represent money, so we already have a full PKI for denomination keys, extensive error reporting, and our merchants provide a de facto certificate transparency scheme. In other words, an adversarial exchange must tell merchants all the denomination keys, make all auditors sign them all, and then tell a targeted user only about a subset. That said, Taler can any certificate transparency scheme used by Privacy Pass can also be used by Taler, presumably