[I am copying this to the tech-net@netbsd.org also as they might want
to fix the NetBSD code]. 

Angelos D. Keromytis writes:
> >Use that keyed hash where? Those packets are proper packets that are
> >received fully, and after that they are processed normally (for
> >example icmp ping). They are created by the attacker, so all the ID
> >stuff etc are selected by the attacker.
> 
> Use a keyed hash to make sure the attacker cannot force all fragments
> to fall in the same hash bucket.

If I remember correctly the reassembly code will try to keep all the
fragments associated with one IP packet in one separate list. We are
now talking about the fragments of the one packets whose first
fragment has already been seen.

I.e we send packets in format:

----------------------------------------------------------------------
1.2.3.4 -> 2.3.4.5, fragid=123, off = 0, ip_len = 8, ip_hlen = 48 bytes
1.2.3.4 -> 2.3.4.5, fragid=123, off = 8, ip_len = 8, ip_hlen = 48 bytes
1.2.3.4 -> 2.3.4.5, fragid=123, off = 16, ip_len = 8, ip_hlen = 48 bytes
1.2.3.4 -> 2.3.4.5, fragid=123, off = 24, ip_len = 8, ip_hlen = 48 bytes
1.2.3.4 -> 2.3.4.5, fragid=123, off = 32, ip_len = 8, ip_hlen = 48 bytes
1.2.3.4 -> 2.3.4.5, fragid=123, off = 40, ip_len = 8, ip_hlen = 48 bytes
1.2.3.4 -> 2.3.4.5, fragid=123, off = 48, ip_len = 8, ip_hlen = 48 bytes
...
1.2.3.4 -> 2.3.4.5, fragid=123, off = 63992, ip_len = 8, ip_hlen = 48 bytes
----------------------------------------------------------------------

That is going to be 8000 fragments. The ip_input will find the struct
ipq *fp to match that packet. The struct ipq *fp will have list of all
those fragments belonging to same packet as a list and it will go
through that list twice in the ip_reass function (one to find out
where to put the fragment, and second time to see if the packet is
complete).

This means that for each of those 56 byte (48 bytes of ip header
(header + some options) and 8 bytes of actual data) * 8000 fragment
packets, we do 2 * 8000 * 8000 / 2 list operations. This means that we
do 64000000 list operations for each 448000 bytes of data. If each
list operation takes about 8 ns (133 MHz memory speed, as the list
operations are most likely limited by the speed of the memory), this
means that cpu time used to receive one packet is 0.512 seconds.
Sending two such packets per second means that the cpu is completely
busy.

This attacks needs bandwidth of 6 MBits/s to use 100% of the cpu time
of the receiver. If the memory speed is slower then the bandwidth goes
down. If the cpu has large enough cache then the list of fragments can
fit there meaning that the list operations are faster than 8 ns /
operation.

This problem is not that bad for example in OpenBSD, as it seems to
calculate the number of fragments based on the actual fragments
received. The NetBSD seems to calculate the number of packets in the
fragmentation queue.

I.e the NetBSD will calculate each of those one packet against
ip_maxfragpackets, and OpenBSD will calculate each of those 8000
fragments as one fragment against ip_maxqueue (i.e one packet is
calculated as 8000 instead of 1). The ip_maxqueue seems to be 300 on
OpenBSD, so this attack does not apply there, because the fragments
are dropped after 300 of them. For NetBSD you can send 200 of those
attack packets before it starts dropping them.

So for NetBSD this attack should work.

Actually best would have both max fragment counter and max packet
counter, as they will detect different kind of attacks. Also ip_reass
could concatenate fragments together if the ipq_fragq goes too long
(or drop the whole packet), and it could also try to optimize the
default case where the new fragment is inserted to the end of to the
beginning of the list. 
-- 
kivinen@ssh.fi
SSH Communications Security                  http://www.ssh.fi/
SSH IPSEC Toolkit                            http://www.ssh.fi/ipsec/