Is IP fragmentation still considered vulnerable

Co-authors of the original paper: Joshua J Daymude, Antonio M Espinoza, Benjamin Mixon-Baca, Jeffrey Knockel, and Jedidiah Crandall.

The vast majority of Internet traffic - including the traffic your browser generated when requesting and receiving the web page you're reading right now - likely uses the IPv4 protocol. Every IPv4 packet has an identifier between 0 and 65,535 (colloquially called an 'IPID') that is used when reassembling packets if ever they are fragmented during routing.

However, the IPID also has a 25+ year history of abuse as a network side channel, chronicled in research papers with titles like 'Fragmentation Considered Harmful' (Kent and Mogul, 1987), 'Fragmentation Considered Vulnerable' (Gilad and Herzberg, 2013), and 'Fragmentation Considered Poisonous' (Herzberg and Shulman, 2013). Attackers can analyse patterns in sequences of IPIDs to leak information about senders or maliciously inject forged packets of their own, poisoning DNS caches and hijacking traffic.

Our recent survey article organizes these IPID-based exploits based on their fundamental approaches and analyses the correctness, security, and performance of the various IPID selection methods that were invented along the way. Below is a summary of our findings, including the surprising recommendation that the oldest IPID selection method - often viewed as trivially insecure - may, in fact, be the best method for many modern, high-traffic servers.

What is an IPID?

IPIDs are 16-bit integers in the header of every IP packet that have existed since the original Internet Protocol by Vinton Cerf in 1978. When an IPv4 packet is larger than the maximum transmission unit (MTU) of the next link in its route, the forwarding node breaks the packet into fragments, each with the same IPID as the original. This enables the receiver to unambiguously determine which fragments belong to which packets during reassembly, so long as the sender avoids reusing IPIDs for different packets sent close in time.

Globally incrementing IPIDs and the idle scan

Naturally, every operating system initially decided on the simplest way to assign distinct IPIDs - for every packet, increment a global 16-bit counter and use its value as the IPID. This is fast, uses a small amount of space, and avoids the problem of IPID collisions, which are only possible after the counter reaches its maximum value and wraps around.

Unfortunately, the predictability of global counters directly led to the discovery of the first IPID-based exploit in December 1998 - the idle scan (see Figure 1). This measurement enables an off-path attacker (in other words, one outside the route between two machines) to detect whether a TCP port on a target machine is open via IPID interactions with a low-traffic 'zombie' machine.

Figure 1 shows that in an idle scan, a measurer M is testing whether a target port on another machine T is open. Measurer M first probes the zombie machine Z's current IPID, x. It then spoofs a SYN packet to the target machine T that appears to have come from Z.

(a) If the target port on T is closed (red X), then T does not respond and M's final probe of Z's IPID is x + 1 mod 2^16.

(b) Otherwise, if the target port on T is open (blue circle), the resulting interaction between T and Z causes M's final probe of Z's IPID to be x + 2 mod 2^16.

A taxonomy of IPID exploits

The discovery of the idle scan seeded an explosion of IPID selection methods implemented across different operating systems, which in turn, drove security researchers to discover new techniques for measurements and attacks (see Figure 2). Generally, these exploits fall into one of two categories - probe comparisons or fragment injections.

As Figure 2 shows, each operating system implementation of IPID selection varies over time in response to exploits, categorized either as probe comparisons (circles) or fragment injections (squares). Since 2000, Linux has implemented two methods, one for atomic packets (per-connection) and one for non-atomic packets (per-destination or per-bucket). FreeBSD has implemented various pseudorandom number generator (PRNG) based methods (dashed lines) but always disables them by default.

Probe comparisons involve:

• Probing a machine's IPID.
• Interacting with that machine such that future IPID values change one way if a property is 'true' and another way if 'false'.
• Probing the machine's IPID again.

By comparing the before-and-after IPIDs across repeated tests, the attacker gains statistical confidence about the property they are inferring, such as whether a port is open or closed, the value of a secret key, or evidence of communication between two machines.

In contrast, fragment injections aim to predict a sender's next IPID and use that IPID to plant malicious fragments in a receiver's reassembly buffer. This may cause the receiver to replace legitimate fragments with malicious ones, enabling exploits like DNS cache poisoning, domain certificate forgery, and intercepting/hijacking traffic.

IPID selection method comparisons

Each method was evaluated on three criteria:

1. Correctness: Does the method support unambiguous reassembly by avoiding IPID collisions?
2. Security: Are sequences of IPID values sufficiently difficult to predict?
3. Performance: What are the method's space and time complexities?

We summarize our major comparisons in the table below. For brevity, we use ✅️ to indicate correctness, ⚔️ for security, ⏱️ for time complexity, and ♾️ for space complexity.

Recommendations

Given how large a factor traffic rate plays into each method's correctness, security, and performance, the 'best' IPID selection method depends on the use case.

Figure 3 shows that, depending on a machine's rates of total outgoing traffic and non-connection-bound (non-CB) traffic, globally incrementing (dark blue), per-bucket (teal), or PRNG-based selection (orange) may provide the best correctness-security-performance tradeoff. Connection-bound (CB) traffic can be handled separately with per-connection selection (white hatching) or combined with the rest depending on what provides the best tradeoffs.

For devices like printers or edge devices with slow traffic (< 1Mbps), it is unlikely that any method will produce IPID collisions and cause correctness issues. So these devices can take advantage of the (near-)optimal security of PRNG-based selection methods without fear of their correctness or performance disadvantages. Devices with moderate traffic (like personal computers) benefit most from per-bucket selection, which overcomes the correctness and scalability issues of PRNG-based methods at faster traffic rates while preserving some stochasticity that complicates prediction.

For busy servers with fast traffic rates (> 1Gbps), we arrive at a surprising result. In the words of Mark Twain - if Mark Twain were a network security researcher - reports of globally incrementing selection's disadvantages are greatly exaggerated. Globally incrementing selection not only scales better than all other methods under high contention (when implemented as an atomic counter), but also overtakes more modern methods in security at high traffic rates. As the rate of traffic increases, correlation between an attacker's subsequent IPID probes weakens, ultimately approaching near-uniformly random values. Thus, perhaps counterintuitively, globally incrementing selection offers near-optimal correctness, security, and performance so long as the machine experiences continuous, heavy traffic.

Closing thoughts

For almost as long as IP fragmentation and IPIDs have existed, the research community has expressed concerns that it is a fundamentally 'harmful', 'vulnerable', or 'poisonous' aspect of the protocol. The often repeated recommendation to simply avoid fragmentation altogether (for example by implementing path MTU discovery and resizing packets a priori) is insufficient, as attackers have consistently developed ways to force fragmentation when needed. Instead, our findings suggest that there is no one-size-fits-all best practice for IPID selection, and operating system developers should make the methods in Figure 3 available as a user-configurable choice that best fits their use case.

Holly Bergen is a PhD student in Computer Science studying under Joshua Daymude in the School of Computing and Augmented Intelligence and the Biodesign Center for Biocomputing, Security and Society at Arizona State University.

The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.