[dns-operations] the mathematics of kaminsky spoofing probability

Fri Aug 1 22:52:40 UTC 2008

So, monitor for ICMP port unreachables leaving your organization. That would
let you know that someone is trying to poison your asset. Monitor ICMP Port
unreachables coming into to your authority servers. That will tell you that
someone is trying to poison your DNS identity. 

Get enough of this monitoring out there, will that have the criminals move
away from this attack vector to ones with less likely hood of getting
noticed?

> -----Original Message-----
> From: dns-operations-bounces at lists.oarci.net 
> [mailto:dns-operations-bounces at lists.oarci.net] On Behalf Of 
> bert hubert
> Sent: Friday, August 01, 2008 3:35 PM
> To: dns-operations at lists.oarci.net
> Subject: [dns-operations] the mathematics of kaminsky 
> spoofing probability
> 
> 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-resilienc
e#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
> _______________________________________________
> dns-operations mailing list
> dns-operations at lists.oarci.net
> http://lists.oarci.net/mailman/listinfo/dns-operations
> 