Re: Verizon
Yes, they're vulnerable. The transaction ID is irrelevant as it is guessed by the attacker with chances of a hit being one in 65536 per shot. The crux of the matter is a static upstream query port on the recursive server being queried, allowing the attacker to both send unique unresolvable queries within the target domain (1.example.com, 2.example.com...) to port 53 AND know which port the server is listening for an answer on. He then fires answers at it pretending to be the server the resolver is querying (remember, this is UDP. No state, easy to spoof, no reply needed once you get an answer accepted). You only need to guess the transaction ID correctly once and then you've polluted the cache for the entire example.com domain for however long you set that answer's TTL to (or the cache lifetime, whichever is smaller) by dint of in-bailiwick answers always being accepted for the whole domain. All the real example.com DNS servers will send back is NXDOMAIN, which doesn't get cached so you have, in effect, limitless query headroom to get the transaction ID correct without the risk of the real servers populating the cache first.
What the patch does is enable the server to use a random source port for every query in a recursive search, spoiling the cracker's ability to track which port the server expects a response on, thus giving the cracker no opportunity to insert his own bogus answers. It is, unfortunately, security by obscurity. We need signed roots and DNSSec. DNS is and always has been insecure. It's only a matter of time before more holes are found and this whole song and dance commences yet again. Of course, that implies ISPs will care enough to set up trust anchors, but that's a discussion for another day.
By the way, if anyone thinks adding 1 IN A x.x.x.x, 2 IN A x.x.x.x etc. to their zones is a defence, just ponder the use of very small shell scripts, uuidgen and sed to create the hostnames to query. I'm sure you'll agree that this idea is no defence at all. The hostname used is just a simple way of explaining the exploit. Even your run-of-the-mill skiddie isn't going to be that obliging. Patch. Now.