Subject: Anti DNS spoofing - Extended Query ID (XQID)

From: Jesper G. Høy <[email-masked]>
Date: Thu, 24 Apr 2008 13:31:55 +0200

Strongly inspired by the elegant DNS-0x20 and recent discussions here, I got
this idea for another way to prevent DNS spoofing which is almost as simple
as DNS-0x20 but quite a bit stronger.

I have tried to formulate this in the following document:
http://www.jhsoft.com/dns-xqid.htm

I hope you guys will read and comment.
If the idea turns out to be solid, I hope someone here might be interested
in co-authoring this into a draft/RCF with me?

It has been a long time since I written anything here, so a short
introduction might be in order:
My name is Jesper G. Høy. I have lived in New Jersey USA for many years but
now live in Denmark.
I am the owner of JH Software and the primary developer of Simple DNS Plus
(a DNS server product for Windows) and have been doing this since 1999.

Looking forward to your feedback.

Sincerely,
Jesper G. Høy

--
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: Florian Weimer <[email-masked]>
Date: Thu, 24 Apr 2008 14:33:53 +0200

* Jesper G. Høy:

> Strongly inspired by the elegant DNS-0x20 and recent discussions
> here, I got this idea for another way to prevent DNS spoofing which
> is almost as simple as DNS-0x20 but quite a bit stronger.
>

Same question as always: Will there be any BCP70 disclosures for this
approach?  Is this covered by the Cisco patent on DNS cookies?

If the magic label and the cookie are added at the end, it is possible
to detect for a client if a recursor supports this protocol extension,
without running into timeouts.  However, the root and TLD servers need
to be updated, and interoperability problems are more likely.

As you note, resolvers cannot QNAME-match error responses (except for
RCODE=3).  This is a problem because some servers will return error
responses when you query a subdomain of an existing name.  Some will
even drop the query.  I guess this is less interoperable than 0x20,
I'm afraid.

-- 
Florian Weimer                <[email-masked]>
BFK edv-consulting GmbH       http://www.bfk.de/
Kriegsstraße 100              tel: +49-721-96201-1
D-76133 Karlsruhe             fax: +49-721-96201-99

---

From: Paul Vixie <[email-masked]>
Date: Thu, 24 Apr 2008 17:06:20 +0000

this proposal suffers from the same problems as every other extended QID
proposal that's been offered over the years, and adds no security.  the
key to understand this is in your text under HOW IT WORKS, subsection 4:

5) The DNS client must resend the query without the XQID-query prefix and XQID
   to the same DNS server.
 The following response is of course vulnerable to DNS spoofing as normal.
 The benefits of XQID are only realized when both sides of a transaction
 implement it.

the two major faults are downgrade and statefulness.  since an initiator is
required to fall back to unextended query ID processing if the responder does
not implement the full proposal, then any attacker can make any initiator
believe that this server does not at this time implement this proposal, which
is a successful downgrade attack.  you'd just be moving the timing around and
adding complexity and traffic but no real security.  the usually-proposed way
to secure against downgrade attacks is to add state in all initiators keeping
track of which responders do or do not implement the proposal, but, dns is
stateless, udp is stateless, ip is stateless, and anything from local load
balancers to distributed load balancers to actual server implementation level
downgrades can invalidate that held state in ways indistinguishable from a
(successful) downgrade attack, and the mere willingness to hold state means
that an initiator's state pool can be managed by attackers, causing so much
new state to be held that older more useful state has to be LRU'd out.

we went around and around on this at the time of EDNS0, and there is just no
way to add more security with something like this.  DNS-0x20 is the first idea
anybody's had where the current installed base is overwhelmingly compatible
and so the added transaction volume against responders who don't bit-for-bit
copy the question name from the request to the response, is worth considering.

if we were going to do something like XQID, we'd do it as an EDNS0 option and
say that if a response comes in without a matching XQID then the whole
transaction must be repeated N times (like N=3 or N=5) against all responders
known to be authoritative for the containing zone, with fully random QID and
UDP port each time.  that's what DNS-0x20 recommends.  but it's not practical
for an EDNS0 XQID option, or for an XQID QNAME extension, because the initial
installed base won't be compatible with it.

the easier-by-far solution is DNSSEC.

---

From: Jesper G. Høy <[email-masked]>
Date: Thu, 24 Apr 2008 19:58:49 +0200

Thanks for your response Paul.

Paul Vixie wrote:
> since an initiator is required to fall back to unextended query
> ID processing if the responder does not implement the full
> proposal, then any attacker can make any initiator believe that
> this server does not at this time implement this proposal,

But that's exactly one of the main points of this idea - NOT to fall back
without first having received a response with the XQID in it.
Even DNS servers that do not understand XQID should still respond with the
full QNAME (as is one of your main points in DNS-0x20) - including the XQID.

This way there is no way for an attacker to make the initiator believe
anything without the attacker knowing the XQID.

I understand and appreciate that similar ideas have probably come up many
times - but I was hoping that this exact point (not to fall back) would make
a difference.

There may be other reasons that this idea won't work - but I hate to see it
shot down for this alone.
 
I hope you will take another look.

Thanks again,
Jesper G. Høy

---

From: Paul Vixie <[email-masked]>
Date: Thu, 24 Apr 2008 18:06:38 +0000

> without first having received a response with the XQID in it.

i understood that.

---

From: Jesper G. Høy <[email-masked]>
Date: Thu, 24 Apr 2008 20:11:10 +0200

Thanks for your response Forian.

Florian Weimer wrote:               
> approach? 

I apologize but I am not familiar with "BCP70 disclosure"?
Google turns up some documents about XML. Not sure how/if that applies?

> Is this covered by the Cisco patent on DNS cookies?

Someone probably has a patent on something similar.
Since Microsoft patented the "IsNot" operator there can't be much left :-)

> without running into timeouts.  

My suggestion was to add them at the beginning (left side).
I haven't explored the opposite, but it wouldn't immediately seem to work
when recursing.

> However, the root and TLD servers need

Not when adding prefix and XQID on left side as pointed out in the doc.

> RCODE=3).

As long as the QNAME is included in the error response the resolver CAN
match it - no matter what the error code is.

> This is a problem because some servers will return error
> even drop the query.

I haven't tested extensively, but I have not run into that situation so far.
Do you have any examples of such servers?

Thanks,
Jesper G. Høy

---

From: Jesper G. Høy <[email-masked]>
Date: Thu, 24 Apr 2008 20:13:21 +0200

> > But that's exactly one of the main points of this idea - NOT to fall
> back without first having received a response with the XQID in it.
> 
> i understood that.

Then how is there a "downgrade fault"?

Thanks,
Jesper G. Høy

---

From: Joe Abley <[email-masked]>
Date: Thu, 24 Apr 2008 17:34:53 -0400

> I apologize but I am not familiar with "BCP70 disclosure"?

I think Florian meant BCP 79, not BCP 70.

   http://www.ietf.org/rfc/rfc3979.txt

Joe

---

From: Florian Weimer <[email-masked]>
Date: Fri, 25 Apr 2008 09:26:13 +0200

>   http://www.ietf.org/rfc/rfc3979.txt

Yes, indeed.  Thanks, and sorry for the typo.

---

From: Jesper G. Høy <[email-masked]>
Date: Fri, 25 Apr 2008 10:20:28 +0200

From: Florian Weimer
> Yes, indeed.  Thanks, and sorry for the typo.

Thanks for the clarification.
And again I do apologize - if I had more experience with this I probably
would have understood.

Yes, there will be full disclosure.
At this time, I do not know of any patents or other IPR relating to this.
Personally I have no intention of patenting or copyrighting this.
It is meant to be owned by the Internet at large - or whatever the RFC term
for that is.

I look forward to your response to my previous message.

Sincerely,
Jesper G. Høy

---

From: Jesper G. Høy <[email-masked]>
Date: Fri, 25 Apr 2008 11:34:46 +0200

Paul - thanks again for your response to this.

My first answer did not address much of what you wrote and I apologize for
that.
Please consider see my full response below:

>> this proposal suffers from the same problems as every other extended
>> QID proposal that's been offered over the years,

Please do not dismiss it just because it is similar to other attempts.
I believe this is a unique approach.

>> and adds no security.

I do believe it does.

>> the key to understand this is in your text under HOW IT WORKS, subsection
>> 4:
>> 5) The DNS client must resend the query without the XQID-query prefix
>> and XQID to the same DNS server.
>> The following response is of course vulnerable to DNS spoofing as
>> normal. The benefits of XQID are only realized when both sides of a
>> transaction implement it.

This only points out that this is not secure if either side does not
implement XQID.
You would never get to item 5) if both sides implemented XQID.

I make no claims that this is secure if only implemented on the resolver.
Rather my point is that it is very simple to implement on both server and
resolver.

>> the two major faults are downgrade and statefulness.  since an
>> initiator is required to fall back to unextended query ID processing if
>> the responder does not implement the full proposal, then any attacker can
>> make any initiator believe that this server does not at this time
implement
>> this proposal, which is a successful downgrade attack.

No, the attacker cannot make the initiator believe that without knowing the
XQID, because the initiator must never fall back before having received a
response with the XQID - as is pointed out in the "important points" section
of the document.

>> the usually-proposed way to secure against downgrade attacks is to add
>> state in all initiators...

Perhaps - but that is not what I am proposing here.
My proposal to secure against downgrade attacks is not to fall back before a
response with the XQID is received.
Servers that do not understand XQID should still return the XQID in the
response QNAME because it will think it is just that - part of the QNAME.

I think this is one of the things that make this proposal so unique - there
is no need to keep state.

>> we went around and around on this at the time of EDNS0, and there is
>> just no way to add more security with something like this. 

I have the utmost respect for you and your expertise in this field, and
again, I appreciate you taking the time to respond to my proposal.

But again, please do not dismiss it just because it is similar to other
attempts.
I do believe my proposal is a unique approach.

>> DNS-0x20 is the first idea anybody's had where the current installed
>> base is overwhelmingly compatible and so the added transaction volume 
>> against responders who don't bit-for-bit copy the question name from
>> the request to the response, is worth considering.

I agree - DNS-0x20 is beautiful.
The only problem I see with DNS-0x20 is that with short domain names and/or
mostly numeric domain names, it doesn't add enough bits to the transaction
identity that it completely eliminates the possibility of spoofing attacks.
It is a significant improvement, but it is not a 100% solution.

What my proposal does is add a minimum of 128 bits - which makes it
practically impossible to spoof.

The major difference is that DNS-0x20 works when only implemented on the
resolver where my proposal requires implementation on both resolver and
server.

There is however also a big similarity - both solutions work with resolver
only implementation for both root and TLD level queries.

>> if we were going to do something like XQID, we'd do it as an
>> EDNS0 option

I did explorer this.
Many DNS servers (including Akamai's) still return "FORMERR" to EDNS0
queries - without copying the EDNS0 OPT record back in the response.
So you invariably run into what you call a "downgrade fault".

My proposal on the other hand works just fine with these same Akamai DNS
servers.
Another reason I was hopeful that this might be a better approach.

>> and say that if a response comes in without a matching XQID then
>> the whole transaction must be repeated N times (like N=3 or N=5)
>> against all responders known to be authoritative for the containing 
>> zone, with fully random QID and UDP port each time.  that's what
>> DNS-0x20 recommends.  but it's not practical for an EDNS0 XQID
>> option, or for an XQID QNAME extension, because the initial 

I can see that.
But then my with my proposal you wouldn't need to repeat N times like that.

>> the easier-by-far solution is DNSSEC.

DNSSEC is by no means easy!
Even when/if the root gets signed, millions of users are still going to have
one heck of a time trying to configure this on their DNS servers.
I think it is fair to say that there are going to be a lot of un-signed
domain names for a very long time.
My proposal requires no user configuration - only implementation.

DNSSEC requires updated DNS servers from the root (or at least TLD) down to
work.
My proposal requires no updates at the root/TLD level.

Don't get me wrong - DNSSEC is good - I just don't think it excludes the
need for other security measures.

My proposal has not been thoroughly tested and it is very possible (perhaps
even very likely) that there is some major technical flaw with it.
I was just hoping that this forum would be the right place to find and
explorer such issues.

I hope you will consider my points and perhaps take another look at my
proposal.

Thanks again for your time.

Sincerely,
Jesper G. Høy

---

From: bert hubert <[email-masked]>
Date: Fri, 25 Apr 2008 13:32:12 +0200

> the easier-by-far solution is DNSSEC.

Let me highlight this sentence. It is exceedingly rare to see 'easier' and
'DNSSEC' in such close proximity!

	Bert

-- 
http://www.PowerDNS.com      Open source, database driven DNS Software 
http://netherlabs.nl              Open and Closed source services

---

From: "Roy Arends" <[email-masked]>
Date: Fri, 25 Apr 2008 14:25:37 +0200

> http://www.jhsoft.com/dns-xqid.htm

Hi Jesper,

I've read your proposal, and I think I understand how it works.

resolver sends XQID--q.cookie to server
compliant server:
   resolver receives XQID--r.cookie from server
non-compliant server:
   resolver receives XQID--q.cookie from server

In order for this to be susceptible to a downgrade attack, the miscreant 
must let the resolver believe that the server does not support XQID, 
(match the XQID--q.cookie). 

Spoofing is trivial when the miscreant has read/write access to the path 
between resolver and server (i.e. no cookie guessing involved). DNSSEC is 
a defense against that class of attack, and I assume this not designed for 
that class (just like 0x20, forgery resilience, etc are not designed for 
that class). IMHO, only some kind of pre-knowledge (like a trusted public 
key, a shared secret, etc) can solve that problem.

Spoofing is hard when the miscreant does not have read access to the path 
(ie a blind attack). Much harder than spoofing the ID, port number, 0x20 
and what have you, since the attacker needs to match the QNAME as well. 
Since spoofing is hard, the downgrade attack is hard.

What is unique about this proposal, compared to others I've seen, is that 
independent of compliance, this does not suffer from a downgrade attack, 
since it difficulty to downgrade is equal to the difficulty to spoof.

I understand the --q/--r are used to disambiguate between a compliant and 
a non-compliant server in order to fall back to a regular query response 
scenario.

Note that a similar scheme can be accomplished with wildcards (see [1] 
below) at the server side (without any server side code hacks)

I don't think the above scenarios add that much to solve this particular 
class of attack. Not because they don't work, but because they require 
some form of tinkering on the server side (0x20 and forgery-resilience do 
not suffer from this). 

fwiw, I don't think a comparison between this proposal and DNSSEC will 
hold, as they do not defend against the same classes of attack.

Regards,

Roy

[1] From Dan Bernstein, http://cr.yp.to/talks/2007.02.02/slides.pdf "The 
DNS security mess" (look for Cookie stops blind attacks)

Example:

server deploys *.www.simpledns.com A 192.0.2.1

resolver sends <cookie>.www.simpledns.com A
resolver receives <cookie>.www.simpledns.com A

In case of rcode=3, resolver falls back to regular query response scenario 
to disambiguate between an nonexistent name (compliance) and a nonexistent 
pre-pended asterisk label (noncompliance).

---

From: Francis Dupont <[email-masked]>
Date: Fri, 25 Apr 2008 14:44:48 +0200

If the only purpose is to extend the query ID + port space the simplest
is to use IPv6. With standard setup a resolver can use ~2^64 different
addresses and paranoids can go easily to ~2^80 different addresses.
Of course this works only with enough IPv6 deployment...

Regards

[email-masked]

---

From: Jesper G. Høy <[email-masked]>
Date: Fri, 25 Apr 2008 15:32:58 +0200

Hi Roy,

Thanks for your response to this.

>> In order for this to be susceptible to a downgrade attack, the
>> miscreant must let the resolver believe that the server does not
>> support XQID, (match the XQID--q.cookie).

Exactly.

>> Spoofing is trivial when the miscreant has read/write access to
>> the path between resolver and server (i.e. no cookie guessing
>> involved). DNSSEC is a defense against that class of attack, and
>> I assume this not designed for that class (just like 0x20, 
>> forgery resilience, etc are not designed for that class).

Correct.

>> What is unique about this proposal, compared to others I've seen,
>> is that independent of compliance, this does not suffer from a
>> downgrade attack, since it difficulty to downgrade is equal to
>> the difficulty to spoof.

Exactly.

>> I understand the --q/--r are used to disambiguate between a
>> compliant and a non-compliant server in order to fall back to a
>> regular query response scenario.
>> Note that a similar scheme can be accomplished with wildcards
>> (see [1] below) at the server side (without any server side code
>> hacks)

Thanks for this reference. I was not aware of that idea (wildcards).
Yes, this idea is very similar.

Wildcards may not require server code hacks, but it does require users to
understand to add wildcards for everything.
A "user side hack" may be a lot harder to implement than a "server side
hack".
And this would also seem to have some unintended side effects (all sub-names
exist).

>> I don't think the above scenarios add that much to solve this
>> particular class of attack. Not because they don't work, but because
>> they require some form of tinkering on the server side

It does require server updates, but only at end-nodes, not at root/TLD.
And those are very minor updates.
I implemented it in our software with less than 20 lines of code.
We are not talking about another DNSSEC implementation.

>> (0x20 and forgery-resilience do not suffer from this).

They don't - but then they only offer small incremental improvements to the
main problem which is the short transaction ID.

For example DNS-0x20 only adds 2 bits to the transaction ID for the domain
".us".
XQID adds 128 bits or more.

>> fwiw, I don't think a comparison between this proposal and DNSSEC 
>> will hold, as they do not defend against the same classes of
>> attack.

Agreed absolutely.
Certainly neither excludes the other.

Thanks,
Jesper G. Høy

---

From: Paul Vixie <[email-masked]>
Date: Fri, 25 Apr 2008 14:04:56 +0000

> 'DNSSEC' in such close proximity!

i know.  but consider the short term cost of the added confidence here, which
is that initially and for some lengthy time afterward, participating initiators
will have to double the number of total transactions against nonparticipating
responders.  this sounds like early EDNS0, except EDNS0 wasn't about security,
and so it could keep responder state in the initiators as to EDNS0 deployment
level.  only one probe was required to shut off EDNS0 toward a responder for
hours days or weeks until the next probe.  with XQID it's every query.  and if
the first query results in a spoofed response (pretending that XQID-R is not
implemented by the real responder) then the second one can be spoofed as well,
so there is theoretically the same forged/flooded vulnerability profile as now.

if we wanted to do this we'd follow donald eastlake's cookie design.  but we
don't want to do this, we want real security in which the only thing spoofed
or flooded responses can do is cause resolution failure, and initiator state
load is controlled entirely by real zone owners and their server operators.

it's very odd to call DNSSEC easier than anything.  but the cost:benefit of
DNSSEC is better than the cost:benefit of any extended query ID solution i've
seen, including early ones i did myself, and including donald's, and including
jesper's.

---

From: [email-masked]
Date: Fri, 25 Apr 2008 14:49:10 +0000

> seen, including early ones i did myself, and including donald's, and including

	actually, cost:benefit here is undefined, so its easy to make that
	assertion.
	the tradeoff, as Roy pointed out, is between atomic transactions
	and a "conversation"...  the value of passing a token that can
	be shown to be intact/authentic aka DNSSEC is different than the
	value in passing a stream/series of valid tokens.  

	there is, imho, value in both techniques.  and the attack profiles
	against either are different as well.

--bill

---

From: Jesper G. Høy <[email-masked]>
Date: Fri, 25 Apr 2008 17:15:14 +0200

> From: Paul Vixie
> i know.  but consider the short term cost of the added confidence
> here, which is that initially and for some lengthy time afterward,
> participating initiators will have to double the number of total
> transactions against nonparticipating responders.  this sounds
> like early EDNS0, except EDNS0 wasn't about security,

I am sorry, I don't understand this argument.
Is security less important than EDNS0?

> and so it could keep responder state in the initiators as to EDNS0
> deployment level.  only one probe was required to shut off EDNS0
> toward a responder for hours days or weeks until the next probe. 
> with XQID it's every query.

In my suggestion I did suggest that resolvers cache the XQID status of
responders so as to avoid exactly this (see "possible issues" section).
Much like with EDNS0.
It is very easy to determine and cache this status based on the response
QNAME.

> and if the first query results in a spoofed response (pretending
> that XQID-R is not implemented by the real responder) then the
> second one can be spoofed as well, so there is theoretically the
> same forged/flooded vulnerability profile as now.

Yes as I pointed out, it only works when implemented by both sides.
Otherwise the result is no better - or worse than today.

> if we wanted to do this we'd follow donald eastlake's cookie design.
> but we don't want to do this,

Again I am sorry, but I don't get it.
Why don't we want better protection against DNS spoofing?

> we want real security in which the only thing spoofed or flooded
> responses can do is cause resolution failure, and initiator
> state load is controlled entirely by real zone owners and their
> server operators.

That would certainly be ideal. But how?
Is it really realistic that the whole Internet will be DNSSEC signed anytime
soon?

> it's very odd to call DNSSEC easier than anything.  but the
> cost:benefit of DNSSEC is better than the cost:benefit of any 
> extended query ID solution i've seen

I am not entirely convinced of that.
For DNSSEC, millions of users around the world need to figure out how to
sign their zones etc.
This is not going to be cheap.

But why does it have to be DNSSEC vs. the other?
Can't multiple solutions co-exist?

Sincerely,
Jesper G. Høy

---

From: "Roy Arends" <[email-masked]>
Date: Fri, 25 Apr 2008 17:34:23 +0200

> And those are very minor updates.

So only the terminating transaction in the resolution graph benefits from 
your proposal? 
Why does an update to root/TLD not benefit from your proposal?

> We are not talking about another DNSSEC implementation.

I don't think anyone will argue about the ease of implementation. However, 
for developers to adopt this approach, this needs to be well designed, 
thought through thoroughly, wash out the corner cases, etc. Before that, 
you have to convince the WG that the benefit of your proposal justifies 
and outweighs the cost involved.

From my point of view, forgery-resilience does already do a lot against 
blind attacks, without the requirement to update the server-side. That 
last point is important because it means that the security improves, 
solely by a unilateral update, without compromising or violating protocol. 

> XQID adds 128 bits or more.

This comparison is a bit off. You need to count the entire domain name, 
not the top level. Next to that, 0x20 and XQID are orthogonal and thus 
those bits can be added. However, the important point here is that 0x20 
does not have that chicken-egg problem. 

> Certainly neither excludes the other.

That is not what your dns-xqid document states:

POSSIBLE ISSUES:
  * Adding XQID labels to QNAME may be a problem with TSIG and DNSSEC 
packets (this has not been explored), but then there is probably no need 
to use XQID for such queries.

Roy

---

From: Jesper G. Høy <[email-masked]>
Date: Fri, 25 Apr 2008 17:57:21 +0200

> From: Roy Arends
> So only the terminating transaction in the resolution graph benefits
> from your proposal?

The other way around.
Root/TLDs benefit right away - no updates are needed to those DNS servers. 

This is because referral responses (as those from root/TLD server) can
always be verified just by looking at the second label of QNAME.
Doesn't matter is they respond with --r or --q prefix.

> and outweighs the cost involved.

Of course - I just thought that this was such a unique idea that it had to
be tested here.

> solely by a unilateral update, without compromising or violating

Agreed - and my suggestion is certainly not an alternative to
forgery-resilience.
Rather it is another way to improve it.

> not the top level.

I believe TLDs are just as vulnerable to spoofing as multi-label names.
In fact spoofing a TLD would be even more serious...

> Next to that, 0x20 and XQID are orthogonal and thus

And again - my suggestion is not an alternative to that, but rather an
improvement.

> packets (this has not been explored), but then there is probably no
> need to use XQID for such queries.

What I mean is that you can still benefit from using XQID for domain names
without DNSSEC - even when other domains have DNSSEC.

Sincerely,
Jesper G. Høy

---

From: "Roy Arends" <[email-masked]>
Date: Fri, 25 Apr 2008 18:11:30 +0200

> Doesn't matter is they respond with --r or --q prefix.

Ok. Thanks for pointing that out.

> Of course - I just thought that this was such a unique idea that it had 
to

Ok.

> In fact spoofing a TLD would be even more serious...

Sure, but that was not the point. The QNAME would hardly ever be solely 
'us' or 'uk' but more likely something like 'www.theregister.co.uk'.

> And again - my suggestion is not an alternative to that, but rather an

I understand that. I was pointing out a flaw in your comparison. 

> without DNSSEC - even when other domains have DNSSEC.

Ok.

Roy