Subject: [dns-privacy] DNS + 0-RTT

From: Tim Wicinski <[email-masked]>
Date: Tue, 5 Apr 2016 14:07:27 -0300

As many of you are aware, with the TLS1.3 spec, there is some security 
concerns around DNS+TLS1.3 0-RTT.  dkg put together some threat models 
and instead of forwarding some long thread, I figure I would put this 
out there and let Mr. Gilmor lay out his theories.

Daniel, you're it.

tim

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 06 Apr 2016 10:03:29 -0300

> out there and let Mr. Gilmor lay out his theories.

Thanks for the nudge, Tim!

There are several different subtle security considerations with 0-RTT:

 a) no client authentication
 b) limited forward secrecy
 c) no replay protection
 d) client linkability

I assume we're not talking about DTLS here, so i'm going to omit any
concerns about:

 e) UDP-style spoofing/flooding/reflection attacks

Have i missed anything?

Also, i might be confused below about the state of 0-RTT and how it
relates to PSK and session-resumption, though i'm more confident in my
understanding based on the TLS WG discussion yesterday.  But please
correct me if i'm confused!

client auth
-----------

For standard DNS traffic, i think we don't care about property (a).
that's good!

forward secrecy
---------------

IIUC for (b), the failing forward secrecy window is constrained by the
duration of the PSK/session resumption ticket.  That's doesn't seem
particularly worrisome to me for DNS.

replay protection
-----------------

For DNS we don't particularly care about replay attacks initially, but
replayable traffic might have some privacy implications.

For example, if Mallory can monitor the traffic to and from the DNS
resolver, and a TLS-wrapped DNS request is made that is answered from
the cache, then the attacker has no additional information about what
the answer is.

But if the request is replayable, Mallory can capture it, and replay it
at different intervals (when parts of the cache might be expired) to try
to coax the recursor to call out to the authoritative resolvers, which
might provide more information about the original query.

This is a minor leak, but probably not something to completely ignore.

client linkability
------------------

(this is in some sense the inverse of "no client authentication": we're
worried that the protocol might allow the server (or others) to identify
clients with greater precision than the client wants)

The TLS client doing 0-RTT can be linked by the server to their previous
session. If the client constrains itself to using each resumption ticket
exactly once, then it limits its linkability exposure to the DNS server.
If the client reuses the resumption ticket, then its sessions are
linkable by any network monitor.

Note that persistent TLS sessions that carry multiple DNS queries of
course have the same "linkability exposure" for queries within a single
TLS session, so it's not *just* a problem for 0-RTT.  and non-0-RTT
session resumption has exactly the same linkability exposure as 0-RTT,
aiui.  So this concern isn't specific to 0-RTT, but if a client wants to
limit its linkability exposure i think it will by definition limit its
use of 0-RTT.

What are the privacy risks of linkability?

 * The DNS server can establish a profile of a given user and their
   interests, even distinguishing between different users behind a LAN
   (or on a shared host with separate resolver sessions)

 * the DNS server (or network observer, in the case of reused session
   tickets) can track a given user as they move across the network,
   unless the client flushes its resumption cache upon network change.

Sadly, this linkability exposure risk is a net loss compared to
cleartext DNS, even compared with cleartext DNS with EDNS0 cookies :/

---------------

So, in conclusion, i think that DNS+TLS-1.3+0-RTT is not too scary.

That said, i'm not convinced that the savings of one round trip time is
particularly significant for the stub-to-resolver use case.  If the
connection is a long-standing connection that stays open (as we expect
for stub-to-resolver), the extra 1-RTT is amortized across lots of
queries; so it's not clear that connection setup speed is as important
in this case.

If we could have a story about how to mitigate the replay attack
concerns (which are already pretty minor), then the linkability concerns
are the only thing that remain, and those can be mitigated by
client-side policy about session ticket reuse (which would basically
extend to policy about when to use 0-RTT and when not to)

I'd be curious to think through how this all relates to TCP Fast Open if
anyone wants to brainstorm it with me.

       --dkg

---

From: Colm MacCárthaigh <[email-masked]>
Date: Wed, 6 Apr 2016 07:08:55 -0700

> forward secrecy

I'd expect many operators to re-use ticket encryption keys for far too
long, as we see with HTTPS today, so the effect is that a dns server bug
may unlock years of 0RTT data. For DNS, the query is always likely to fit
in there.

> replay protection

There's a simpler attack too; if the RRSet contains multiple RRs, it's
common for resolvers to rotate the order of the RRs in a fixed and
predictable order. So you can query a name you suspect was queried, then
replay the target query, then query the name again, and confirm your
suspicion. This requires only a copy of the target 0RTT section, and access
to query the resolver, so a typical wifi scenario would do. Multi-RR
responses are very common these days too.

-- 
Colm

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sat, 09 Apr 2016 06:58:10 -0300

On Wed 2016-04-06 11:08:55 -0300, Colm MacCárthaigh wrote:
>  On Wed, Apr 6, 2016 at 6:03 AM, Daniel Kahn Gillmor <[email-masked]> wrote:
>
>  > forward secrecy
>  > ---------------
>  >

This would be a good argument against doing any sort of session
resumption, i think, not just 0-RTT.

>  suspicion.

Just to make sure i understand this attack: suppose the rotation of two
RRs returned for a given response goes:

  A,B
  B,A
  A,B
  ...

Then the attacker would query, note the order, replay, then query again.
if the order received each time was the same, it's strongly suggestive
that it was the correct guess.  Is that the proposed attack?

>  This requires only a copy of the target 0RTT section, and access

It strikes me that we should discourage privacy-sensitive resolvers from
employing this pattern. though i'm not sure where that documentation
would go or how to write it.  Is there a term for this kind of stateful
response history leakage?

thanks for pointing it out.

         --dkg

---

From: Colm MacCárthaigh <[email-masked]>
Date: Sat, 9 Apr 2016 14:58:43 -0700

> resumption, i think, not just 0-RTT.

I intend more as an argument against the kind of session resumption that is
in TLS. Elsewhere the protocol has all sorts of reasonable limits on key
re-use, and they're enforced with decent mechanisms. But there's a gigantic
out in that ticket encryption keys are "outside" of  the protocols own
scope and so frequently they end up being a very weak point in the chain.
We should do something about that. I don't mean that session resumption as
a concept is a bad one.  I do mean that folks will hard-code those keys,
not rotate them nearly frequently enough, and that since DNS queries fit in
the 0RTT data the reality will be that a single key compromise could
uncover years of queries. Seems like a pretty big deal.

> that it was the correct guess.  Is that the proposed attack?

Yep - you have it. It's easier too when there are more RRs, since the
signal is stronger, but an attacker can repeat the attack as many times as
necessary to gain confidence that they've identified the query.

> response history leakage?

Bind9 calls it "cyclic" rrset-order:

https://www.safaribooksonline.com/library/view/dns-bind/0596004109/ch03s19.html

but I'm not sure if it comes from a recommendation in any RFC - I couldn't
find one from a quick search.

-- 
Colm

---

From: Shane Kerr <[email-masked]>
Date: Mon, 11 Apr 2016 14:52:44 +0200

Colm,

At 2016-04-09 14:58:43 -0700
> find one from a quick search.

People who know more can correct me if I'm wrong, but my understanding
is that this sort of RRset rotation is intended to work around clients
that would always pick use first RR from an RRset. Back in the day,
that meant that one gopher server would take all the load. ;)

Obviously a DNS server would prefer not to have to do the work of
ordering queries. If you use cyclic order, then you have to maintain
state about the last answer. If you randomize it, then you need some
source of entropy.

I haven't done a full search, but here's a quick look at support.

On the authoritative side, BIND 9 of course offers any option (fixed
order, round-robin, or ranomized), whereas NSD and I believe Knot are
fixed.

On the recursive side, BIND 9 again offers any response, whereas
Unbound is fixed (PowerDNS has a feature request for round-robin, but
is currently also fixed (*)).

Like most of DNS, privacy was not considered when developing this
capability.

My own recommendation would be that a fixed order be used in all
on-the-wire communication, and that we rely on client-side libraries to
either understand that multiple answers may appear to a question or at
alternatively to randomize the one answer they use. (Note that this is
independent of the privacy concerns, as it results in simpler code and
more deterministic behavior all around.) :)

Cheers,

--
Shane

(*) https://github.com/PowerDNS/pdns/issues/2521

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Mon, 11 Apr 2016 09:33:30 -0400

> state about the last answer. If you randomize it, then you need some

randomized doesn't require a lot of entropy -- it just requires some
small chunk at system startup to seed a CSRPNG that you can use
indefinitely.

> on-the-wire communication, and that we rely on client-side libraries
> to either understand that multiple answers may appear to a question or
> at alternatively to randomize the one answer they use. (Note that this
> is independent of the privacy concerns, as it results in simpler code
> and more deterministic behavior all around.) :)

I do like the simplicity and clarity of your proposal, but relying on
client-side libraries to be fixed seems like a non-starter,
unfortunately.  This is the classic IETF problem for any protocol with a
deployed base; the folks who have the incentive and capacity to fix some
endpoints aren't necessarily the folks who control the "right" endpoints
to fix :/

   --dkg

---

From: Colm MacCárthaigh <[email-masked]>
Date: Mon, 11 Apr 2016 10:35:06 -0700

> endpoints aren't necessarily the folks who control the "right" endpoints

Based on my reading of the charter, I think it's within the remit of this
WG to have a short I-D recommending random shuffling of RRs, permitting
fixed order, but "MUST NOT" for cyclic. For both recursive, and
authoritative servers. Happy to do it if folks don't think it's crazy.

-- 
Colm

---

From: Robert Edmonds <[email-masked]>
Date: Mon, 11 Apr 2016 13:54:01 -0400

> is currently also fixed (*)).

Unbound actually does support both fixed and randomized, and the entropy
is taken from an interesting place: the ID field from the query.

-- 
Robert Edmonds

---

From: Colm MacCárthaigh <[email-masked]>
Date: Mon, 11 Apr 2016 10:59:02 -0700

> is taken from an interesting place: the ID field from the query.

I think if there are more than 8 RRs, that won't be enough entropy to
generate all possible permutations.

-- 
Colm

---

From: Shane Kerr <[email-masked]>
Date: Wed, 13 Apr 2016 14:09:00 +0200

Colm,

At 2016-04-11 10:59:02 -0700

> generate all possible permutations.

At first I thought this was shocking. SHOCKING.

But if the goal is merely to mix up the answers a bit so that software
that uses the first RR does not always get the same answer, then it is
Good Enough(tm). Even with a fully-predictable QID this is fine.

It's only when you consider the order of the RR private that this
becomes a concern.

I admit I don't fully understand how information leakage is supposed to
happen. But if it is a valid concern then probably a cryptographically
secure random number generation is needed, and needs to be documented.

Cheers,

--
Shane