Subject: [dns-privacy] draft-wijngaards-dnsop-confidentialdns and DDoS

From: Paul Hoffman <[email-masked]>
Date: Fri, 13 Mar 2015 17:19:52 -0700

Greetings again. I mentioned this to Wouters a while ago, before the DPRIVE WG started, but it is worth bringing up here if the WG is considering this for widespread deployment.

draft-wijngaards-dnsop-confidentialdns running over UDP opens up the server to a trivial CPU denial-of-service because the server needs to attempt to do an expensive asymmetric decryption for every request that it gets that has the ENCRYPT QTYPE and an ENCRYPT RR in the authority section. It takes no cryptographic effort for a bot client to create the hard-to-process ENCRYPT RR: the RDATA can be any random crap. Note that the RDATA size in draft-wijngaards-dnsop-confidentialdns is pretty much unbounded, because the ENCRYPT RRs in a query contain not only the actual request, but they might also hold additional ENCRYPT RRs for keys for the reply. This asymmetry (bot clients take no effort to create requests that cause the server huge CPU resources for exponentiations) makes the proposal dangerous to deploy for a server because it can't decide when to not try to decrypt.

Changing draft-wijngaards-dnsop-confidentialdns over to TCP is one possibility, but even then this protocol forces a server to perform more expensive exponentiations than setting up a TLS session. Or you can re-invent IKEv2 with a cookie-like mechanism, but even then, the CPU DDoS is still an issue, although less of one.  These are why people have proposed TLS as a transport: all the anti-DDoS that has been developed for secure web servers comes to secure DNS servers for free.

--Paul Hoffman

---

From: "W.C.A. Wijngaards" <[email-masked]>
Date: Thu, 19 Mar 2015 16:49:05 +0100

Hi Paul,

On 14/03/15 01:19, Paul Hoffman wrote:
> Greetings again. I mentioned this to Wouters a while ago, before
> the DPRIVE WG started, but it is worth bringing up here if the WG
> is considering this for widespread deployment.
> 
> draft-wijngaards-dnsop-confidentialdns running over UDP opens up
> the server to a trivial CPU denial-of-service because the server
> needs to attempt to do an expensive asymmetric decryption for every
> request that it gets that has the ENCRYPT QTYPE and an ENCRYPT RR
> in the authority section. It takes no cryptographic effort for a
> bot client to create the hard-to-process ENCRYPT RR: the RDATA can
> be any random crap. Note that the RDATA size in
> draft-wijngaards-dnsop-confidentialdns is pretty much unbounded,
> because the ENCRYPT RRs in a query contain not only the actual
> request, but they might also hold additional ENCRYPT RRs for keys
> for the reply. This asymmetry (bot clients take no effort to create
> requests that cause the server huge CPU resources for
> exponentiations) makes the proposal dangerous to deploy for a
> server because it can't decide when to not try to decrypt.

Yes senders can send packets to the server that has to spend CPU on that.

Could perhaps a different algorithm, like ED25519, provide better
performance, and would that performance then be adequate?

The draft allows negotiation of a symmetric key so normally a lot of
asymmetric operations can be avoided by the use of a cache.

For a cookie mechanism, there is the cookie draft from Eastlake and
Andrews.  That solves other denial of service issues as well.  And use
rate limiting on un-cookied-asymmetric crypto.

The size is not really unbounded, because of UDP limits; but yes there
are no particular restrictions on size.  And it could work over TCP
too.  Are restrictions on size necessary?

> 
> Changing draft-wijngaards-dnsop-confidentialdns over to TCP is one
> possibility, but even then this protocol forces a server to perform
> more expensive exponentiations than setting up a TLS session. Or
> you can re-invent IKEv2 with a cookie-like mechanism, but even
> then, the CPU DDoS is still an issue, although less of one.  These
> are why people have proposed TLS as a transport: all the anti-DDoS
> that has been developed for secure web servers comes to secure DNS
> servers for free.

Yes it is a good idea to look at TLS and see what protection
mechanisms are missing from this simple 'encrypt DNS packet' draft.

Changing to TCP only is not really the main thrust for this draft.
However, it does work over TCP (if for some reason the exchange is
using TCP for larger data).

How is the exponentiation more expensive than TLS?  It still requires
asymmetric operations to establish it, and just as many?

Best regards,
   Wouter

> 
> --Paul Hoffman _______________________________________________ 
> dns-privacy mailing list [email-masked] 
> https://www.ietf.org/mailman/listinfo/dns-privacy
>

---

From: Paul Wouters <[email-masked]>
Date: Thu, 19 Mar 2015 12:02:50 -0400 (EDT)

> performance, and would that performance then be adequate?

Different algorithms differ in performance how much? A factor 2? Maybe
10? Compared to a botnet, I don't think that it is very relevant at all.

> Andrews.

Demanding source ip verification before allowing crypto seems a very
good idea with no real impact other than rejecting spoofed IPs or
old clients - and old clients won't support crypto anyway.

Paul

---

From: Zhiwei Yan <[email-masked]>
Date: Fri, 20 Mar 2015 07:43:53 +0800

Hi, all,
I think it's better that this draft contains some solution about the client authentication to decrease/avoid the DoS attack.
But it's really not the focus of this draft. In order to solve this problem, many other schemes can be used, such as DHCP, SAVI and DANE. Anyway, this draft can make use of them to authenticate the client.

Best Regards,
Zhiwei Yan

> 在 2015年3月20日，上午12:02，Paul Wouters <[email-masked]> 写道：
> 
> _______________________________________________
> dns-privacy mailing list
> [email-masked]

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 19 Mar 2015 17:59:34 -0700

> Yes senders can send packets to the server that has to spend CPU on that.

That's only part of the issue I raised: the bigger part is the huge amount of CPU the client can cause the server to spend with almost no effort on the client's part.

> performance, and would that performance then be adequate?

No to the latter question. Given that the client can cause an unbounded amount of decrypting for the server, a faster algorithm is nice but does not alleviate the problem.

> asymmetric operations can be avoided by the use of a cache.

Allows, but does not require. So, in the meantime, the attacker can starve the server's CPU.

> Andrews.  That solves other denial of service issues as well.

No, it really doesn't in the proposal here. It just means that the server will know which IP the attack is coming from. That's kind of useless for a resolver that has to provide service to everyone in an address range.

> And use

At that point, this protocol becomes more complicated than TLS.

> too.  Are restrictions on size necessary?

This protocol has asymmetric decryption on messages *much* larger than what are normally used for asymmetric crypto. So, yes, restrictions are really necessary.

> mechanisms are missing from this simple 'encrypt DNS packet' draft.

See above, as a start.

> using TCP for larger data).

If the protocol runs over TCP, it inherently causes either more round trips than TLS, or much more CPU usage. That doesn't seem like any advantage.

> asymmetric operations to establish it, and just as many?

In TLS, the asymmetric calculations are done on short values only to create a shared symmetric key. In this protocol, the asymmetric calculations are on much longer values, and a single client message can cause many such calculations. TLS (and IKE) were designed to avoid that.

--Paul Hoffman

---

From: Watson Ladd <[email-masked]>
Date: Thu, 19 Mar 2015 19:00:56 -0700

> That's only part of the issue I raised: the bigger part is the huge amount of CPU the client can cause the server to spend with almost no effort on the client's part.

A botnet can also spend a very small amount of bandwidth to generate
large bandwidth responses. Of course, the specification of multiple
possible response keys is pointless: DNSCurve had a very similar
design, without these wrinkles. I would like to know what exactly is
wrong with DNSCurve/DNScrypt as a solution to the kind of problems
we're talking about.

> No to the latter question. Given that the client can cause an unbounded amount of decrypting for the server, a faster algorithm is nice but does not alleviate the problem.

The current speed record for DH exchange is around 70,000 CPU cycles
on a recent Intel CPU. That means that a server can decrypt 50,000
requests per second. It's trivial to design a mechanism by which this
exchange has to be done only when new clients connect, rather than on
every request.
> No, it really doesn't in the proposal here. It just means that the server will know which IP the attack is coming from. That's kind of useless for a resolver that has to provide service to everyone…

Why can't a resolver stop serving abusive clients?

> This protocol has asymmetric decryption on messages *much* larger than what are normally used for asymmetric crypto. So, yes, restrictions are really necessary.

Is decrypting 32 bytes encrypted ECIES (or say crypto_box) actually
faster than decrypting 1024 bytes? The answer is "by epsilon": once
the asymmetric key is computed, it is reused, and the time difference
is for encrypting with AES. Of course, the draft doesn't actually
specify *any* encryption algorithm, which is why evaluating it is
difficult.

> In TLS, the asymmetric calculations are done on short values only to create a shared symmetric key. In this protocol, the asymmetric calculations are on much longer values, and a single client mess…

How does using TLS avoid the need to protect against DoS from sending
lots of Client Hellos? Also, the size of data encrypted with ECIES
doesn't affect the runtime.

Sincerely,
Watson Ladd

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

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 19 Mar 2015 19:23:05 -0700

On Mar 19, 2015, at 7:00 PM, Watson Ladd <[email-masked]> wrote:
> large bandwidth responses.

I was speaking only of CPU exhaustion, not bandwidth exhaustion. Nothing in this proposal makes the current bandwidth exhaustion attacks much better or worse.

> Of course, the specification of multiple

We've asked, repeatedly, for specs on DNScrypt to consider in the WG. I don't see any in the Internet Drafts repo.

> exchange has to be done only when new clients connect, rather than on

That speed is for 16-byte messages, yes? The proposal is has messages much larger than that, some of which require multiple asymmetric decrypts.

> Why can't a resolver stop serving abusive clients?

Because it can't identify them early enough, given the way that the protocol allows many decrypts needed per query.

> specify *any* encryption algorithm, which is why evaluating it is

This protocol is not using ECIES.

> lots of Client Hellos?

It doesn't. However, dealing with a bogus ClientHello takes significantly less work than dealing with the possible client messages in this protocol.

> Also, the size of data encrypted with ECIES

This protocol is not using ECIES.

--Paul Hoffman

---

From: "W.C.A. Wijngaards" <[email-masked]>
Date: Fri, 20 Mar 2015 10:02:18 +0100

Hi Paul,

On 20/03/15 01:59, Paul Hoffman wrote:
>>> Greetings again. I mentioned this to Wouters a while ago,
>>> before the DPRIVE WG started, but it is worth bringing up here
>>> if the WG is considering this for widespread deployment.
>>> 
>>> draft-wijngaards-dnsop-confidentialdns running over UDP opens
>>> up the server to a trivial CPU denial-of-service because the
>>> server needs to attempt to do an expensive asymmetric
>>> decryption for every request that it gets that has the ENCRYPT
>>> QTYPE and an ENCRYPT RR in the authority section. It takes no
>>> cryptographic effort for a bot client to create the
>>> hard-to-process ENCRYPT RR: the RDATA can be any random crap.
>>> Note that the RDATA size in 
>>> draft-wijngaards-dnsop-confidentialdns is pretty much
>>> unbounded, because the ENCRYPT RRs in a query contain not only
>>> the actual request, but they might also hold additional ENCRYPT
>>> RRs for keys for the reply. This asymmetry (bot clients take no
>>> effort to create requests that cause the server huge CPU
>>> resources for exponentiations) makes the proposal dangerous to
>>> deploy for a server because it can't decide when to not try to
>>> decrypt.
>> 
> That's only part of the issue I raised: the bigger part is the huge
> amount of CPU the client can cause the server to spend with almost
> no effort on the client's part.
> 
>> Could perhaps a different algorithm, like ED25519, provide
>> better performance, and would that performance then be adequate?
> 
> No to the latter question. Given that the client can cause an
> unbounded amount of decrypting for the server, a faster algorithm
> is nice but does not alleviate the problem.

Thank you (and Paul) for telling me.  I thought it would have been a
solution, and that asymmetric crypto was fast enough for doing it all
the time.  There are likely many parts of solutions, in IKE, TLS, that
are much better than this draft, because I do not know IKE and TLS
internals.

>> The draft allows negotiation of a symmetric key so normally a lot
>> of asymmetric operations can be avoided by the use of a cache.
> 

The crypto in the packet format causes unnecessary asymmetric load.
The packet format has to be fixed in some way.

The client cryptographical authentication: solution space is big for
this.  I am also trying to avoid it, as it is not the main point now.

Cookies help with identifying IPs in the DoS; and then ratelimiting
can be applied.  But legit IPs can continue the attack.

TLS does not have this problem, but why doesn't it?  The server has to
do crypto for a client.  And clients can start new connections by
sending a (couple) packets.  If cookies do not solve it, TCP also does
not solve it.  Is the idea that the client has to invest CPU power in
computing something before the server will invest CPU power?  botnets
will have more cpu power than the server (just like bandwidth)...
Otherwise, the solution seems to look at the protection mechanism from
TLS (if it has any) and see if that can be copied.

The protocol could be changed to mandate that every message has to
carry the SYM key establishment, for this one packet or for more
packets.  That SYM key encrypts a couple bytes algorithm identifier
and the crypto material for a symmetric key, thus it is small.  And
then change to mandate that that key is used to crypt further
materials in the packet.  That change may lower the CPU required for
the server (and in the answer, for the client)?

Best regards,
   Wouter

> 
>> For a cookie mechanism, there is the cookie draft from Eastlake
>> and Andrews.  That solves other denial of service issues as
>> well.
> 
> No, it really doesn't in the proposal here. It just means that the
> server will know which IP the attack is coming from. That's kind of
> useless for a resolver that has to provide service to everyone in
> an address range.
> 
>> And use rate limiting on un-cookied-asymmetric crypto.
> 
>> The size is not really unbounded, because of UDP limits; but yes
>> there are no particular restrictions on size.  And it could work
>> over TCP too.  Are restrictions on size necessary?
> 
> This protocol has asymmetric decryption on messages *much* larger
> than what are normally used for asymmetric crypto. So, yes,
> restrictions are really necessary.
> 
>> 
>>> 
>>> Changing draft-wijngaards-dnsop-confidentialdns over to TCP is
>>> one possibility, but even then this protocol forces a server to
>>> perform more expensive exponentiations than setting up a TLS
>>> session. Or you can re-invent IKEv2 with a cookie-like
>>> mechanism, but even then, the CPU DDoS is still an issue,
>>> although less of one.  These are why people have proposed TLS
>>> as a transport: all the anti-DDoS that has been developed for
>>> secure web servers comes to secure DNS servers for free.
>> 
>> Changing to TCP only is not really the main thrust for this
>> draft. However, it does work over TCP (if for some reason the
>> exchange is using TCP for larger data).
> 
> If the protocol runs over TCP, it inherently causes either more
> round trips than TLS, or much more CPU usage. That doesn't seem
> like any advantage.
> 
>> How is the exponentiation more expensive than TLS?  It still
>> requires asymmetric operations to establish it, and just as
>> many?
> 
> In TLS, the asymmetric calculations are done on short values only
> to create a shared symmetric key. In this protocol, the asymmetric
> calculations are on much longer values, and a single client message
> can cause many such calculations. TLS (and IKE) were designed to
> avoid that.
> 
> --Paul Hoffman
>

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 20 Mar 2015 10:33:59 +0000

On 19/03/15 23:43, Zhiwei Yan wrote:
> Hi, all, I think it's better that this draft contains some solution
> about the client authentication to decrease/avoid the DoS attack. But
> it's really not the focus of this draft. In order to solve this
> problem, many other schemes can be used, such as DHCP, SAVI and DANE.
> Anyway, this draft can make use of them to authenticate the client.

I, and probably others, would fairly strongly object if the work
of this group that is intended to enhance privacy required all
clients to be authenticated, and hence identified, and thus give
up privacy.

There may be a place for authenticated clients in this space (e.g.
perhaps within an Enterprise n/w) but that had better not be the
main mitigation for potential DoS attacks.

S.

> Best Regards, Zhiwei Yan
>> Different algorithms differ in performance how much? A factor 2?
>> Maybe 10? Compared to a botnet, I don't think that it is very
>> relevant at all.
>> 
>>> and Andrews.
>> Demanding source ip verification before allowing crypto seems a
>> very good idea with no real impact other than rejecting spoofed IPs
>> or old clients - and old clients won't support crypto anyway.
>> 
>> Paul
>> 
>> _______________________________________________ dns-privacy mailing
>> list [email-masked] 
> _______________________________________________ dns-privacy mailing
> list [email-masked]

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 20 Mar 2015 09:11:51 -0400

> main mitigation for potential DoS attacks.

There is message authentication, client authentication, device
authentication and user authentication and they are very different things
where privacy is concerned.

One of the reasons why I am not keen on 'just' use TLS is that it forces
one particular approach that is optimized for a different purpose. I find
it much easier to provide the desired

As far as DNS privacy goes, the big performance issue is the DNS lookup. We
need to get latency reduced to the absolute minimum there and we need to
have strong protections preventing people from DoS-ing the resolution
hosts. For this particular interaction, my preference is for symmetric key
based authentication using a kerberos style ticket to allow stateless key
management on the server. The request is going to be encrypted, so we have
a symmetric key at this point.

So the question is how to establish a shared secret/ticket pair and how
long it would be valid for.

In the enterprise case we are going to require authentication of the user
and/or device in order to connect to enterprise resources behind the split
horizon. Here we will want to do a one time user/device authentication to
establish a local credential.

In the anonymous use case, the simplest approach might be to simply set up
a TLS connection to the DNS service and request a ticket via a HTTP/JSON
type interaction. That is what my current drafts describe.

The problem with the purely anonymous case is that what our customers are
currently paying us to provide is not actually 'privacy'. They are paying
for a mechanism that bypasses local DNS based censorship and a curated
DNS/IP address space that has the criminal element excluded. That makes
things rather complicated because quite often a user may have different
ideas about what censorship is good and which is bad.

This is quite a challenging problem to get 100% right. But if the solution
is less than 100% we are not going to get Microsoft, Apple or Google to
deploy on the platforms 95% of the market uses.

---

From: Watson Ladd <[email-masked]>
Date: Fri, 20 Mar 2015 07:55:02 -0700

> main mitigation for potential DoS attacks.

What's wrong with DNScrypt? Apparently people asked where the docs
are: https://github.com/jedisct1/dnscrypt-proxy/blob/master/TECHNOTES.

The writeup isn't the best, but it should be possible to see what is
going on from this, and it seems very similar to the Wijngaards draft.
Sincerely,
Watson Ladd

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 20 Mar 2015 12:41:43 -0400

> going on from this, and it seems very similar to the Wijngaards draft.

Well since this is a standards forum, creating the design is 10% of
the work and getting the specification written down is 80%. Getting
people to agree on one approach is the other 90%.

I did take a look at DNSCrypt. I don't think it is very different from
mine. The main feature I add that I don't think they have is that I
eliminate the overhead from multiple record queries. Which I think is
necessary to make DNSSEC deployment practical or use of SRV
ubiquitous.

Today a DNS client typically makes separate record lookups for A and
AAAA records. In discussions with the browser providers they have told
me that two lookups is a hard limit for them. They are not willing to
perform additional lookups for SRV, TLSA or any other records.

While DNS does in theory support multiple queries, it only returns one
result. This made it impossible to use multiple queries in practice
and much of the legacy infrastructure is built on the assumption that
there is only one query per DNS request/response. Now given that we
are planning a change that is discontinuous, this is arguably
something we could fix by changing the DNS protocol to add multiple
responses. But that approach would require significant changes in a
part of the DNS stack that is not currently affected. And it would
still leave the problem of what to do when a response overruns the
Ethernet MTA etc.

In my experiments, it is possible to fit a 'comprehensive' DNS query
consisting of A, AAAA, SRV and TLSA records in one UDP request packet
and one UDP response packet smaller than the ethernet MTA for 100% of
'sensible' configurations that don't involve DNSSEC.

Unless you start picking really long DNS names or obnoxiously long
sets of SRV options, responses fit comfortably inside a packet.

DNSSEC is a different matter if you are using RSA2048 as the signature
scheme. 256 bytes per key and per signature is just too large to
expect to be able to fit in one packet. But even there the signatures
still fit very comfortably in 2 packets.

What I am trying to do here is to maximize the acceptability of DNS
Privacy to potential deployment constituencies as my top priority.

* Meet all the performance constraints that the Microsoft, Mozilla and
Google teams have raised with me in the past.

* Maximize the potential for early adopter use by making DNS Privacy
the solution to the problems of DNSSEC deployment and the use of
enterprise VPN.

* Minimize the complexity of the solution. By which I don't mean 'link
to a huge library that is at best understood by EKR and Peter Guttman.

Against this we have folk whose best argument is that their solution
can be almost as good as mine if people deploy new TCP stacks.

---

From: Paul Wouters <[email-masked]>
Date: Fri, 20 Mar 2015 13:01:05 -0400 (EDT)

On Fri, 20 Mar 2015, Watson Ladd wrote:

> What's wrong with DNScrypt?

It's just a preconfigured new VPN protocol where the clients need to
know the public key of this new VPN protocol provider to setup a VPN
limited to "DNS"Curve packets.

- It is incompatible with IETF VPN protocols (IPsec/IKE, TLS)
- It is incompatible with actual DNS packets
- It does not support (from what I can deduce) DNSSEC
- It requires chaining to an actual DNS resolver
- It has no crypto agility (from what I can deduce)

The Wijngaards drafts also defines a new VPN protocol, but for a very
good reason - it is attempting to use the DNS protocol as transport,
while remaining completely compatible with DNS (eg does not throw
cruft over port 53 that is not DNS) Whether that is a good idea,
I am still undecided on but to me it is a justification for why not
using TLS or IKE/IPsec

If the starting point is "preconfigured public key", I see no reason why
not to use IPsec or TLS as the transport to encrypt regular DNS traffic.

In other words, dnscrypt does not add anything to our toolbox that we
don't already have, so there is no reason to add it.

Paul