At most this decreases the chance of a succesful attack 65k times, at worst it doesn't help because of NAT, and if you're running a default MS
Honestly, I haven't had time to play around with any of the exploits floating around, but given 1 attempt = at most 2 packets (though it's probably much closer to 1, since you can try lots of responses per packet), we can send 32k packetrs pretty quickly, and the figures here also seem to say it works pretty damn quickly.
I'm not going to do any figures, but given how network speeds seem to go constantly upwards (or do we want to speculate about an upper cap?), we're going to reach a problem at some stage where senging 65k times the amount of data is going to be bloody fast again, and this will be an issue all over again.
And if that ever happens; what's left to randomize in the query? nothing as far as I can tell, so is the hope that by then we'll have all switched to DNSSEC, or are we planning on altering the DNS protocol at that point?
Anyway, going in a completely different direction, I want to take issue with the idea that seems to be pervading a lot of descriptions of the DNS bug that poisoning random subdomains isn't an issue.
For your typical attack, yes, poisoning random subdomains is kind of useless, however a lot of the web is held together by the idea that absolutely everything in a DNS tree of a domain is controlled by that domain and is to some extent trustworthy (think cookies and document.domain in JavaScript).
Also, it seems odd that given that the fact that you could poison random domains seems common knowledge to some people Dan is nominated for another pwnie award for XSS-ing arbitrary nonexistant subdomains. Sure, that bug gives you the ability to phish people more easil, but to me the biggest part of that seemed to be the fact that you could easily attack the parent domains form there.
Anyway, the patch, while having it's limitations, seems to buy us some time with both these bugs, and in fact should buy us time with any bugs where responses are forged, so that's always a good thing.
