Subject: The math of kaminsky-spoofing a randomising source port resolver

From: bert hubert <[email-masked]>
Date: Fri, 1 Aug 2008 14:40:39 +0200

Hi everybody,

It was great fun to listen in on the DNSEXT meeting in Dublin yesterday. In
it I heard calls for understanding the problem better before rushing out
fixes, or even worse, a series of fixes that we ask people to install ASAP.

A few days ago I started to do the math on how hard it is to
'kaminksy-spoof' a fully randomised source port resolver. This message will
not elaborate on Dan's finding beyond the fact that it allows an attacker a
near infinite amount of chances to spoof a question.

The math is fairy trivial, but as I'm no expert it took me some time. I've
asked Evgeniy Polyakov and Jasper Spaans to read over my work, and they
found no obvious mistakes in it. But do take care, this stuff is fresh, and
I am a physics dropout!

The math
--------

I use the same symbols as in
http://tools.ietf.org/html/draft-ietf-dnsext-forgery-resilience#section-7.2
It may be instructive to read this section before delving into the rest of
this message.

      I: Number distinct IDs available (maximum 65536)

      P: Number of ports used (maximum around 64000 as ports under 1024
      are not always available, but often 1)

      N: Number of authoritative nameservers for a domain (averages
      around 2.5)

      F: Number of 'fake' packets sent by the attacker

      R: Number of packets sent per second by the attacker

      W: Window of opportunity, in seconds.  Bounded by the response
      time of the authoritative servers (often 0.1s)

      D: Average number of identical outstanding queries of a resolver
      (typically 1, see Section 5)

The combined chance to succeed with a single 'non-kaminsky spoofing
attempt':

   If the Window of opportunity length is 'W' and the attacker can send
   'R' packets per second, the number of fake packets 'F' that are
   candidates to be accepted is:

                          D * R * W
   F = R * W  ->   P_s  = ---------
                          N * P * I

Let's assume 'R' is fixed (it is a property of the network between the
attacker and the resolver).

Each spoofing attempt outlined above takes 'W' seconds. This means that if
you have T seconds for your attempt, you can perform T/W separate attacks.

The combined chance for success then becomes:

                       T/W
P_cs = 1 - ( 1 - P_s) 

If we put some common numbers in P_s, with source port randomization, we
find that P_s is really really small - P*I is in the order of 4*2^32,
whereas D, R and W are rather small (say 1, 100k and 0.1).

The approximation of P_cs is therefore:

WARNING: The approximation I use only applies for source port randomized
servers, otherwise the error is too big. It also does not hold for large
values of T!

             T * P_s             T * D * R
P_cs =      ---------      =     ---------
                W                N * P * I

Note how 'W' (the latency with the authentic auth server) fell out of the
equation!

Plugging in some common numbers, this gives:

P_cs = H * R / 1150000

Where H is the number of hours allotted. Again note that this is an
approximation,.

The full formula, which holds for larger values of R and T:

                               T / W                              10 * T
            (      D * R * W )                 (           R    )
P_cs  = 1 - ( 1 -  --------- )          =  1 - ( 1 -  --------- )         
            (      N * P * I )                 (        4.2e10  )

A caveat is that this math does not take into account the packet that asks
the original question, which happens once every 'W' seconds. The numbers on
the right also assume you can guess the authoritative nameserver that you
need to spoof.

If you plug in some realistic numbers in the P_cs formula, the chance of
succesfully spoofing a domain within two hours is around 8.1%, assuming you
can get 50000 packets/second to arrive at the resolver.

This will have cost you in the order of 1.5-2 gigabyte of packets though.

After 24 hours, the chance rises to around 64% - costing your 0.4TB of packets.

For your gnuplotting pleasure:
D=1.0
R=5000.0
W=0.1
N=1.0
P=64512
I=65535

Pcs(t) = 1 - (1 - ((D*R*W)/(N*P*I)))**(t/W)

Discussion
----------

If you delve into this deeper, it is also possible to do 'front loaded'
attacks where you do not wait out the full 'W' time window, but start on a
new question after (say) 0.1W already. This turns out not to disturb the
numbers measurably.

Evgeniy also did the math for not randomly blasting source port*ID packets,
but to make sure no duplicates are transmitted, and this turns out not to
matter a lot either.

The numbers above are all for 'perfect spoofing' - in actual life, packets
will get dropped, or the authentic authoritative server gets its answer in
quicker etc, so expect real life performance to be worse (or from our
perspective, 'better').

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.

The calculations above do not hold for nameservers that drop a query in case
of a detected spoofing attempt (when it sees too many "near misses"). This
technique does not invalidate the repeatability of the Kaminksy-technique,
but does minimise the chances of each individual spoof succeeding. There is
a reasonably popular resolver out there with such spoofing detection.

Smarter techniques?
-------------------
It may be possible that there are smarter, more adaptive ways to spoof a
server. But so far I haven't found them. Evgeniy is the kind of genius
however that I expect will discover new techniques if they exist - he is
currently working on his code.

Conclusion
----------
Even a perfectly source port randomized server can be spoofed, but it takes
real work and real amounts of time. More work is needed to protect the DNS.

-- 
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: Alex Bligh <[email-masked]>
Date: Fri, 01 Aug 2008 14:25:34 +0100

Bert,

> P_cs =      ---------      =     ---------

I see nothing wrong in your maths. Taking it from this stage
put in (as you suggest)
 D=1
 N=2.5
 I=65536
And look for P_cs=0.5

0.5 = T * 1 * R
      ----------
      2.5 * P * 65536

T = 81920 * P / R (seconds, for a 50% success rate)
Or
R = 81920 * P / T

So, for an attack on a non randomised port (P=1) to be more likely to
succeed than not within 100ms, you need approx 82,000 pps. Assuming Malory
is prepared to wait a day for his attack, he only needs to send one packet
every 10 seconds (practically undetectable).

With port randomisation (P=64000), Malory will need approximately 64,000
pps to have an even chance of a successful attack within a day.

Due to the effect of caching, Malory can presumably stop his attack when he
has a first successful hit, and the record will remain for just as long as
the TTL of the spoofed record.

This is assuming Malory doesn't do anything intelligent to speed up
his attack or parallelise multiple attacks, which would of course
make things easier.

It goes without saying that it would be trivial to orchestrate an attack
that focused solely on nameservers with low values of P, as (e.g.) the
OARC test demonstrate it's possible to guess this remotely.

Alex

---

From: bert hubert <[email-masked]>
Date: Mon, 4 Aug 2008 12:45:02 +0200

> After 24 hours, the chance rises to around 64% - costing your 0.4TB of packets.

The first gigabyte number is wrong - 2 hours of this will cost you around
36GB of packets. 24 hours around 0.4TB of packets.

This is assuming 100 bytes per attempt, which at 50000 packets/s is around
40 megabits/s. Given some overhead, make it a good 50 megabits/s.

        Bert

---

From: Masataka Ohta <[email-masked]>
Date: Mon, 04 Aug 2008 21:46:12 +0900

bert hubert wrote:

> correction! Re: The math of kaminsky-spoofing a randomising source port resolver

Why do you call such a well known vulnerability of DNS, which was
documented in section 2.2 of RFC3822 in 2004 several years after it
had been publicly known, kaminsky-spoofing?

> 40 megabits/s. Given some overhead, make it a good 50 megabits/s.

Your bandwidth figure is applicable to attackers but not to victims of
the attackers attacking many victims at once.

So, if an attacker have 1000 victims, the attacker needs 1/1000 less
time to compromise one or more victims of the attacker than an attacker
with only one victim and each victim feel 1/1000 less amount of traffic.

							Masataka Ohta

---

From: Florian Weimer <[email-masked]>
Date: Mon, 04 Aug 2008 15:57:17 +0200

> had been publicly known, kaminsky-spoofing?

I think you mean section 2.3 of RFC 3822.  I agree that the basic
attack is presented in that section.

I'm not sure if the authors were fully aware of the implications.  I
guess ISC would have rolled out source port randomization a long time
ago if they were.

> with only one victim and each victim feel 1/1000 less amount of traffic.

Correct.  And as we've seen over and over again, you can actually
monetize attacks even if you don't know the identities of your victims
before you start the attack, so it's a real problem.

-- 
Florian Weimer                <[email-masked]>
BFK edv-consulting GmbH       http://www.bfk.de/
Kriegsstraße 100              tel: +49-721-96201-1
D-76133 Karlsruhe             fax: +49-721-96201-99

---

From: Jaap Akkerhuis <[email-masked]>
Date: Mon, 04 Aug 2008 16:18:21 +0200

There is no section 2.3 in RFC 3822. That RFC is about "Finding
Fibre Channel over TCP/IP (FCIP) Entities Using Service Location
Protocol version 2 (SLPv2)" so I'm a bit lost where you all are
talking about.

	jaap

---

From: Paul Vixie <[email-masked]>
Date: Mon, 04 Aug 2008 14:22:41 +0000

> From: Florian Weimer <[email-masked]>
> 
> * Masataka Ohta:

indeed, noone on earth knew that this could be done in 11 seconds until
february 2008.  given the severe trauma caused by udp port randomization
for firewalls and NATs and solaris-10 and so on, i think there was a real
and correct cost-benefit tradeoff being made when this attack took days
or weeks of sustained multimegabit traffic to pull off.

> before you start the attack, so it's a real problem.

agreed.  my two even-worse-case scenarios for this have been every bot
doing a short 200-packet attack on some random RDNS every time it's about
to go back into its wait-for-command mode, and then the high-fanout mode
described above by masataka.  if the attacker's goal is to drive traffic
to a phishing site, then rather than think of creative ways to spell ebay's
or paypal's or a bank's URI-domain, or hiding that spelling behind images
or javascript, they can just toss their seeds into the wind and let them
sprout where they may.  (i live outside any city, and i have great respect
for the power of weeds and wild grasses to gradually take over every open
acre.)

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

---

From: Florian Weimer <[email-masked]>
Date: Mon, 04 Aug 2008 17:39:56 +0200

* Jaap Akkerhuis:

> There is no section 2.3 in RFC 3822.

RFC 3833, sorry.  *argh*

---

From: Stefan Schmidt <[email-masked]>
Date: Mon, 4 Aug 2008 17:52:17 +0200

> or weeks of sustained multimegabit traffic to pull off.

Tradeoff yes, trauma not really for that is something that requires a shock.
You knew that this patch needed some ironing out and that the best way of
achieving that is to just roll it out, no need to be shocked about that now.

When i switched our recursive DNS from BIND9 to PowerDNS recursor in 2006 i
was surprised that the recursor didn't use up more system resources than BIND9
even so it did randomize the query port. Apparently this can be done right
and from what i hear this also works pretty well on Solaris installations.

For years before my switch i wondered why ISC did not simply use Linux' epoll
or FreeBSD's kqueue where available, how about you?

	Stefan
-- 
"cron loves you too, that's why it sends you so much mail."
- Paul Vixie, author of Vixie Cron

---

From: Paul Vixie <[email-masked]>
Date: Mon, 04 Aug 2008 16:47:57 +0000

> From: Stefan Schmidt <[email-masked]>
> 

let's be clear about this.  neither dnscache nor powerdns was creating as many
simultaneous upstream flows in those years as the kaminsky defense requires,
and the market size for these tools was in those years so small that many of
the firewall / NAT / kernel instabilities BIND is running into as we deploy 
UDP port randomization were simply not encountered until now.

smaller and less popular implementations need have no fear of damaging their
reputations by being seen "legislating from the bench".  in BIND's case we are
not able to adopt simplistic attitudes like "requires a shock" lest our user
community storm our front yard with torches and pitchforks in hand.

that's why the nuanced view of this is as a "real and correct cost-benefit
tradeoff".  now that kaminsky changed the costs and benefits, ISC has adapted.

> When i switched our recursive DNS from BIND9 to PowerDNS recursor in 2006
> i was surprised that the recursor didn't use up more system resources
> than BIND9 even so it did randomize the query port. Apparently this can
> be done right and from what i hear this also works pretty well on Solaris
> installations.

see above.

> For years before my switch i wondered why ISC did not simply use Linux'
> epoll or FreeBSD's kqueue where available, how about you?

because it didn't make any performance difference for the number of
descriptors we had open simultaneously, this was another cost-benefit
tradeoff.  there was insufficient need to justify the complexity.  post
kaminsky, there is sufficient need to justify the complexity.

> - Paul Vixie, author of Vixie Cron

:-).

---

From: Bryan Seitz <[email-masked]>
Date: Mon, 4 Aug 2008 15:23:37 -0400

> UDP port randomization were simply not encountered until now.

FYI,

   In early 2006 I migrated approximately 120 BIND nameserver installations down to
approximately 30 PowerDNS installations for a very large ISP.  This migration not only 
allowed us to scale down the number of servers and save money on server hardware, but 
also improved query latencies and increased security due to port randomization. Thus,
source port randomization did not have an impact performance and we were able to reduce 
our server count by a factor of 4.

> > - Paul Vixie, author of Vixie Cron

it sure does ;)

-- 
             
Bryan G. Seitz

---

From: Stefan Schmidt <[email-masked]>
Date: Mon, 4 Aug 2008 22:56:36 +0200

> simultaneous upstream flows in those years as the kaminsky defense  

There you lost me, i am totally unclear what you mean by upstream flows.
In case of PowerDNS recursor:
Less outgoing queries per recursive lookup, true, but that did not  
change post 'kaminsky'.
As for releases i don't consider OS distributions upstream but anyway  
there had been some.

> UDP port randomization were simply not encountered until now.

True if you're counting market size in deployments and not users served.

> tradeoff".  now that kaminsky changed the costs and benefits, ISC  

So smaller is easier and closer to the community.
Sounds like better to me. *scnr*

   Stefan
--
"Since light travels faster than sound, people appear bright until you  
hear
them speak."
- anonymous

---

From: Stefan Schmidt <[email-masked]>
Date: Tue, 5 Aug 2008 01:20:29 +0200

> simultaneous upstream flows in those years as the kaminsky defense  

Thanks to another reader of this list the penny dropped. ;)
By 'kaminsky defense' you probably referred to the 'repeat the query n- 
times' or 'fallback to tcp' methods that were under discussion mostly  
on dns-operations@ and i thought you were referring to the mere port  
randomization.

What Bert Hubert's math is saying is that it requires a tremendous  
amount of time and packets to successfully spoof a recursive  
nameserver that uses good randomness on both query id and source port  
selection.
I won't say we're safe now, but i think he has proven that - if done  
right - it buys us enough time so that we do not need to rush into  
approving the next best thing.

As to catch up with another subthread: The 'Kaminsky Exploit/Bug/ 
Problem' is in the press and Dan is getting most of the credit for it,  
thats done, no way around it. I think calling it the Kaminsky whatever  
for now just simplifies referencing and makes it easier for people to  
follow the discussion. Lets just make sure we don't create a 'Kaminsky- 
RFC'.

  Stefan

---

From: Paul Vixie <[email-masked]>
Date: Mon, 04 Aug 2008 23:24:22 +0000

> There you lost me, i am totally unclear what you mean by upstream flows.

ok, never mind.

> > and the market size for these tools was in those years so small that ...
> 

i was not distinguishing.  we could argue about that distinction in today's
world but i was referring to "in those years" which was yesterday's world
and there is no argument to be made about that distinction historically.

> > smaller and less popular implementations need have no fear of damaging
> > their reputations by being seen "legislating from the bench".  in
> > BIND's case we are not able to adopt simplistic attitudes like
> > "requires a shock" lest our user community storm our front yard with
> > torches and pitchforks in hand.
> >
> > that's why the nuanced view of this is as a "real and correct cost-
> > benefit tradeoff".  now that kaminsky changed the costs and benefits,
> > ISC has adapted.
> 

smaller may be easier, but open source is either close to the community or
it's dead, so smaller isn't any closer to the community.  ISC chooses to
serve the largest possible community, and so we avoid ramming things down
the community's throat -- no "shocks" come through us.  amusingly, some of
the later-coming f/l/oss dns implementors have claimed that ISC was failing
to serve the community because we didn't shock enough, and others said we
were failing to serve the community because we shocked too often, and some
have even said that we got it wrong both ways.

followups to dnsops, please -- this thread isn't about the protocol any more.

---

From: Masataka Ohta <[email-masked]>
Date: Wed, 06 Aug 2008 16:35:12 +0900

Paul Vixie wrote:

>>>i'm comfortable with that approach, although i think it's safe to use
>>>it as glue for any NS RR,
>>
>>It is unsafe, because, 1.2.3.4 will give you forged answer for other
>>queries to ns.example2.com.
 
> when we last discussed this, i said that no nameserver should hand out
> glue for zones outside its apex, and that if it does hand out such glue
> then it ought not be believed.

As long as glue is used as glue and no other purposes, which is
necessary now, there is no point to avoid any glue information.

> my position hasn't changed.  has yours?

You should change your posision now.

BTW, the following senario seemingly require handling of additional
As so that "apex" is not a meaningful concept.

	1) an attacker ask a victim nameserver NS of example.com.

	2) the attacker repeatedly ask a victim nameserver MX of
	<random>.example.com.

	3) the victim nameserver forward the question to NS of
	example.com

	4) the attacker guess ID and gives false answers with source
	address of NS of example.com:

		<random>.example.com	MX	0 www.example.com

	with a additional record of

		www.example.com		A	<forged IP>

That is, except for glue-A, an additional record should be accepted only
if its name exactly matches the query name.

							Masataka Ohta

---

From: Florian Weimer <[email-masked]>
Date: Wed, 06 Aug 2008 10:55:36 +0200

> if its name exactly matches the query name.

This is correct.

Additional section processing has been useless for a while.  It turns
out that it is very difficult to make use of data in the additional
section in a dual stack environment because lack of A (or AAAA) RRs in
the additional section for a MX DNAME does not mean that these records
do not exist in DNS.  Consequently, you need to perform an additional
DNS transaction anyway in many cases.

---

From: Tony Finch <[email-masked]>
Date: Wed, 6 Aug 2008 14:53:33 +0100

> > will you propose text for the forgery-resilience draft that expresses
> > your point of view?
>
> "Glue A from a name server is, in general, outside of the zone served
> by the name server and is never authoritative. The glue can be used
> only for the original query."

Shouldn't this kind of thing go in a revision of RFC 2181?

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
FITZROY: SOUTHWEST VEERING NORTHWEST 5 TO 7. ROUGH. RAIN OR SHOWERS. MODERATE.

---

From: Paul Vixie <[email-masked]>
Date: Wed, 06 Aug 2008 15:41:10 +0000

> Shouldn't this kind of thing go in a revision of RFC 2181?

not that text, certainly.  but i do agree in general that once we can agree
on what should be done, an update to RFC 2181 and 2308 should be made.

---

From: Paul Vixie <[email-masked]>
Date: Wed, 06 Aug 2008 16:13:26 +0000

> You should change your posision now.

that's what you said ten years ago, too.  let me caution you now, as then,
against any attempt at "proof by vigorous reassertion."  i've demonstrated
(again) that your proposed solution is more complex than what everybody now
does (which is to either not send or not accept out-of-baliwick glue) and
that your proposed solution creates some new problems while failing to fully
address the problem we have now.  what's your factual, detailed, response?

> if its name exactly matches the query name.

i agree with florian's answer to this, where he said that the additional
data section is mostly useless.  i agree with your proposed policy, as
stated above.  the only A or AAAA RRs that should be sent or accepted in
the additional data section are those which (a) referenced by an NS RR
in the authority or answer sections, and (b) having owner names at or below
the owner name of the NS RRset who references them.  these records should
be sent onward if the NS RRset which references them is sent onward.  these
records should be used by the iterator to reach the nameservers whose 
addresses they are.  they should not be used in any other way, and if some
other use is demanded, then normal recursion should be done to get real
answers to replace what's in cache before that use is made.

---

From: Masataka Ohta <[email-masked]>
Date: Thu, 07 Aug 2008 09:47:39 +0900

> against any attempt at "proof by vigorous reassertion."

The bitter reality for you is that, if you admitted your mistake 10 years
ago, Kaminsky couldn't have used glue-A for his attack.

Kaminsky's originality beyond rfc3833 is to have provided a yet another
proof that your authority model is broken.

> i've demonstrated
> does

That many people are using a broken authority model means they
are insecure.

> the owner name of the NS RRset who references them.

Totally wrong. I never proposed such a broken policy.

							Masataka Ohta

---

From: Masataka Ohta <[email-masked]>
Date: Thu, 07 Aug 2008 09:52:18 +0900

Florian Weimer wrote:

> Or you cache referrals without storing any name server name.
> Conceptually, this seems to be the much simpler approach.

If you mean the cached referral is tagged with the original query,
the complexity is no different from mine.

If you don't, it's insecure.

Paul Vixie wrote:

> i don't think so, since nameservers can be renumbered without being
> renamed.

TTL, which must be properly configured by zone administrators, takes
care of it.

						Masataka Ohta

---

From: Paul Vixie <[email-masked]>
Date: Thu, 07 Aug 2008 01:04:47 +0000

> From: Masataka Ohta <[email-masked]>
> 

kaminsky's initial vector was poisoned NS RRsets, so, i doubt that i would
have seen myself as culpable in that way, even if i thought i'd made the
mistake you think i made.

> proof that your authority model is broken.

that explaination is just not detailed or complete enough.  please try again?

> That many people are using a broken authority model means they

that explaination is just not detailed or complete enough.  please try again?

> Totally wrong. I never proposed such a broken policy.

i was agreeing with what you had stated above, and then explaining how i
related this policy change to my own.  i think if you read my words
carefully you will see that we are not so far apart.

---

From: Masataka Ohta <[email-masked]>
Date: Thu, 07 Aug 2008 10:04:25 +0900

bert hubert wrote:

> How about just not caching the glue-A?

If you receive a referral and try several nameservers, you must
keep the glue information, which is called caching.

> It is out of bailiwick.

As I showed with MX, under ID guessing attack, "bailiwick" is a
broken concept.

Throw it away.

						Masataka Ohta

---

From: Masataka Ohta <[email-masked]>
Date: Thu, 07 Aug 2008 10:14:42 +0900

> that explaination is just not detailed or complete enough.  please try again?

The bitter reality for you is that, if you admitted your mistake 10
years ago, Kaminsky couldn't have used glue-A for his attack.

> that explaination is just not detailed or complete enough.  please try again?

The bitter reality for people using a broken authority model is that,
if they admitted their mistake 10 years ago, Kaminsky couldn't have
used glue-A for his attack.

> carefully you will see that we are not so far apart.

First, you must forget broken concepts such as apex and bailiwick.

Then, you must read my words carefully.

> if its name exactly matches the query name.

						Masastaka Ohta

---

From: Paul Vixie <[email-masked]>
Date: Thu, 07 Aug 2008 01:49:29 +0000

masataka, i think we're done here.  i have treated you respectfully, as one
internet engineer to another, and you have responded without honour.  goodbye.
--paul

---

From: Masataka Ohta <[email-masked]>
Date: Thu, 07 Aug 2008 10:56:58 +0900

Paul Vixie wrote:

> masataka, i think we're done here.

No. You have been done 10 years ago.

						Masataka Ohta

---

From: Florian Weimer <[email-masked]>
Date: Fri, 08 Aug 2008 09:59:51 +0200

> the complexity is no different from mine.

No, after detecting a referral, you record the addresses in the
additional section and store it at the name of the zone.  You don't
associate it with any name server names.  This means that the data can
only be used for this referral, and nowhere else.

This prevents cache insertion through glue records.  You can even use
address information from out-of-zone glue to locate servers (provided
that the upstream server filters out-of-zone data properly, which is
probably something you cannot assume).

> TTL, which must be properly configured by zone administrators, takes

Agreed.