Subject: [dnsext] Possible alternatives to draft-vandergaast-edns-client-ip-00.txt ?

From: Brian Dickson <[email-masked]>
Date: Wed, 3 Feb 2010 13:06:02 -0400

If we're uncomfortable with sending client IP addresses to authority
servers, how can similar results be achieved?

This is similar to a problem in routing system design, which has been
looked at by the IRTF folks.

It boils down to three choices - push, pull, or publish/query.

All three have issues of scaling, timeliness, and
reliability/resiliency/shared-fate.

Sending client IP (however you try to anonymize it) is a "push".

Having the authority server(s)/CDN(s) somehow inform all the resolvers
in the world of their individual geo-ip (etc) boundaries (I don't even
know how that would even be possible) would be "pull", or "reverse
push".

The third alternative would be "publish/query".

It could conceivable be done in a manner that would achieve some
manner of scalability, some transparency regarding privacy issues, and
presumably good interoperability with adequate backward compatibility.

The exact mechanisms for signaling/negotiating usage of the mechanism
would likely be similar to draft-vandergaast-edns-client-ip-00.txt,
i.e. using EDNS[01] as an in-band, in-packet channel. (The alternative
would require additional look-ups.)

The "publish" part would be that the geo-ip information used by such
CDN networks, would be published in a DNS zone somewhere, probably in
a format similar to in-addr.arpa and ip6.arpa, but under its own
domain or sub-domain.

There would be one "tree" of geo-ip information per geo-ip provider,
whether that be internal to a CDN, or by a geo-ip provider, or whoever
else wants to do it themselves.

The RR's in those trees would be "nonce" values, each representing an
equivalence class of whatever geographic location+granularity the
geo-ip provider identifies as being "the same". A set of IP addresses
the geo-ip provider thinks are "close" would share a nonce.

The resolver would need to know which geo-ip tree to query, probably
signaled by either an EDNS[01] value (DNS label of the root of the
tree), or some kind of RR.

The resolver would then look up (either in its cache, or directly) the
client's IP, to determine the nonce.

The resolver would then attach the nonce in an EDNS[01] option to the
query, and the authority server would return an appropriate result.

The use of the nonce effectively anonymizes the query/answer.

The use of the same tree for many authoritative zones effectively
further anonymizes the geo-ip lookups, since the likelihood of the
nonce being found in-cache increases monotonically over time.

Paranoid clients can do lookups to well-known "safe" zones, or even
the geo-ip providers' nonce trees directly, to prime the cache, before
doing "real" lookups, e.g. of their <illegal goods/services
provider>'s web site.

Comments on this idea?

Anyone think it is worth pursuing?

Brian

---

From: Ted Hardie <[email-masked]>
Date: Wed, 3 Feb 2010 12:16:37 -0800

Hi Brian,

Some comments in-line.

> know how that would even be possible) would be "pull", or "reverse

I can imagine a different mix here that has the geo-ip boundaries published only
to the interested resolvers.  A resolver is "interested" whenever it has
a query for which localization is available; the problem is that it induces
latency.

Imagine a resolver sending a query for an RR to the relevant authoritative
server; it gets an answer and additional data that localization data is
available.  An interested resolver can then request the localization data
and serve the localized answer instead of the original answer.  This
unfortunately generates at least one additional round-trip plus the processing
time.  If resolvers chose not to get localized data when the requester was
local (presuming that the original answer had been localized to the resolvers
IP), then this also leaks the information that the resolver thought
the requester
was local.

This may fall into your publish/query model, but it seems slightly different.

> The use of the nonce effectively anonymizes the query/answer.

Doesn't this depend on the size of the set of IP addresses the geo-ip
provider thinks is close?  What if the set sharing a nonce is still a /24?

> Anyone think it is worth pursuing?

I think it is very useful to think about the problem space more generally,
rather than starting out with a solutions draft.

regards,

Ted Hardie

---

From: "George Barwood" <[email-masked]>
Date: Wed, 3 Feb 2010 23:39:34 -0000

----- Original Message ----- 
From: "Brian Dickson" <[email-masked]>
To: <[email-masked]>
Sent: Wednesday, February 03, 2010 5:06 PM
Subject: [dnsext] Possible alternatives to draft-vandergaast-edns-client-ip-00.txt ?

> servers, how can similar results be achieved?

I don't think we really are uncomfortable with sending client IP addresses.

But it seems to me the main alternate solution would be for clients to be
given a full list of IP addresses, and then pick the "best" one by using a
service for this purpose ( DNS caches could offer this as an extra service,
possibly consulting routing information to make a good choice ).

A "suppress tricks" option might be useful here, with meaning
"don't try and pick the best server, I know how to do that".

The problem here is the large amount of work required to develop the
necessary infrastructure, get clients updated, overcome inertia.

I think the draft is a more realistic solution for the short term.

---

From: Brian Dickson <[email-masked]>
Date: Thu, 4 Feb 2010 18:23:41 -0400

Hi, Ted,

My follow-up has in-line comments as well, plus a bunch of new stuff
at the bottom.

> a query for which localization is available; the problem is that it induces

I think the idea of the original draft
(draft-vandergaast-edns-client-ip-00.txt), of using EDNS0 options,
would be applicable in this context, to avoid latency. Basically, a
resolver doing this kind of thing,
would always do the "option", and keep track of places where the
option is recognized.

> time.

This would be true for the first query to that authority server, but
not subsequent queries, presuming
that the resolver tracks option-state by authority server.

Perhaps delegation servers which are geo-aware (i.e. which delegate to
geo-aware authority servers,
and which know how to add the EDNS0-option) could add unsolicited
information regarding the geo-ip-awareness
associated with the delegation itself?

If an authority server is known to answer queries including
localization data, and the resolver
is interested, the resolver would always send the localized version of the data.

Whether it makes sense to always request localized data, can be
reduced to the "dogbert law of salting meals".
(Dogbert always adds salt to food, because 999/1000 meals need salt,
while a meal is about 100 mouthfuls.
Tasting first before adding salt, results in 10 times more unpleasant
mouthfuls.)

> If resolvers chose not to get localized data when the requester was

Counter this with the notion, that when the requester is local, the
nonce for the local localization should be sent....

> provider thinks is close?  What if the set sharing a nonce is still a /24?

It is certainly possible, even probably, that there will exist nonces
which consist of a set of a single /24.

However, let's presume that the nonce granularity *generally* is only
as useful as the ability to easily aggregate
and serve the statistics on the nonces.
There is the competing desire to still have the performance benefits
of a sanely-sized set of nonces, e.g. hashed lookups.
Unique nonces at a /24 granularity (in IPv4) would require O(10M) nonces.
On the other hand, I doubt that market granularity beyond O(1000)
nonces has any particular value.
And from a true geographic and topological basis, the number of
policies the nonces would likely map onto would probably be smaller,
perhaps O(100).

The mappings of nonce -> policy would likely differ by zone, i.e. data
being served.
But the benefits of reducing the number of things mapped to O(1000)
would benefit *both* the CDN *and* the resolver operator.

The issues for those who find themselves in a /24 nonce, are left as
an exercise for the paranoid.
(Think NSA filter-fodder signature lines, only implemented in a
port-knocking style of fake-DNS-queries method, with randomized
choices.)

> rather than starting out with a solutions draft.

Agreed.

I only put the specifics in, to demonstrate that it was not a strictly
academic argument.

Once you can demonstrate that *a* solution is possible, then the
specifics of *which* solution
is preferred makes much more sense.

So, more generalized ideas on the problem space:

What assumptions on respective sizes of data set suggest feasibility
of any particular solution (what are the boundary conditions,
basically)
Whether there exists one or more actual geo-ip incoherent systems in
use today (we know this is true, actually)
Whether there is significant benefit to avoiding a "format war"
between proprietary systems
Whether there exist independent geo-ip providers (i.e. not also
serving incoherent data)
Whether there are enough independent producers and consumers and
combined producer/consumers of geo-ip/incoherent DNS data to justify
the effort
Whether there is demonstrable benefit (even to market dominant
entities) for cooperation among competitors in this space
Whether the expected number of direct participants (producing or
consuming geo-ip/DNS data) >> number of unique DNS software
implementations

What method to use for publishing the reverse -> nonce data
What method to encode the reverse prefix data
What the relationship is between query vs answer on reverse->nonce lookups
What size of nonce is needed
What, if any, structure or association needs to be used in the nonce

Where is computation required, and how much
Who benefits in what way, and at what cost to whom
What incremental changes are needed, and what is the impact to traffic
What existing systems are able to produce
What existing systems are able to consume

I think the assumptions will suggest avenues of discussion on the
other areas, so I'll tackle those first.

1) O(zones) >> O(nonces) (for zones using a geo-ip non-coherence mechanism)
=> It doesn't make sense to build a system with a trivial usage base,
in terms of zones
2) O(geo-ip-prefixes) >> O(nonces)
=> It only makes sense to use nonces if there is a many-to-one
mapping, on average
3) O(geo-ip-prefixes) << O(zones_i x nonce_i | i=1..N)
=> Stated another way - the expectation is that the geo-ip cache will
be fully populated before the zones are all cached - otherwise there
is no net benefit
4) cache hit %age (geo-ip-prefixes) >> cache hit %age (zone,nonce tuples)
5) speed of population of geo-ip-prefix->nonce cache >> 1:1 lookup:cache
=> What is the cold-start behaviour? Priming the system will be
important in general, on the resolver side. Analogous to priming the
root from the hints file.
6) afinity(stub-resolver-ip, geo-ip-prefix->nonce) >> random-distribution
=> The real benefits are when cache hit %age on zone data is better
than random. This assumption is the most tenuous, more data would be
needed. But. I would expect that regionalized content is more likely
to be regionally consumed.

To summarize the assumptions and their corollaries:
- Separating the geo-ip from the authority data, by means of reference
"nonce", is necessary but not sufficient, to achieve scaling,
interoperability, and privacy
- Speeding up the geo-ip cache population (e.g. by returning much more
data from the geo-ip mapping, than just a single prefix->nonce, for
any lookup) is likely needed to achieve critical mass fast enough
- The ability to selectively use (or not use) individual geo-ip sets,
gives control to the recursive resolver
- The size of the served set of zones needs to be big enough to justify the use
- The nonces cannot collide between geo-ip providers
- Efficient on-the-wire encoding is necessary
- Avoiding or eliminating geo-ip cache management "gunk" overhead, is
needed to achieve buy-in - that work should be done by the provider of
geo-ip data, to achieve a good "fairness" balanace
- The mostly-unchanging nature of the geo-ip mappings, may lead to
further network-centric optimizations, e.g. use of torrents, or other
kinds of peer-to-peer resolver cache population techniques
- It's all about the geo-ip cache, and making the nonce set size as
small as possible, particularly on a per-authority-server and/or
per-zone-served basis
- If a given RR is returned with a nonce, when queried with a nonce,
having an EDNS0 options "additional nonce" section listing other
nonces for which the same result is valid, would further improve
scalability

Here are the meta-arguments in favour of developing a standard for the
CDN-like DNS tricks, i.e. incoherent answers that are cacheable,
presuming the ability of a resolver to cache information relative to
query geo-ip.

A) There are already one or more systems doing so, even as a
vertically integrated set of components. Whether it is seen as a
"business", a "service", or a "protocol" is somewhat academic.
B) Currently, to make use of any one system, requires pointing one's
stub resolver at one such proprietary (set of) resolver(s).
C) There is no way to intelligently make use of multiple such systems,
without further proprietary arrangements.
D) Proprietary stuff means "no code available"

Now consider what adding a standard to this accomplishes:
I) Inter-provider cooperation is possible, e.g. where respective
geo-ip sets have "better" accuracy
II) Inter-consumer interoperability means real market competition is
the logical outcome
III) Arbitrary third parties can "roll their own" resolvers and expect
them to work fine
IV) The scaling benefits happen as a result of all of the above -
without limiting the resolver activity to equipment operated by the
provider of the geo-ip data, the scalability becomes more manageable.
Offloading of any portion of the resolver-side work, is of benefit to
the producer, and having resolvers under one's own control enhances
the trust and reliability of the combined system
V) The ability to select resolvers, or even build and operate
resolvers, in arbitrary locations, allows one to manage risk,
especially related to regionalized laws and surveillance. I can put a
compatible resolver on a hosted server anywhere I want, based on what
I worry most about. Privacy - Europe or Canada;
surveillance/tampering, not US or China; subpoena/extradition/etc.,
some remote place that ironically is generally uncool, like any "axis
of evil" country.
VI) Standards based and widely used or at least relatively high
demand, means it is likely to get built into one or more mainline DNS
software products - better for everyone.
VII) Places some aspect of design (including peer review) in dnsext -
for whatever that adds

DNS tricks might be a bad idea, but they're already a reality.

The idea is to reject one reality, and substitute another, better one
(to paraphrase Adam from Mythbusters.)

Brian