One document matched: draft-bellovin-itrace-00.txt

Network Working Group                                           Bellovin
Internet Draft                                        AT&T Labs Research

Expiration Date: September 2000                               March 2000


                        ICMP Traceback Messages

                      draft-bellovin-itrace-00.txt


1. Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   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.


2. Abstract

   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 to the destination.












Bellovin                                                        [Page 1]

Internet Draft        draft-bellovin-itrace-00.txt            March 2000


3. 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.


3.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].


4. Message Definition

   A router implementing this scheme SHOULD generate and emit a
   Traceback packet with probability of about 1/20,000.  The message
   contains the following fields (in this draft, we are not going to
   define the syntax of the different fields):

        Back link -- information on the previous hop (see below)

        Forward link -- information on the next hop

        Timestamp, in NTP format

        Traced packet -- as much of the traced packet as will fit.
        (Note:  this is a variable-length field, since there are many
        different types of authentication fields.)

        Authentication

   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



Bellovin                                                        [Page 2]

Internet Draft        draft-bellovin-itrace-00.txt            March 2000


   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 fields, a chain can be constructed and partially verified even
   without examining the authentication fields.


4.1. Link Fields The purpose of the link fields 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 subfields of a link field are always arranged in "forward order".
   That is, the "destination" subfield is always the address of the
   router closer to the ultimate recipient of the traceback packet.
   Thus, on back link packets, the generator's own address is the
   destination; on forward link packets, the generator's address is the
   source address.

   A link field consists of three subfields:  the interface name of the
   generator (it is assumed that the generator does not know its
   neighbors' interface names), the source and destination IP addresses
   of the two routers (with appropriate IPv4/IPv6 indicators), and the
   link-level association string.  The association string is an opaque
   blob that is known to and used by both routers.  On LANs, it is
   constructed by concatenating the source and destination MAC addresses
   of the pair of machines.  If there are no such addresses (say, for a
   point-to-point link), a suitable string MUST be provisioned in both
   routers.  This field is used to tie together Traceback messages
   emitted by adjacent routers.  Recipients SHOULD use the TTL field
   differences in conjunction with the link fields to verify the chain.


4.2. Authentication data

   An attacker may try to generate fake Traceback messages, prinarily 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.




Bellovin                                                        [Page 3]

Internet Draft        draft-bellovin-itrace-00.txt            March 2000


4.2.1. Null Authentication Option

   Given the TTL definition and the link fields, it is unclear whether
   or not we even need stronger authentication.  An attacker at a given
   location can generate packets that appear to be coming from further
   away; he or she cannot generate packets that appear to be closer.
   Thus, the uncorrupted routers between the target and the attacker
   will point unambiguously to some point of attack.

   That said, it is unclear if this is sufficient.  The distributed
   denial of service attacks involved a massive amount of traffic from
   many different sources; plausible-looking fake chains could easily
   deceive a victim.


4.2.2. Cleartext Random Strings

   A second authentication option is to include a unique cleartext
   string in the packet.  The same string would be used for some
   interval (probably a few minutes).  A validation field -- a
   digitally-signed list of the last several authentication strings,
   plus their validity intervals -- would prevent easy forgery of these
   strings.

   Cleartext validation strings are unique per output interface.  This
   makes it harder for the attacker to collect such strings as seen by
   the target of the attack, since the strings are headed towards the
   target, and hence away from the attacker.

   One useful form of string is the pair <interfacename,NTP time>.  It
   carries its own guarantee of freshness, and if digitally signed can
   be presumed to be authentic.

   A variation on this scheme would involve the router sending
   occasional separate validation messages.  This removes the validation
   field from the traceback packets, at the cost of requiring the
   recipient to see two ICMP messages from the same router.


4.2.3. HMAC Authentication

   Instead of using cleartext strings, an HMAC [RFC2104] could be
   computed.  Again, a validation field could be sent, listing the last
   several HMAC keys but not the current one.  This should be immune to
   forgery; again, though it requires reception of at least two ICMP
   messages to fully validate the chain.





Bellovin                                                        [Page 4]

Internet Draft        draft-bellovin-itrace-00.txt            March 2000


4.2.4. PKI Requirements

   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.


5. Implementation Requirements

   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%; should not be an undue burden on the recipient.  The
   probablity 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
   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.  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.









Bellovin                                                        [Page 5]

Internet Draft        draft-bellovin-itrace-00.txt            March 2000


6. Related Work

   The other scheme proposed for packet Traceback is by Savage et al.
   [Savage00].  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).  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.


7. 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.


8. 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                                                        [Page 6]

Internet Draft        draft-bellovin-itrace-00.txt            March 2000


9. References

   [RFC792]  "Internet Control Message Protocol". J. Postel.
   Sep-01-1981.

   [RFC2104]       "HMAC: Keyed-Hashing for Message Authentication". H.
   Krawczyk,      M. Bellare, R. Canetti. February 1997.

   [RFC2119] "Key words for use in RFCs to Indicate Requirement Levels".
   S.  Bradner. March 1997.

   [RFC2402] "IP Authentication Header".  S. Kent and R. Atkinson.
   November 1998.

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

10. Author Information


Steven M. Bellovin, Editor
AT&T Labs Research
Shannon Laboratory
180 Park Avenue
Florham Park, NJ 07974
USA
Phone: +1 973-360-8656
Email: smb@research.att.com



















Bellovin                                                        [Page 7]