Subject: [dns-privacy] Solving the problem

From: Watson Ladd <[email-masked]>
Date: Sat, 25 Oct 2014 12:08:07 -0700

Dear all,

Let's imagine that we actually want to make it hard for anyone to
figure out what data is being requested via DNS. DNSCurve won't work:
the nameservers involved learn what the request is and who made it.
Combining it with DNSSEC+ISP cache also won't work: the ISP learns
what you requested from it, and that you made the request.

This doesn't change with QNAME minimization: caches still learn what
the request was, and some servers have to see the entire request,
including servers that aren't necessarily trusted.

It doesn't change if the entity actually doing the lookup is at the
other end of some connection, but merely moves the problem around.
Even if you share the entity doing the lookups with many other people,
this may still be an issue until we get to large enough numbers where
the entity becomes a real target it in its own right.

Can we actually solve this problem? Yes: there are PIR protocols that
force an attacker to compromise multiple independent parties to learn
the results of a query. Many of these PIR protocols are very
efficient. More work is needed to determine how inefficient they are,
impacts on the time taken to respond to a query, and what the best
algorithm is.

The cost is that caches may have to do slightly more work, and
communication costs will probably increase significantly. How to load
data in from the DNS into the caches when it isn't found is a problem
I'm still thinking about.

Sincerely,
Watson Ladd

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Sat, 25 Oct 2014 21:40:00 +0200

On Sat, Oct 25, 2014 at 12:08:07PM -0700,
 Watson Ladd <[email-masked]> wrote 
 a message of 37 lines which said:

> Can we actually solve this problem? 

"Privacy" is not binary. We do not try to make impossible for the
attacker to learn things, just to make it more difficult than it is. 

> Yes: there are PIR protocols that force an attacker to compromise
> multiple independent parties to learn the results of a query.

> Many of these PIR protocols are very efficient.

Do you have more specific references?

---

From: Watson Ladd <[email-masked]>
Date: Sat, 25 Oct 2014 13:34:17 -0700

> attacker to learn things, just to make it more difficult than it is.

This is why proposals should be clear about who they protect against: most
do not protect against DNS servers or DNS caches, and so most don't
actually protect against malicious ISPs or other entities that provide DNS
resolution. Some proposals don't even protect against observers in certain
parts of the network.

> Do you have more specific references?

http://cacr.uwaterloo.ca/techreports/2010/cacr2010-17.pdf
https://www.usenix.org/system/files/conference/usenixsecurity12/sec12-final90.pdf

Sincerely,
Watson Ladd

--
"Those who would give up Essential Liberty to purchase a little Temporary
Safety deserve neither Liberty nor Safety."
-- Benjamin Franklin