1Max Planck Institute for Software Systems (MPI-SWS) 2Rice University
In this paper, we present Pretty Good Packet Authentication (PGPA), a simple service that can establish whether or not a given host has sent a particular packet. PGPA provides a firm basis on which to act against the culprit, and, at the same time, it enables innocent users to defend themselves against false accusations. We also describe an implementation of PGPA that can be deployed incrementally and with minimal changes to the current Internet.
On the one hand, because IP addresses in the Internet can be easily spoofed, malicious users can use forged addresses to evade detection. In fact, it is well known that vulnerabilities in the interdomain routing protocol, BGP, can be exploited to hijack entire IP prefixes for short periods of time. The hijacker can send and receive traffic from the hijacked pool of IP addresses during this time. For example, a recent study of email spam has shown that some spammers use this technique to work around black-listed IP addresses . Worse, under the current state of affairs, the victim could be falsely accused and held responsible for actions of the attacker.
Recently, researchers at the University of Washington demonstrated the potential for such false accusations by causing hundreds of DMCA take-down notices to be generated for several machines that were not participating in file sharing networks, including their own printer and a network access point . In a more serious case, an innocent user was suspected of having downloaded child pornography because his ISP had made a mistake when looking up an IP address for the police. By the time the mistake was discovered, the police had already confiscated his computers and searched his home .
On the other hand, if an offending packet does have the correct source address, the sender can use the weakness of the current mechanism as an excuse. Since one cannot be sure whether the packet's source IP address was spoofed or not, the real sender can plausibly deny having sent the packet. Thus, it is difficult to hold users accountable for their actions.
In this paper, we present a system called Pretty Good Packet Authentication (PGPA), which addresses these problems by offering a simple packet authentication service. PGPA determines whether or not a host H has sent a specific packet P at approximately time t. This provides a firm basis on which to act against the owners of hosts that send malicious or illegal traffic, since they can no longer deny having sent it, or use the lack of reliable authentication as an excuse. At the same time, PGPA can establish that a suspected device has not sent a particular packet, which gives innocent users the ability to defend themselves against false accusations.
Unlike systems that are designed for online verification of the traffic source , PGPA authenticates packets not just to their recipients, but to anyone who has access to them. For example, a system administrator can use intercepted packets to convince the police that a certain user has attempted to break into one of his systems, and the police can query PGPA to verify his claims. With an online verification system, an intercepted packet would not be convincing evidence because the accused user could claim that the source address had been forged by the administrator.
PGPA also protects users' privacy. Since PGPA only answers queries about specific packets and specific points in time, it cannot be used to spy on the user's traffic or to screen user's traffic for suspicious behavior. In order to get useful information out of PGPA, the inquirer must either be the recipient of the packets in question, or he must have intercepted them or obtained them from the recipient. In all cases, the content of the packets and the suspected source is already known to the inquirer; PGPA merely affirms the authenticity of the source address.
On the one hand, PGPA is a simple service; it does not attempt to match the functionality of full-blown accountability systems like AIP . On the other hand, it has the advantage of being much easier to deploy than a clean-slate solution. We show that PGPA can be implemented on the user's Internet access link, without requiring changes to routers or to the Internet backbone, and that it can be incrementally deployed.
The rest of this paper is structured as follows. We give a brief overview and discuss related work in Section 2, we outline an implementation of PGPA in Section 3, and we discuss several applications in Section 4. In Section 5, we conclude the paper and briefly outline future work.
We propose a weaker form of packet authentication, which enables an ISP to verify whether a given, recently transmitted IP packet was sent by one of its customers. Stated more precisely, PGPA provides the following capability:
We will show that this capability can be implemented and deployed in a straightforward manner.
On another related topic, accountability on the Internet has been proposed as the ability to associate an action with the responsible entity. The Accountable Internet Protocol (AIP)  is a replacement for IP that allows hosts and domains to prove that they own the address they use. Based on this foundation, the protocol aims at dealing with source spoofing, route spoofing and denial-of-service (DoS). However, AIP is a clean-slate design whose deployment would require upgrading major components of the Internet, including the network protocol and the addressing structure.
In this paper, we settle for a narrower goal: verifying that a packet was sent from the host whose IP address appears in the packet's header. We show that this simple capability can be deployed quite easily and still provides powerful properties.
|Figure 1: Example PGPA setup. The PGPA device keeps a digest of the packets the customer transmits. Given a packet and the approximate time of transmission, it can verify whether the packet is authentic.
Deploying packet authentication on the access links has three distinct advantages. First, it does not require upgrades or additional processing in the high-speed backbone. Second, it helps against customer-side spoofing because the ISP knows which IP addresses have been assigned to each link (e.g., via DHCP) and can filter out any packets with different addresses. Finally, it provides for incremental deployment, since each access link can be upgraded independently. This provides us with a feasible deployment path.
A different question is whether an ISP must be trusted by its customers not to blame them (accidentally or deliberately) for packets they did not actually send. This depends on how PGPA is implemented; we will discuss the details in Section 3.2.
Of course, if the device is physically within the user's reach, he can destroy the device, and thus the evidence it contains. Hence, user-side monitors cannot be used to fight severe crime. Even though the destruction of the device would raise suspicion and might even be punishable by itself, that punishment may be preferable to the penalty for the crime. If this is a concern, the monitors should be deployed at the ISP instead.
Packets can also be transformed by IP fragmentation. A simple way to handle fragmentation is to have the monitor reassemble outgoing packets before calculating their digests, and to allow PGPA queries only for complete packets. If an observer intercepts packet fragments, he must reassemble the corresponding packets and issue a PGPA query for the reassembled packet.
An inexpensive hard drive should be sufficient for almost all access links - especially since most connections are asymmetric and have a low-capacity upstream. Today, top-of-the-line DSL connections have a capacity of 1 Mbps, so they can transmit at most 3,125 40-byte packets per second. (This corresponds to a TCP acknowledgment; data packets are usually much larger.) Hence, even under worst-case assumptions, a 187 GB hard drive is sufficient to keep a SHA-1 hash and a 32-bit timestamp for a month. Furthermore, since storage capacity has grown faster than bandwidth , future technology will tend to make it possible to store the necessary data for increasingly longer periods. Having storage at the access link is increasingly common; service providers are already deploying managed boxes, such as TriplePlay gateways or set-top boxes , many of which already include a storage device with substantial capacity.
The chances of success for such an attack are low, because the attacker would have to guess not only the entire contents of a packet - including `random' fields such as the TCP sequence number, the TCP acknowledgment number and the IP identifier - but also the approximate time of its transmission. PGPA must allow a small time window when checking timestamps; after all, there are queueing delays and clocks on the Internet are only loosely synchronized, so we cannot expect the requester to know the exact time when the packet was sent. However, this window can be kept small, on the order of seconds. It would be difficult for the attacker to correctly guess all of the above header fields (80 bits) plus the approximate time of transmission. Furthermore, the monitor can introduce additional randomness by replacing the IP identifier, or by adding a header option with a random value. Finally, the rate at which the monitor answers queries can be limited to prevent search attacks.
If the monitor device is stolen and compromised, the attacker could run a dictionary attack on the stored hash values. To mitigate the risk of information leakage in this case, the monitor can include a salt value when calculating the hashes.
Thus, the guarantee we achieve is: Given a packet P, a timestamp t that is not more than Tmax in the past, and a source IP address S, the ISP that owns S can verify whether S has sent P at approximately time t, provided that monitors are deployed on the ISP's access links.
The facility allows an ISP to verify whether a given packet that was allegedly sent by one of its customers is authentic. This capability is useful whenever one of the ISP's customers is accused of having sent offending traffic.
For instance, ISPs frequently receive complaints from copyright holders or law enforcement agencies, alleging that one of the ISP's customers has participated in illegal activity on the Internet and demanding that the ISP reveal the identity of the customer associated with a given IP address. Today, ISPs have to take such demands at face value and reveal the customer's identity. When the allegation turns out to be incorrect, this may be tragic for the customer and embarrassing for the ISP. For instance, among many recent cases, an IP address that was implicated as having downloaded copyrighted material from a BitTorrent turned out to be that of a printer . Using a packet authentication facility, an ISP can check if an allegation is well-founded. It can demand to be presented a packet trace of the offending traffic and check if matching hash values are found in the associated customer's traffic digest.
PGPA can also be used to improve existing schemes to mitigate denial of service attacks. For instance, a ``shut-up'' service was proposed, which allows a host D to ask that a particular host S who is sending traffic to D be prevented from sending any further traffic . Packet authentication can be used to validate such requests, thereby preventing abuse of the ``shut-up'' service.
From the perspective of a customer, IP packet authentication provides a defense against false accusations. We have already mentioned the case of , where an innocent user was accused of having downloaded child pornography. Packet authentication would have allowed the user's ISP to establish that the offending traffic was not sent by its customer, and thus to protect him from false accusation and slander. Even in the case of a clerical error, such as a mixed-up IP address, the user could easily have proved his innocence by agreeing to an inspection of his monitor device.
Finally, PGPA can serve as a building block for a global IP packet authentication service, which enables anyone on the Internet to verify the authenticity of any IP packet they receive. The service would enable hosts to present an arbitrary IP packet and ask if the packet is authentic. The service would determine the ISP (AS) responsible for the packet's source IP address, and query that ISP's PGPA system. The service answers with an indication of either ``authentic'' (i.e., a matching packet digest is found in the source's traffic digest), ``not authentic'' (i.e., a matching packet digest is not found), or ``unknown'' (i.e., the source AS does not provide packet authentication or the packet has expired from the source's traffic digest). The service itself can be secured from manipulation using techniques similar to those used in DNSSEC .
However, PGPA is only a first step towards more accountability on the Internet. Many issues cannot be addressed by PGPA alone. For example, consider a situation where a user's access link is shared, possibly without his knowledge or consent (perhaps through an open wireless access point). If someone who is sharing the user's access link misbehaves, the user cannot prove his innocence using PGPA. A similar situation arises when the user's machine sends illicit traffic without the user's knowledge, for example, if the machine has been infected by malware. We leave solutions for these as future work.
 D. E. Eastlake. RFC 2535: Domain name system security extensions. https://www.faqs.org/rfcs/rfc2535.html, March 1999.
 J. Gray. Distributed computing economics. Technical Report MSR-TR-2003-24, Microsoft Research, Mar 2003.
 S. Guha, P. Francis, and N. Taft. ShutUp: End-to-end containment of unwanted traffic. Technical Report https://hdl.handle.net/1813/11101, July 2008.
 Heise.de. IP-Verwechslung führt zu falschem Kinderporno-Verdacht. https://www.heise.de/newsticker/meldung/105094, 2008.
 N. Laoutaris, P. Rodriguez, and L. Massoulie. ECHOS: Edge capacity hosting overlays of nano data centers. SIGCOMM Comput. Commun. Rev., 38(1):51-54, 2008.
 M. Piatek, T. Kohno, and A. Krishnamurthy. Challenges and directions for monitoring P2P file sharing networks. In 3rd USENIX Workshop on Hot Topics in Security (HotSec '08), July 2008.
 A. Ramachandran and N. Feamster. Understanding the network-level behavior of spammers. In Proceedings of SIGCOMM'06, Sept. 2006.
 S. Savage, D. Wetherall, A. Karlin, and T. Anderson. Practical network support for IP traceback. In Proceedings of SIGCOMM'00, Aug 2000.
 A. C. Snoeren, C. Partridge, L. A. Sanchez, C. E. Jones, F. Tchakountio, B. Schwartz, S. T. Kent, and W. T. Strayer. Single-packet IP traceback. IEEE/ACM Trans. Netw., 10(6):721-734, 2002.