Using the DNS Question to Carry Randomness - a Temporary Hack?

I read Mark Rothman's post "Boiling the DNS Ocean". This lead me to a thought (just a thought), that somewhere within the existing DNS protocol, there has to be a way of introducing more randomness in the DNS question and get that randomness back in the answer, simply to increase the probability that a resolver can trust an authoritative response. Of course having never written a resolver, I'm not qualified to analyze the problem -- but this being the blogosphere, that's not a reason to quit posting.

So at the risk of committing bloggo-suicide....Here goes......

Plan 'A' was to figure out if the unused bits in the ancount, nscount or ascount of the question could be used to send more random bits to the authoritative DNS. The ADNS would have to return those bits somewhere, and not in the same fields, because in the answer those bits are already used. Perhaps in an additional RR? It sounds hard to implement, and it would require that the ADNS and resolver both be upgraded. Try again.

Plan B is to use additional question records to send randomness from the resolver to the authoritative DNS, and figure out how to get them back.

Hmm…….How about using NXDOMAIN to carry the bits back to the resolver?

If I am a resolver, instead of asking one question (the one I want to know), I ask two questions, one that I want to know, and one that nobody knows, not even the authoritative DNS. Like perhaps asking for an A record made up of a long string of random bytes. Depending on the response, I can decide to trust or not trust the answer. Lets say that I need to know an A record for www.example.com. First - I set qdcount=2, then in one request I ask example.com's NS's two questions:

Question 1: www.example.com
Question 2: longstringofrandombytes.example.com

If I get a valid response for the first question and an NXDOMAIN response for the second, I know that I've got a reply from a valid ADNS rather than a spoofed reply. An attacker spoofing the valid ADNS will not know the longstringofrandombytes part of the second question and cannot reasonably guess that string. The real ADNS will reply to the second question with either an NXDOMAIN error or a valid IP. If I get the NXDOMAIN error for the same longstringofrandombytes.example.com that I asked for, I'm good to go.

If the ADNS responds with a valid IP address or CNAME, I know that the DNS in question is doing NXDOMAIN re-writing or it has a wildcard. I can trust and cache that answer, annoying though it may be. If I get neither IP nor NXDOMAIN, the response is suspect.

From what I can see, which isn't very far, Plan B could be implemented by a resolver without any change to the upstream authoritative DNS. The upstream would just see a bunch of requests that it would reply to with NXDOMAIN. Heck - it probability is already seeing tons of those, with all the exploit attempts that likely are flying around. The resolver would have to either track the longstringofrandombytes that it sent for each question, or it would have to use some sort of hash/cookie to validate the bytes without storing or caching them for the duration of the round trip.

This is definitely an ugly hack, and I’m not even sure it would work. It wouldn't make sense to use it for stub resolvers, it doesn't help man-in-the-middle attacks, and ADNS's would see increased load. But - there is no shared secret to manage as in TSIG, it doesn't require a top-down deployment like DNSSEC, and there is no protocol layer change (as far as I can figure out....) and there is no coordinated world wide deployment needed. Each operator can update one resolver at a time.

So am I smoking too much weed? Probably................my guess is that there is something I'm missing.

A bit of searching uncovered a similar concept being discussed at ietf org. 

OK - I'm not the first one to dream this up. There is a difference though. That proposal is similar, but seems to have died, and from what I can tell, would require both ends of the transaction to be aware of the 'new plan'. That requirement makes that proposed too hard to implement as a short term solution.

Obviously the topic of short and a long term fixes for the DNS issue is already being discussed in circles where discussions like this actually matter. The problem is finding a solution that can be implemented on a wide scale, and per Vixie's summary of the conversation in the above link:
a solution here would be opportunistic and pairwise deployable, requiring
no flag days; it would require no new technical expertise for end users; it
would have only graceful failure modes; it would not be subject to downgrade
attacks; and ideally, it would require no new protocol development work.
a solution here would be opportunistic and pairwise deployable, requiring no flag days; it would require no new technical expertise for end users; it would have only graceful failure modes; it would not be subject to downgrade attacks; and ideally, it would require no new protocol development work.
The 'pairwise deployable' part is still a problem. There are an awful lot of nameservers our there.

--Mike