[for IPPT BOF] IPPT BOF C. Partridge INTERNET-DRAFT C. Jones D. Waitzman 14 November 2001 A. Snoeren BBN Technologies November 2001 New Protocols to Support Internet Traceback 1. Status of this Memo This document is an Internet-Draft and is NOT offered in accordance with Section 10 of RFC2026, and the author does not provide the IETF with any rights other than to publish as an Internet-Draft. 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/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html 2. Abstract A discussion of the protocol issues involved in developing a protocol to support packet traceback, where tracing involves querying space-efficient packet logs which are kept in various locations in the network. 3. Introduction In the past year, a space-efficient packet logging scheme using hashing and bloom filters has been developed. The scheme makes it possible to trace back single packet attacks within the recent past. This scheme does not require a change to the end hosts using IP. Partridge Expires 14 May 2001 [Page 1] Internet Draft Internet Traceback 14 November 2001 The development of such a scheme invites us to think about what protocols are needed to effectively perform the packet tracing both within and across administrative domains, how to secure the logging system against attack, and how to prevent the logging system from being used for unauthorized purposes. This Internet-Draft attempts to briefly spell out the various issues and provides a strawman set of protocol definitions as the starting point for discussion. The discussion here is primarily based on the work done in reference [SPIE]. For a slightly different view of the issues, the reader may wish to read reference [IIDS]. Readers should not that this draft explicitly is NOT a standards track document. It is written for the purpose of discussing whether the IETF should undertake to develop standards in this area. Also, BBN Technologies is deeply interested in seeing this technology made widely available, and readers are urged not to make any assumptions about BBN's willingness to license based on the limited grants of rights in the Status of Memo section above. The limited grant is done simply to defer the intellectual property issues until they can be discussed at the December 20001 IETF meeting. 4. The Source Path Isolation Engine The Source Path Isolation Engine (SPIE) is one particular implementation of a system that provides IP traceback capability on a per-packet basis. For context, we briefly describe its space efficient logging scheme here. For more details, the reader is advised to read [SPIE]. The basic idea is that every packet seen at a logging point is multiply hashed (multiple different hash keys are produced) and for each hash value, a corresponding bit is set in a bitmap. To determine if a packet has been seen at a given logging point within a specific time window, we simply take the original packet, apply the multiple hashes and confirm that all the corresponding bits are set in the bitmap. If not all the bits are set, we know (with 100% certainty) that the packet has not been seen in that time window. If all the bits are set, we know with high probability that the packet has been seen. (There's a small chance of a hash collision, so occasionally false positives occur -- the rate of false positives can be tuned). Summarizing, the scheme stores a few bits (typically about 5) per packet. Given an average packet size of 1000 to 2000 bits, this means the scheme stores only about 0.5% of the bandwidth going past Partridge Expires 14 May 2001 [Page 2] Internet Draft Internet Traceback 14 November 2001 or through a logging point. Some additional information is stored when packets undergo transformations, such as NAT conversions, IP tunneling, and IPsec, but the size of that information is small relative to the hash information. A few wrinkles in the scheme are of interest. First, the hash functions must be different at each logging point. This reduces the probability of hash collisions (false positives) across multiple routers, adjacent on the packet's path. Otherwise hash collisions at one point get propagated all along the colliding packets' path. Second, even though the amount of data stored is relatively low, if one wants to be able to trace packets several hours or days after an attack, it is probably necessary to store logs in storage facilities which are not necessarily co-located with the original logging points. The major implications are (1) that to trace a packet, you actually must have some way to (re)hash the packet for each log that is to be examined and (2) there must be some way to discover where logs are stored. Even if other space-efficient mechanisms are developed, it seems likely that some form of these two implications will hold true. SPIE achieves its space efficiency by storing information that in combination with the packet (e.g., using the packet to recreate the particular hash pattern) will reveal if a packet has passed by -- and presumably this kind of trick will be used by any other space efficient mechanism. Second, no matter how space-efficient an approach is, eventually it will generate enough data that secondary storage is desirable. 5. Architecture and Terminology A general architecture for a traceback system has the following layers: data generators, data distribution hierarchy, traceback controllers, and users requesting tracebacks. The data generators are often routers but may also be standalone tracing devices such as packet sniffers. In small systems, the data distribution hierarchy might not be necessary. The user requesting tracebacks is likely to be a intrusion detection system (IDS). An IDS queries the traceback system some time after a suspicious packet is detected. The traceback system, in turn, queries the the data generator's digest caches for the relevant time period. The query results are then used in a simulated reverse path flooding algorithm to build an attack graph that indicates the packet's source(s). Traceback results are provided by the traceback system to the initiating IDS. Partridge Expires 14 May 2001 [Page 3] Internet Draft Internet Traceback 14 November 2001 The terms that we will use for the four layers are: o data generators: Data Generation Agent (DGA) o data distribution hierarchy: Collection and Reduction Agent (CAR) o traceback controllers: Traceback Manager (TM) o users requesting tracebacks: IDS We will now show some example protocols between these layers. 6. Communication Protocol The traceback process requires a communication protocol that pro- vides for reliable, efficient, and secure collaboration among system components. Traceback and topology information is exchanged between components through the use of a message protocol. As an example, this section presents the Source Path Isolation Engine (SPIE) [SPIE] message pro- gram. The SPIE message protocol requires the use of a reliable transport protocol for message transmission. Messages are variable in length, and may be larger than the maximum size of an IP datagram. The sim- plest solution is to use TCP, because it provides reliability, large data block transmission, and is easily compatible with IETF standard security mechanisms. The protocol described here is independent of the IP version, v4 or v6. The rest of this section describes one possible protocol, defined in the traditional IETF box diagram packets fashion. An alternative approach, not discussed further, is to use the BEEP as specified in RFC-3080. All messages are transmitted in network byte order. Any SPIE message that parses incorrectly, contains inconsistent information, or fails security measures is dropped without further processing, and the connection over which the message was received may be disconnected. Communications security is further discussed below. Partridge Expires 14 May 2001 [Page 4] Internet Draft Internet Traceback 14 November 2001 6.1 Message Header A SPIE message consists of a header and a payload. Data pertinent to all payload types is contained within the header. The payload contains either a topology update, traceback request, or traceback reply. Figure 1 diagrams the message header that is common to all SPIE messages. 0 8 16 24 32 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | Message Type | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1: SPIE message header. The "Version" field indicates which protocol engine is to parse the incoming SPIE message. Only one version of the SPIE protocol is currently defined, and is represented as 0x01. The "Message Type" field identifies the payload type that follows the message header. Three message types are defined, as listed in the following table. Type Code | Message Type ===========+================ 0x01 | Mapping -----------+---------------- 0x02 | Trace Request -----------+---------------- 0x03 | Trace Reply The format of the message payload depends on the message type. Each message type is discussed in subsequent sections. There is no explicit "terminate" message -- a SPIE process can simply drop the connection when it wishes. The peer process may or may not terminate any outstanding processing when the connection which was responsible for that processing terminates. The length of a SPIE message, including the header, is provided in the "Message Length" field, and is represented in bytes. A SPIE message must contain a message header; therefore, the minimum size of a SPIE message is 8 bytes. The maximum size of a message is bounded by the size of the length field, which is approximately 4G bytes. A SPIE message is not bounded by the size of an IP datagram because a SPIE message may contain an IP datagram. The "Message Length" field allows determination of how much data a SPIE process needs to read from a TCP connection to get an entire Partridge Expires 14 May 2001 [Page 5] Internet Draft Internet Traceback 14 November 2001 SPIE protocol message. 6.2 Mapping Message A SPIE mapping message conveys topology information, and is sent in the following instances. o A CAR or DGA identifies itself to upstream components at the time of connection establishment. o A CAR identifies to upstream components the components within its coverage area at the time they become active. Mapping messages are only transmitted upstream to components higher in the system hierarchy, and used internal to the SPIE system. Therefore, a TM does not transmit mapping messages. The format of a mapping message is shown in Figure 2. 0 8 16 24 32 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sender ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Number of SPIE Components | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ SPIE Components ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2: SPIE mapping message. The "Sender ID" field contains the unique 32-bit SPIE identifier of the component that sent the message. The "Number of SPIE Compo- nents" field specifies the number of 32-bit SPIE IDs that are listed in the SPIE Components field that follows. The components identified in the "SPIE Components" field are those that are within the coverage area of the component sending the map- ping message. A DGA is responsible only for itself, and never includes any SPIE components. Mapping messages from CARs include zero or more SPIE components. 6.3 Trace Request Message The traceback process is initiated at a SPIE component with the reception of a SPIE trace request message. A trace request is sent in the following instances. Partridge Expires 14 May 2001 [Page 6] Internet Draft Internet Traceback 14 November 2001 o An IDS or other authorized entity requests a TM to perform a packet trace. o A TM or CAR requests a packet trace local to a CAR's coverage area. o A TM or CAR queries a DGA about packet membership in its digest cache. A single request message is defined for use by all components that request SPIE traceback services. Figure 3 diagrams the trace request message format. 0 8 16 24 32 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Requester ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Number of Requests | Trace Packet Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Requests ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Trace Packet ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3: SPIE trace request message. The "Requester ID" field contains the unique 32-bit SPIE identifier of the component requesting the packet trace, and a 32-bit message identifier is contained within the "Message ID" field. Together, the requester ID and message ID uniquely identifies the trace request during its lifetime. The number of requests included in the "Requests" field of a trace request message is specified in the "Number of Requests" field. Trace request messages originating from an IDS or other external entity must contain one, and only one, request; whereas SPIE compo- nents are allowed to include one or more requests within a single message. Requests are detailed in section 5.3.1. All the requests contained in a trace request message pertain to the single trace packet included at the end of the message. The "Trace Packet Length" field specifies the length of the packet in bytes. Partridge Expires 14 May 2001 [Page 7] Internet Draft Internet Traceback 14 November 2001 The trace packet must consist of at least one byte and not exceed the size of an IP datagram. 6.3.1 Request A request identifies an initial DGA and time interval from which to begin the traceback process. Figure 4 shows the format of a request. 0 8 16 24 32 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Earliest Time + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Latest Time + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DGA ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 4: Request of a SPIE trace request message. The "DGA ID" field contains the unique 32-bit SPIE identifier of the DGA at which to begin the packet trace. A time interval during which the packet is thought to have traversed the DGA is provided by the "Earliest Time" and "Latest Time" fields. SPIE timestamps are represented as the number of seconds since mid- night of January 1, 1970 GMT and the number of microseconds in this second. The timestamp fields of the request message are function- ally equivalent to a 64-bit timeval structure in which the first 32 bits represent seconds and the second 32 bits represent microsec- onds. If no time bound is provided for the "Earliest Time" field, all bits of the field are set to 0. All bits of the "Latest Time" field are set to 1 if a time bound is not specified. 6.4 Trace Reply Message A SPIE trace reply message provides traceback results, and is sent only in response to a specific trace request. One or more reply messages may be sent for a single request. Figure 5 diagrams the Partridge Expires 14 May 2001 [Page 8] Internet Draft Internet Traceback 14 November 2001 trace reply message. 0 8 16 24 32 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Requester ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Message ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Reply Type | Reserved | Num Replies | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Replies ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 5: SPIE trace reply message. The "Requester ID" and "Message ID" fields are copied from the cor- responding fields of the request message to which the reply is in response. The type of reply message is identified in the "Reply Type" field. Three reply types are defined as listed in the follow- ing table. Type Code | Reply Type ===========+============== 0x01 | Event -----------+-------------- 0x02 | Transform -----------+-------------- 0x03 | Source Reply The number of replies, of the type specified, included in the "Replies" field is provided in the "Num Replies" field. A reply message must contain at least one reply, and a transform reply message may not contain more then one reply. Event or source reply type messages may include more then one reply. 6.4.1 Event Reply SPIE components report error and status events during the traceback process through the event reply message. Figure 6 shows the format of an event reply. Partridge Expires 14 May 2001 [Page 9] Internet Draft Internet Traceback 14 November 2001 0 8 16 24 32 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Event Type | Reserved | Data Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Data ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 6: Event reply field of a SPIE trace reply message. The "Event Type" field specifies the type of event being reported. An enumerated set of events are defined in the table below. (NOTE: We have not defined the event types yet.) Event Code | Event ============+=============================== 0x01 | End of Reply The amount of data, in bytes, included in the "Data" field of the event message is specified within the "Data Length" field. Zero to approximately 64K bytes of data may be included in the message in multiples of four bytes. The data to be included is dependent on the type of event being reported. 6.4.2 Source Reply A source reply reports the results of a successful query of a DGA's digest cache for packet membership. Figure 7 depicts the source reply field of the SPIE trace reply message. 0 8 16 24 32 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Num Entries | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Trace Entries ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 7: Source reply field of a SPIE trace reply message. The "Source ID" field contains the unique 32-bit SPIE identifier of the DGA for which the results are being reported. The "Num Entries" field specifies the number of trace entries Partridge Expires 14 May 2001 [Page 10] Internet Draft Internet Traceback 14 November 2001 included in the source reply. At least one trace entry must be pro- vided. The contents of a trace entry are defined in the following section. 6.4.3 Trace Entry A trace entry specifies a time interval during which a packet was determined to have traversed the DGA identified by the "Source ID" field of the source reply. Figure 8 shows the format of a trace entry. The "Start Time" and "End Time" fields define the time interval dur- ing which the traced packet traversed the DGA specified in the source reply. Both fields contain SPIE timestamps that have been described in section 5.3.1. If no time is provided for the "Start Time" field, all bits of the field are set to "0". The bits of the "End Time" field are set to "1" if no time is provided. 0 8 16 24 32 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Start Time + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + End Time + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Num Neighbors | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Neighbors ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 8: Trace entry field of a SPIE source reply message. The trace entry also provides a list of neighboring DGAs to which the DGA identified in the source reply maintained active connections during the time interval specified. The "Num Neighbors" field spec- ifies the number of neighbors listed in the "Neighbors" field. At least one neighbor must be identified. A neighbor is represented by its unique 32-bit SPIE identifier. 6.4.4 Transform Reply Partridge Expires 14 May 2001 [Page 11] Internet Draft Internet Traceback 14 November 2001 A transform reply reports the traceback results of a packet that was determined to have undergone transformation. Figure 9 diagrams a transform reply. 0 8 16 24 32 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Num Sources | Transform Packet Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Source Replies ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Transform Packet ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 9: Transform reply field of a SPIE trace reply message. The inverted trace packet is included at the end of the transform reply . The "Transform Packet Length" field specifies the length of the packet in bytes. The transform packet must include at least one byte, and must not exceed the size of an IP datagram. The "Source Replies" field contains a list of one or more source replies, as defined in the previous section. The "Num Sources" field specifies the number of source replies included in the trans- form reply. The source replies identify the DGAs through which the inverted packet was determined to have traversed. The first source reply listed is the DGA at which the packet actually underwent transformation. 7. Management Development of a MIB that provides counters for various SPIE state transitions, such as counting traceback requests, etc., is straight- forward. A table providing information about the currently open downstream connections is also straightforward. It is probably unwise to make the log data or outstanding traceback request infor- mation available via a MIB, as that data are very sensitive. Nor it is recommended to make any control features available via a MIB. Further MIB development is To Be Done. 8. Security Considerations Secure communications is essential within SPIE. Two principles gov- ern how communication is conducted: Partridge Expires 14 May 2001 [Page 12] Internet Draft Internet Traceback 14 November 2001 1. All SPIE communication is authenticated. 2. Data is kept confidential. Authenticating SPIE messages prevents unauthorized entities from using the SPIE system to produce unnecessary traffic that overloads network resources, possibly effecting or enabling denial of service attacks. The insertion of malicious data into the query process by an attacker is also prevented by message authentication. Data con- fidentiality is required in preventing attackers from monitoring the SPIE system to determine the effectiveness of their attacks or from gaining information on other suspected attacks. 8.1 Authentication and Authorization All SPIE communication between the STM, SCARs, and DGAs must be authenticated. Also, authentication and authorization of communica- tion between the STM and any entity requesting a packet trace MAY be required. This authentication can be provided through a number of mechansims. The remainder of this subsection, however, will describe the use of a public key infrastructure (PKI) such as that proposed in [S-BGP] as an example of how to satisfy the require- ments. 8.1.1 IDS Authorization SPIE operators MAY require that an IDS obtain proper authorization to issue queries. This authority MAY be verified through a set of X.509 certificates [X.509]. One such certificate binds the public key of the querying IDS to a set of destination IP addresses that the IDS may issue queries for. The certificate MUST be issued by a CA that is approved by the STM and authorized to issue certificates to IDSs for use with this STM. This can be verified in a number of ways, possibly through a chain of certificates rooted the entity administering the STM. This authority certificate, in combination with an address attesta- tion [X-Auth], verifies the IDS's authority to issue a query for a particular packet. Specifically, the packet MUST be destined for an address range contained within the authorized address block, as ver- ified by the address attestation. An address attestation binds a public key to a certain set of IP addresses, and verifies ownership of that address space. These attestations can be issued in a hier- archy that parallels the current IP allocation system, rooted at ICANN [S-BGP]. Traceback requests for a packet destined to an IP address outside the range(s) specified in the certificate MUST NOT be processed by the STM. Partridge Expires 14 May 2001 [Page 13] Internet Draft Internet Traceback 14 November 2001 8.1.2 Node Authentication Each node in a SPIE system (including STMs, SCARs, DGAs) MUST be mutually authenticated. This MAY be facilitated through the use of public key cryptography, in particular through an X.509-based PKI. Since all nodes within a single SPIE system are likely to be admin- istered by the same entity, however, key distribution is likely to be quite lightweight. >From the point of view of an IDS, the STM speaks for the entire SPIE system. Hence, each STM MUST be configured with a public/pri- vate key pair that it uses to sign all correspondence with IDSs. Further, this key MUST be bound to the entity responsible for the SPIE system through a certificate issued by a CA that is mutually agreeable to the SPIE system and the querying IDS. SCARs MUST be configured with the identity and public key(s) of their responsible STM or key(s) for a responsible CA. Further, they should also have access to the public keys of all parties responsi- ble for DGAs/routers in their region of the network. 8.1.3 DGA Authentication As with other nodes in the SPIE system, DGAs MUST be configured with the identity and public key of their responsible SCAR. Alterna- tively, they may be configured with keys for CAs responsible for the relevant SCAR. Unlike SCARs and STMs, however, DGAs may on occasion be owned or operated by an entity other than that operating the STM, such as an end customer. Hence, in addition to the internal SPIE authorization between the DGA and its SCAR(s), the authority of the DGA to report on traffic for any particular routers MAY be verified through a certificate binding the DGA's public key to the router's ID [S-BGP]. This cer- tificate MAY be verified in a separate name space [X.509] than cer- tificates internal to the SPIE system, and have a correspondingly distinct trust anchor. In such a case, the answers provided by an external DGA MAY be tagged, and the attack graph annotated appropri- ately when returned to the querying IDS. 8.2 Denial of Service Authentication addresses the primary worry about denial of service, as long as the authentication method can prevent replay attacks. Additional worries about denial of service can be too many traceback requests being sent to an STM in a limited period of time. STMs MAY apply admission control to any traceback requests submitted Partridge Expires 14 May 2001 [Page 14] Internet Draft Internet Traceback 14 November 2001 by an IDS. The STM MAY elect to ignore requests from a particular source or all sources for some time period. The policy applied to a query MAY vary depending on the IDS submitting the query, and MUST NOT violate the terms of the IDS's authority certificate, if pre- sent. Admissions decisions MAY be based on, but are not limited to, such factors as recent IDS request history, current system load, and packet source/destination. 8.2.1 Traffic Isolation Traceback operations will often be requested when the network is unstable (likely due to the attack that triggered the traceback); traceback communications must succeed in a timely fashion even in the face of network congestion and instability. If traceback traf- fic is not properly insulated from normal network traffic, the traceback system may be unable to complete a traceback during peri- ods of network congestion or routing failures. Traceback traffic SHOULD be isolated from standard traffic. The best solution is to provide the traceback with an out-of-band channel, possibly through either physically or logically separate (e.g. ATM VCs) links. Even without private channels, it is still possible to ensure successful transmission by granting sufficient priority and configuring static routes for traceback traffic. 8.2.2 Transformation Overload Assuming that packet transformations represent a small percentage of the overall IP traffic traversing a router, an efficient traceback implementation can easily handle the resource requirements of log- ging transformation information. Attackers, though, may view packet transformations as a method of denial of service attack. The number of transformations that are recorded during a given time interval is bounded by the rate at which the router is able to process the packet transformations. Therefore, a DGA should aim to handle packet transformations at a rate equal or greater than the associated router. As a result, the router, rather than the DGA, is the bot- tleneck in processing packet transformations. This task is made easier by the fact that the vast majority of transformations occur only at low-to-medium speed routers. Sophisticated transformations such as tunneling, NATing, and the like are typically done at cus- tomer premises equipment. Further, many ISPs turn off standard transformation handing, often even ICMP processing, at their core routers. 8.3 Confidentiality Conducting a packet traceback likely indicates a level of increased interest by the querying party. Information about the packet being Partridge Expires 14 May 2001 [Page 15] Internet Draft Internet Traceback 14 November 2001 traced, or the results of that trace, may be confidential, and potentially useful to eavesdroppers in launching related attacks. 8.3.1 Message Confidentiality Hence, it is essential that the traceback system keep the contents of packets submitted for traceback confidential, and, further, not disclose the results of the trace to anyone other than the requester. The necessary level of confidentiality can be achieved using IPsec or TLS between all components. Traceback messages that contain confidential information MUST be encrypted. In general, this includes trace queries that contain any packet or path informa- tion or trace replies that contain attack graph information. 8.3.2 Result Obfuscation After obtaining the results of a traceback query, a traceback system MAY obscure internal topology by removing internal components of the attack graph. Nodes of the attack graph that are currently candi- date sources (such as hosts, border routers, nodes external to the traceback enabled network, or nodes otherwise determined to have possibly injected the node into the network) MUST NOT be omitted. If internal nodes are removed from the graph, adjacency information MUST be preserved in order to allow the correct interpretation of the attack graph. In general, modifications to the attack graph that do not affect the correctness or accuracy MAY be made in order to conceal the internal topology of a provider's network, but this practice is discouraged. 8.4 Known Vulnerabilities A traceback system based upon binary packet observance records (a DGA records the presence or absence of any particular packet) is designed to trace any distinct IP packet to its source(s), and typi- cally does not concern itself with the multiplicity of any particu- lar packet. It is possible to exploit this fact to launch an ``amplification'' denial-of-service attack that the traceback system alone is not able to isolate. Specifically, a router or host cannot surreptitiously insert a new, distinct packet into a traceback- enabled network. It may, however, duplicate packets already in the network without detection, effectively amplifying the size of a traffic flow. In particular, a router R on the path between two hosts A and B may duplicate all packets going from A to B in an attempt to overwhelm downstream resources, including any routers and network links on the path from R to B, and even B itself. The usefulness of such an attack is limited by the requirement R lie Partridge Expires 14 May 2001 [Page 16] Internet Draft Internet Traceback 14 November 2001 on the path between A and B. Furthermore, duplicate packets are only undetectable if they fall within the same digest table page. Duplicate packets inserted significantly after the original packet will likely fall into a later digest table page on some downstream router, and therefore be detected as a distinct, later packet. Sim- ilarly, large numbers of duplicate packets would become apparent even to extremely simplistic network monitoring tools. Hence, an attacker likely can only increase the size of an individual flow by a small factor. A naive attacker might attempt to increase the attack's effective- ness by amplifying a large number of flows destined to the same des- tination. This serves only to help isolate the attacker's location, however. If packets from several of the amplified flows are traced using SPIE, and their attack paths compared, the attacker must lie on the shared portion of the paths. As the number of flows ampli- fied by the attacker grows, the portion of the path shared by all attack paths will converge to the path between the attacker and the destination, effectively identifying the rogue source R. 9. Intellectual Property Some of the concepts and ideas discussed in this draft are the sub- ject of pending patent applications by BBN Technologies. 10. Acknowledgements To avoid a huge author list, this ID lists only the parties who con- tributed large portions of text to this document. However, a number of people have contributed to the thinking this document reflects. These people include: Steve Kent, Doug Maughan, Luis Sanchez, Bev Schwartz, Tim Strayer and Fabrice Tchakountio. Any dumb statements herein are purely the fault of Craig Partridge. 11. References [IIDR] Schnackenberg D., Djahandari, K., and Stern, D., "Infrastructure for Intrusion Detection and Response", Proc. IEEE DISCEX 2000, Jan 2000, Hilton Head, South Carolina, USA. [S-BGP] Lynn, C., Mikkelson J., and Seo, K. "Secure BGP (S-BGP)", Internet-Draft, draft-clynn-s-bgp-protocol-00.txt, October 1999. (expired) Partridge Expires 14 May 2001 [Page 17] Internet Draft Internet Traceback 14 November 2001 [SPIE] Snoeren, A., Partridge, C., Sanchez, L., Jones, C., Tchakountio, F., Kent S., and Strayer, W., "Hash-Based IP Traceback," SIGCOMM 01, August 27-31, 2001, San Diego, California, USA. [X-Auth] Lynn, C., "X.509 Extensions for Authorization of IP Addresses, AS Numbers, and Routers within an AS", Internet-Draft, draft-clynn-bgp-x509-auth-01.txt. October 1999. (expired) [X.509] ITU-T Recommendation X.509 (1997 E): "Internet X.509 Public Key Infrastructure Technology - Open Systems Interconnection - The Directory: Authentication Framework", June 1997. 12. Authors' Addresses Craig Partridge, Christine Jones, David Waitzman, Alex Snoeren BBN Technologies 10 Moulton St Cambridge MA 02138 USA EMail: {craig,cej,djw,snoeren} at bbn.com Partridge Expires 14 May 2001 [Page 18]