Network Working Group M. Mathis Internet-Draft J. Heffner Expires: January 8, 2005 B. Chandler PSC July 10, 2004 Fragmentation Considered Very Harmful draft-mathis-frag-harmful-00 Status of this Memo By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http:// www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on January 8, 2005. Copyright Notice Copyright (C) The Internet Society (2004). All Rights Reserved. Abstract IPv4 fragmentation is not sufficiently robust for general use in today's Internet. The 16-bit IP identification field is not large enough to prevent frequent missassociated IP fragments and the TCP and UDP checksums are insufficient to prevent the resulting corrupted data from being delivered to higher protocol layers. In this note we describe some easily reproduced experiments demonstrating the problem and estimate the scale the data corruption in the presence of ever growing data rates. Mathis, et al. Expires January 8, 2005 [Page 1]
Internet-Draft Fragmentation Considered Very Harmful July 2004 1. Introduction The IPv4 header was designed at a time when data rates were several orders of magnitude lower than those achievable today. In this document, we describe a consequent scale-related failure in the IP identification (ID) field, where fragments may be mis-associated at a rate high enough likely to invalidate assumptions about data integrity failure rates. We also outline scenarios in which data corruption may happen reliably and reproducibly. While a number of problems with IP fragmentation have been well documented [1], this presents a relatively new and serious operational problem given the severity of the failure mode, and that it occurs on what is today common communications equipment. It is especially pertinent due to the recent proliferation of UDP bulk transport tools which do not do MTU discovery , and some network equipment which ignores the Don't Fragment (DF) bit in the IP header as a work-around for MTU discovery problems [2]. 2. Wrapping the IP ID Field The Internet Protocol standard specifies: "The choice of the Identifier for a datagram is based on the need to provide a way to uniquely identify the fragments of a particular datagram. The protocol module assembling fragments judges fragments to belong to the same datagram if they have the same source, destination, protocol, and Identifier. Thus, the sender must choose the Identifier to be unique for this source, destination pair and protocol for the time the datagram (or any fragment of it) could be alive in the internet." [3] Strict conformance to this standard limits transmissions in one direction between any address pair to no more than 65536 datagrams per maximum packet lifetime. Obviously hosts do not follow the standard so strictly. Assuming a maximum packet lifetime on the order of seconds, today it is common for host interfaces to send at rates higher than this. For example, a host with a 100 Mbps interface sending 1500 byte packets may send 65536 packets in under 8 seconds. The problem occurs when a fragment is dropped by the network, and a later fragment is received that, while part of a different datagram, has the same ID value and fragment offset as the dropped fragment. The two fragments will be incorrectly spliced together and delivered to the layer above IP. It is common that the fragment offset and length would match since packets of the same size sent along the same Mathis, et al. Expires January 8, 2005 [Page 2]
Internet-Draft Fragmentation Considered Very Harmful July 2004 path will be fragmented in the same manner. In 65537 segments, there must be at least two with matching ID fields. If the sender is transmitting segments fast enough that datagrams are send with duplicate ID fields within the reassembly timeout (a suggested value is 15 seconds [3]), then fragments may be mis-associated. The case of particular concern occurs when only the first fragment of a datagram is lost by the network. The remaining fragments will be stored in the fragment reassembly buffer, and at some point in the future a new packet will arrive with the matching ID field. This new first fragment will be (incorrectly) matched up with the rest of the old packet and delivered to the upper layer. Assuming the fragments are delivered in order, the rest of the new datagram will be buffered, forming a cycle. One of every 65536 datagrams will be incorrectly reassembled by the IP layer. It is possible to have a number of simultaneous cycles, bounded by the size of the fragment reassembly buffer. Most TCP implementations today participate in MTU discovery [4], which will avoid this problem by avoiding fragmentation. However, as a work-around for MTU discovery problems [2], some TCP implementations and communications gear provide mechanisms to disable path MTU discovery by clearing or ignoring the DF bit. 3. Harmful Effects of Mis-associated Fragments When the mis-associated fragments are delivered, transport-layer checksumming should detect these datagrams as incorrect and discard them. When the datagrams are discarded, it could pose a problem for loss feedback congestion control algorithms since there will be a high number of non-congestion-related losses. However, transport checksums may not be designed to handle such high error rates, either. The UDP checksum is only 16 bits in length. If these checksums follow a uniform random distribution, we expect mis-associated datagrams to be accepted by the checksum at a rate of one per 65536. With only one mis-association cycle, we expect corrupt data delivered to the application layer once per 2^32 datagrams. This number can be significantly higher with multiple cycles. With non-random data, the UDP checksum may be even weaker still. It is possible to construct datasets where mis-associated fragments will always have the same checksum. Such a case may be considered unlikely, but is worth considering. "Real" data may be more likely than random data to cause checksum hotspots and increase the probability of false checksum match [5]. Also, some applications may turn off checksumming to increase speed, though this practice has Mathis, et al. Expires January 8, 2005 [Page 3]
Internet-Draft Fragmentation Considered Very Harmful July 2004 been found to be dangerous for other reasons [6]. 4. Experimental Results To test the practical impact of fragmentation on UDP, we ran a series of experiments with a common UDP bulk transport protocol, Reliable Blast UDP (RBUDP), part of the QUANTA networking toolkit. It is one of the tools used as an alternative to TCP for high-bandwidth applications on specialized networks. The choice to use RBUDP has very little to do with the protocol itself, as any UDP transport tool without extra corruption detection would work equally well. In order to diagnose corruption on files transferred with RBUDP, we used a file format including embedded sequence numbers and MD5 checksums. These were placed such that one set was included in each fragment of each datagram. Thus it was possible to distinguish random corruption from that caused by mis-associated fragments. Two types of dataset were used. In the first, all space not used for sequence numbers and MD5 checksums was filled with pseudo-random data, giving datagrams random checksums. The second was constructed in a similar manner except that the upper halves of each 32-bit word were filled with the 16-bit ones complement of the lower half. This gave each 32-bit word a zero ones-complement sum, so datagrams had constant checksums. With these constant checksums, mis-associated fragments were guaranteed not to fail the UDP checksum test. Each dataset used was 400 MB in size. The RBUDP tools were used to send the datasets between a pair of hosts at slightly less than the available datarate. Near the beginning of each flow, a brief secondary flow was started to induce packet loss in the primary flow. Throughout the life of the primary flow, we typically observed mis-association rates on the order of 0.05%. In datasets with constant checksums, each of these mis-associations resulted in corrupted data. In sending datasets with random checksums 100 times (for a total of 100 GB), we observed one corruption and 41091 bad UDP checksums. 5. Remedies IPv6 is less vulnerable to this type of problem, since its fragment header contains a 32-bit identification field [7]. Mis-association will only be a problem at packet rates 65536 times higher than for IPv4. Since mis-association of fragments will only occur when the IP ID field is wrapped within the fragment reassembly timeout, it is possible to reduce the timeout so that this situation is less likely Mathis, et al. Expires January 8, 2005 [Page 4]
Internet-Draft Fragmentation Considered Very Harmful July 2004 to occur. Since the timeout is set by the receiving host while the IP ID field is set by the sending host, it is not generally possible to set the timeout low enough so that a fast sender's fragments will not be mis-association, yet high enough so that a slow sender's fragments will not be unconditionally discarded before it is possible to reassemble them. It is not within the scope of this document to recommend timeout values. Another means of solving the corruption issue is to add stronger integrity checking, which can be done at any layer above IP. This is a natural side effect of using cryptographic authentication. At the network layer, if IPsec AH is in use, the mis-associated fragments should be discarded with extremely high probability. Other higher layers may use longer checksums (for example, SCTP's is 32 bits in length [8]) or cryptographic authentication (SSH message authentication codes [10]). While stronger integrity checking may prevent data corruption, it will not solve the problem of a high effective loss rate. 6. Security Considerations If a malicious entity knows that a pair of hosts are communicating using a fragmented stream, it may present an opportunity for this entity to corrupt the flow. By sending "high" fragments (those with offset greater than zero) with a forged source address, the attacker can deliberately cause corruption as described above. Exploiting this vulnerability requires only knowledge of the source and destination addresses of the flow, and fragment boundaries. It does not require knowledge of port or sequence numbers. If the attacker has visibility of packets on the path, the attack profile is similar to injecting full segments. Using this attack makes blind disruptions easier, and could certainly be used effectively to cause denial of service. However, only streams using IPv4 fragmentation are vulnerable. Because of the nature of the problems outlined in this draft, the use of IPv4 fragmentation for critical applications may not be advisable regardless of security concerns. 7 References [1] Kent, C. and J. Mogul, "Fragmentation considered harmful", Proc. SIGCOMM '87 vol. 17, No. 5, October 1987. [2] Lahey, K., "TCP Problems with Path MTU Discovery", RFC 2923, September 2000. [3] Postel, J., "Internet Protocol", STD 5, RFC 791, September Mathis, et al. Expires January 8, 2005 [Page 5]
Internet-Draft Fragmentation Considered Very Harmful July 2004 1981. [4] Mogul, J. and S. Deering, "Path MTU discovery", RFC 1191, November 1990. [5] Stone, J., Greenwald, M., Partridge, C. and J. Hughes, "Performance of Checksums and CRC's over Real Data", IEEE/ACM Transactions on Networking vol. 6, No. 5, October 1998. [6] Stone, J. and C. Partridge, "When The CRC and TCP Checksum Disagree", Proc. SIGCOMM 2000 vol. 30, No. 4, October 2000. [7] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6) Specification", RFC 2460, December 1998. [8] Stewart, R., Xie, Q., Morneault, K., Sharp, C., Schwarzbauer, H., Taylor, T., Rytina, I., Kalla, M., Zhang, L. and V. Paxson, "Stream Control Transmission Protocol", RFC 2960, October 2000. [9] Kent, S. and R. Atkinson, "IP Authentication Header", RFC 2402, November 1998. [10] Ylonen, T. and C. Lonvick, "SSH Transport Layer Protocol", draft-ietf-secsh-transport-18 (work in progress), June 2004. [11] Clark, D., "IP datagram reassembly algorithms", RFC 815, July 1982. Authors' Addresses Matt Mathis Pittsburgh Supercomputing Center 4400 Fifth Avenue Pittsburgh, PA 15213 US Phone: 412-268-3319 EMail: mathis@psc.edu Mathis, et al. Expires January 8, 2005 [Page 6]
Internet-Draft Fragmentation Considered Very Harmful July 2004 John W. Heffner Pittsburgh Supercomputing Center 4400 Fifth Avenue Pittsburgh, PA 15213 US Phone: 412-268-2329 EMail: jheffner@psc.edu Ben Chandler Pittsburgh Supercomputing Center 4400 Fifth Avenue Pittsburgh, PA 15213 US Phone: 412-268-9783 EMail: bchandle@psc.edu Appendix A. Support This work was supported by the National Science Foundation under Grant No. 0083285. Mathis, et al. Expires January 8, 2005 [Page 7]
Internet-Draft Fragmentation Considered Very Harmful July 2004 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the IETF's procedures with respect to rights in IETF Documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2004). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Mathis, et al. Expires January 8, 2005 [Page 8]