Steve Bellovin
   Internet Draft                                    AT&T Labs Research
   Document: draft-ietf-itrace-02.txt                      Marcus Leech
                                                             Tom Taylor
                                                        Nortel Networks
   Expires: April 2002                                     October 2001


                          ICMP Traceback Messages


tatus of this Memo

   This document is an Internet-Draft and is subject to all provisions
   of Section 10 of RFC2026.

   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.


bstract

   It is often useful to learn the path that packets take through the
   Internet, especially when dealing with certain denial-of-service
   attacks.  We propose a new ICMP [RFC792] message, emitted randomly
   by routers along the path and sent randomly to the destination (to
   provide useful information to the attacked party) or to the origin
   (to provide information to decipher reflector attacks).















   Bellovin et al     Standards Track - Expires April 2002           1
                       ICMP Traceback Messages          November 2002

able of Contents

   Status of this Memo............................................1
   Abstract.......................................................1
   Table of Contents..............................................2
   1. Introduction................................................3
      1.1 Requirements Keywords...................................3
      1.2 Definitions.............................................3
   2. Message Definition..........................................4
      2.1 Conventions For Presentation............................4
      2.2 Overall Message Format..................................4
      2.3 Forward and Backward Link Elements......................5
         2.3.1 Back Link (TAG=0x01)...............................6
         2.3.2 Forward link (TAG=0x02)............................7
         2.3.3 Interface Identifier (TAG=0x03)....................7
         2.3.4 IPV4 address pair (TAG=0x04).......................7
         2.3.5 IPV6 address pair (TAG=0x05).......................7
         2.3.6 MAC address pair (TAG=0x06)........................8
         2.3.7 Operator-defined link identifier (TAG=0x07)........8
         2.4 Timestamp (TAG=0x08).................................9
      2.5 Traced packet (TAG=0x09)................................9
      2.6 Probability (TAG=0x0A)..................................9
      2.7 RouterId (TAG=0x0B).....................................9
      2.8 Authentication data....................................10
         2.8.1 HMAC Authentication data (TAG=0x0C)...............10
         2.8.2 Key Disclosure List (TAG=0x0D)....................11
         2.8.3 Key Disclosure (TAG=0x0E).........................11
         2.8.4 Public-key Information (TAG=0x0F).................13
   3. Procedures.................................................13
      3.1 Generation Of Traceback Messages.......................13
         3.1.1 Implementation Requirements -- Message Generation.14
         3.1.2 Implementation Requirements -- Message Reception..14
      3.2 Configuration..........................................14
      3.3 Processing Of Received Messages........................14
   4. Related Work...............................................15
   5. Security Considerations....................................15
   6. Acknowledgements...........................................16
   7. References.................................................16
   8. Author Information.........................................17















   Bellovin         Standards Track - Expires April 2002             2

                       ICMP Traceback Messages          November 2002

. Introduction

   It is often useful to learn the path that packets take through the
   Internet.  This is especially important for dealing with certain
   denial-of-service attacks, where the source IP is forged.  There are
   other uses as well, including path characterization and detection of
   asymmetric routes.  There are existing tools, such as traceroute,
   but these generally provide the forward path, not the reverse.

   We propose an ICMP Traceback message to help solve this problem.
   When forwarding packets, routers can, with a low probability,
   generate a Traceback message that is sent along to the destination.
   With enough Traceback messages from enough routers along the path,
   the traffic source and path can be determined.


.1 Requirements Keywords

   The keywords "MUST", "MUST NOT", "REQUIRED", "SHOULD", "SHOULD NOT",
   and "MAY" that appear in this document are to be interpreted as
   described in [RFC2119].


.2 Definitions

   Element: a component of the proposed message which is explicitly
   identified by a tag, and is encoded using a Tag-Length-Value (TLV)
   format.  Some elements will contain other elements as described
   below.

   Field: a component of the proposed message which is identified
   through its relative position within the header or within a
   particular element.

   Generator: the router which itself generates the ICMP Traceback
   message or on behalf of which this message is generated by some
   other entity.

   Link: a logical connection between the Generator and another entity,
   along which the traced packet has passed.

   Peer: the entity at the other end of the link, which either sent the
   traced packet to the Generator or received it from the Generator.
   [Will this always be a router, or will edge routers trace packets
   received from or sent to hosts?]

   Traced Packet: the packet which is the subject of an ICMP TRACEBACK
   message.






   Bellovin         Standards Track - Expires April 2002             3

                       ICMP Traceback Messages          November 2002

. Message Definition

.1 Conventions For Presentation

   As indicated below, aside from the initial octet, the elements of
   the ICMP TRACEBACK message are concatenated without any padding to
   create word boundary alignment.  The fields within each element are
   similarly concatenated without intervening padding.  The diagrams
   presenting the individual elements therefore show the length and
   relative order of the fields making them up, but do NOT indicate
   alignment on any specific boundary.  Each field beyond the initial
   tag and length is shown beginning on a separate line, although in
   fact fields are contiguous in the actual message.

.2 Overall Message Format

   The proposed message is carried in an ICMP packet, with ICMP TYPE of
   TRACEBACK.  (The numeric values for this field will be assigned by
   IANA.  For IPv6, the TRACEBACK should be classified as
   Informational.)  The CODE field MUST always be set to 0 (no code),
   and MUST be ignored by the receiver.

   Traceback Message

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Type      |     Code=0    |          Checksum             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                             Message body                      |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ .....-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   The body of any ICMP TRACEBACK message consists of a series of
   individual elements that are self-identifying, using a TAG-LENGTH-
   VALUE scheme as follows:

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     TAG       |     LENGTH                    |   VALUE...    .
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   This structure is recursive, in that for certain element types the
   VALUE field will contain one or more components which are also in
   TAG-LENGTH-VALUE (TLV) format.  Top-level elements may appear in any
   order, and a receiver MUST be capable of processing them in any
   order.  Elements contained within the VALUE field of a parent
   element may also appear in any order within that field and present a
   similar requirement to the receiver.  Elements are placed
   consecutively within the message body without intervening padding;
   hence elements in general are not aligned to word boundaries.





   Bellovin         Standards Track - Expires April 2002             4

                       ICMP Traceback Messages          November 2002

   The TAG field is a single octet, with values as follows:
        Tag     Element Name                            Notes

        0x01    Back Link
        0x02    Forward Link
        0x03    Interface Name                          1
        0x04    IPv4 Address Pair                       1,2
        0x05    IPv6 Address Pair                       1,2
        0x06    MAC Address Pair                        1,3
        0x07    Operator-Defined Link Identifier        1,3
        0x08    Timestamp
        0x09    Traced Packet Contents
        0x0A    Probability
        0x0B    RouterId
        0x0C    HMAC Authentication Data
        0x0D    Key Disclosure List                     4
        0x0E    Key Disclosure                          4
        0x0F    Public-Key Information                  4

        Note 1: this item is a sub-element within Back or Forward Link
        elements.

        Note 2: at least one of these elements MUST be present within a
        Link element.

        Note 3: either the MAC Address Pair or the Operator-Defined
        Link Identifier element but not both MUST be present within a
        Link element.

        Note 4: the Key Disclosure List MUST contain one or more Key
        Disclosure elements and exactly one Public-Key Information
        element.

   LENGTH is always set to the length of the VALUE field in octets, and
   always occupies two octets, even when the length of the VALUE field
   is less than 256 octets.


.3 Forward and Backward Link Elements

   An ICMP TRACEBACK message MUST contain one Forward Link element or
   one Back Link element; it MAY contain one instance of each.  A Link
   element specifies a link along which the traced packet travelled to
   or from the Generator.  The purpose of the Forward and Back Link
   elements is to permit easy construction of a chain of Traceback
   messages.  They are further designed for examination by network
   operations personnel, and thus contain human-useful information such
   as interface names.

   The Value field of a link element consists of three components:




   Bellovin         Standards Track - Expires April 2002             5

                       ICMP Traceback Messages          November 2002

        * the interface name at the Generator only. (It is assumed
           that the Generator does not know its neighbors' interface
           names.)  This is encoded in an Interface Name element.

        * the source and destination IP addresses of the Generator and
           its peer.   These are encoded in an IPv4 or IPv6 Address
           Pair element.

        * the link-level association string.  The association string
           is an opaque blob which is used to tie together Traceback
           messages emitted by adjacent routers.  Thus all Link
           elements referring to the same link MUST use the same value
           for the association string, regardless of which entity
           generates them.

           On LANs, the association string is constructed by
           concatenating the source and destination MAC addresses of
           the two interfaces to the link, and is encoded in a MAC
           Address Pair element.  If there are no such addresses (say,
           for a point-to-point link), a suitable string MUST be
           provisioned in both routers; this is encoded in an Operator-
           Defined Link Identifier element.

   The fields of the Address Pair elements are always arranged in
   "forward order" from the point of view of the traced packet.  That
   is, the "destination" field is always the address of the entity
   closer to the ultimate recipient of the traceback packet.  Thus, in
   Back Link elements, the generator's own address is placed in the
   destination field of the IP and MAC Address Pair subelements; in
   Forward Link elements, the generator's address is placed in the
   source field.


 2.3.1 Back Link (TAG=0x01)

   The Back Link element provides identifying information, from the
   perspective of the Generator, about the link that the traced packet
   arrived from.  The VALUE field of this element consists of three TLV
   subelements, one each for the Interface Identifier, the IP Address
   Pair, and the association string.  Element lengths shown include the
   tag and length fields.  Elements may appear in a different order
   from that shown.

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x01   |     LENGTH (variable)         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |              INTERFACE IDENTIFIER (variable length)           .
   +          IPV4 or IPV6 ADDRESS PAIR (11 or 35 octets)          +
   .       MAC ADDRESS PAIR (15 octets) or OPERATOR-DEFINED LINK   .
   +       IDENTIFIER (variable length)                            +
   .                                     ...                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Bellovin         Standards Track - Expires April 2002             6

                       ICMP Traceback Messages          November 2002


 2.3.2 Forward link (TAG=0x02)

   The Forward Link element provides identifying information, from the
   perspective of the Generator, about the link that the traced packet
   was forwarded on.  Its structure is the same as that of the Back
   Link element.

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x02   |     LENGTH (variable)         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |              INTERFACE IDENTIFIER (variable length)           .
   +          IPV4 or IPV6 ADDRESS PAIR (11 or 35 octets)          +
   .       MAC ADDRESS PAIR (15 octets) or OPERATOR-DEFINED LINK   .
   +       IDENTIFIER (variable length)                            +
   .                                     ...                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


 2.3.3 Interface Identifier (TAG=0x03)

   This element contains the name of the interface to the link at the
   generating router.  The length is variable.  The VALUE field
   typically contains a human-readable character string.

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x03   |     LENGTH (variable)         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |              INTERFACE NAME (variable length)                 .
   +                           ...                                 +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


 2.3.4 IPV4 address pair (TAG=0x04)

   This element contains two 4-octet IPV4 addresses of the ends of the
   corresponding link; hence the LENGTH field is always 0x0008.  As
   noted above, the addresses MUST always be presented in the order of
   their traversal by the traced packet.

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x04   |     LENGTH=0x0008             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   UPSTREAM ADDRESS (4 octets)                 |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                 DOWNSTREAM ADDRESS (4 octets)                 |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+






   Bellovin         Standards Track - Expires April 2002             7

                       ICMP Traceback Messages          November 2002

 2.3.5 IPV6 address pair (TAG=0x05)

   This element contains two 16-octet IPV6 addresses of the ends of the
   corresponding link; hence the LENGTH field is always 0x0020.  As
   noted above, the addresses MUST always be presented in the order of
   their traversal by the traced packet.

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x05   |     LENGTH=0x0020             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   UPSTREAM ADDRESS (16 octets)                .
   +                           ...                                 +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                 DOWNSTREAM ADDRESS (16 octets)                .
   +                           ...                                 +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


 2.3.6 MAC address pair (TAG=0x06)

   This element contains two 6-octet IEEE MAC addresses of the ends of
   the corresponding link; hence the LENGTH field is always 0x000C.  As
   noted above, the addresses MUST always be presented in the order of
   their traversal by the traced packet.

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x06   |     LENGTH=0x000C             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   UPSTREAM ADDRESS (6 octets)                 .
   +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   .                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   .                 DOWNSTREAM ADDRESS  (6 octets)                .
   +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   .                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


 2.3.7 Operator-defined link identifier (TAG=0x07)

   The value of this element is an opaque field of varying length.  If
   the peer also emits ICMP TRACEBACK messages for the same link, it
   MUST use the same value.  Further definition will emerge in a later
   document.








   Bellovin         Standards Track - Expires April 2002             8

                       ICMP Traceback Messages          November 2002

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x07   |     LENGTH (variable)         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                LINK IDENTIFIER (variable length)              .
   +                           ...                                 +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


.4 Timestamp (TAG=0x08)

   This element contains the time, in NTP timestamp format [RFC1305],
   at which the traced packet arrived at the Generator.  This element
   MUST be present at the top level within the TRACEBACK message.

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x04   |     LENGTH=0x0008             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    INTEGER PART  (4 octets)                                   .
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   .    FRACTION PART  (4 octets)                                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


.5 Traced packet (TAG=0x09)

   This element provides the contents of the traced packet, as much as
   can reasonably fit, subject to link and router resource constraints.
   This element MUST be present at the top level within the TRACEBACK
   message, and MUST contain at least the IP header and the first 64
   bits of the body of the traced packet.

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x09   |     LENGTH (variable)         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   .           Complete Packet Header (>=24 octets)                .
   .                Packet body   (>= 8 octets)                    .
   .                          ...                                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


.6 Probability (TAG=0x0A)

   This element contains the inverse of the probability used to select
   the traced packet. It appears as an unsigned integer, of one, two,
   or four octets.  This element SHOULD be present at the top level
   within the TRACEBACK message.

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x0A   |     LENGTH=0x0001/2/4         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   VALUE (1, 2,.or 4 octets)   .                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Bellovin         Standards Track - Expires April 2002             9

                       ICMP Traceback Messages          November 2002



.7 RouterId (TAG=0x0B)

   This element contains opaque identifying information, useful to the
   organization that operates the router emitting the ITRACE message.
   This element MUST be present at the top level within the TRACEBACK
   message.

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x0B   |     LENGTH (variable)         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |              ROUTER IDENTIFIER (variable length)              .
   +                           ...                                 +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


.8 Authentication data

   An attacker may try to generate fake Traceback messages, primarily
   to conceal the source of the real attack traffic, but also to act as
   another form of attack.  We thus need authentication techniques that
   are robust but quite cheap to verify.

   The ideal form of authentication would be a digital signature.  It
   is unlikely, though, that routers will be able to afford such
   signatures on all Traceback packets.  Thus, although we leave hooks
   for such a variant, we do not further define it at this time.

   What is provided instead is a hash code (the HMAC Authentication
   Data element), supported by signed disclosure of the keys most
   recently used (the Key Disclosure and Public Key Information
   elements).  The current key MUST NOT be included in this disclosure.


 2.8.1 HMAC Authentication data (TAG=0x0C)

   This element MUST be present.  It contains four subfields:

        * algorithm, one(?) octet: HMAC-MD5-128, HMAC-MD5-96, HMAC-
           SHA1-160, HMAC-SHA1-96, ...  Codepoints are under
           investigation.  One candidate is the set of 16-bit
           Authenticatication Algorithm codepoints maintained by IANA
           within the ISAKMP codepoint set.  See
           http://www.iana.org/assignments/isakmp-registry.

        * keyid: eight octet key identifier

        * timestamp of the time at which the hash was taken, NTP
           format (eight octets)



   Bellovin         Standards Track - Expires April 2002            10

                       ICMP Traceback Messages          November 2002

        * MAC data: variable

           The MAC data field covers the entire IP datagram, including
           header information.  Where header information is mutable
           during transport, such information is set to zero (0x00) for
           purposes of calculating the HMAC. This field is as long as
           is appropriate for the given MAC algorithm.

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x0C   |     LENGTH (variable)         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | HMAC ALG (1?) |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               .
   +                   KEY IDENTIFIER (8 octets)                   +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               .
   +                   TIMESTAMP (8 octets)                        +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   MAC DATA (algorithm dependent)              .
   +                                                               +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


 2.8.2 Key Disclosure List (TAG=0x0D)

   A packet SHOULD contain a list of recently-used keys for hash
   algorithms.  This is provided in the Key Disclosure List element.
   This element MUST contain at least one Key Disclosure subelement,
   and MUST also contain a Public Key Information subelement pointing
   to the keys used to sign the Key Disclosures.  In accordance with
   the general rule for construction of the TRACEBACK message, the
   subelements may be presented in any order and the receiver MUST be
   able to process them regardless of the order in which they are
   presented.

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x0D   |     LENGTH (variable)         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               .
   +          KEY DISCLOSURE(s) and PUBLIC KEY INFORMATION         +
   .                            ...                                |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


 2.8.3 Key Disclosure (TAG=0x0E)

   The primary content of the Key Disclosure element consists of a key
   used to authenticate previous TRACEBACK messages and the starting
   and ending times between which that key was used.  The algorithm is

   Bellovin         Standards Track - Expires April 2002            11

                       ICMP Traceback Messages          November 2002

   assumed to be the same as that used to authenticate the current
   message (and shown in the HMAC Authentication Data element).  The
   element MUST also contain a digital signature covering the Key
   Disclosure element.

   The structure of the Key Disclosure element is as follows:

        * keyid for the key being disclosed: eight octets

        * validity:  two NTP timestamps giving validity period (start,
          end)

        * key length: one octet

        * key material: variable [key length] octets

          Keying material for the chosen HMAC function MUST conform to
          the requirements for keys outlined in [RFC2104].

        * public key signature algorithm identifier, one(?) octet:
          PKCS1-RSA-MD5, PKCS1-RSA-SHA1, DSS-SHA1, X9.62-ECDSA-SHA1 ...
          See [RFC2459] section 7 and [PKALGS] (which will supersede
          that section when finished) for more information on signature
          algorithms.  Codepoints are under investigation.

        * signature length: two octets.  Unsigned integer number of
          octets of signature

        * signature: variable [siglength] octets.

          The signature covers the entire key disclosure element, less
          the signature field itself.






















   Bellovin         Standards Track - Expires April 2002            12

                       ICMP Traceback Messages          November 2002

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x0E   |     LENGTH (variable)         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               .
   +                   KEY IDENTIFIER (8 octets)                   +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               .
   +                   START TIME (8 octets)                       +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               .
   +                     END TIME (8 octets)                       +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | KEY LEN (1)   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   KEY MATERIAL (KEY LEN octets)               .
   +                           ...                                 +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | SIG ALG (1?)  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | SIGNATURE LENGTH (2 octets)   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   SIGNATURE (SIG LEN octets)                  .
   +                           ...                                 +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


 2.8.4 Public-key Information (TAG=0x0F)

   Digital signatures are useless without some way of authenticating
   the public key of the signer.  The ideal form of authentication
   would be a certificate-based scheme rooted in the address
   registries.  That is, the registries are the authoritative source of
   information on who owns which addresses; they are thus the only
   party that can easily issue such certificates.

   Until such a PKI is in existence, we suggest that each ISP publish
   its own root public key.  Current registry-based databases can be
   used to verify the owner of an address block; this information can
   in turn be used to locate the appropriate root key.

   The public-key information element can be used to discover the
   appropriate public keys, and other related information.
   This element contains a URL, pointing to an XML page that contains
   the public key used to sign key-disclosure elements.





   Bellovin         Standards Track - Expires April 2002            13

                       ICMP Traceback Messages          November 2002


   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    TAG=0x0F   |     LENGTH (variable)         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               .
   +                   URL (variable)                              +
   .                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+





. Procedures

.1 Generation Of Traceback Messages

   A router implementing this scheme SHOULD generate and emit an ICMP
   Traceback packet with probability of about 1/20,000, although local
   site policy MAY adjust this to better suit local link utilization
   metrics.  It MUST then randomly select with equal probability to
   send this packet to the origin or the destination of the sampled
   packet.

   Some requirements are imposed on the IP header of the Traceback
   message.  In particular, the source address SHOULD be that
   associated with the interface on which the packet arrived.  If that
   interface has multiple addresses, the address chosen SHOULD, if
   possible, be the one by which this router is known to the previous
   hop.  If the interface has no IP address, the "primary" IP address
   associated with the router MAY be used.  ("Primary" is discussed
   below.)

   The initial TTL field MUST be set to 255.  If the Traceback packet
   follows the same path as the data packets, this provides an
   unambiguous indication of the distance from this router to the
   destination.  More importantly, by comparing the distances with the
   link elements, a chain can be constructed and partially verified
   even without examining the authentication fields.


.1.1 Implementation Requirements -- Message Generation

   The probability of Traceback generation SHOULD be adjustable by the
   operator of the router.  A default value of about 1/20000 is
   suggested.  If the average maximum diameter of the Internet is 20
   hops, that translates to a net increase in traffic at the
   destination of about .1%; this should not be an undue burden on the
   recipient.  The probability SHOULD NOT be greater than 1/1000.

   Packet selection SHOULD be based on a pseudo-random number, rather
   than a simple counter.  This will help block attempts to time attack


   Bellovin         Standards Track - Expires April 2002            14

                       ICMP Traceback Messages          November 2002

   bursts.  There does not appear to be any requirement for
   cryptographically strong pseudo-random numbers.

   A suggested scheme involves examination of the low-order bits of a
   linear congruential pseudo-random number generator (LCPRNG).  If
   they are all set to 1, the packet should be emitted.  This permits
   easy selection of probabilities 1/8191, 1/16383, etc.  N.B.  While
   the low-order bits of LCPRNGs are not very random, that does not
   matter here.  As long as the period of the generator is maximal, all
   values, including all 1s in the low-order bits, will occur with the
   proper probability.

   Although this document describes a router-based implementation of
   Traceback messages, most of the functionality can be implemented via
   outboard devices.  For example, suitable laptop computers can be
   used to monitor LANs, and emit the traceback messages as
   appropriate, on behalf of all of the routers on that LAN.


 3.1.2 Implementation Requirements -- Message Reception

   Hosts SHOULD be designed so that the operator can enable and disable
   the collection and storage of ICMP TRACEBACK messages as required.


.2 Configuration

   The association string used in the Forward and Back Link elements
   can be built up from the MAC addresses of the link endpoints.  If
   there are no such addresses (say, for a point-to-point link), a
   suitable string MUST be provisioned in both routers, to be used as
   the Operator-Defined Link Identifier.


.3 Processing Of Received Messages

   To circumvent attacks in the course of which false ICMP TRACEBACK
   messages are emitted, these messages SHOULD be validated before use.
   Some validation can be done before the HMAC keying information is
   disclosed.  In particular, when messages appearing to relate to
   adjacent segments of a chain have been identified, recipients SHOULD
   use the TTL field differences in conjunction with the link elements
   to verify the chain.

   Because HMAC key disclosure is done only after the end of the period
   of validity for the key, authentication of a given set of ICMP
   TRACEBACK messages requires that further messages be collected and
   examined beyond the period of interest, until the required key
   appears.  The processing entity SHOULD then verify the signature on
   the key before applying the key itself to validation of the message.




   Bellovin         Standards Track - Expires April 2002            15

                       ICMP Traceback Messages          November 2002

. Related Work

   Another scheme proposed for packet Traceback is by Savage et al
   [SWKA00].  It relies on a very clever encoding of the path in the IP
   header's ID field.  That is, in-flight packets may have their ID
   field changed to provide information about the path.  The recipient
   can decode this information.

   There are a number of advantages of this compared to ICMP Traceback.
   No extra traffic is generated.  More importantly, the trace
   information is bound to the packets, and hence doesn't follow a
   different path and isn't differentially blocked by firewalls or
   policy routing mechanisms.  However, there are disadvantages as
   well.  For one thing, the ID field cannot be changed if
   fragmentation is necessary (though they propose some schemes to
   ameliorate this).  Moreover, AH [RFC2402] provides cryptographic
   protection for the ID field; if it is modified, the packet will be
   discarded by the receiving system.  And IPv6 has no ID field at all.
   A number of other packet-marking schemes have been proposed.

   A different approach is hash-based traceback, by Snoeren et al
   [SPSSJTK01].  In this scheme, routers along the path are queried
   about whether or not they have seen a certain packet; a very compact
   representation is used to store recent history.  The problem is that
   queries must be done very soon after the attack, unless the routers
   have some way of offloading historical data to bulk storage.

   [SDS00] descibes a scheme for coupling IDS systems.  A sensor that
   detects an attack tells its neighbors; they in turn look for the
   same signature, and notify their neighbors.  The current prototype
   only works within an administrative domain; work is currently under
   way to produce an inter-domain version.


. Security Considerations

   It is quite clear that this scheme cannot cope with all conceivable
   denial of service attacks.  It is limited to those where a
   significant amount of traffic is coming from a relatively small
   number of sources.  Furthermore, those sources must themselves be in
   some sense evil or corrupted.  An attack based on inducing innocent
   and uncorrupted machines to send traffic to the victim would be
   traceable only to these machines, and not to the real attackers.


. Acknowledgements

   The ICMP Traceback message is the product of an informal research
   group; members include (in alphabetical order) Steven M. Bellovin,
   Matt Blaze, Bill Cheswick, Cory Cohen, Jon David, Jim Duncan, Jim
   Ellis, Paul Ferguson, John Ioannidis, Marcus Leech, Perry Metzger,
   Robert Stone, Vern Paxson, Ed Vielmetti, Wietse Venema.


   Bellovin         Standards Track - Expires April 2002            16

                       ICMP Traceback Messages          November 2002


. References

   [PKALGS] : L. Bassham, R. Housley, W. Polk, "Algorithms and
   Identifiers for the Internet X.509 Public Key Infrastructure
   Certificate and CRL Profile", Internet Engineering Task Force, work
   in progress.

   [RFC792] : J. Postel, "Internet Control Message Protocol", RFC 792,
   Internet Engineering Task Force, September 1981.

   [RFC1305]: David L. Mills, "Network Time Protocol (Version 3):
   Specification, Implementation and Analysis", RFC 1305, Internet
   Engineering Task Force, March 1992.

   [RFC2104]: H. Krawczyk, M. Bellare, R. Canetti, "HMAC: Keyed-Hashing
   for Message Authentication", RFC 2104, Internet Engineering Task
   Force, February 1997.

   [RFC2119]: S. Bradner, "Key words for use in RFCs to Indicate
   Requirement Levels", RFC 2119, Internet Engineering Task Force,
   March 1997.

   [RFC2402]: S. Kent and R. Atkinson, "IP Authentication Header", RFC
   2402, Internet Engineering Task Force, November 1998.

   [SWKA00] : Stefan Savage, David Wetherall, Anna Karlin and Tom
   Anderson, "Practical Network Support for IP Traceback", Technical
   Report UW-CSE-2000-02-01, Department of Computer Science and
   Engineering, University of Washington,
   http://www.cs.washington.edu/homes/savage/traceback.html.

   [SDS00] :  D. Schnackenberg, K. Djahandari, and D. Sterne,
   "Infrastructure for Intrusion Detection and Response", Proceedings
   of the DARPA Information Survivability Conference and Exposition
   (DISCEX), Hilton Head Island, SC, January 25-27, 2000.

   [SPSSJTK01]: A.C. Snoeren, C. Partridge, L.A. Sanchez, W.T. Strayer,
   C.E. Jones, F. Tchakountio, and S.T. Kent, "Hash-Based IP
   Traceback", BBN Technical Memorandum No. 1284,
   http://www.ir.bbn.com/documents/techmemos/TM1284.ps, February 7,
   2001.


. Author Information

   Steven M. Bellovin,
   AT&T Labs Research
   Shannon Laboratory
   180 Park Avenue
   Florham Park, NJ 07974
   USA
   Phone: +1 973-360-8656

   Bellovin         Standards Track - Expires April 2002            17

                       ICMP Traceback Messages          November 2002

   Email: smb@research.att.com

   Marcus D. Leech
   Nortel Networks
   P.O. Box 3511, Station C
   Ottawa, ON
   Canada, K1Y 4H7
   Phone: +1 613-763-9145
   Email: mleech@nortelnetworks.com

   Tom Taylor [Editor]
   Nortel Networks
   P.O. Box 3511, Station C
   Ottawa, ON
   Canada, K1Y 4H7
   Phone: +1 613-736-0961
   Email: taylor@nortelnetworks.com





































   Bellovin         Standards Track - Expires April 2002            18