So let's say we want to poison the cache of nameserver.bigisp.com so that customers of a big ISP trying to find www.phatbank.com will be directed to a machine with an IP address of 220.127.116.11 instead of the real webserver at 18.104.22.168.
Let's assume we know the source IP address from which nameserver.bigisp.com will send recursive DNS queries and we know the IP address to which it will receive DNS queries from clients.
We start by sending DNS queries to nameserver.bigisp.com asking for A records for nonexist00000001.phatbank.com and then nonexist00000002.phatbank.com and then nonexist00000003.phatbank.com and so on. These subdomains of phatbank.com don't exist and the responses that nameserver.bigisp.com receives from a legitimate nameserver will say so.
At the same time as we send the queries, we'll also send answers to nameserver.bigisp.com, but our answers won't say NXDOMAIN, they'll say 22.214.171.124.
Most of these answers will be ignored because the legitimate answer will arrive first, but if we send enough queries and corresponding answers, we hope that one of our answers will be accepted before the legitimate one.
When that happens, the cache is poisoned. nameserver.bigisp.com will cache a result that, for example, says nonexist00065535.phatbank.com is at 126.96.36.199. Cool. What's cooler is that each of our bogus answers contained what's known as an Additional Resource Record and each said:
www.phatbank.com is at 188.8.131.52
This additional information is accepted and cached by nameserver.bigisp.com because it refers to the same domain as its query. Job Done.
This is my understanding of the exploit for the DNS flaw which Dan Kaminsky has helped to get fixed and which has possibly been independently rediscovered by Halvar Flake, then written about in a blog post by E. Copeland at Matasano which was quickly removed, but not before it had been noticed. On his website, Dan Kaminsky posted a quick response entitled 13 > 0 (which is, of course, true and we've had a good head-start because of it) in which he reiterated the, now more urgent, need for patches to be applied. The fact that the exploit now seems to be public may make people rethink their stance on this issue when talking about vulnerabilities in perspective. It's worth noting however, that nothing is yet confirmed with regard to this possible exploit and I think we'll not see Dan cave in to pressure to give-up the goods before Black Hat.
UPDATE: 2008-07-24T15:45 +0100 UTC
It seems the exploit could be even more devastating than this. A metasploit framework exploit module has been created for this flaw here: bailiwicked_host.rb "This exploit caches a single malicious host entry into the target nameserver by sending random hostname queries to the target DNS server coupled with spoofed replies to those queries from the authoritative nameservers for that domain. Eventually, a guessed ID will match, the spoofed packet will get accepted, and due to the additional hostname entry being within bailiwick constraints of the original request the malicious host entry will get cached".
A further exploit module was later added: bailiwicked_domain.rb "This exploit replaces the target domains nameserver entries in a vulnerable DNS cache server. This attack works by sending random hostname queries to the target DNS server coupled with spoofed replies to those queries from the authoritative nameservers for that domain. Eventually, a guessed ID will match, the spoofed packet will get accepted, and the nameserver entries for the target domain will be replaced by the server specified in the NEWDNS ['The hostname of the replacement DNS server'] option of this exploit".
As pointed out in some analysis by Nate McFeters and Billy Rios, this newer module allows a nameserver cache to be poisioned with a fake nameserver for an arbitrary domain meaning an attacker would control the cache entries for all subdomains of that domain.