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

[url]http://tools.ietf.org/html/draft-ietf-dnsext-forgery-resilience#section-7.2[/url]

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.

--

[url]http://www.PowerDNS.com[/url] Open source, database driven DNS Software

[url]http://netherlabs.nl[/url] Open and Closed source services

--

to unsubscribe send a message to [email]namedroppers-request@ops.ietf.org[/email] with

the word 'unsubscribe' in a single line as the message text body.

archive: <http://ops.ietf.org/lists/namedroppers/>