Subject: Re: [dnsext] IP fragmentation security

From: Nicholas Weaver <[email-masked]>
Date: Mon, 1 Jun 2009 12:18:28 -0700

On Jun 1, 2009, at 10:58 AM, George Barwood wrote:

> Are there any DNS security concerns regarding fragmented IP packets?
>
> Would it be possible for a blind attacker to spoof a fragment of a  
> response, which might allow modification of a packet without needing  
> to guess the DNS ID?
>
> For example
>
> dig example.se @ns.iana.org +dnssec
>
> generates a response of more than 512 bytes. The (unsigned)  
> additional section might  therefore be modified by a blind attacker,  
> without needing to guess the ID, opening up cheap denial of service  
> attacks (and probably other nastiness) against DNSSEC.
>
> [ I don't know if this attack works, as I'm not very familiar with  
> IP fragmentation, but I don't at first sight see why it doesn't work ]

If the legit response was not fragmented, this can't work.

If the legit response WILL be fragmented, at a point the attacker  
knows, the attacker can overwrite the value POST fragmentation-point  
with some reasonably high probability if the attacker knows the  
authority's IPID chosen, esp if the defragmenter keeps unrestored  
fragments around for a long time, with just a single packet, depending  
on how the resolver does reassembly.

This might actually be really useful in some narrow cases:

Suppose authority A can generate large records.  And recursive  
resolver B is being targeted, and will request  packets using EDNS0  
and a request size large enough to cause fragmentation (eg, Bind).

The attacker does a query on B which is sent to A, and sends a  
fragment as well which overwrites the Authority or Additional field in  
the response, where the fragment is actually sent before the legit  
packet from A is received.

Basically, the packets sent (assume the fragmentation occurs at 1000  
bytes and the ID that A will use is X:

Attacker -> B:  DNS request
B->A:           DNS query
Attacker -> B:  Spoofed response:  A->B, ID X, off 1000
A->B:           A->B, ID X, fragment
                 A->B, ID X, off 1000

which B reassembles as the first 1000 bytes being A's response, and  
the rest being the attacker's response (overwriting glue fields)

The requirements:

1)  A must have a predictible (or collidable) IPID

2)  B must enable EDNS and request > MSS packets

3)  The response from A must not have DF set, and must be fragmented.

4)  Attacker can cause B to generate a request to A where the response  
from A is sufficiently large that it will be fragmented

5)  The Auth/additional field data which the attacker overwrites must  
be accepted by B without further validation (eg, independent glue  
fetch, DNSSEC).

6)  B must hold the "out of order" fragment from the attacker and use  
that to reassemble once the first piece from the legit server is  
received, rather than discarding that small fragment immediately.  Big  
open question, and probably target specific.

So the constraints are pretty tight, but there may definitely be  
usable, eg, targeting www.se:

dig +norecurse +dnssec ANY www.se @ns2.nic.se

(run 3 times):

The TCPdump output is:

12:14:57.996240 IP (tos 0x0, ttl 64, id 15775, offset 0, flags [none],  
proto UDP (17), length 63) 192.150.186.168.53968 > 194.17.45.54.53:  
57977 [1au] ANY? www.se. (35)
12:14:58.175309 IP (tos 0x0, ttl 41, id 5452, offset 0, flags [+],  
proto UDP (17), length 1500) 194.17.45.54.53 > 192.150.186.168.53968:  
57977*- 19/0/11 www.se. SOA[|domain]
12:14:58.175463 IP (tos 0x0, ttl 41, id 5452, offset 1480, flags [+],  
proto UDP (17), length 1500) 194.17.45.54 > 192.150.186.168: udp
12:14:58.175466 IP (tos 0x0, ttl 41, id 5452, offset 2960, flags  
[none], proto UDP (17), length 271) 194.17.45.54 > 192.150.186.168: udp
12:14:58.587969 IP (tos 0x0, ttl 64, id 64915, offset 0, flags [none],  
proto UDP (17), length 63)

192.150.186.168.53969 > 194.17.45.54.53: 64664 [1au] ANY? www.se. (35)
12:14:58.767143 IP (tos 0x0, ttl 41, id 5453, offset 0, flags [+],  
proto UDP (17), length 1500) 194.17.45.54.53 > 192.150.186.168.53969:  
64664*- 19/0/11 www.se. SOA[|domain]
12:14:58.767287 IP (tos 0x0, ttl 41, id 5453, offset 1480, flags [+],  
proto UDP (17), length 1500) 194.17.45.54 > 192.150.186.168: udp
12:14:58.767289 IP (tos 0x0, ttl 41, id 5453, offset 2960, flags  
[none], proto UDP (17), length 271) 194.17.45.54 > 192.150.186.168: udp
12:14:59.099446 IP (tos 0x0, ttl 64, id 6650, offset 0, flags [none],  
proto UDP (17), length 63)

192.150.186.168.53970 > 194.17.45.54.53: 53097 [1au] ANY? www.se. (35)
12:14:59.278499 IP (tos 0x0, ttl 41, id 5454, offset 0, flags [+],  
proto UDP (17), length 1500) 194.17.45.54.53 > 192.150.186.168.53970:  
53097*- 19/0/11 www.se. SOA[|domain]
12:14:59.278637 IP (tos 0x0, ttl 41, id 5454, offset 1480, flags [+],  
proto UDP (17), length 1500) 194.17.45.54 > 192.150.186.168: udp
12:14:59.278640 IP (tos 0x0, ttl 41, id 5454, offset 2960, flags  
[none], proto UDP (17), length 271) 194.17.45.54 > 192.150.186.168: udp

So you can clearly see that IPID is predictable, you can generate  
responses that WILL fragment, and there is such lovely goop in the  
additional section that, if not validated, will allow you to reassign  
the notion of what nameservers are responsible for www.se

The only question is, how does the authority's IP reassembler chose  
which fragments to use.

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: Nicholas Weaver <[email-masked]>
Date: Mon, 1 Jun 2009 12:45:56 -0700

One other comment:  Conservative glue policies (eg, Unbound's, etc,  
the "no race until win" policies) would be immune to this attack if it  
works.

---

From: Alex Bligh <[email-masked]>
Date: Mon, 01 Jun 2009 21:15:49 +0100

> A->B:           A->B, ID X, fragment

This attack can be enhanced by supplying many spoofed responses with
different IPIDs. Combined with low cache times (so B->A query is
made frequently) this would seem to have a high chance of success.

Last time I looked at an IP stack (which was admittedly ten years ago):
* Fragments arriving out of order didn't matter (so it doesn't matter if
  the spoofed fragment arrives before the first real fragment)
* The first real fragment "won", and (at least in a two fragment case) the
  reassembled UDP packet would hit the application before the real second
  fragment appeared.

This would appear to give it some mileage for a non-DNSSEC attack. But
I am not sure it is of much more use for a DNSSEC attack than flooding
the resolving nameserver with spoofed SERVFAIL responses (i.e. it's
"just" a DoS). Or am I missing something?

--
Alex Bligh

---

From: Matthew Dempsky <[email-masked]>
Date: Mon, 1 Jun 2009 15:24:17 -0500

Another comment: the attacker also has to forge the UDP checksum,  
which includes the source port and txid, but is itself only 16 bits.  
On the other hand, the attacker doesn't have to bother repeating the  
query name, so it opens the possibility for a birthday attack.

Does anyone know any DNSSEC enabled zones containing wildcard names  
with large recordsets?

On Jun 1, 2009, at 2:45 PM, Nicholas Weaver  
<[email-masked]> wrote:

> the "no race until win" policies) would be immune to this attack if  
> it works.
>
>
> --

---

From: Nicholas Weaver <[email-masked]>
Date: Mon, 1 Jun 2009 13:26:21 -0700

> Does anyone know any DNSSEC enabled zones containing wildcard names  

OH, good point.  Forgot about the UDP checksum.

So you're right, this will fail because the checksum includes the  
exisiting entropy sources.

---

From: Matthew Dempsky <[email-masked]>
Date: Mon, 1 Jun 2009 15:37:04 -0500

Actually, the checksum is a simple 16-bit ones-complement checksum and  
fragments are required to be 8-byte aligned. If you can guess what  
should have been in the fragment (presumably much lower entropy for  
most queries) couldn't you forge the checksum with reasonable  
probability?

On Jun 1, 2009, at 3:26 PM, Nicholas Weaver  
<[email-masked]> wrote:

>> which includes the source port and txid, but is itself only 16  
>> bits. On the other hand, the attacker doesn't have to bother  
>> repeating the query name, so it opens the possibility for a  
>> birthday attack.
>>

---

From: Nicholas Weaver <[email-masked]>
Date: Mon, 1 Jun 2009 13:52:03 -0700

> exisiting entropy sources.

Oh wait: here's the math:

Its 2^16 regardless of the entropy sources (port, 0x20, ID, etc):

The checksum is a 2^16 value.  The attacker must match:

a)  The IPID (predictable or 1 in 2^16, but assume predictible)

b)  The checksum (1 in 2^16, matched by basically having a random 16b  
value somewhere in the attacker's fragment, as this checksum includes  
both port and TXID and 0x20, and if the attacker knew those, he could  
respond directly))

However, the attacker gets only one try per query, since the first  
packet which matches IPID is used to be in the checksum (a checksum  
failure will mean a dropped UDP packet, not a "retry assembly" I'm  
assuming).

So its not kaminski-level even when it under conditions that work  
(authority sends a large, fragmented response with a predictable  
IPID), because although its a glue race-until-win style attack, you  
can only generate only one attack packet per query, which means ~2^16  
queries to generate a successful attack, and you need to be  
effectively sequential to keep the IPID predictable.

The same glue policy countermeasures against Kaminski attacks also  
works here, BTW.

Apologies for my stupidities.

---

From: Nicholas Weaver <[email-masked]>
Date: Mon, 1 Jun 2009 14:04:50 -0700

On Jun 1, 2009, at 1:37 PM, Matthew Dempsky wrote:

> Actually, the checksum is a simple 16-bit ones-complement checksum  
> and fragments are required to be 8-byte aligned. If you can guess  
> what should have been in the fragment (presumably much lower entropy  
> for most queries) couldn't you forge the checksum with reasonable  
> probability?

Oh wait, YEAH!  You're right.

So the requirements are:

a)  The attacker must be able to cause the target resolver to generate  
a suitably large query

b)  The query response needs:
	a)  Predictable or guessable IPID
	b)  Predictable or guessable fragment to be overwritten.

The attacker just ensures that his fragment he overwrites maintains  
the same checksum (probably easy, the lower 16b of the TTL field and  
other fields would be good candidates, or name munging, or...) or  
randomly permutes say, the lower 16b of the TTL field (randomizes the  
checksum to give a 1 in 2^16 match)

---

From: Douglas Otis <[email-masked]>
Date: Tue, 2 Jun 2009 21:30:46 -0700

> for most queries) couldn't you forge the checksum with reasonable  

Set it to zero.

Although RFC 1122 section 4.1.3.4 indicates UDP Checksums should  
default enabled, a number of DNS packets do not use UDP checksums.

-Doug

---

From: Nicholas Weaver <[email-masked]>
Date: Wed, 3 Jun 2009 10:46:43 -0700

On Jun 3, 2009, at 10:44 AM, Matthew Dempsky wrote:

> On Tue, Jun 2, 2009 at 9:30 PM, Douglas Otis <[email-masked]>  
> wrote:
>> Set it to zero.
>
> The UDP checksum will be in the same fragment as the UDP ports and the
> DNS transaction id.  The potential benefit from attacking fragments
> other than the first is that you don't have to blindly guess the
> primary source of entropy in the packet, you just have to forge a
> fragment that checksums the same as the legitimate fragment.

Which means you only need to know what the legitimate fragment looks  
like, because its a 1-complement checksum (so fully associative and  
communative), so the inserted fragment's checksum needs to match the  
legitimate fragment's checksum.

---

From: Matthew Dempsky <[email-masked]>
Date: Wed, 3 Jun 2009 10:44:34 -0700

---

From: Douglas Otis <[email-masked]>
Date: Wed, 3 Jun 2009 12:31:34 -0700

On Jun 3, 2009, at 10:46 AM, Nicholas Weaver wrote:
>> The UDP checksum will be in the same fragment as the UDP ports and  
>> the DNS transaction id.  The potential benefit from attacking  
>> fragments other than the first is that you don't have to blindly  
>> guess the primary source of entropy in the packet, you just have to  
>> forge a fragment that checksums the same as the legitimate fragment.

Agreed.

In addition, whenever UDP checksums become disabled by the query sum,  
this might be cause for concern as well.

-Doug