Subject: unaligned compression

From: "D. J. Bernstein" <[email-masked]>
Date: 29 Nov 1999 03:06:23 -0000

Say you're building a DNS packet, and you want to add BLAH.NET IN NS
FOO.BAR.ORG to the end of the packet.

You look at the packet so far. You spot \3org\0 at byte position 200.
Can you replace the new \3ORG\0 with a pointer to byte position 200?

The first \3org\0 might not be part of a domain name. Perhaps there just
happens to be a TTL of 57635431 seconds. Or perhaps there's a .ORG name
inside a record type that this server doesn't recognize. New record
types can't be compressed, but can they be the _target_ of compression?

RFC 1035, as usual, doesn't make the protocol clear. It simply says ``a
prior occurance [sic] of the same name.'' It doesn't exclude fortuitous
occurrences of the name. Are there any clients that have trouble with
this type of compression?

RFC 1123 requires that name servers ``use compression in responses.''
What exactly does this mean? Is the maximum possible compression
required in every case?

---Dan

---

From: [email-masked]
Date: Mon, 29 Nov 1999 17:20:43 +1100

> Can you replace the new \3ORG\0 with a pointer to byte position 200?

	Yes.
> types can't be compressed, but can they be the _target_ of compression?

	Yes, compression pointers can point into uncompressable RRdata.
> this type of compression?

	Not that I am aware of.  Any such client would be non-compliant.
> What exactly does this mean? Is the maximum possible compression

	To get the maximum possible compression you would have to look
	domainnames in non-names.  This would be a non-trivial issue.

	What generally happens is you build up a dictionary on
	names in the message as you build up the message along with
	there starting offsets.  When you go to add a name you look
	for the name in the dictionary.  If found you add a
	compression pointer.  If not found you a the first label
	and repeat until you get to the root label which you just add.
	Having added the name you add new name to the dictionary along
	with its offset if you didn't get a match at the first attempt.

	Now the dictionary can be fixed sized or it can be complete.

	The reason RFC 1123 makes it a MUST (where possible) is that
	otherwise responses that could have fitted in the UDP DNS message
	would require a TCP response.

	Mark	

--
Mark Andrews, Internet Engines Inc. / Internet Software Consortium
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

From: Paul A Vixie <[email-masked]>
Date: Sun, 28 Nov 1999 22:07:11 -0800

> this type of compression?

knowing pvm as i do, i believe that had he considered this when authoring
rfc 1035, he would have said something along the lines of:

|be conservative in what you generate.  only point to other names.
|
|be liberal in what you accept.  believe pointers even to non-provably-names.
|
|be safe in what you parse.  no matter where a pointer points, don't follow
|loops and don't exceed total lengths of either the name or any label.

unless he comes back from the beach and says otherwise, that's my advice too.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 29 Nov 1999 23:59:19 -0000

> domainnames in non-names.  This would be a non-trivial issue.

By ``issue'' you mean, I presume, that BIND doesn't do this. Sometimes
it misses a compression target. On occasion it unnecessarily truncates a
packet. Right?

Yes or no: Is BIND violating RFC 1123's ``MUST use compression in
responses''? If not, exactly how much compression is actually required
by RFC 1123?

In the real world, does anybody care about compression of packets that
already fit comfortably into 512 bytes? If BIND is trying to minimize
bandwidth, why does it provide NS records with its final answers?

---Dan

---

From: "D. J. Bernstein" <[email-masked]>
Date: 30 Nov 1999 00:56:51 -0000

> > Are there any clients that have trouble with this type of compression?

However, the local-compression draft says, without justification, that
``pointers should be verified to really point to the start of a label.''

If a client starts following this advice, and a server starts performing
unaligned compression, we'll have massive interoperability problems. Are
any clients actually doing what the local-compression draft says? Why?

The local-compression draft also says, again without justification, that
RP, AFSDB, RT, PX, and NAPTR ``MUST NOT be compression targets.'' This
prohibits compression allowed by RFC 1035, so it contradicts RFC 1123.
Right?

---Dan

---

From: Paul A Vixie <[email-masked]>
Date: Mon, 29 Nov 1999 19:10:03 -0800

> Yes or no: Is BIND violating RFC 1123's
> ``MUST use compression in responses''?

no.

---

From: [email-masked]
Date: Tue, 30 Nov 1999 15:39:14 +1100

Local-compression was killed in last call.

---

From: [email-masked]
Date: Tue, 30 Nov 1999 15:37:59 +1100

> it misses a compression target. On occasion it unnecessarily truncates a

	I mean named does not hunt for names where it does not know before
	hand that they exist.  It won't go looking for a label inside of
	a TTL for example.

	BIND uses a dictionary approach outlined in the previous response.
	It currently fails to put some potential compression targets out
	of the question into the dictionary.  This is an oversight.
> responses''? If not, exactly how much compression is actually required

	BIND attempts uses compression wherever it is legal to compress.
> already fit comfortably into 512 bytes?

	No one really cares.

> If BIND is trying to minimize

	Because you don't get the load spread over the correct servers
	if you don't.

	Mark