Subject: [DNSOP] Clarification question: compression pointers always to names earlier in the packet?

From: Viktor Dukhovni <[email-masked]>
Date: Wed, 24 Oct 2018 05:01:53 -0400

My reading of RFC 1035 is that DNS name "compression"
via "pointers" is restricted to name strictly earlier
in the DNS message:

   4.1.4. Message compression

   In order to reduce the size of messages, the domain system utilizes a
   compression scheme which eliminates the repetition of domain names in a
   message.  In this scheme, an entire domain name or a list of labels at
   the end of a domain name is replaced with a pointer to a prior occurance
                                                            ---------------
   of the same name.

And yet, here and there I see mention of having to take care to avoid "loops",
but loops are impossible in a monotone strictly decreasing sequence.

Is there a later RFC that relaxes the constraint and allows pointers to names
later in the message?  I'm having a bit of trouble finding the later text...

Secondarily, can the pointer point to some odd-ball location earlier in the
message that is not semantically a label in its original context, but just
happens to carry data that decodes as the desired label?  Or, are pointers
only valid to prior locations that are corresponding labels in their original
context?

-- 
	Viktor.

---

From: bert hubert <[email-masked]>
Date: Wed, 24 Oct 2018 11:21:48 +0200

> but loops are impossible in a monotone strictly decreasing sequence.

Yes. This is one of the best ways of preventing such loops. Some libraries
accidentally allowed a jump to the same place though, if I recall correctly.

PowerDNS, for reasons I'm trying to find out, not only checks if a jump went
backwards but also refuses to go backwards more than 100 times. It may be
that someone made a packet that burned a lot of CPU time.

https://github.com/PowerDNS/pdns/commit/9114819cc4c5dad50ba92c8a9ab8d852811db365

> later in the message?  I'm having a bit of trouble finding the later text...

Not that I know of. But it might accidentally work in some places, including
I think old (2.9 era) PowerDNS software. 

> only valid to prior locations that are corresponding labels in their original

I'd say "don't do that". Someone really clever might one day find you can
point back to a location in the middle of a name that so happens to be
parseable as a whole name (remember, there is a length field there). 

It would likely work though in most implementations.

	Bert

---

From: Shane Kerr <[email-masked]>
Date: Wed, 24 Oct 2018 11:22:10 +0200

Viktor,

>     the end of a domain name is replaced with a pointer to a prior occurance

I think the concern is something like this:

offset  octet
100     3
101     'f'
102     'o'
103     'o'
104     192
105     100

104 and 105 together point to offset 100, which will cause a loop even 
though they point to an earlier label.

> only valid to prior locations that are corresponding labels in their original

I have seen code which does this (there was an early version of the Knot 
authoritative server which used non-label offsets if it happened to have 
the correct data). Certainly it is easily possible that RDATA contains 
valid labels which could be used to by compression.

I think that for performance reasons most DNS software producing packets 
will maintain some data structure of prior labels & names in a packet 
and only reference those in compression. However, anything consuming DNS 
packets should probably be prepared for arbitrary pointers to previous 
locations in the packet - and also handle loops somehow (the usual 
options apply: either explicitly recording locations visited in 
traversal or just maintaining a counter and failing at some point).

Cheers,

--
Shane

---

From: Joe Abley <[email-masked]>
Date: Wed, 24 Oct 2018 02:30:02 -0700

> but loops are impossible in a monotone strictly decreasing sequence.

Surely any sequence of labels that terminates with a pointer to any
label within that same sequence is an existence proof of such a loop.
The degenerate case is a single label terminated by a pointer to
itself.

Joe

---

From: Martin Hoffmann <[email-masked]>
Date: Wed, 24 Oct 2018 12:06:38 +0200

bert hubert wrote:
> > And yet, here and there I see mention of having to take care to
> > avoid "loops", but loops are impossible in a monotone strictly
> > decreasing sequence.  
> 
> Yes. This is one of the best ways of preventing such loops. Some
> libraries accidentally allowed a jump to the same place though, if I
> recall correctly.
> 
> PowerDNS, for reasons I'm trying to find out, not only checks if a
> jump went backwards but also refuses to go backwards more than 100
> times. It may be that someone made a packet that burned a lot of CPU
> time.

Alternatively, you could track and enforce the 255 octet limit of
domain names while chasing the compression pointers.

Kind regards,
Martin

---

From: Tony Finch <[email-masked]>
Date: Wed, 24 Oct 2018 11:45:51 +0100

Viktor Dukhovni <[email-masked]> wrote:
>
> My reading of RFC 1035 is that DNS name "compression" via "pointers" is
> restricted to name strictly earlier in the DNS message: [snip]
>

Shane and Joe have answered this, but I just want to say that this is the
FIRST thing I look for in a DNS message parser, because it is such a
common denial of service vulnerability, and it's a good bit of slapstick
fun to find code that repeats this mistake.

There are two basic ways to avoid it:

* Limit the number of pointers you will follow.

* Keep a high-water-mark separate from the current location, and require
  pointers to be strictly less than the HWM. (I prefer this way.)

Note that limiting the overall length of the name isn't enough, because a
pointer can loop without making the name longer.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Viking: West or northwest, 5 to 7, occasionally gale 8 until later. Rough or
very rough. Rain then showers. Moderate or poor, becoming good.

---

From: Martin Hoffmann <[email-masked]>
Date: Wed, 24 Oct 2018 12:48:31 +0200

Tony Finch wrote:
> 
> Note that limiting the overall length of the name isn't enough,
> because a pointer can loop without making the name longer.

You are, of course, right.

Kind regards,
Martin

---

From: "John Dickinson" <[email-masked]>
Date: Wed, 24 Oct 2018 14:38:51 +0100

>    the end of a domain name is replaced with a pointer to a prior 

Not strictly to do with loops but we noticed that not all nameservers 
use the same compression algorithm. See section 9.1 and appendix B of 
https://datatracker.ietf.org/doc/draft-ietf-dnsop-dns-capture-format

John
> _______________________________________________
> DNSOP mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dnsop

John Dickinson

http://sinodun.com

Sinodun Internet Technologies Ltd.
Magdalen Centre
Oxford Science Park
Robert Robinson Avenue
Oxford OX4 4GA
U.K.

---

From: Ray Bellis <[email-masked]>
Date: Wed, 24 Oct 2018 16:00:14 +0100

>   pointers to be strictly less than the HWM. (I prefer this way.)

Right, but to be safe the HWM should be initialised with the position of
the _start_ of the label sequence that's being parsed.

Any time you follow a pointer you reset the HWM to the target of that
pointer (which per the rule above must be lower than the current value).

Ray

---

From: Tony Finch <[email-masked]>
Date: Wed, 24 Oct 2018 16:46:37 +0100

> pointer (which per the rule above must be lower than the current value).

Exactly, yes :-)

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Southeast Iceland: Westerly 7 to severe gale 9, veering northerly 4 or 5,
occasionally 6 later. Very rough or high. Showers, perhaps wintry later.
Moderate or poor.

---

From: Viktor Dukhovni <[email-masked]>
Date: Wed, 24 Oct 2018 12:54:52 -0400

> The degenerate case is a single label terminated by a pointer to

So I gather that:

  1.  Pointers must indeed go back to an earlier location in the packet.
  2.  This is not alone quite sufficient to prevent loops.

Thus, given "1" we get the follow possibilities:

    a.  The most recent pointer expands to a name that terminates
        at an offset prior to the pointer.

    b.  The most recent pointer leads to an earlier label of the
        same domain (length-1 pointer loop).  This is easy to detect.

    c.  The most recent pointer expands to a domain that moves
        past the location of the pointer, without arriving at that
        pointer, because it is just part of the data of some label.
        For example:

           ... 10 05 l a r r y 10 m o e  NNN MMM     c u r l y [...]
              | initial length 10 label |ptr 10 back|
                 |len 5 label |len 10 pointer-skipping label |

        yielding the domain name:

		\005larry\010moe.larry.moe\NNN\MMMcurly.[...]

	in which the double occurence of "larry" and "moe" just
	happens to be possible to compress away, due to a fortuitous
        position in the packet, with the pointer bytes also matching
        label content within the domain name.

So it seems that with "1" enforced, and "b" easily handled, it seems
to me (ready to be proved wrong again) that the remaining way one
can get loops is for some pointer to expand to something that
(directly without traversing any other pointer) reaches that very
same pointer or skips past it as ordinary data in the expanding
name.  Such a packet does not violate the restriction on pointers
going forward, but supposing no loop results, is this a valid
compressed name?

I'm inclined to say that such a compressed name, by creating a
pointer to a name that ultimately that same pointer as label content,
is all too clever and that I would not be wrong to write a decoder
that rejects such compressed encodings.

Am I missing something this time?

-- 
	Viktor.

---

From: Tony Finch <[email-masked]>
Date: Wed, 24 Oct 2018 18:29:52 +0100

> 		\005larry\010moe.larry.moe\NNN\MMMcurly.[...]

That's disgusting :-)

The high-water-mark algorithm forbids it, though, because the "ptr 10
back" does not go back before the HWM, which is the initial octet
with value 10. (BIND and Net::DNS use the HWM algorithm, for example.)

But you can pull a similar overlap trick if you reach back a little
further, like this:

	#!/usr/bin/perl
	use Net::DNS;
	my $buffer = "\x06\x03foo\xc0\x00\x03bar\x00";
	my $dn = decode Net::DNS::DomainName (\$buffer, 1);
	printf "%s\n", $dn->string;

output is:

	foo.\003foo\192\000.bar.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Humber: West or northwest 4 or 5, occasionally 6 until later. Moderate or
rough. Mainly fair. Moderate or good.

---

From: Ted Lemon <[email-masked]>
Date: Wed, 24 Oct 2018 15:52:12 -0400

Is there ever a valid reason to have a pointer to a pointer, though?   This
is dead easy to detect.

---

From: Mark Andrews <[email-masked]>
Date: Thu, 25 Oct 2018 07:10:14 +1100

No.

> On 25 Oct 2018, at 6:52 am, Ted Lemon <[email-masked]> wrote:
> 
> Is there ever a valid reason to have a pointer to a pointer, though?   This is dead easy to detect.
> 
> On Wed, Oct 24, 2018 at 6:48 AM Martin Hoffmann <[email-masked]> wrote:
> Tony Finch wrote:
> > 

-- 
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742              INTERNET: [email-masked]

---

From: Shane Kerr <[email-masked]>
Date: Wed, 24 Oct 2018 22:25:12 +0200

John,

> https://datatracker.ietf.org/doc/draft-ietf-dnsop-dns-capture-format

It's not too surprising. I am pretty sure that producing optimal name 
compression (by size) is the same as one of packing problems, which are 
either NP-complete or NP-hard depending on the particulars:

https://en.wikipedia.org/wiki/Packing_problems

I think that this is only true if you allow re-ordering of RRset as well 
as RR within a set, but still.

If you don't allow re-ordering then I think the overall complexity of 
compressing a message is the same as sorting, O(NlgN), which while a lot 
better is still not great, because you need to search through all prior 
labels to find the longest match when compressing each name.

I think it's due to these fundamentally expensive costs that different 
name servers use the various heuristics you mention in the C-DNS draft 
to try to get a good balance of speed & size.

Cheers,

--
Shane

---

From: Ted Lemon <[email-masked]>
Date: Wed, 24 Oct 2018 16:26:37 -0400

The good news is that in a typical DNS message, N is pretty small.
 Although I suppose in an internet-facing name server, pretty small is
still pretty big...

---

From: Mukund Sivaraman <[email-masked]>
Date: Thu, 25 Oct 2018 08:39:26 +0530

>  Although I suppose in an internet-facing name server, pretty small is

In BIND, name compression is still one of the big consumers of CPU. It
was tweaked for 9.12 to reduce the aggression of finding longest match,
but the custom compression specification in DNS is awkward. Matching
against every previously emitted label sequence when done aggressively,
dealing with case issues, limiting compression offset to first 16kB of
the message, etc. are all quirks.

A generic compression algorithm such as deflate over the whole message
may have done better as libraries have fast hand-written matching
subroutines in assembly. Such arch specific code of fast custom matching
is not reasonable to expect of a DNS implementation.

Disabling compression is almost desirable to avoid finding matches
(hence the message-compression named option), but RFC 1123 (which
predates EDNS) forbids it.

		Mukund

---

From: George Michaelson <[email-masked]>
Date: Thu, 25 Oct 2018 13:21:52 +1000

As long as we're in UDP, with DNSSEC, and many NS, packetsize in DNS
will be a "thing" and revoking label compression pushes to fragments
and/or TCP.

Personally, I think TCP is fine, and the emergence of long-lived
bindings in DNS is fine, and this is a bit overblown as a problem.
But, I get reminded by people just how long, deep and *old* the CPE
embedded DNS footprint is. Which believes UDP at 512 is a "thing"

So basically, yes: you can turn it off. But. Is it wise?

-G