Subject: kaminsky resistance, section by section

From: Paul Vixie <[email-masked]>
Date: Thu, 28 Aug 2008 19:22:06 +0000

the perfect platonic form of kaminsky's observation is that the target of
the poison does not have to match the q-tuple.  all else is a reflection of
that form, including ttl bypasses (ADNS which fails to answer unknown qtype,
middleboxes which block or drop unknown qtype, RDNS which fails to cache
some qtypes, etc), and no matter what is the form of the non-qtuple-matching
poison.  i've watched with interest as weaver, ohta, and others have explored
ways to protect against each known form of poison or to protect against any
form of non-qtuple-matching poison.  yesterday leo bicknell of ISC re-raised
a proposal that seemed to him related to dns-0x20 but wasn't, and which had
seemed to me earlier on to be "too partial" to be worth its deployment cost,
but the debates have swirled long enough now that i think there's "meat" here.

section by section, then, here's what we could do.  the header section is not
an issue since it contains only flags and metadata.  the question section is
not an issue since it can by universal convention only hold one q-tuple and
that q-tuple is both well understood and well extended by dns-0x20.  of the
other three sections there is much to say.  note in advance that nothing i'll
say removes the need for port randomization or DNSSEC, but i'm starting to be
of the opinion that (a) we don't have to live with the ten-hour attack, and
(b) we have more we must do while we complete the long march toward DNSSEC.

it's nec'y that the result of all transactions be cached, whether that
result was NXDOMAIN, NODATA, SERVFAIL, timeout, or live data.  failing to
cache the result of "this q-tuple from that ADNS", means that a given
q-tuple can be serially attacked.  it's also nec'y that multiple
simultaneous outstanding upstream transactions not be the result of
multiple simultanous cache misses from downstream queries, or else any
given q-tuple can be attacked in parallel.  caches must be deep enough to
hold at least several seconds of full rate churn, so that no q-tuple can be
attacked multiple times per second.

for the answer section it's essential that only records whose owners match
the q-tuple be cached or forwarded or consumed.  so, full cname chains, or
partial cname chains, whether apparently sharing a baliwick with the
q-tuple or not, are unusable.  it's no longer going to be possible to make
an authority server a stealth slave for some common CNAME destination and
try to cut down the number of round trips needed to complete a CNAME chain.

for the authority section we have the problems of fast flux, of poison, of
load balancers, and of legitimate NS RRset changes.  we must allow a
response to have the effect of changing the cached NS RRset, but we cannot
allow the kind of immediate+direct replacement that's been widely
implemented to date.  one non-immediate non-direct approach (proposed by me
and by others) is to reduce the TTL rather than replacing the RRset so as
to allow slow legitimate changes to cached NS RRsets but to ensure that
changes are validated through the parent zone somehow.  leo bicknell's
observation yesterday is that at the cost of one extra round trip per
delegation discovery we can separate the discovery of the delegation chain
from the discovery of the answer.  since we can hope that a delegation
chain will be used many times before it expires or is replaced, this is a
reasonable design cost.  therefore for any given q-tuple where we have no
specifically associated knowledge of its delegation chain, we can first ask
for <randomstring>.<qname> and iterate downward along the returned NS RRsets
until we receive one that isn't a delegation (indicating that "randomstring"
matches a wilecard, or until we receive an NXDOMAIN.  since there's no way
to be sure that www.<domain> and ftp.<domain> aren't zone apexes, we'll have
to ask for <random>.www.<domain> and <random>.ftp.<domain> separately, even
though we'll normally just learn that only <domain> has an NS RRset.  this
extra cost allows us to commit to a draconian NS RRset replacement strategy:
if a response contains an NS RRset which attempts to change the cache, then
simply ignore the new one and delete the cached one, and restart iteration.
(this policy isn't effective without bicknell's NS RRset discovery modality,
since the iteration we'd fall back to today, is predictable and vulnerable.)

for the additional section we have quite a lot of protection from RFC 2181
already.  kashpureff taught us a lot.  but even so we're currently capable
of inserting new RRsets into the cache which while "in baliwick" are at
least theoretically attached to poisoned MX or SRV or NS records in the
answer or authority section.  nothing i've said above about protecting the
other sections makes it safe to consume, cache, or reuse in-baliwick data
contained in the additional section.  ohta has long urged that we collapse
the data structure to remove the intermediate name (target of MX/SRV/NS,
owner of A/AAAA) and just associate addresses directly with the records that
need this kind of "glue".  weaver has recently made an observation which i
find compelling -- if one follows ohta's proposal only for the purpose of
making a direct query to that baliwick for the glue record in question, and
never let anything in the additional section affect the cache at all ever,
then we've closed this window.  but i'm only compelled by this proposal in
light of bicknell's observation (described earlier), such that the downquery
meant to retrieve this glue should begin with a <random>.gluename query in
order to complete the delegation chain through to the subzone's apex, after
which point a normal query for the gluename against that baliwick, with the
normal rules for caching only answers matching the q-tuple and disallowing
subsequent NS RRset replacement without first deleting and reaquiring that
link in the delegation chain.

this description is hard to follow, and frankly it was hard to write.  i'm
conjoining "things you have to do differently when you decide where to send
a query" with "things you have to do differently when you receive an answer"
and that makes a lot of people nervous.  but as you contemplate the anxiety
and complexity in this proposal, note that its approach is to try to decide
what CAN be cached, and not to try to decide what CAN'T be cached.

i ask that questions of the form "i don't understand" or "this makes no sense"
be sent to me personally rather than to the list -- i will then know what i
need to improve in the proposal and we can avoid compounded misunderstandings
that will make the evaluation of this take even longer than it must.

and note, again, that even if successful, this proposal doesn't reduce the
need for DNSSEC, since it only seeks to protect against off-path attacks, and
we all ought to continue to be very concerned about on-path attacks as well.

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: Paul Vixie <[email-masked]>
Date: Thu, 28 Aug 2008 23:49:22 +0000

meaning no disrespect to leo bicknell, a more careful review of my inbox
reveals that evan hunt, not leo bicknell, first told the idea of "prepend
random label to the qname until you're sure you know the entire delegation
chain", so in fairness to evan, i will change this attribution the next
iteration of the writeup of this.

---

From: Tony Finch <[email-masked]>
Date: Fri, 29 Aug 2008 18:05:26 +0100

On Thu, 28 Aug 2008, Paul Vixie wrote:

> for any given q-tuple where we have no specifically associated knowledge
> of its delegation chain, we can first ask for <randomstring>.<qname> and
> iterate downward along the returned NS RRsets until we receive one that
> isn't a delegation (indicating that "randomstring" matches a wildcard,
> or until we receive an NXDOMAIN.  since there's no way to be sure that
> www.<domain> and ftp.<domain> aren't zone apexes, we'll have to ask for
> <random>.www.<domain> and <random>.ftp.<domain> separately, even though
> we'll normally just learn that only <domain> has an NS RRset.  this
> extra cost allows us to commit to a draconian NS RRset replacement
> strategy: if a response contains an NS RRset which attempts to change
> the cache, then simply ignore the new one and delete the cached one, and
> restart iteration.

Doesn't that make it easy for an attacker to force you to spend all your
time rediscovering the victim domain's NS RRset so that you are never able
to resolve any victim names?

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
MALIN HEBRIDES BAILEY: SOUTHWESTERLY 5 OR 6,OCCASIONALLY 7 AT FIRST. MODERATE
OR ROUGH, OCCASIONALLY VERY ROUGH. RAIN OR DRIZZLE, FOG PATCHES IN MALIN,
SHOWERS IN BAILEY LATER. MODERATE OR GOOD, OCCASIONALLY VERY POOR IN MALIN.

---

From: Paul Vixie <[email-masked]>
Date: Fri, 29 Aug 2008 17:24:12 +0000

> to resolve any victim names?

"easy" is in the eye of the beholder.  if noone is derandomizing your UDP
port numbers then it will take an average of ten hours at multi-hundred-mbit
to get you to do this one time.  and that's assuming you don't have good 0x20
connectivity, or a private invitation-only VPN that RDNS and ADNS are part of
but which attackers are mostly not, or TSIG, or TKEY, or PING, or DNSSEC.