Subject: Re: [Ietf-behave] Requiring NATs to process Out-of-order fragmented TCP packets

From: Pyda Srisuresh <[email-masked]>
Date: Wed, 16 Mar 2005 23:22:26 -0800 (PST)

--- nagendra modadugu <nagendra@xxxxxxxxxxxxxxx> wrote:
> > >Sounds like we are saying about the same thing. If the amount of 
> > >memory is
> > >set to 0 then one thing happens, if it is set above that, then 
> > >something
> > >else happens. I think the end story for the applications is going to 
> > >be they
> > >can't make assumptions about what will happen to out of order 
> > >fragments.
> > 
> > Which is a nice way of saying "if fragmentation occurs, everything could
> > break."
> > 
> > This makes it sounds like applications need to prevent the network from
> > fragmenting packets, then, which means they MUST do PMTUD for both UDP
> > and for TCP?
> 
> I'm for processing of in-order fragments--from what I discovered while 
> working on DTLS, PMTUD is rarely turned on, and some OS's don't even
> correctly implement getsockopt() to return the MTU value received in an
> ICMP MTU exceeded message.  This makes it hard for even MTU-mindful
> applications to do the right thing.
> 

[suresh] You are right, Path MTU discovery is rarely turned on. Many
applications (especially UDP based) are not even MTU mindful. 

> Out-of-order fragments is a wash--it doesn't seem to be worth the effort
> (even though an DoS attack against a buffering-NAT isn't particularly
> effective).  
> 
> Discussion below.
> 
> 
> Out-of-order Fragments:
> 
> Suppose buffering of fragments is supported by the NAT, so that IP
> packets can be correctly reconstructed and forwarded.  An attacker could 
> do the following:
> 
>   (1) Generate an IP packet with SA={IP of some popular server, e.g.
>       some IMAP server}, DA={external IP address of the NAT}.
>   (2) Fragment the IP packet into F1, F2, .., Fn, such that the TCP
>       header lies entirely in F1.
>   (3) Transmit F2, F3, .., Fn (skipping F1).
>   (4) The NAT buffers all the fragments received since, the (SA,SD) pair
>       is likely to be a valid tuple for current connections, and the NAT
>       has no further information upon which to filter the fragments
>       (typically port numbers).
> 
> This is potentially a bad situation--an attacker can force the NAT to buffer 
> packets (a) without having to be on a connection path, and (b) can be 
> successful with a very high probability.
> 
> The way to counter such an attack is to timeout fragment buffering.
> One way to implement this is for the NAT to fix a time window in which
> all the fragments for an IP packet must arrive--to be generous, say 100ms.  
> So if the attacker can attack at line rate, say 10Mbps, then the NAT 
> needs to buffer at most ~125kB of data (100ms worth of data).
> 
> It's possible that the numbers I've picked are way off, but if they're
> anywhere close to realistic, the attack isn't terribly effective--it doesn't 
> take much memory on part of the NAT to implement out-of-order fragment 
> processing.  Besides which, attacking at line rate is indicative of a
> much bigger problem.
>
[suresh] It sounds like what you are saying is that it is not a big deal for a
NAT to support out-of-order fragments through reassembly and that fragment
based Dos attack is something NATs can handle. If I understood you correctly, I
agree with what the assessment.
 
> I recall hearing a story about a Juniper 'bug' in their routers that
> resulted in reordering packets.  Apparently, this bug had caused some
> software to break, eventually forcing Juniper to fix the bug.

[suresh] Nagendra - this is less to do with fragments and more to do with
reorderign the IP packets itself. I believe, Juniper was reorderig IP packets
(TCP and UDP alike) while forwarding due to some internal bandwidth problems
within their core router. I suspect, many TCP stacks are sensitive to receiving
out-of-sequence segments.

> If any of this story is true, then I'm leaning towards concluding that
> out-of-order packets are a rareity (if packet N+1 is received before
> packet N, then chances are that packet N has been dropped along the
> way) in which case out-of-order fragment processing is not much use
> anyway.
> 
[suresh] That is not true. Let me not name the OSes. Suffices to say, many PC
and server stacks do send IP fragments in reverse order. Also, as you say, the
network could also cause the fragments to arrive Out of order sometimes.

So, both these are actually good reasons for NAT to support out-of-order
fragment reassembly.

> Of course, things could go terribly wrong if the timer code is buggy,
> or timer values are too large--which is not an unlikely scenario.
> 
> 
> In-order-fragments:
> 
> In-order fragments can be easily processed without need for buffering 
> based on their IP identifier fields.  Since there is no buffering, the
> worst an attacker can do is slip packets through the NAT from the outside 
> (an attack that can also be accomplished without employing IP fragments).

[suresh] I replied to Cullen in a different thread. So, I wont expand on this
further here. I believe, support of in-order-fragments alone, tantamounts to no
support of fragmentation. 

cheers,
suresh

---

From: nagendra modadugu <[email-masked]>
Date: Thu, 17 Mar 2005 01:43:12 -0800 (PST)

(Sorry Mark, you might be feeling SPAMMED--this is the last message I'll 
send directly to you.)

> agree with what the assessment.

I have made a number of assumptions, both about the numbers and also regarding
how a NAT might respond to out-of-order fragments.  Someone needs to comment
on these assumptions.  Even if the assumptions work out--I don't see 
out-of-order
fragment processing as worthwhile, unless someone has *real data* to backup the
claim that IP packets are routinely re-ordered.

> out-of-sequence segments.

Ummmm ... in what way precisely are IP fragments not also IP packets?

> network could also cause the fragments to arrive Out of order sometimes.

Again, I refer to the Juniper story. 
Can you name the platforms that fragment IP packets at source? 

> So, both these are actually good reasons for NAT to support out-of-order

I'm still don't think so, but I'll elaborate on this point separately.  Note 
that
there are also a number of implementation caveats. 

nagendra

---

From: Bryan Ford <[email-masked]>
Date: Thu, 17 Mar 2005 06:49:17 -0800 (PST)

Comments inline.

On Thursday 17 March 2005 02:22, Pyda Srisuresh wrote:
> > > Which is a nice way of saying "if fragmentation occurs, everything
> > > could break."
> > >
> > This is potentially a bad situation--an attacker can force the NAT to
> > buffer packets (a) without having to be on a connection path, and (b) can
> > be successful with a very high probability.
> >
> > all the fragments for an IP packet must arrive--to be generous, say
> > 100ms. So if the attacker can attack at line rate, say 10Mbps, then the
> > NAT needs to buffer at most ~125kB of data (100ms worth of data).
> >
> > anywhere close to realistic, the attack isn't terribly effective--it
> > doesn't take much memory on part of the NAT to implement out-of-order
> > fragment processing.  Besides which, attacking at line rate is indicative
> > of a much bigger problem.
>
> [suresh] It sounds like what you are saying is that it is not a big deal
> for a NAT to support out-of-order fragments through reassembly and that
> fragment based Dos attack is something NATs can handle. If I understood you
> correctly, I agree with what the assessment.
>
> reorderign the IP packets itself. I believe, Juniper was reorderig IP
> packets (TCP and UDP alike) while forwarding due to some internal bandwidth
> problems within their core router. I suspect, many TCP stacks are sensitive
> to receiving out-of-sequence segments.
>
> [suresh] That is not true. Let me not name the OSes. Suffices to say, many
> PC and server stacks do send IP fragments in reverse order. Also, as you
> say, the network could also cause the fragments to arrive Out of order
> sometimes.

I think it may be useful to make a distinction between "slightly out-of-order 
fragments" and "seriously out-of-order fragments".

If the multiple fragments comprising a logical datagram are received out of 
their "natural" order (e.g., because the originating host OS sent them in 
reverse order), but the fragments of one datagram are at least not (badly) 
intermixed with the fragments of previous or subsequent datagrams, then that 
is an example of "slightly out-of-order".  I think that NATs MUST be able to 
deal with such "slightly out-of-order" packets, for the reasons Suresh cites.

If on the other hand fragments 2, 3, and 4 of datagram A arrive first, then 
all of datagrams B, C, D, ..., then fragment 1 of datagram A finally arrives 
after several or many other datagrams have been seen, that is a "seriously 
out-of-order fragment".  It is obviously unreasonable to expect NATs to 
handle seriously out-of-order fragments beyond a certain point, for the 
well-known security reasons.  And I think that Nagendra is right that many 
TCP/IP stacks (we can call them buggy TCP/IP stacks if you like, but they 
definitely exist) start behaving very poorly if routers in the network start 
routinely reordering packets, hence the Juniper experience.

I would like to propose the following as a "starting point" for the NAT 
fragment handling requirements:

1. NATs MUST at the very minimum be able to handle a datagram whose fragments 
appear in an arbitrary order on the wire but "all together", not intermixed 
with fragments of other datagrams.

2. NATs MUST protect themselves from fragmentation-based DoS attacks.

I personally think #1, the lower bound, should probably be raised somewhat 
beyond the "absolute bare minimum" suggested above, if we can agree on a 
suitable way to specify how "out-of-order" a packet's fragments need to be 
before the NAT is no longer required to handle them.  Nagendra's suggestion 
of a time window seems perfectly good to me, but the metric could 
alternatively be based on packet count (i.e., the NAT is only required to 
hold on to fragments within an N-packet window after the first fragment 
arrives), or byte count.  We could leave the choice of metric to the NAT 
designer, but specify a minimum required value in each case.  I don't have 
enough experience with fragmentation issues to make a suggestion as to what 
exactly would be best here.  My point is merely that NATs really need to 
support _some_ kind of out-of-order fragment handling, at the very least so 
as to be able to handle the "slightly out of order" fragments that some 
TCP/IP stacks actually generate on the originating endpoint.

Cheers,
Bryan

> [suresh] I replied to Cullen in a different thread. So, I wont expand on
> this further here. I believe, support of in-order-fragments alone,
> tantamounts to no support of fragmentation.
>
> cheers,
> suresh
>
>
> _______________________________________________
> Ietf-behave mailing list
> Ietf-behave@xxxxxxxxxxxxxxxxxxx
> https://list.sipfoundry.org/mailman/listinfo/ietf-behave

---

From: Melinda Shore <[email-masked]>
Date: Thu, 17 Mar 2005 06:59:42 -0800 (PST)

On Thursday, March 17, 2005, at 09:49 AM, Bryan Ford wrote:
I would like to propose the following as a "starting point" for the NAT
fragment handling requirements:
1. NATs MUST at the very minimum be able to handle a datagram whose 
fragments
appear in an arbitrary order on the wire but "all together", not 
intermixed
with fragments of other datagrams.

2. NATs MUST protect themselves from fragmentation-based DoS attacks.
It seems to me that the second should be a SHOULD.  We have firewalls
to deal with that sort of problem and I have some serious reservations
about NATs dinking around with TCP machinery.
Melinda

---

From: Dan Wing <[email-masked]>
Date: Thu, 17 Mar 2005 07:16:01 -0800 (PST)

(I'm glad everyone is familiar with the poor characteristics of PMTUD, 
and that we have to put requirements on NATs to handle IP fragments.)

On Mar 17, 2005, at 1:43 AM, nagendra modadugu wrote:

Can you name the platforms that fragment IP packets at source?
There are rumors that Linux did (does) this; I don't know if that's 
still the case, but Google hasn't found a mention about the behavior 
being different in recent Linux releases.  But I haven't checked 
sources.

Justification, according to this post, is it helps performance of the 
sending system:
http://www.ussg.iu.edu/hypermail/linux/kernel/0001.1/1196.html

More information here:
http://www.google.com/search?q=linux+fragment+reverse+order
-d

---

From: Bryan Ford <[email-masked]>
Date: Thu, 17 Mar 2005 07:18:24 -0800 (PST)

> about NATs dinking around with TCP machinery.

Sure, I have no problem with that.

Cheers,
Bryan

---

From: Dan Wing <[email-masked]>
Date: Thu, 17 Mar 2005 07:29:50 -0800 (PST)

On Mar 17, 2005, at 6:49 AM, Bryan Ford wrote:
I think it may be useful to make a distinction between "slightly 
out-of-order
fragments" and "seriously out-of-order fragments".
If the NAT's inbound traffic is 'quiet' (such as a residential NAT with 
only
one UDP stream that is getting fragmented).  But if there are two 
streams that
are being fragmented, the NAT would start to behave erratically if the 
fragments
are considered "seriously" out of order by the NAT.  This could work 
okay for
a quiescent residential NAT but wouldn't work well for a busier SOHO 
NAT such
as at a coffeeshop (they're often the same $50 802.11 device, of 
course).

And Linux appears to always send UDP fragments "seriously" out of order 
--
fragment #1 with the UDP header is sent last.

If the multiple fragments comprising a logical datagram are received 
out of
their "natural" order (e.g., because the originating host OS sent them 
in
reverse order), but the fragments of one datagram are at least not 
(badly)
intermixed with the fragments of previous or subsequent datagrams, 
then that
is an example of "slightly out-of-order".  I think that NATs MUST be 
able to
deal with such "slightly out-of-order" packets, for the reasons Suresh 
cites.

If on the other hand fragments 2, 3, and 4 of datagram A arrive first, 
then
all of datagrams B, C, D, ..., then fragment 1 of datagram A finally 
arrives
after several or many other datagrams have been seen, that is a 
"seriously
out-of-order fragment".  It is obviously unreasonable to expect NATs to
handle seriously out-of-order fragments beyond a certain point, for the
well-known security reasons.  And I think that Nagendra is right that 
many
TCP/IP stacks (we can call them buggy TCP/IP stacks if you like, but 
they
definitely exist) start behaving very poorly if routers in the network 
start
routinely reordering packets, hence the Juniper experience.
The problem with TCP performance is with TCP _segments_ arriving out of 
order,
not TCP fragments arriving out of order.  The IP stack reassembles out 
of
order fragments, but the TCP stack handles putting the TCP segments into
their correct order.

One thing I'm unclear on -- do you want the NAT to re-order the 
fragmented
packets?  I don't see this as a requirement, and I don't see much 
advantage
to the NAT sending the packets to the host in-order (#1...N), backwards
(#N..1), or in exactly the same order the NAT received them.

2. NATs MUST protect themselves from fragmentation-based DoS attacks.
I don't quite agree with separating "all together" from "slightly 
together" as part of (1).

-d

I personally think #1, the lower bound, should probably be raised 
somewhat
beyond the "absolute bare minimum" suggested above, if we can agree on 
a
suitable way to specify how "out-of-order" a packet's fragments need 
to be
before the NAT is no longer required to handle them.  Nagendra's 
suggestion
of a time window seems perfectly good to me, but the metric could
alternatively be based on packet count (i.e., the NAT is only required 
to
hold on to fragments within an N-packet window after the first fragment
arrives), or byte count.  We could leave the choice of metric to the 
NAT
designer, but specify a minimum required value in each case.  I don't 
have
enough experience with fragmentation issues to make a suggestion as to 
what
exactly would be best here.  My point is merely that NATs really need 
to
support _some_ kind of out-of-order fragment handling, at the very 
least so
as to be able to handle the "slightly out of order" fragments that some
TCP/IP stacks actually generate on the originating endpoint.

Cheers,
Bryan
So, both these are actually good reasons for NAT to support 
out-of-order
fragment reassembly.

In-order fragments can be easily processed without need for buffering
based on their IP identifier fields.  Since there is no buffering, 
the
worst an attacker can do is slip packets through the NAT from the 
outside
(an attack that can also be accomplished without employing IP 
fragments).
[suresh] I replied to Cullen in a different thread. So, I wont expand 
on
this further here. I believe, support of in-order-fragments alone,
tantamounts to no support of fragmentation.

cheers,
suresh

---

From: Pyda Srisuresh <[email-masked]>
Date: Thu, 17 Mar 2005 08:23:58 -0800 (PST)

I agree. Please see my comments below.

cheers,
suresh

> And Linux appears to always send UDP fragments "seriously" out of order 
[suresh] Yup.

> (#N..1), or in exactly the same order the NAT received them.
[suresh] I agree. The whole reason that NAT needs to reassemble fragments is so
NAT can match the reassembled IP datagram against the NAT sessions it manages.
NAT is unable to do this with fragments. Once frags are assembled, I agree with
Dan, there is no need for a requirement on the ordering of fragments out of
NAT. Depending upon the implmentations, the IP stack may even be out of bounds
from NAT and hence unenforceable.

> together" as part of (1).
[suresh] My thinking likewise. 

cheers,
suresh

---

From: Bryan Ford <[email-masked]>
Date: Thu, 17 Mar 2005 08:56:27 -0800 (PST)

> as at a coffeeshop (they're often the same $50 802.11 device, of

OK, excellent point (as in, duhh, why didn't I think of that :)).  Even if the 
routers keep the fragments between a particular pair of IP endpoints in-order 
(which I believe most routers these days try very hard to do), the 
convergence of multiple fragmented streams from different source endpoints 
destined for a single target endpoint can cause the fragments to become 
"seriously out-of-order" with respect to each other at the receiver and at 
intermediate NATs.

There definitely appears to be no "one size fits all" solution to this 
problem, and as a result I think my original suggestion still more-or-less 
stands: the decision on how seriously out-of-order fragments a NAT can handle 
ultimately probably needs to be left to the NAT designer and/or 
administrator.  But even the "quiet residential NAT" at least needs to be 
able to handle the "slightly out of order" fragments sent by Linux boxes even 
in the absence of intermixing of streams, and even residential NATs probably 
SHOULD be able to handle at least a few fragmented streams from different 
sources being intermixed together in the network.  For large NATs the 
appropriate thresholds are probably different.

Perhaps one appropriate approach would be to recommend a minimum metric based 
on the number of simultaneous TCP streams the NAT is designed to be able to 
handle.  This is an issue NAT designers have to think about anyway, since 
they usually have to decide how big to let the NAT's TCP session table grow, 
and perhaps other related internal limits.

We could suggest, for example, that if a NAT is intended to be able to handle 
N simultaneously active TCP sessions crossing the NAT, then it SHOULD have 
enough fragment reordering buffer space so that a packet will be reassembled 
and forwarded correctly as long as its fragments appear within a window of 
N*M*K received bytes, where M is some reasonable maximum expected TCP segment 
size (e.g., 1500 for a typical Ethernet-oriented NAT), and K is some constant 
"fudge factor".  That way, in the (admittedly simplistic) case where 
fragments from the N active TCP streams are getting multiplexed together 
more-or-less fairly by intermediate routers, a given M-byte TCP segment's 
fragments should appear at the NAT within a window of N*M total received 
bytes.  The fudge factor K accounts for unfairness we wish to tolerate in how 
the streams are multiplexed: e.g., if there are only two streams (N=2) but 
one stream is getting only one byte through the pipe for the other's three, 
then a fudge factor K=2 will (I think) still allow both streams to get 
handled properly, but K=1 would kill the slower stream.

Note that I'm not suggesting a particular mechanism or metric by which NATs 
"should" decide how long to keep out-of-order fragments.  My purpose here is 
only to suggest one possible approach we might take to derive a "rule of 
thumb" that NAT designers could use to calculate a reasonable fragment 
re-ordering window size for a NAT of a particular size/capacity.  I don't 
have any experimental evidence supporting the above rule of thumb in 
particular (or any other), and I will gladly defer to anyone who can suggest 
a better one.

> And Linux appears to always send UDP fragments "seriously" out of order

Yes, now that you mention it, I believe you're right.

> (#N..1), or in exactly the same order the NAT received them.

I was wondering that too.  There may be a slight benefit to NATs at least 
gathering the fragments of a packet together and forwarding them all together 
(rather than still intermixed with fragments of other packets as it may have 
received them).  This may reduce the chance that the fragments will 
subsequently get "too far out of order" for the receiver or subsequent NATs 
to piece back together - thus making the NAT effectively behave as sort of a 
"misorder-reducing device" along the network path.  But I believe NATs will 
probably do this anyway regardless of the exact order in which they transmit 
the fragments (original received order, or some fixed order), and so far I 
don't really see any benefit in specifying anything regarding this aspect of 
NAT behavior.

> together" as part of (1).

Yes, you're right, it's unfortunately not that simple due to the convergence 
of multiple fragmented streams.  But see my suggestions above.

Bryan

---

From: Senthil Sivakumar <[email-masked]>
Date: Thu, 17 Mar 2005 11:12:38 -0800 (PST)

Processing in-order fragments is very similar to processing a regular 
non-fragmented
packet as far as NAT is concerned (it is a different discussion if NAT 
supports ALGs).
The whole discussion of fragment processing is relevant to receiving 
out-of-order
fragments where the L4 information is not present in the IP packet received.
NAT cannot translate this packet correctly if it is doing PAT unless it has
the L4 information.  So a NAT could

1. let the packet go without translation (bad, packet won't reach its 
destination)
2. Drop the packet (bad, same as above)
3. Queue the packet (with a timer/some mechanism to prevent Dos attacks on 
itself)

The behavior as it exists today in terms of dealing with out of order 
fragments is
non-deterministic and hence we should propose a predictable behavior, so,
3, seems to be the most logical choice.

Senthil

---

From: Dan Wing <[email-masked]>
Date: Thu, 17 Mar 2005 13:24:57 -0800 (PST)

On Mar 17, 2005, at 6:59 AM, Melinda Shore wrote:

On Thursday, March 17, 2005, at 09:49 AM, Bryan Ford wrote:
I would like to propose the following as a "starting point" for the 
NAT
fragment handling requirements:

2. NATs MUST protect themselves from fragmentation-based DoS attacks.
It seems to me that the second should be a SHOULD.  We have firewalls
to deal with that sort of problem and I have some serious reservations
about NATs dinking around with TCP machinery.
TCP segments != IP fragments.  What's the dinking around with TCP 
machinery you're concerned with?

-d

---

From: Cullen Jennings <[email-masked]>
Date: Fri, 18 Mar 2005 17:38:16 -0800 (PST)

>>> with fragments of other datagrams.

This sounds like a very contrived sort of scenario - image I had a
application that worked when it was the only applications, but then
periodically failed when other applications where behind the same NAT. This
does not sound like a good situation.

I'm not really in agreement with requirements that make NATs do something
that helps some of the time but don't solve any problem for the application
a bunch of the time.

Cullen (not as chair)