Subject: [DNSOP] Application level DNS message fragmentation

From: Mukund Sivaraman <[email-masked]>
Date: Mon, 8 Dec 2014 14:02:12 +0530

Hi all

[I am reluctant to send this, as it could very well be a stupid
 idea. But as at least one person has suggested I discuss it on DNSOP,
 so here it is.]

When a server (plain or EDNS capable) is queried via UDP, and determines
that the response won't fit into 512 (plain) or the client's UDP message
size (EDNS), it sets TC=1 forcing the client to retry via TCP.

Fragmentation at the IP layer causes issues. Fragmentation could occur
when the PMTU is lower than the advertised EDNS message size. IP
fragments may be dropped by devices on the path causing the UDP datagram
to not arrive at the user application. Packets with DF=1 also are not
fragmented by a router if it cannot forward it.

With EDNS, when the client message size is small, a response may still
not fit in a single datagram causing the client to retry using TCP.

----

Can we have the following scheme so that fragmentation is supported at
the application level?

When a server determines that the response doesn't fit into a single
datagram (512 or the client's message size), the server splits the reply
into multiple fragment datagrams (512 or some discovered PMTU that
works) such that:

1. Each datagram is a DNS reply message with identical header field
values (except for section counts) and TC=1 in each of them. The ID
field has the same value among all reply fragments.

2. Each datagram contains part of the RRs that form the complete reply,
split on RR boundaries. The DNS header contains the appropriate section
counts for that datagram. The datagrams need not be equal in size.

3. An additional RR (plain DNS) or pseudo RR (inside OPT) called
FRAGMENT is present in every datagram with 2 16-bit fields containing
the count of fragments, and current fragment. (Though a DNS message is
limited to 1<<16 octets and a DNS datagram can be at least 512 octets
long, 16-bit fields are better for fragment count as the datagrams can
be of different sizes.)

4. A client that doesn't know about this scheme notices TC=1 and retries
with TCP. Datagrams other than the first one should be ignored as they
are duplicate replies with the same message ID.

5. A client that is aware of this scheme finds TC=1 and the FRAGMENT RR
and does reassembly (similar to IP fragment reassembly such as RFC 815),
DNS messages being limited to 1<<16 octets too.

This scheme still restricts the size of a single RR to the datagram
size. Reassembly (unlike IP fragments) doesn't require offsets such as
used in RFC 815 as RRs are wholly contained inside one datagram.

TSIG can also be made to work with such a scheme on fragment by fragment
basis.

----

This scheme is not for replacing TCP. As mentioned above, if a TXT RR
containing multiple character-strings doesn't fit in a single datagram
for example, and truncation happens, it'll require TCP. It's not for
replacing EDNS's large datagram sizes too. But it is possible for EDNS
replies to overflow path MTU causing loss of replies, and when loss is
noted, on second attempt, truncation could occur as the message no
longer fits in reduced datagram size.

Some things can still be served by UDP where possible (without involving
all the baggage of TCP.. roundtrips for starting SYN/ACK, for most DNS
requests having the connection remain in slow-start phase, etc.)  As an
example, with a fragment datagram max size of 512, replies could
traverse a firewall that blocked large replies.

This scheme should be backwards compatible with (ignored by) existing
implementations. Client implementations of this scheme can also signal
support with FRAGMENT 0 0.

		Mukund

---

From: Paul Vixie <[email-masked]>
Date: Mon, 08 Dec 2014 21:53:15 -0800

this was originally proposed in EDNS, but failed to reach consensus.

---

From: Mark Andrews <[email-masked]>
Date: Tue, 09 Dec 2014 16:58:39 +1100

> this was originally proposed in EDNS, but failed to reach consensus.

Which doesn't mean it won't reach consensus now.  Too many moving pieces
back then.

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

---

From: Paul Vixie <[email-masked]>
Date: Mon, 08 Dec 2014 22:08:16 -0800

> Mark Andrews <mailto:[email-masked]>
> Monday, December 08, 2014 9:58 PM
>

let's find out:

http://ietfreport.isoc.org/idref/draft-vixie-dnsext-edns2/

-- 
Paul Vixie

---

From: Mukund Sivaraman <[email-masked]>
Date: Tue, 9 Dec 2014 13:46:14 +0530

Hi Paul

> this was originally proposed in EDNS, but failed to reach consensus.

Do you have links to some references so that I can read what was
discussed?

		Mukund

---

From: Mukund Sivaraman <[email-masked]>
Date: Tue, 9 Dec 2014 14:01:13 +0530

Hi Paul

> http://ietfreport.isoc.org/idref/draft-vixie-dnsext-edns2/

This draft mentions this feature as TCP only. The use case I was
thinking of was in getting DNS messages over UDP through, not larger
than 1<<16 message sizes. Because there is no sequence in UDP, it'd also
need the index and count in every segment/fragment.

I didn't mention label sequence compression in the prior message. In the
case of fragments over UDP, message compression would occur as before
(RFC 1035) where OFFSET is valid within a datagram (fragment).  As
offsets do not cross datagram boundaries, this would aid simple
implemementation.

		Mukund

---

From: Mukund Sivaraman <[email-masked]>
Date: Tue, 9 Dec 2014 14:03:06 +0530

> need the index and count in every segment/fragment.

reliable delivery

---

From: Paul Vixie <[email-masked]>
Date: Tue, 09 Dec 2014 02:58:36 -0800

the idea is in my opinion relevant, and worthy of pursuit. i have
questions of clarification.

> Mukund Sivaraman <mailto:[email-masked]>
> Monday, December 08, 2014 12:32 AM
> ...
>

there is no reason to support this in non-EDNS. if someone won't upgrade
to EDNS, then (1) we have no responsibility toward improving their DNS
experience, and (2) they probably will not upgrade to this multi-message
proposal either. (arguments of the form, "we want this to work when both
endpoints can do EDNS but the middlebox forbids EDNS", are answered by
noting that middleboxes probably would not permit multi-message DNS,
either.)

i think there is no PMTU that works. marka has fought this battle for a
long time, and he's currently suggesting 1280-(headersize) for IPv6 and
1500-(headersize) for IPv4, period. my hope is that any recommendation
for application-level fragmentation for DNS on UDP/53 would say
"MAX(reliably determined PMTU, MIN(client's offered buffer size, 1500 or
1280 depending on transport protocol))."

you might also allow the initiator to offer an ideal local-interface
maximum fragment size and MIN() against that also..
> counts for that datagram. The datagrams need not be equal in size.

splitting an RR-set across messages makes my skin itch. i know it's the
right thing to do and i'm not objecting. just letting you know, somebody
will some day not recognize the OPT code that describes this as a
multi-message transaction, and cache a partial RR-set, and we'll google
the message i am now typing to show them the error of their ways.
> long, 16-bit fields are better for fragment count as the datagrams can

i think the absence of ACK-based timing means that packet trains longer
than 256 packets are too dangerous to contemplate. even with some kind
of application-layer inter-record-gap that's a lot of packets to inject
without needing to hear an OK signal from the remote end. therefore i
suggest two 8-bit fields.
> are duplicate replies with the same message ID.

i think that wastes end-to-end bandwidth, and should be avoided, by
having the initiator solicit (for QUERY) or probe (for UPDATE) using an
EDNS OPT, rather than letting the responder just spew.
> DNS messages being limited to 1<<16 octets too.

referencing your later message on this thread, i don't think compression
pointers can be allowed to point out-of-message. so, each message will
form its own string dictionary. if that's what you meant to say then i'm
sorry for misunderstanding you.
> support with FRAGMENT 0 0.

i'd like to see this coupled to the cookie proposal, so that if cookies
aren't used, then this option is not available.

i'm in moderate support.

-- 
Paul Vixie

---

From: David Dagon <[email-masked]>
Date: Tue, 9 Dec 2014 14:26:06 -0500

> long, 16-bit fields are better for fragment count as the datagrams can

This is an interesting idea. I tried to consider abuse of this
approach, though perhaps that's unfair since you've not had the chance
to fully describe things.

Here are scenarios you might consider:

  a) An attacker could create a zone that fragments into {1...N}
     packets for common MTUs, and start sending them, slowly using a
     crafted authority.  There's a small delay, e.g.,
     $DEFAULT_TIMEOUT-1, between packets, to keep the slot open as
     long as possible.  If I recall djb dnscache is at the low end
     with 100 slots (though often adjusted upwards), BIND is 1000 or
     so.  Resource exhaustion seems likely.  Cf. the recent
     multi-vendor disclosures.

     In the ideal average case, authority responses would be "one and
     done"---either an answer or timeout, absent other delegations and
     requeries, etc.  Your proposal contemplates keeping more state,
     longer.

     Perhaps this is a chore for the recursive implementations, since
     a good idea should not be rejected because it might be poorly
     executed.  For example, the recursive outbound queue might be a
     priority heap, and new iterative chases evict state held for
     app-frag'd packets, for which there's already partial zone
     information.

     Nonetheless, I wonder if your proposal would consider a maximum
     number of fragments (else, try TCP) because of these scenarios.
     (I'd be curious what legitimate fragmentation problems require a
     large max-frag value?)

  b) Further, depending on the recursive, the port must be kept open
     and not recycled with a new set of source ports, if that's the
     recursive strategy for SPR.  Conceivably, one could induce
     queries for FRAGMENT-crafted authorities, forcing the recursive
     to a fixed set of of SPR values.

     This seems like a speculative attack, but I do wonder if, in the
     simplest case, attackers could enjoy a longer Kaminsky attack
     window, if they identify a zone that tends to frag, since the
     qid/spr pair must be held for the Nth fragment.  The strongest
     strategy would be to spoof the last frag packet, which
     (presumably) would be sent last).

     Perhaps your protocol would therefore call for a randomized order
     of the RRs being fragmented, to pose a hazard for guessing about
     the Nth fragment.  (Duplicate RRs should not occur, but sometimes
     do; perhaps you'd give treatment to this in your proposal.)

     I believe the right answer here is: DNSSEC solves this, rather
     than adding more state in intermediate packets, which might not
     always arrive.
      
  c) It strikes me that this would make a very high bandwidth
     (asymmetric) covert channel application---large data transfers
     from the authority, without the client's inconvenience of sending
     upstream queries for each partial fragment.  

     Some attackers currently stuff virus binaries into zones, using
     TXT records, so the "malware drop site" is in a reputable public
     recursive cache with long TTLs---the malicious NS having long
     since been "self remediated" to SERVFAIL or REFUSED.  (I have
     some examples if you're curious.)

     This is not very common, perhaps because the book keeping for
     this type of attack is complex---lots of state on the victim side
     to get each fragment of the virus over TXT records, requeries for
     drops, etc.

     Beyond this misuse, there is some appeal to streaming content
     from an authority, e.g.:

       dig -t TXT hollywood-movie.example.com | awk '{...}' | mplayer

     assuming the fragments monotonically increase in order, etc.  No
     need for a for loop and demuxing.

     Still, this is not a wise use of DNS.  I'd be interested in your
     thoughts on a max-frag, if only to discourage channel abuse, and
     "novelty use", and whether such a limit would affect legitimate
     zones.
      
  d) Related to that, this might give DNS DDoSing another increase in
     yield.  Perhaps this is not a significant problem because: (1) The
     increase is small for the repeated headers, and (2) DNS DDoS'ers
     often already have more than enough resources; and (3) the common
     case would require the DDoS attacker to craft a zone that nicely
     frags over common MTUs, creating an artifact for later
     attribution.

  e) Minor mechanical question: What if the recursive witnessing
     FRAGMENT packets decides to start in TCP before the balance of
     the frag set arrives?  This seems like something a recursive
     implementation would handle, and not your proposal.  It would be
     useful to know what portion of TC=1 answers are seemingly
     "ignored" by recursives.

You might well dismiss all of these concerns as implementation details
for the recursives or small problems found in existing risks.  But I'd
be very curious to hear your thoughts.  

I'm particularly interested in learning the needs for legitimate
frag'd lookups, and the impact of a small cap on max-frag packets.

-- 
David Dagon
[email-masked]
D970 6D9E E500 E877 B1E3  D3F8 5937 48DC 0FDC E717

---

From: Mukund Sivaraman <[email-masked]>
Date: Thu, 11 Dec 2014 14:56:12 +0530

Hi Paul

I've started preparing a draft on Stephen Morris's suggestion.

> noting that middleboxes probably would not permit multi-message DNS,

Nod. FRAGMENT would be an EDNS option. Also note that we drop down to up
to 512 in BIND even with EDNS (don't remember off the top of my mind if
it is UDP payload or including all headers), which is perfectly fine for
the case where PMTU is small and DO=1 is required (though it won't be
very successful).

> 1280 depending on transport protocol))."

I didn't think of suggesting a fragment size in the draft any more than
what RFCs up to EDNS(0) discuss for DNS message sizes, but I'll keep
this in mind. You'll see the draft and you can suggest changes about
this.

I'll ask Mark about this, but the PMTU determination (or rather, a
payload size that works as PMTU can be lower) is from the client's
side. As it misses responses from the server, it lowers the offered
buffer size and retries. The server-side would use this offered buffer
size (and perhaps its link MTU to avoid IP fragments at source). The
server side can't determine the PMTU as it doesn't get acks.

> the message i am now typing to show them the error of their ways.

:-)

> suggest two 8-bit fields.

You are right. The fields are updated to 8 bits each. I've put in a
section about network considerations where congestion is
discussed. Also, with more fragments, the probability of loss goes up,
and because there is no acknowledgement, large numbers will cause
problems. The draft would need to recommend limits and behavior.

> EDNS OPT, rather than letting the responder just spew.

It seems that the client would have to solicit with more fields anyway
(to avoid increasing the chance of Kaminsky attack). Because there are
more reply datagrams sent, there is a slightly better chance of attack
succeeding, which we could avoid by adding extra entropy such as a
nonce. There is also the case of amplification attacks that needs to be
considered.

> sorry for misunderstanding you.

Nod, and this would assist easy implementations as they can throw away a
fragment after parsing it without waiting for all of them.

> aren't used, then this option is not available.

Some sort of measure has to be in place to avoid possibility of
amplification attacks.

		Mukund

---

From: Mukund Sivaraman <[email-masked]>
Date: Thu, 11 Dec 2014 15:33:05 +0530

Hi David

Thank you for reviewing the idea, and thinking of all these
scenarios. It's much appreciated. I've started writing a draft for this
proposal, and I'll address these items in it.

>      number of fragments (else, try TCP) because of these scenarios.

For various reasons (congestion, probability of loss, etc.), a limit on
number of fragments are necessary. We'll discuss this when reviewing the
draft.

On the topic of keeping state, a resolver would not be worser than in
the case of TCP where it needs to wait for data to arrive in individual
TCP segments and have the event loop keep the message-received-so-far
over mutiple reads. Timeouts for the UDP case could be handled similarly
by an implementation.

>      (I'd be curious what legitimate fragmentation problems require a

For many regular queries that currently result in truncation, I suppose
they could be served by a very small multiple of fragments (mind forces
me to throw some random number such as less than 4, but it would depend
on the payload size being used).

>      than adding more state in intermediate packets, which might not

The same source port would be used to receive replies for that query as
before. Other queries aren't required to use the same port (although in
implementation, they might for some time, if a socket pool is used for
performance reasons).

This does increase the chance of a Kaminsky style attack slightly, so
adding a nonce (some bits of random) somewhere in the request will be
necessary.

>      "novelty use", and whether such a limit would affect legitimate

UDP protocols especially attract all sorts of attacks. A rogue server
can send a large number of replies even with current DNS over UDP for a
single query.

Limit on number of fragments will be suggested for several reasons, and
also behavior in these cases. Checks in client implementation will be
necessary (such as checks done now) on whether it can trust reply
datagrams.

There is also the case of amplification attacks.

>      frags over common MTUs, creating an artifact for later

I don't understand the attack described here; please can you explain it?

>      useful to know what portion of TC=1 answers are seemingly

I don't understand this clearly too.

For various reasons, it now seems that request for FRAGMENT would have
to be signalled by the client.

What a resolver wants to do at any time is its wish. It can send a UDP
request, and not wait for a reply before it starts TCP, dropping the
corresponding UDP replies. Through the (IP, port, message ID) tuple, it
can match a DNS query and its corresponding replies.

It can even start another UDP request for the same, but with a different
message ID.

		Mukund