Despite what various commenters around the blogosphere think (I've read a few but can't find the links now), Dan Kaminsky's online "Check My Dns" utility doesn't:
What it does is check whether your ISP's DNS server is patched. Plain and simple. It looks for one thing -- source port randomization. This does not give away the exploit, it checks for the existence of the sledgehammer fix that prevents the exploit from working.
Now that you have the IP address, your browser can fetch the results page. The web page is generated dynamically by parsing the hex string out of the URL you requested, using Ajax to fetch the relevant port and TXID data stored on Dan's server, and printing out a "safe" or "vulnerable" message such as:
Your name server, at 22.214.171.124, appears to be safe.
Requests seen for 6313d97e498e.toorrr.com:
That's all. Nothing tricky. This particular DNS server is deemed safe because the source port varies from one request to the next.
Come to think of it, those source ports don't really look that random, do they? For anybody "in the know", is that amount of randomness sufficient to protect against the attack?