Subject: More 0x20 craziness

From: "George Barwood" <[email-masked]>
Date: Fri, 29 Aug 2008 13:59:57 +0100

When sending a query to a root or 1st level server, it seems you can prepend a sufficiently long arbitrary label (say 80 Xs, or 10 random characters), giving as much entropy as you want either via 0x20, or just by simply checking the Question in the response.

It sounds crazy, but I have just tried it and it seems to work. Or maybe it is me that has gone crazy.

I'm not sure if there are any hidden assumptions here that might need to be standardised, or whether these random prefixes could cause any problems for the root / 1st level servers?

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Fri, 29 Aug 2008 15:30:20 +0200

On Fri, Aug 29, 2008 at 01:59:57PM +0100,
 George Barwood <[email-masked]> wrote 
 a message of 61 lines which said:

> It sounds crazy, 

Isn't it simply XQID?

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

--
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: "George Barwood" <[email-masked]>
Date: Fri, 29 Aug 2008 14:49:16 +0100

> Isn't it simply XQID?

But it doesn't need any change in the servers, so can work today.

But I'm now looking at what may prove to be a mirage, but appears to be 
wonderful, a miracle.

(1) Find the correct name server(s) (if not in cache). During this phase, 
prepend a random label to the question, so that there is no lack of entropy, 
rendering spoofing impossible. Only relies on authoritative servers copying 
Question back, not 0x20. No repetition needed.

(2) Submit the client query to the name server(s). Duing this phase ignore
Authority and Additional sections, only accept Answers where LHS matches 
question.
Repeat to gain more entropy if desired.

I haven't tried this yet, so may be horribly mistaken!

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Fri, 29 Aug 2008 15:54:40 +0200

On Fri, Aug 29, 2008 at 01:59:57PM +0100,
 George Barwood <[email-masked]> wrote 
 a message of 61 lines which said:

> When sending a query to a root or 1st level server,

OK, I understand better now your idea and how it is different from
XQID. But, then, it seems it will work only with delegation-only
zones, no? It is not the case of every TLD...

This works, you get the right referral:

% dig @a-dns.pl A aNTIForgeRYstuFf-www.google.pl            

; <<>> DiG 9.5.0-P2 <<>> @a-dns.pl A aNTIForgeRYstuFf-www.google.pl
; (1 server found)
;; global options:  printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 18522
;; flags: qr rd; QUERY: 1, ANSWER: 0, AUTHORITY: 2, ADDITIONAL: 0
;; WARNING: recursion requested but not available

;; QUESTION SECTION:
;aNTIForgeRYstuFf-www.google.pl.        IN      A

;; AUTHORITY SECTION:
google.pl.              86400   IN      NS      ns1.google.com.
google.pl.              86400   IN      NS      ns2.google.com.

But this does not:

% dig @a-dns.pl A ANTiForgeRYstuFF-b-dns.pl

; <<>> DiG 9.5.0-P2 <<>> @a-dns.pl A ANTiForgeRYstuFF-b-dns.pl
; (1 server found)
;; global options:  printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NXDOMAIN, id: 4023

---

From: Alex Bligh <[email-masked]>
Date: Fri, 29 Aug 2008 15:16:40 +0100

> ;; ->>HEADER<<- opcode: QUERY, status: NXDOMAIN, id: 4023

As I read what George was suggesting, you've addressed that to the
wrong server, and the correct query would be:

$ dig @a.root-servers.net A ANTiForgeRYstuFF-b-dns.pl

; <<>> DiG 9.4.2-P1 <<>> @a.root-servers.net A ANTiForgeRYstuFF-b-dns.pl
; (1 server found)
;; global options:  printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 62848
;; flags: qr rd; QUERY: 1, ANSWER: 0, AUTHORITY: 7, ADDITIONAL: 9
;; WARNING: recursion requested but not available

;; QUESTION SECTION:
;ANTiForgeRYstuFF-b-dns.pl.	IN	A

;; AUTHORITY SECTION:
pl.			172800	IN	NS	B-DNS.pl.
pl.			172800	IN	NS	G-DNS.pl.
pl.			172800	IN	NS	E-DNS.pl.
pl.			172800	IN	NS	F-DNS.pl.
pl.			172800	IN	NS	H-DNS.pl.
pl.			172800	IN	NS	A-DNS.pl.
pl.			172800	IN	NS	D-DNS.pl.

;; ADDITIONAL SECTION:
A-DNS.pl.		172800	IN	A	195.187.245.44
B-DNS.pl.		172800	IN	A	80.50.50.10
D-DNS.pl.		172800	IN	A	213.172.174.70
E-DNS.pl.		172800	IN	A	213.218.118.26
F-DNS.pl.		172800	IN	A	217.17.46.189
F-DNS.pl.		172800	IN	AAAA	2001:1a68:0:10::189
G-DNS.pl.		172800	IN	A	149.156.1.6
G-DNS.pl.		172800	IN	AAAA	2001:6d8:0:1::a:6
H-DNS.pl.		172800	IN	A	194.0.1.2

Alex

---

From: Stephane Bortzmeyer <[email-masked]>
Date: Fri, 29 Aug 2008 16:18:37 +0200

On Fri, Aug 29, 2008 at 03:16:40PM +0100,
 Alex Bligh <[email-masked]> wrote 

> $ dig @a.root-servers.net A ANTiForgeRYstuFF-b-dns.pl

No, I do not think I was wrong, George mentioned the root servers but
also the TLD servers.

I we limit his scheme to the root servers, it works *today* (the root
is delegation-only) but it is quite limited.

---

From: Mohsen Souissi <[email-masked]>
Date: Fri, 29 Aug 2008 16:57:23 +0200

On 29 Aug, Stephane Bortzmeyer wrote:
 | On Fri, Aug 29, 2008 at 03:16:40PM +0100,
 |  Alex Bligh <[email-masked]> wrote 
 |  a message of 53 lines which said:
 | 
 | > As I read what George was suggesting, you've addressed that to the
 | > wrong server, and the correct query would be:
 | >
 | > $ dig @a.root-servers.net A ANTiForgeRYstuFF-b-dns.pl
 | 
 | No, I do not think I was wrong, George mentioned the root servers but
 | also the TLD servers.
 | 
 | I we limit his scheme to the root servers, it works *today* (the root
 | is delegation-only) but it is quite limited.
                           ^^^^^^^^^^^^^^^^^^^

==> I suspect it is even much more limited than you think, unless I
have missed something...

While there are no changes on the servers side, I think it is not the
case for the stub resolver.

As a matter of fact, while it is straigthforward to manually prepend
some an extra string to the original QNAME and then submit the new
query to root/tld servers by using some special DNS client like "dig",
which entity would/should do such prepending for *real DNS traffic*
typically originated by applications:

- the stub resolver when being invoked by the application, and in that
  case it would forget about the QNAME, unless it sends two queries
  (one with prepending and a second one without prepending)?

- the recursive name server (rdns) queried by the stub resolver on
  behalf of the application behind it? And in that case, would the
  rdns store the original query and send it the second time after the
  prepended query?

So in both cases, I don't think it works *today as is* without hacking
either one of the entities above. 

Mohsen.

---

From: Evan Hunt <[email-masked]>
Date: Fri, 29 Aug 2008 15:01:12 +0000

> % dig @a-dns.pl A ANTiForgeRYstuFF-b-dns.pl

What you want here is ANTiForgRYstuFF.b-dns.pl (dot, not hyphen).  That
allows you to determine whether b-dns.pl is a zone apex.  In this case it
isn't, so you get NXDOMAIN and you know the closest enclosing zone is "pl".
"foo.pl", on the other hand, is a zone apex and "dig @a-dns.pl A
alkjerf.foo.pl" does get you the proper delegation.

(I've been playing with the same idea for a few days; Paul Vixie
mentioned it here yesterday in the post "kaminsky resistance, section
by section".)

-- 
Evan Hunt -- [email-masked]
Internet Systems Consortium, Inc.

---

From: Andrew Sullivan <[email-masked]>
Date: Fri, 29 Aug 2008 11:00:22 -0400

[no hat]

On Fri, Aug 29, 2008 at 01:59:57PM +0100, George Barwood wrote:

> When sending a query to a root or 1st level server, it seems you can
> prepend a sufficiently long arbitrary label (say 80 Xs, or 10 random
> characters), giving as much entropy as you want either via 0x20, or
> just by simply checking the Question in the response.

Well, that happens to work for your current cases.  But how can you
possibly know that without asking?

A

-- 
Andrew Sullivan
[email-masked]
+1 503 667 4564 x104
http://www.commandprompt.com/

---

From: [email-masked]
Date: Fri, 29 Aug 2008 16:09:28 +0100

> wrong server, and the correct query would be:

This is essentially the same (if not identical) as Paul was talking about 
in his "Section by Section" e-mail from last night - adding a random 
prefix on the front of the QNAME during delegation chain resolution.

The hardest part is zone-cuts.  For example, if I've got:

$ORIGIN example.com
www     IN      NS      ns1.example.net

  and

$ORIGIN www.example.com
@       IN      A       192.168.1.1

- how do we identify those without doing every (final) query twice? 

Asking for <nonce>.www.example.com to the root and .com servers will give 
high entropy queries that get you the delegation chain as far as 
example.com's nameservers.  But if we then only ask those servers the 
original question we've got no additional entropy on the resulting 
referral.  So (as Paul said) you still have to ask for 
<nonce>.www.example.com, and then get the referral, and then finally get 
NXDOMAIN, and only then can you ask the original question.

That appears to mean twice as many queries to the real authoritative 
servers, for every QNAME, since it's perfectly possible for 
foo.example.com to have a different final delegation chain to 
www.example.com.

Ray

I also came up with this independently earlier this month, but only 
mentioned it to Roy and Wouter and didn't happen to mention it to Paul.

-- 
Ray Bellis, MA(Oxon)
Senior Researcher in Advanced Projects, Nominet
e: [email-masked], t: +44 1865 332211

---

From: Paul Vixie <[email-masked]>
Date: Fri, 29 Aug 2008 16:02:23 +0000

> When sending a query to a root or 1st level server, it seems you can =
> prepend a sufficiently long arbitrary label (say 80 Xs, or 10 random =
> characters), giving as much entropy as you want either via 0x20, or just =
> by simply checking the Question in the response.
> 
> It sounds crazy, but I have just tried it and it seems to work. Or maybe =
> it is me that has gone crazy.
> 
> I'm not sure if there are any hidden assumptions here that might need to =
> be standardised, or whether these random prefixes could cause any =
> problems for the root / 1st level servers?

aside from the fact that some names are really in those zones and so no rule
of the form "if it's a top level or root zone query, behave as follows" can
scale, this duplicate some elements of a proposal i sent here yesterday (which
lacks this scaling limit) entitled "kaminsky resistance, section by section."

---

From: Paul Vixie <[email-masked]>
Date: Fri, 29 Aug 2008 16:10:39 +0000

> - how do we identify those without doing every (final) query twice? 

we don't.  that's the cost.

> foo.example.com to have a different final delegation chain to

once per new QNAME per RDNS per TTL.  this is a lower number than you'd think.

> mentioned it to Roy and Wouter and didn't happen to mention it to Paul.

i've also seen it mentioned in various non-mailing-list discussions all
year during the kaminsky exercises, but it could never overcome its
cost:benefit analysis until evan hunt mentioned it yesterday while i was
trying to figure out once again a way to delete contested NS RRsets from
the cache without immediately getting them poisoned by an attacker who
knew i'd be going uphill to refresh them.

---

From: Alex Bligh <[email-masked]>
Date: Fri, 29 Aug 2008 17:33:36 +0100

> once per new QNAME per RDNS per TTL.  this is a lower number than you'd

If combined with 0x20, could one only make the additional query if
(i) the original qname's case was not preserved or (ii) the qname
did not itself contain sufficient entropy (e.g. ".", "com." etc.)?

Alex

---

From: Paul Vixie <[email-masked]>
Date: Fri, 29 Aug 2008 16:54:51 +0000

> did not itself contain sufficient entropy (e.g. ".", "com." etc.)?

i love the sound of that, except, there isn't "an" additional query in the
sense of "the one at the end that turns out to be one too many, that we'd
like to avoid".  you literally don't know which one is going to be the one
you'd be trying to avoid, until after you've received an answer to it.

however, if you changed this proposal to say "if there enough 0x20 bits
and if the servers all echo them properly, then it's not nec'y to fully
discover the NS RRset chain", then we could get a little further before
logjamming on two other issues.

issue the first is, the goal of this part of the proposal is to make it
possible to be very draconian in the NS RRset replacement strategy, and
i'm pretty sure that the number of bits i'd want to be protected by is
in the 64-or-so range when i'm about to make a predictable refill query.

issue the second is, one never knows if there's a UDP port derandomizer
somewhere in the path between an RDNS and an ADNS, so the number of 0x20
bits needed for full confidence is really 48 or so, and that's a very
long qname indeed.

great thought though.  you had me hoping there for a minute.

---

From: Alex Bligh <[email-masked]>
Date: Fri, 29 Aug 2008 19:11:47 +0100

> you'd be trying to avoid, until after you've received an answer to it.

I need to think a bit more about that. I think a query by query illustration
of how the "section by section" approach works would help illustrate it
to people in general (not just me).

> bits needed for full confidence is really 48 or so, and that's a very

Is it a reasonable assumption that if "the internet" (perhaps signaled
by a couple of test probes) is not behind a port derandomiser, then
no nameserver is? IE is discovery that an RDNS is "behind" a derandomiser
(NAT / ALG etc.) sufficient to use as a heuristic for needing more
entropy in the qname (under 0x20 or some other proposal), or do we
also need to consider the case where any arbitrary ADNS might have
a derandomiser in front of it? I am thinking that if we could put
in the category of "if you run an ADNS like this you deserve to get
your domains spoofed more easily", then an RDNS which could detect
whether it is behind a NAT through queries to a couple of servers
that happened to support a suitable extension could by extension apply
(or not apply) that to all servers, and hence require more bits of
entropy.

A possible nit with approaches that rely on prepending data to
the qname is that they risk shortening the maximum 'true' qname
length. I think in the real world the heaviest user here is NSEC3
(no comments about DNSSEC and 'real world' in the same sentence
please) and one presumes that this isn't a problem.

Alex

---

From: "George Barwood" <[email-masked]>
Date: Fri, 29 Aug 2008 19:10:03 +0100

I have now tried it out, and there seems to be a problem in some cases.

The akamaiedge.net Bailwick returns Name Error (3) for

<nonce>.E120.G.akamaiedge.net

with a SOA record ( and no name servers / referral ).

However in stage 2, it generates a referral for the question 
E120.G.akamaiedge.net

[ Client query was www.paypalobjects.com ]

It still seems to be a good trick for queries to root and TLD servers, but I 
still cannot see any way of getting high security for akamaiedge.net ( 
although of course 0x20 helps a bit ).

---

From: "Roy Arends" <[email-masked]>
Date: Fri, 29 Aug 2008 20:17:29 +0200

Paul Vixie wrote on 08/29/2008 06:10:39 PM:

> Ray Bellis wrote on 08/29/2008 05:09:28 PM:
>

Since I'm mentioned here, I'll respond.

Ray Bellis mentioned this idea to me on the 10th of August. I subsequently 
discussed it with Wouter Wijngaards as a possible scenario to add entropy 
during resolution of the delegation chain (for implementation in Unbound). 
I've not seen it mentioned before elsewhere. 

This is roughly what was discussed at the time:

During resolution, prepend a label with a nonce to the query. The query 
would look like <nonce>.www.example.com. Each request has a unique nonce, 
a nonce is never re-used.

This continues until an authoritative answer is received (either NXDOMAIN, 
wildcard, CNAME, DNAME, anything that either terminates or restarts the 
resolution process). That authoritative answer comes most likely from a 
server that is authoritative for the www.example.com domain. (most likely, 
since in theory, the <nonce>.www.example.com name could be delegated from 
the www.example.com domain, which is most unlikely, as that would suggest 
delegation point wildcard NS RRSets).

Anyway, we now have an address of a nameserver that is authoritative for 
www.example.com.
We could send it a priming query for the authoritative nameservers (Wouter 
Wijngaards idea).
In any case, we can now send it a query for www.example.com.

Regards

Roy

---

From: Paul Vixie <[email-masked]>
Date: Fri, 29 Aug 2008 19:41:57 +0000

> I need to think a bit more about that. I think a query by query
> illustration of how the "section by section" approach works would help
> illustrate it to people in general (not just me).

you're right of course.

> Is it a reasonable assumption that if "the internet" (perhaps signaled by
> a couple of test probes) is not behind a port derandomiser, then no
> nameserver is? IE is discovery that an RDNS is "behind" a derandomiser
> entropy in the qname (under 0x20 or some other proposal), ...

i'm saying no, because the probes can become a new vulnerability (to either
attacks, or implementation errors, or new kinds of middleboxes), and because
topology and topography can change.  and that's not counting the possibility
that an RDNS may be in a multipath topology where some packets get their UDP
port numbers derandomized and some do not.  there's too much variability, now
and in the future, for me to get comfortable with modality of this kind.  i'd
be a lot more comfortable if we came up with something we "just always do".

> A possible nit with approaches that rely on prepending data to the qname
> is that they risk shortening the maximum 'true' qname length. I think in
> the real world the heaviest user here is NSEC3 (no comments about DNSSEC
> and 'real world' in the same sentence please) and one presumes that this
> isn't a problem.
> 
> Alex

indeed, we're talking about burning some qname length.  however, i'm only
asking for 64 bits, which using base32 is eleven ASCII characters, which is
not a lot to take out of a 256-character quota.

---

note that many "nameservers" just don't answer some of the queries i'm saying
we should send to protect the authority section.  the NS's for www.cnn.com
just time out on "dig @dmtns01.turner.com. kjhsdfkjhsdf.www.cnn.com in a".
this is clearly not a real name server, it's a dns middlebox of some kind,
one of many that does the wrong thing.  (i don't mind somebody who doesn't
answer NS queries since these are always diagnostic in nature, but someone
who won't send a delegation unless they recognize the qname is just evil.)
((thanks to dan kaminsky's blog for pointing out the CNN example, and to
robert edmonds who shared it with me.))

---

From: Paul Vixie <[email-masked]>
Date: Fri, 29 Aug 2008 19:44:59 +0000

> ...
> ...

root name servers have to answer priming queries.
noone else has to, and many do not.

---

From: JINMEI Tatuya / 神明達哉<[email-masked]>
Date: Fri, 29 Aug 2008 12:53:59 -0700

At Fri, 29 Aug 2008 20:17:29 +0200,

> In any case, we can now send it a query for www.example.com.

One thing I've puzzled about regarding this type of approach is its
cost-benefit tradeoff.  If we can only use it in identifying
intermediate NSes, I thought our 'best current practice' (i.e.,
randomized QID + source port (+ perhaps source IP address (+ perhaps
'traditional' 0x20))) already provided reasonable security.  We could
also use this to confirm possible change of already cached NS as
seemingly indicated in this thread, but for that purpose we can
actually simply fetch the authoritative NS RRset directly; then the
trust ranking concept of RFC2181 will protect us from further attacks.

Of course, the <nonce> or <random> makes the transaction even securer,
so if we can get it free, that would be wonderful; but it actually
comes with a cost, including more queries that are redundant
otherwise, handling miscellaneous corner cases or non compliant
authoritative servers, run-time cost including getting additional
entropy, and of course implementation cost (which is probably minor,
though).

So far, the tradeoff is not so obvious to me (indeed, it seems to me
the known benefit isn't worth the cost), but as no one else seems to
have the same doubt, am I missing something fundamental, or does the
benefit so obviously outweigh the cost for others?

---
JINMEI, Tatuya

---

From: Alex Bligh <[email-masked]>
Date: Fri, 29 Aug 2008 20:54:51 +0100

--On 29 August 2008 19:41:57 +0000 Paul Vixie <[email-masked]> wrote:

> note that many "nameservers" just don't answer some of the queries i'm
> saying we should send to protect the authority section.  the NS's for
> www.cnn.com just time out on "dig @dmtns01.turner.com.
> kjhsdfkjhsdf.www.cnn.com in a". this is clearly not a real name server,
> it's a dns middlebox of some kind, one of many that does the wrong thing.
> (i don't mind somebody who doesn't answer NS queries since these are
> always diagnostic in nature, but someone who won't send a delegation
> unless they recognize the qname is just evil.) ((thanks to dan kaminsky's
> blog for pointing out the CNN example, and to robert edmonds who shared
> it with me.))

Well, I think breaking resolution for ADNS (or more accurately middlebox
infested ADNS) which are clearly and irrefutably non-compliant is an
acceptable price given vendors have now some time to fix it, assuming
the population isn't that large - after all port randomisation broke
many dubious firewall configs and was deemed acceptable, and I suspect
the total number of broken DNS middleboxen is far smaller than this.
I'm sure cnn.com have a vested interest in making sure cnn.com continues
to resolve, and far more ability to make sure it does than your
average Joe firewall user.

Alex

---

From: [email-masked]
Date: Fri, 29 Aug 2008 22:44:35 +0100

> but for that purpose we can actually simply fetch the authoritative
> NS RRset directly; then the trust ranking concept of RFC2181 will
> protect us from further attacks.

The problem as I saw it is that the real authoritative NS RRset (the one 
that's in the delegated zone) has to be fetched from an IP address which 
is learnt from DNS requests which are less credible (per RFC2181 rules).

Or, to put it another way, you're suggesting that we believe 5th tier 
information ("glue from a primary zone") to get 3rd tier information 
("authoritative data included in the answer section of an authoritative 
reply").

However, the Kaminksy attack pollutes the cache with spoofed 4th tier data 
("data from the authority section of an authoritative answer").
_
So, we've a known attack against tier 4, but we have to _really_ believe 
the tier 5 data before we can reliably obtain the real tier 3 data.

Ray

---

From: JINMEI Tatuya / 神明達哉<[email-masked]>
Date: Fri, 29 Aug 2008 15:22:49 -0700

> ("authoritative data included in the answer section of an authoritative 

Right, but that part is established by "identifying intermediate NSes"
(quoting my previous message) and "I thought our 'best current
practice' (i.e., randomized QID + source port (+ perhaps source IP
address (+ perhaps 'traditional' 0x20))) already provided reasonable
security" (ditto).  Note that the available window for the attacker is
very limited (generally, just once per TTL) because we'd trigger the
confirmation query if we detect an update attempt with different
information.

Again, I understand the additional nonce makes this process even
securer.  My question is whether the benefit outweighs its cost.

---
JINMEI, Tatuya

---

From: Paul Vixie <[email-masked]>
Date: Fri, 29 Aug 2008 22:51:45 +0000

> acceptable price given vendors have now some time to fix it, assuming the
> population isn't that large - after all port randomisation broke many
> dubious firewall configs and was deemed acceptable, and I suspect the
> total number of broken DNS middleboxen is far smaller than this.  I'm
> sure cnn.com have a vested interest in making sure cnn.com continues to
> resolve, and far more ability to make sure it does than your average Joe
> firewall user.

i'm not sure how successful bind or unbound or nominum would be with a
patch that broke www.cnn.com, however.

---

From: Paul Vixie <[email-masked]>
Date: Fri, 29 Aug 2008 22:56:49 +0000

> Internet Systems Consortium, Inc.

i am also reconsidering these issues.