how to protect name servers against cache corruption

I'm in receipt of some private e-mail from Thomas Ptacek on this topic,
and I feel that to the extent this thread deserves any further attention,
private e-mail is a more appropriate forum than the NANOG mailing list.
To give the flavour of what such a discussion would look like, so that
those who aren't part of it won't feel they are missing anything, I'll
respond to Thomas Ptacek's latest (and last, perhaps?) NANOG message:

To answer your question briefly: there are fixes for both the poisoned-RR
problem (extensive validity checking and non-caching cut-through
responses), as explained by Johannes Erdfelt,

Those patches were against BIND-4 as I recall, and have not been updated
or even discussed since BIND-8.1.1 and BIND-4.9.6 came out. If there are
"variants" of what you're here calling the "poisoned-RR problem" (which
makes it sound a little like what AlterNIC was doing), which have been
shown to work against BIND-8.1.1 or BIND-4.9.6, I have *not* been shown.
What I would like to see is at least a typescript of "dig" commands which
demonstrate the vulnerability, though I'm willing to accept a line by line
description of how the code can be misdirected.

Based on the speed with which the community responded to the MD4 challenge,
I can only assume that if a "white hat" learns of a way BIND-8.1.1 is
vulnerable, they will beat a pathway to the press and to my inbox.

                                          and there are fixes for the
guessable-ID problem (randomized query IDs backed up by server-survival
assurances using "cookie" queries, along with a attack detection mechanism
that reduces the entire problem to a denial-of-service attack). Neither of
these involve DNSSEC.

Here, I'd like to quote from the Lout source code for my Usenix Security
Symposium (#5, Salt Lake City, September 1995) paper, which is online in
PostScript(tm) form at <URL:>:

  @SubSection @Title{Query @S{ID} Prediction} @Begin
  With only 16 bits worth of query @S{ID} and 16 bits worth of @S{UDP}
  port number, it's hard not to be predictable. A determined attacker
  can try all the numbers in a very short time and can use patterns
  derived from examination of the freely available @S{BIND} source
  code. Even if we had a white noise generator to help randomize our
  numbers, it's just too easy to try them all.

In an extended dialogue with one of the authors of a recent BugTraq report
on BIND security, I suggested that as long as resolvers do not scoreboard
*and* cryptographically randomize their query ID's, and as long as routers
do not do source-address verification, and as long as hosts do not prevent
source address from being used on packets arriving from the net,
it *does*not*matter* what we do in the name servers.

In fact, I have working code for a scoreboarding resolver, but it requires
a 64Kbit bitmap as well as a *lot* of dynamic memory to do "the right thing".
(It's also asynchronous with its own "eventlib" context, but it's not a thing
you'd want to run on PC grade machine or workstation.) 10 million instruct-
ions and 1 million data references seems too expensive for a hostname lookup.
And if you followed all of that you now know why I proposed TSIG.

The Point:

Any security conscious person who reads RFC 1034 and RFC 1035 will come up
with a half dozen ideas for how to pervert any RFC-compliant name service.
Only two of the easy half dozen will work in practice, the others just sound
like good ideas.

I am always willing to accept diffs and trouble reports about BIND, and the
ones which solve real problems become part of official patches and releases.
If anybody has a suggestion as to how I can be more reasonable than that, I
am listening hard.