Subject: [Secdispatch] Dispatching draft on key consistency

From: Christopher Wood <[email-masked]>
Date: Fri, 4 Mar 2022 13:09:38 -0800

There are a number of different protocols that require multiple clients to discover a common — or consistent — cryptographic public key for use, including: Privacy Pass [1], Oblivious DoH [2], and Oblivious HTTP [3]. Consistency here means that all clients obtain the same view of the public key. An inconsistent view can lead to privacy attacks. 

For example, in Privacy Pass, if an attacker can somehow force a single (set of) client(s) to use a public key that is distinct from all other clients, then the key used effectively partitions the set of clients into two buckets, and the size and number of these partitions influence the overall privacy posture of the protocol. 

As this was a pattern across at least two disjoint protocols, we felt it would be useful to document some approaches for building key consistency into systems. The result is [4]. This has been previously presented in the context of the Privacy Pass working group [5], but was not pushed forward as a work item. 

We’d like to ask for time during SECDISPATCH to (a) determine if there’s interest in moving this document forward in some way, and if so, (b) determine what venue would be best to move it forward.

Thanks,
Chris, for the authors

[1] https://datatracker.ietf.org/wg/privacypass/about/
[2] https://datatracker.ietf.org/doc/draft-pauly-dprive-oblivious-doh/
[3] https://ietf-wg-ohai.github.io/oblivious-http/draft-ietf-ohai-ohttp.html
[4] https://datatracker.ietf.org/doc/draft-wood-key-consistency/
[5] https://datatracker.ietf.org/doc/slides-110-privacypass-key-consistency-and-discovery/

---

From: Michael Richardson <[email-masked]>
Date: Sat, 05 Mar 2022 14:03:18 -0500

Christopher Wood <[email-masked]> wrote:
    > There are a number of different protocols that require multiple clients
    > to discover a common — or consistent — cryptographic public key for
    > use, including: Privacy Pass [1], Oblivious DoH [2], and Oblivious HTTP
    > [3]. Consistency here means that all clients obtain the same view of
    > the public key. An inconsistent view can lead to privacy attacks.

    > For example, in Privacy Pass, if an attacker can somehow force a single
    > (set of) client(s) to use a public key that is distinct from all other
    > clients, then the key used effectively partitions the set of clients
    > into two buckets, and the size and number of these partitions influence
    > the overall privacy posture of the protocol.

"somehow" ... such an attacker can substitute any on-path attacker key.
I don't see how this is distinct from all the other attacks.

    > [5] https://datatracker.ietf.org/doc/slides-110-privacypass-key-consistency-and-discovery/

In reviewing the documents, it seems that it's not "somehow", it's that the proxy has been
persuaded to collude with a third party.  Perhaps that would be better to say.
Perhaps "persuaded" is the wrong term as well, since I think that the goal is
to defend the proxy against NSLs that would force the proxy to collude.

What is needed is a kind of canary such that for clients can detect when they
are being singled out, and then refuse to operate with that proxy.  By
existence of such a mechanism, proxies can effectively render themselves
useless to such forms of "persuasion".

--
Michael Richardson <[email-masked]>   . o O ( IPv6 IøT consulting )
           Sandelman Software Works Inc, Ottawa and Worldwide

---

From: Christopher Wood <[email-masked]>
Date: Fri, 11 Mar 2022 14:33:58 -0800

Hi Michael,

Apologies for the delayed reply. Please see inline below.

> On Mar 5, 2022, at 11:03 AM, Michael Richardson <[email-masked]> wrote:
> 
> 

The problem here is, say, forcing one single client to use key A and all other clients to use key B. The attacker would then be able to identify the individual client whenever key A is used.

> persuaded to collude with a third party.  Perhaps that would be better to say.

It’s not clear to me what you mean by "the proxy” here. The document doesn’t make any assumption about a proxy. Indeed, direct discovery a la section 4.1 (https://datatracker.ietf.org/doc/html/draft-wood-key-consistency-02#section-4.1) involves only client and server. Would you mind clarifying what you mean?

> useless to such forms of "persuasion".

The purpose of key consistency is to give clients a way to ensure they are not being singled out, not to tell clients when they are being singled out. These seem like different sides of the same coin, no?

Best,
Chris

---

From: Michael Richardson <[email-masked]>
Date: Fri, 11 Mar 2022 18:40:53 -0500

> The problem here is, say, forcing one single client to use key A and
    > all other clients to use key B. The attacker would then be able to
    > identify the individual client whenever key A is used.

I understand.

    > It’s not clear to me what you mean by "the proxy” here. The document
    > doesn’t make any assumption about a proxy. Indeed, direct discovery a
    > la section 4.1
    > (https://datatracker.ietf.org/doc/html/draft-wood-key-consistency-02#section-4.1)
    > involves only client and server. Would you mind clarifying what you
    > mean?

Oblivious DoH and Oblivious HTTP involve some kind of intermediary.
Maybe calling it a proxy is incorrect, but there is a third party.

    > The purpose of key consistency is to give clients a way to ensure they
    > are not being singled out, not to tell clients when they are being
    > singled out. These seem like different sides of the same coin, no?

Hard to prove a negative.
Easier to give them a way to recognize a positive, I think.

Either way, what does the client do when it figures out it has been singled out?

If the goal is to hide in the crowd,  then if there is a spotlight on you,
better act "normally" right, and not give away that one has figure out one
has been found out?

The client probably needs to go ahead and pretend it hasn't been singled out,
and do some innoculous transactions anyway, right?

---

From: Christopher Wood <[email-masked]>
Date: Fri, 11 Mar 2022 18:15:12 -0800

> On Mar 11, 2022, at 3:40 PM, Michael Richardson <[email-masked]> wrote:
> 
> 

I think there’s still a misunderstanding here. This draft discusses key consistency that can be _used_ by things like ODoH and OHTTP since, at the end of the day, key consistency is a separable problem. In other words, the draft doesn’t assume any particular protocol in which the key material is used, though the choice of consistency mechanism one uses may certainly be influenced by the protocol for which consistency is required.

> Easier to give them a way to recognize a positive, I think.

Hmm… I’m not sure I’m following you. Ensuring consistency is proving a positive, i.e., that all clients share the same view of the keying material. (It’s possible we’re saying the same thing but with different words.)

> Either way, what does the client do when it figures out it has been singled out?

That’s up to the client to decide, I think. It could choose to not use the key for the corresponding protocol, raise some alarms, or whatever else makes sense for the given application.

> and do some innoculous transactions anyway, right?

As above, what the client does when it cannot guarantee consistency is a detail left to the relevant application. That said, I think you’re right in that the client’s behavior — reactive or not — should not lend itself to further privacy problems. 

Best,
Chris

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 11 Mar 2022 18:22:34 -0800

On Fri, Mar 11, 2022 at 6:15 PM Christopher Wood <[email-masked]>
wrote:

> >>>> [5]
> https://datatracker.ietf.org/doc/slides-110-privacypass-key-consistency-and-discovery/
> >>>
> >> (
> https://datatracker.ietf.org/doc/html/draft-wood-key-consistency-02#section-4.1
> )
> I think there’s still a misunderstanding here. This draft discusses key
> consistency that can be _used_ by things like ODoH and OHTTP since, at the
> end of the day, key consistency is a separable problem. In other words, the
> draft doesn’t assume any particular protocol in which the key material is
> used, though the choice of consistency mechanism one uses may certainly be
> influenced by the protocol for which consistency is required.
>

Just to sharpen this point, there are uses of key consistency other than
for proxied protocols. For instance, consider the case where you want to
amortize the cost of solving a captcha. In this case, the server would
force the user to solve the captcha and then issue some number of signed
tokens (with some kind of VOPRF or something so that it didn't see the
actual token value) which can then be used to avoid the captcha the next
time. For obvious reasons, we'd like the same key to be used to compute the
VOPRF for each user.

> Hmm… I’m not sure I’m following you. Ensuring consistency is proving a
> positive, i.e., that all clients share the same view of the keying
> material. (It’s possible we’re saying the same thing but with different
> words.)
>
> That’s up to the client to decide, I think. It could choose to not use the
> key for the corresponding protocol, raise some alarms, or whatever else
> makes sense for the given application.
>
> As above, what the client does when it cannot guarantee consistency is a
> detail left to the relevant application. That said, I think you’re right in
> that the client’s behavior — reactive or not — should not lend itself to
> further privacy problems.
>

I think in the case I described above, you wouldn't use the token going
forward and maybe warn the user.

-Ekr

> _______________________________________________
> Secdispatch mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/secdispatch
>