dns cache threats

[VictorKaum]

*for educational purposes only*

While surfing on AO I noticed that I did not came accros an article about the renewed (half 2003) DNS cache poisoning threat. Since this info is all available on the net on several different boards and sites and I only offer a summary, I do not consider this as a tutorial. While many tutorials I have seen on AO are nothing more than that.

The purpose of this thread is to gain attention to a very old and known idea of attack that recently came back, after the implementation of mathematical ideas into scripts poisoning dns caches allowing several nasty stuff on the net. From 'changing' website content by simply directing to a spoofed site, to 'man in the middle attacks' against companies and individuals in order to gain access to information or internal systems.

It's basic knowledge that bind is/was vulnerable to several dns cache poisoning approaches. Therefor many info on the net is provided to allow adminstrators to construct cache systems that are less vulnerable to such attacks.

The 'old style' dns cache poisoning has recently gained popularity again with the discovery of two possible new attacks. One uses the known mathematical birthday paradox (Vagner Sacramento), the other uses a sligthly complicated phase space analysis spoofing (Michal Zalewski) to poison the cache of BIND systems. Vagner Sacramento and Joe Stewart discovered that a dns server replies with n answers to n queries thus simplifying dns cache poisoning using the birthday paradox math. Ramon Izaguirre wrote a tool (happydnsspoofing) implementing this knowledge to poison BIND dns cache.

The birthday paradox is also an important mathematical issue for cryptographers.

The Birthday Paradox
Theorem BIRTHDAY PARADOX: Applying a random mapping f : S -> S to \sqrt{2|S|} values is expected to produce about 1 collision.
Proof: Let ck be a list of choices, where each choice comes from S, and let Ck be the list of all such choices.
By definition, if there is a collision in ck in Ck, there will be an i,j in 0..k-1, i < j, such that cki = ckj.
Given i,j in 0..k-1, i < j, every value in (SxS) is equally likely to be the value of (cki, ckj). This follows from Ck being SxSxSx...xS.
There are |S|*|S| possible pairs in SxS,
|S| of which have the same first and second term,
so 1/|S| of all possible pairs have the same first and second term.
Each c in Csqrt(2|S|) has (sqrt(2|S|)(sqrt(2|S|)-1)/2) = (|S|-sqrt(|S|/2)) pairs (ci, cj) where i < j.
Since every possible pair is equally likely, the chances that c has a (ci, cj) with i < j and ci = cj is (|S|-sqrt(|S|/2))/|S|, which is about 1.
Therefore a set of sqrt(2|S|) independent choices from S will have about 1 collision.

source: http://science.howstuffworks.com/fra.../exchange.html

This means for example that one away password hashes can be calculated much faster cause you only need to find two messages with a hash of the same value. This only requires hashing 2 to the power of m/2 random messages and not 2 to the power of m messages. This dramaticly improves the change to get the hash. So whenever you have to sign a document digitaly, make sure you make a slight change (adding a space por dot) in order to prevent that a very similar false document could match the hash of the real one signed by yourself, since a set of independent choices will have about 1 collision, in that case a real and false document hash.

Those discoveries are important cause the majority of DNS caching is assured by BIND (Berkeley Internet Name Daemon) running on *nix. Since the raise of firewalls, IDS, virusscanners and all kind of sorts of defence the DNS server still is an interesting target. For example to do 'man in the middle attacks'. A very popular attack, aclaimed to be very unsuccesfull due to randomized sequences, but when those random numbers are not so random as thought things become easier. The mathematical 'solutions' like the birthday paradox and the phase space analysis prove that a high grade of succes is possible without the need of thousands and thousands of packets. This indicates that man of the middle attacks using dns cache poisoning are a reality. Are you sure you are surfing on the server you think you are?

For example Alex want to make a secure connection (SSL) with his Bank, Camille has poisoned the DNS cache of Alex's ISP.

Normal situation
Alex -> ISP -> Bank
Alex <- ISP <- Bank

Man in the middle attack
Alex -> Poisoned DNS cache ISP -> Camille (spoof) -> Bank
Alex <- Poisoned DNS cache ISP <- Camille (spoof) <- Bank

This is all old news, and are very known attacks, allthough the new possibilities shed another light on the issue.

Therefor it's important to use more secure DNS constructions in order to complicate or wipe out such forms of attacks. This can be done with the split-split DNS setup. The simple split dns does not give you a proper defense against such types of session hijacking the split-split dns does. The end customer however can only hope his or her ISP implemented a decent (read secure) dns solution.

The split-split dns approach uses different cache servers to separate internal from external queries with separate dns resolvers and advertisers

So in fact you have at least three servers doing your dns caching, more (6) if you need load balancing or error tolerance.

- a DNS resolver in the DMZ
- a DNS advertiser in the DMZ
- an internal DNS server



---------------------------------
| More info and important links |
---------------------------------

'BIND'
http://www.isc.org/products/BIND/

'Securing a name server'
http://www.linuxsecurity.com/resourc...ame_server.pdf
http://www.isc.org/products/BIND/bind-security.html

'Birthday Paradox'
http://science.howstuffworks.com/question261.htm
http://www.sciencedaily.com/encyclop...rthday_paradox

'Birthday paradox and cryptography'
http://www.itsecurity.com/dictionary/bday.htm
http://science.howstuffworks.com/fra.../exchange.html

'Birthday attack'
http://www.x5.net/faqs/crypto/q95.html
http://mathworld.wolfram.com/BirthdayAttack.html
http://mathworld.wolfram.com/Cryptog...hFunction.html
http://www.ciphersbyritter.com/NEWS4/BIRTHDAY.HTM
http://www.chiark.greenend.org.uk/pi...er/020781.html
http://cert.uni-stuttgart.de/archive.../msg00311.html

'phase space analysis spoofing'
http://razor.bindview.com/publish/pa...seq.html#phase
http://www.securiteam.com/securitynews/5JP021P4AO.html

'The next generation of DNS cache poisoning'
http://www.inet-sec.org/docs/spoofin...-poisoning.htm
http://mlug.missouri.edu/list-archiv.../msg00185.php3

'split-split dns on isaserver'
http://www.isaserver.org/tutorials/Y...Split_DNS.html

'Microsoft article on how to create a split-split cache'
http://download.microsoft.com/downlo..._brain_DNS.doc

[Tedob1]

Victor, really great post.

I see allot of probability and much outright guessing as in the attractor theory, a method that ‘might’ be successful if the delivery delays were similar, the OS and network conditions were known and could be reproduced in your lab to develope the attractor set, Etc. Not to mention that the algorithm can’t be proven or rather hadn’t been proven at the time of the papers writing.

Has the algorithm been proven and is this now a viable method of attack or just mathematical masturbation

[VictorKaum]

The birthday paradox is proven and there are tools written in perl to exploit the possibilities of birthday attacks see "An Implementation of a Birthday Attack in a DNS Spoofing"

The phase space analysis gives a very good probability for getting the right sequence.
and Michal Zalewski even has gone further and came with an implementation followed by a cert advisory. This thing can be used in ISN guessing. Strange Attractors and TCP/IP Sequence Number Analysis - One Year Later

http://lcamtuf.coredump.cx/newtcp/
http://www.cert.org/advisories/CA-2001-09.html
http://www.securityfocus.com/library/category/234

I had to implement those links in my first post somehow I forgot to post the follow up on phase space analysis, perhaps cause the birthday paradox got my attention to much.

However you are right in 2001 it was sort of mathematical/thearetical method but in 2002 / 2003 it became more... therefor the renewed attention to DNS poisoning.

thx for the reply

[groovicus]

What's this? Security related stuff?? And it's even on the front page...wowsers.

Great post Victor..even if a bit over my head...

Cheers!

[VictorKaum]

for Tim_axe : here you have a link to a test with birthdays of soccer players:
http://media.fastclick.net/w/get.med...tscoin.htm&d=f
about the phase space analysis see also:
http://www.securiteam.com/securitynews/5JP021P4AO.html
documents containing ideas to implement such sort of attacks are common on the net, for example http://www.lurhq.com/cachepoisoning.html

Tedob1 :
the DNS auditing tool DNSA, is going to implement Michal Zalweski's ISN prediction into their auditing tool. It's expected to be in version 0.5
http://www.packetfactory.net/projects/dnsa/
it's a powerfull tool that can be used for cache poisoning, DNS sniffing, ISN predictions, DNS spoofing, ... Probably when this new version comes out, the new OpenBSD ISN generator has become the standard on openbsd installs.

more: a long thread with the good old *nix versus MS discussion based on the article from Zalewski at slashdot http://slashdot.org/articles/02/06/30/1334233.shtml