Subject: calculating the chance of spoofing an agile source port randomised resolver

From: bert hubert <[email-masked]>
Date: Mon, 4 Aug 2008 23:03:14 +0200

Dear working group,

This message sets out to calculate how hard it is to spoof a resolver that
takes simple, unilateral, steps to prevent such spoofing.

Unilateral in this case means that any resolver can implement these steps,
without changing the DNS protocol or authoritative server behaviour.
Everybody that implements the ideas below immediately improves the general
security of the DNS.

To save you all the reading, the simple unilateral measures can bring down
the chance to be spoofed to under 1% after a year of non-stop 50 megabit/s
packet blasting.

Note however that my math or my ideas may be wrong. Please read carefully!

Work so far
-----------
Recapping, calculations so far show that a fully source port randomized
nameserver can be spoofed with a 64% chance of success within 24 hours,
requiring around 0.4TB of packets to be generated. If 2 hours are available,
the chance of success is 8.1%.

This assumes that the attacker is able to generate around 50 megabits/s, and
also important, that the resolver is able to process 50k incoming responses/s.

Details are on
http://www.ops.ietf.org/lists/namedroppers/namedroppers.2008/msg01194.html
with the caveat that where it says "1.5 - 2 GB", it should say "36GB". 

Since that posting, quite a number of people have studied the calculations,
and they appear to hold up.

Note that the present post does not address the dangers created by those
able to actively intercept and modify traffic - people with such abilities
have little need to spoof DNS anyhow.

Situation
---------
The current situation is not acceptable - the resources needed to perform a
successful spoofing attack are available, if not generally, then to an
relevant subset of Internet users.

It turns out that it takes a lot of effort to get the world to apply even a
minor patch that has received tremendous front-page coverage on all the
security websites - the source port randomisation patches in this case.

So if we want to move quickly, we need a solution that can be rolled out
without having to upgrade large parts of the Internet.

Agile countermeasures
---------------------
There are a number of strategies a resolver could employ to make itself
effectively unspoofeable, some of these include:

A) Sending out questions over TCP/IP
B) Repeating questions a number of times, and requiring the answers to be
   equivalent

The problems with these two techniques is that they imply a certain overhead
and increase the general CPU utilization on the Internet.

Furthermore there are strategies that make spoofing harder, but not
impracticable:

C) Case games ('dns-0x20')
D) Use multiple source addresses
  
A very comprehensive enumeration of techniques can be found on
http://www.ops.ietf.org/lists/namedroppers/namedroppers.2008/msg01131.html

Sadly, it appears that on this impressive list there is nothing without more
or less unacceptable overhead that really gets us out of the woods, where
this is arbitrarily defined as reducing the spoofing success rate to below
1% after a year of non-stop trying at 50 megabit/s.

Detecting a spoofing attempt in progress
----------------------------------------
Since any spoofed response has a chance of around 2^-32 of being accepted,
it stands to reason around 2^31 bogus responses will arrive at the resolver
before the attacker manages to achieve his goals.

Since we know we have effective countermeasures available, like A and B
mentioned above, we could deploy these in case a spoofing attempt is
detected. Remember that A and B are generally available, but that we don't
want to resort to them all the time, for all domains, because of their
overhead.

Occasionally, port numbers get modified in transit. Additionally, responses
to queries sometimes arrive late enough that a new equivalent query has
since been sent. This means we should not consider a single response
mismatch to be a sign of a spoofing attempt in progress.

If we allow X mismatches before falling back on A or B, the chance of a
single query being spoofed is:

            X
        ---------  ~= 2^-32 * X
	N * P * I 

Assuming each individual attack lasts W seconds (being latency between the
authentic authoritative server and the resolver), the combined spoofing
chance after T seconds becomes:

                    T/W
1 - (1 - 2^-32 * X)       ~= 2^-32 * X * T/W

Putting in 20 for X and 0.1s for W, this gets us a combined spoofing chance
of 0.4% for a full day. Interesting, but not good enough, especially since
the attacker might well send only X packets per attempt, and launch far more
attempts.

However, if the attacker has a defined goal about what to spoof, each
successive attempt might be for a different domain name, or differ in other
respects, but all those attempts will share some characteristics.

Two things that will be identical, or at least reasonably unique are the
source address of the spoofed packet (aka, the network address of the
authentic authoritative server), plus the 'zone cut apex'. This last bit
requires some understanding of the way a resolver works.

(I made up this phrase, 'zone cut apex', but I think there are people with
better knowledge of DNS verbiage than I, I'd love to hear of a better name)

When a resolver asks NS1.EXAMPLE.COM for 'this.is.a.long.example.com', the
resolver knows it is asking NS1.EXAMPLE.COM in its role as 'EXAMPLE.COM'
nameserver - this is how it selected that server.

This means that an attacker might try many variations on
'this.is.a.long.example.com', what will remain identical is the 'zone cut
apex', which is 'EXAMPLE.COM'. What will also remain identical is the
(small) set of example.com servers available.

I'll get into more detail after Dan Kaminksy has held his presentation. The
upshot however is that multiple different attempts can be correlated, and
thus be counted together in the spoofing-detection counts.

If we conservatively decide to impose a 5 minute 'fallback to A or B'-regime
for a {source IP, zone cut apex}-tuple, and leave the detection limit at 20,
this means an attacker will have one chance every 5 minutes of getting in an
attempt.

This is equivalent to setting W equal to 300 seconds above, yielding us a
combined chance of spoofing a domain after a year of trying of 0.05%.

Well within our goal.

Reality intrudes
----------------
Sadly, the reality is that we won't recognize all spoofed packets that
guessed wrong, so to speak. Typical operating systems will only let a
nameserver know about packets that arrived on a socket open for that
purpose.

In the very worst case, the server is only listening on a single port, and
by the time a single mismatch is received by the nameserver process, on
average 32000 will have arrived on the network interface.

This means that in the calculation above, if we don't take additional
measures, we need to set X to 32000, leading to a combined *monthly*
spoofing chance of 6.4% (and a yearly near-certainty).

Fine tuning things
------------------
By raising the fallback period to an hour, the yearly spoofing chance
becomes 6.5%, assuming we only see 1 in every 32000 spoof attempts.

If in addition a small number of sockets is kept open, say 10, to function as
'canary ports', X reduces to 3200, and the yearly spoofing chance is back at
a low 0.65%.

Canary ports serve no function except to detect spoofing attempts. For
efficiency reasons, these ports may simply be ports that had previously been
used for source port randomisation, but kept around somewhat longer.

The number of canary ports, and the fallback period can be tuned at will to
achieve desired spoofing resilience levels.

Remaining Problems
------------------
Countermeasure 'A' does not work for domains not offering TCP service.
Countermeasure 'B' does not work for domains where single authoritative
servers generate differing answers to repetitive questions. This might
happen in case of (hardware) load balancers, or load balanced desynchronised
nameservers.

Best results might be achieved by alternately trying countermeasure A and B
- any server that does not support TCP *and* sends out inconsistent replies
is in for some tough love if someone attempts to spoof the domains it hosts.

Conclusion
----------
If the calculations and ideas elaborated above hold up, it appears feasible
to achieve arbitrarily low spoofing chances, without doing any further
protocol work.

Importantly, such changes would allow individual resolvers to protect their
users without having to wait for changes to all authoritative servers.

In other words, everybody who participates receives an immediate benefit.

-- 
http://www.PowerDNS.com      Open source, database driven DNS Software 
http://netherlabs.nl              Open and Closed source services

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: Wouter Wijngaards <[email-masked]>
Date: Tue, 05 Aug 2008 09:32:33 +0200

Hi Bert,

You seem to be hard at work continuing the forgery resilience
calculations for this new vulnerability.  I would suggest this is not
something for the forgery-resilience draft that is in WGLC right now?

The calculations are interesting, but I would prefer to discuss after
the full disclosure.  This means that informed opinions can be given
instead of vague guesses.

I think your baseline is wrong.  You quote 24 hours for one unpatched
chance?  But in the dnsext working group we saw 95 msec easily achieved?
There must be something wrong here.  This would bring the one year final
result here down to 0.095 / (24*3600) of a year time (about 30 seconds).

| Since that posting, quite a number of people have studied the
calculations,
| and they appear to hold up.

Where was that?

| Note that the present post does not address the dangers created by those
| able to actively intercept and modify traffic - people with such abilities
| have little need to spoof DNS anyhow.

Well they do, but not criminally so. (it may be an unethical action)

| Agile countermeasures
| The problems with these two techniques is that they imply a certain
overhead
| and increase the general CPU utilization on the Internet.

Yes, we lack good countermeasures.

Except for DNSSEC.  DNSSEC is a very good countermeasure.  Good protocol
work.  Serious data protection.  The protocol and software
implementations have just been completed end of last year (when DNSEXT
went to sleep).  But it seems that it needs some time before everyone
can deploy this.  I read your post as looking for interim solutions, to
buy the internet time to deploy DNSSEC.

| Detecting a spoofing attempt in progress
| the attacker might well send only X packets per attempt, and launch
far more
| attempts.

See Masataka Ohta's post.  Detection may not work well at all, and as
you argue can easily be circumvented.

| (I made up this phrase, 'zone cut apex', but I think there are people with
| better knowledge of DNS verbiage than I, I'd love to hear of a better
name)
| I'll get into more detail after Dan Kaminksy has held his
presentation. The
| upshot however is that multiple different attempts can be correlated, and
| thus be counted together in the spoofing-detection counts.

Zone cut apex idea.  Well I think I understand what you mean with zone
cut apex, at least :-)

| Conclusion
| ----------
| If the calculations and ideas elaborated above hold up, it appears
feasible
| to achieve arbitrarily low spoofing chances, without doing any further
| protocol work.

Unfortunately, I do not think the above holds up.

| Importantly, such changes would allow individual resolvers to protect
their
| users without having to wait for changes to all authoritative servers.
|
| In other words, everybody who participates receives an immediate benefit.

This is certainly a good property for solutions (i.e. like 0x20 has).

Best regards,
~   Wouter

---

From: bert hubert <[email-masked]>
Date: Tue, 5 Aug 2008 10:17:28 +0200

> something for the forgery-resilience draft that is in WGLC right now?

This is most definitely not for the draft, which I consider wrapped up and
finished. 

> chance?  But in the dnsext working group we saw 95 msec easily achieved?

I quote 4-8 seconds for very high chances of success, which is very much in
line with what was demonstrated at the working group:

  Interestingly, setting P=1 predicts very perfect chances of spoofing within
  4-8 seconds - about in line with what the exploits out there achieve on
  non-source port randomised servers.

>From the working group demo, I recall the attack succeeding most of the
time, and taking a number of seconds on average. 

> | Since that posting, quite a number of people have studied the calculations,

On namedroppers and dns-operations. Alex Bligh and Florian Weimer commented
specifically on the lists, Evgeniy Polyakov and Jasper Spaans also verified
the calculations, off-list. 

> buy the internet time to deploy DNSSEC.

Well - I personally would not bet on DNSSEC ever being deployed fully. But
that is irrelevant to the discussion - my post is indeed about what can and
perhaps needs to be done today, by any resolver on the internet.

> you argue can easily be circumvented.

Hmm - I may be wrong, but I've given it a lot of thought and I don't see how
the detection can easily be circumvented. Any individual spoofing attack is
overwhelmingly likely to fail, and can hence be detected safely.

But it would be very good to see if we as a working group could punch
practical holes in this. Our track record is not perfect, we did not see
everything coming, but the brightest minds of DNS do hang out here.

Regarding what Masataka Ohta says, I don't fully understand what he means,
but I think what he says does not mean spoofing detection can be evaded
easily.

	Bert

---

From: Alex Bligh <[email-masked]>
Date: Tue, 05 Aug 2008 09:25:49 +0100

>| and they appear to hold up.

I verified Bert's formulae down to the point I snipped in my email. I did
not verify the numbers he plugged in (I couldn't quite see where he
was going) but I did calculate using his formulae the packet rate
required where an attack on an unpatched server was more likely than
not to yield in less than 100ms (the "John Dickinson number"). This
was 82,000 pps (manageable, just, but then John said he demonstrated
it yielded once in less than 100ms - to have a 1 in 20 chance of succeeding
you'd only need 8,200 pps).

The read I took from Bert's calculations (which I think is different
from the read Bert took) was:
* Brute forcing the calculations shows that there is still a risk with
  port randomisation
* The situation is even worse if NAT is involved
* There are several possible bits of cleverness one could add that would
  make attacks (a) more effective and (b) less detectable. I left a large
  hint as to one of these but don't really want to spell it out on a
  public mailing list.

These leads me to believe that port randomisation is insufficient as
a solution. I believe the extra tweaks (canary ports etc.) are just
as likely to lead to DoS vectors as improved security.

I realise this may not be quite where Bert was driving, but I do
agree with the formula part of his maths.

> Yes, we lack good countermeasures.

I think the CPU concern is misplaced. We do not need to do full encryption /
decryption (which will be CPU intensive) to avoid spoofing. The worst
case CPU required is a hash on a packet, which is really no more
CPU than already needed to process a DNSSEC query/answer. This could
either be done by DNSSEC itself, by a mechanism like signing (e.g. a hash
of the answer with a preshared key), or by a mechanism like IPsec AH
transport integrity protection which is no worse (i.e. hashing the
transport layer too). There are several possibilities involving
existing protocols and potential new protocols but none seems to have
particularly serious CPU utilisation ramifications.

Alex

---

From: bert hubert <[email-masked]>
Date: Tue, 5 Aug 2008 10:38:54 +0200

> * The situation is even worse if NAT is involved

We agree fully on the above. I do think that we've raised the bar beyond the
obvious. I know several people trying to spoof a SPR-nameserver in their own
networks and nobody has succeeded so far, mostly for practical reasons.

See http://tservice.net.ru/~s0mbre/blog/devel/networking/dns/index.html for
an attempt in progress involving 250-300kpps. 

> (...)

Your belief may well be correct - but I also believe that if we really apply
our minds to it, it may be possible to discover and implement simple
countermeasures that make spoofing a fully source port randomised nameserver
so hard that it becomes harder than other attacks which would lead to the
same result.

For one thing, the canary ports don't work behind a stateful firewall
without further smartness being applied. So more thinking is definitely
needed.

> >| The problems with these two techniques is that they imply a certain overhead

The CPU concern is regarding the mere use of TCP or repeating queries. The
bar is set that low. I'm not sure if I agree with this sentiment btw - there
is not a lot that can be implemented without increasing packet size or
count.

	Bert

---

From: Alex Bligh <[email-masked]>
Date: Tue, 05 Aug 2008 11:18:59 +0100

--On 5 August 2008 10:38:54 +0200 bert hubert <[email-masked]> 
wrote:

> Your belief may well be correct - but I also believe that if we really
> apply our minds to it, it may be possible to discover and implement simple
> countermeasures that make spoofing a fully source port randomised
> nameserver so hard that it becomes harder than other attacks which would
> lead to the same result.

Sure. Personally I think solutions based on limiting the trust given to
the spoofed records supplied (as I think Masataka Ohta suggested) is
the most fruitful route here (which would kill the attack dead) but I
recognise I don't have sufficient protocol guru qualifications to help
much beyond pointing out it might well require caching more than one
instance of (purportedly) the same glue record, i.e. the query which
resulted in the cache entry is going to end up forming part of the
key in the cache lookup, which is a bit of change.

Alex