[dns-operations] the mathematics of kaminsky spoofing probability

Fri Aug 1 22:35:28 UTC 2008

Hi everbody - this is mostly a crosspost from namedroppers (the IETF DNSEXT
list), with some typos fixed. Since the original post, several people have
voiced confidence over the mathematics, so it appears the numbers might
actually be correct.

I hope people find it useful.

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 you 0.4TB of packets.

For your gnuplotting pleasure:
D=1.0
R=50000.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