Re: [Ohai] DoubleCheck and CONNECT-UDP

[Ben Schwartz <[e-mail]>]

On Wed, Jul 27, 2022 at 3:42 PM Matthew Finkel <sysrqb=
[e-mail]> wrote:

> On Tue, Jul 26, 2022 at 10:57:33PM -0400, Ben Schwartz wrote:
> > During my presentation today, I suggested that the DoubleCheck procedure
> might not need CONNECT-UDP if it's acceptable for the Service Description
> Host (SDH), which is presumed to be affiliated with the gateway, to learn
> the pool of client IPs.  On second thought, I believe the CONNECT-UDP
> tunnel is indeed necessary.
> >
> > Without the CONNECT-UDP tunnel, clients would authenticate the KeyConfig
> by fetching it directly from the SDH.   In this arrangement, it is often
> possible for the gateway to identify the precise client IP that issued a
> particular OHTTP request, due to timing correlation.  If the rate of
> queries to this gateway (through this relay) is relatively low (<1 QPS),
> correlation is trivial.  The gateway can constantly rotate its KeyConfig,
> forcing clients to reauthenticate it before each OHTTP request.
> >
> > At higher query rates, other tricks are possible, such as rotating the
> KeyConfig and then slow-walking the authentication responses.  By sending
> authentication responses to each client "one at a time", the SDH and
> Gateway can observe the OHTTP request that follows each authentication
> response.
> >
> > In other words, OHTTP requests are linkable (via timing) to the
> corresponding KeyConfig authentication requests, so these authentication
> requests must not be linkable to anything else.  This means authentication
> requests from all clients on the relay must be indistinguishable, so they
> must all go through a single proxy.
>
> I agree, thanks for thinking through this attack and writing a
> concrete proposal for achieving key consistency and correctness. We
> should probably update the referenced informational KCCS document with
> some of these insights, as well. I also appreciate how this design
> leverages multiple discovery methods.
>
> As for feedback on the draft:
> 1) Is there a specific reason why this depends on the Access Service
> Descriptions? I see why they are useful, but they seem more like a
> convenience than a required dependency, is this true?
>

I would describe it as an important convenience.

This draft uses Access Service Descriptions in two ways:

1. To describe the Target service.  This is important because we need to
apply our consistency rules to three separate pieces of information:
- The Gateway URL
- The KeyConfig
- The Target service (however it is described)

If these aren't described by a single resource, we need to apply the
DoubleCheck procedure independently to each resource.  I think this is
probably possible to do safely, but it seems inefficient.  However, I have
heard arguments for splitting up this information (e.g. adding a layer of
indirection between the Access Description and the KeyConfig), and that may
be an OK solution.

2. To describe the Relay.  This is important because the client needs to be
configured with the Relay/cache, an affiliated transport proxy (e.g.
CONNECT-UDP), and ideally an affiliated DoH server.  I think we can
reasonably ask users to paste one magic URL into a settings field
somewhere, but I don't think we can ask them to copy-paste three magic URLs.

2) The concern described at the end of the introduction around not
> using the same update mechanism for key rotation as the one used for
> configuring the "Service Description" seems like a bit of a stretch.
> First, key rotation should not be occurring at such a high frequency
> that a slower (software release process) update mechanism is
> inadequate.


I'm not sure I agree with this.  Would you rely on the Android OS update
system to rotate a compromised key?  Are you sure your Windows updates take
effect without a reboot?

I agree that the example is artificial.  Perhaps a more compelling example
would be a public ODoH server, represented by a string (e.g. a URL)
copy-pasted from the public documentation into a settings panel.  The
string comes from a trusted source, but there is no live channel to update
it, so it can't contain the KeyConfig.


> Second, as mentioned in the KCCS document, we recommend
> specifying a "minimum validity period" for these keys such that a
> service can't easily partition users based on which key they know/use.
> While we didn't recommend any specific minimum period length, I would
> certainly recommend a lower-bound on the order of days (with typical
> rotation on the order of weeks, at a minimum). Providing more
> flexibility and agility opens more avenues for abuse, but I am
> interested in hearing any trade-offs you thought about for this, too.
>

Counterintuitively (at least to me), I believe DoubleCheck guarantees
authenticity and consistency regardless of validity period.  However,
extremely short validity periods might generate excessive revalidation
overhead.

3) Not directly feedback on this draft, but most obviously, the
> consistency guarantees are only limited to users of the same relay (I
> believe you mentioned this, but I can't find it now), so we may be
> missing "global" consistency (if the service is used via
> multiple/arbitrary relays). As discussed in other contexts, "global
> consistency" really reduces to ensuring each client request originates
> from a sufficiently large client anonymity set. Defining "sufficiently
> large" is likely context and application-specific, but it should be
> explicitly considered in deployments. This is related to "precondition
> (1)", but it is not the same. Do you have thoughts you can share on
> this?
>

I've been assuming that each client only accesses the service via one relay
(at least for an extended period of time).  If that's true, it follows that
the user's anonymity set is already reduced to the number of users on the
relay, and our challenge is to avoid reducing it further.

Spreading requests across multiple distinct relays is an intriguing idea,
but I haven't given it much thought.

4) A possible TODO: Regarding the response by a Service when the
> Service Description changes but a request's If-Match header identifies
> a previous version of the resource: Should the Service cache old
> versions for a certain time? Maybe something like an additional
> max-age length? The draft doesn't seem to specify when the Service
> should stop returning a success response for old resources.
>

The draft says

   If the Service Description changes, and the resource receives a
   request whose "If-Match" header identifies a previously served
   version that has not yet expired, it MUST return a success response
   containing the previous version.

So basically it's just the max-age.

5) A possible TODO: What should be the client's behavior if the
> response from the relay is rejected or if establishing the CONNECT-UDP
> tunnel fails? Fail-open? Fail-closed? Attempt check via alternative
> relay and/or choose different service? This could be
> application-specific logic, but it could be worth describing
> trade-offs of different behaviors in this situation.


Agreed!  I haven't thought much about what to do in this situation.


> In particular,
> the relay is in a position to maliciously perform a denial of service
> during this check and it could force the client to choose a different
> service (possibly one that will collude with the relay).
>

Interesting.

On a more nitty-note, I'm not sure how much you like the "DoubleCheck"
> name, but as another option we've referred to similar behavior as
> "multi-path verification".
>

I'm happy to adjust the name, but I do think we should try to make it clear
that this is a specific interoperable protocol, not just a strategy.

"Multi-path validation" attempts to solve more or less the same problem,
but it relies on different assumptions and achieves a different consistency
guarantee.