*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