
     Sequence Number Attacks

     By Rik Farrow

     Kevin Mitnick's alleged attack on Tsutomu Shimomura's Computers
     used a vulnerability in TCP/IP and mistaken trust.

     Questions regarding this article should be directed to the author
     at rik@spirit.com.

     December 25, 1994 found Tsutomu Shimomura, a computational
     physicist for the San Diego Supercomputer Center, on his way to
     the Sierra Nevadas to go skiing. He had left his personal network
     of computers running at his beach cottage in Del Mar, just north
     of San Diego. Perhaps it is fortunate for us he did so.

     Just after two o'clock in the afternoon, Shimomura's home systems
     were probed, then successfully attacked using something new in
     Internet attacks, sequence number guessing. Shimomura also works
     as a security expert, which made his systems both desirable
     targets for attack, and allows us to understand in detail what
     happened. Because, unlike most networks, Shimomura was using
     tcpdump to monitor traffic incoming from his Internet connection,
     and routinely sent his logs to an offsite location.

     Sequence number guessing is not really new. Steve Bellovin, a
     researcher at Bell Labs, and co-author of the Firewalls and
     Internet Security book (Addison-Wesley, 1994, ISBN 0-201-63357-4),
     included details of an attack scenario in his 1989 paper entitled
     ``Security Problems in the TCP/IP Protocol Suite''. But the
     Christmas day attack is the first known use of the technique.

     To better understand what happened, it helps to understand a
     little about how TCP (Transport Control Protocol) works. TCP is
     used for establishing bidirectional streams, like those used for
     remote terminal connections (established with telnet or rlogin
     utilities). TCP is also used for transferring large amounts of
     data, for example with FTP or connecting to a Web server.

     TCP provides a reliable connection. That is, unlike most other
     parts of the Internet Protocol suite (such as ICMP, Internet
     Control Message Protocol, or UDP, User Datagram Protocol), TCP
     establishes a connection between the local and remote site. Once
     the connection has been successfully established, groups of bytes
     of data are acknowledged by sending a sequence number back to the
     sending site. If the sending site does not receive an
     acknowledgement quickly enough, it will resend the data. If the
     sending site has resent the same data several times
     unsuccessfully, it will send an error to the application saying
     that the connection has been broken.

     The sequence number is used to acknowledge receipt of data. At the
     beginning of a TCP connection, the client sends a TCP packet with
     an initial sequence number, but no acknowledgement (there can't be
     one yet). If there is a server application running at the other
     end of the connection, the server sends back a TCP packet with its
     own initial sequence number, and an acknowledgement: the initial
     sequence number from the client's packet plus one. When the client
     system receives this packet, it must send back its own
     acknowledgement: the server's initial sequence number plus one.
     Thus, it takes three packets to establish a TCP connection (see
     Part A of Figure 1 which shows the time-line diagram.

     There's more to TCP, of course. You won't learn all about TCP in
     this short article (try Doug Comer's book Internetworking with
     TCP/IP, Volume 1, Principles, Protocols, and Architecture. Second
     Edition (Prentice Hall, 1991 ISBN 0-13-468505-9) or W. Richard
     Steven's TCP/IP Illustrated, Volume 1 (Addison-Wesley, 1993, ISBN
     0-201-63346-9). For now, it's important to understand that TCP
     packets include flag bits that get set to indicate conditions.
     When you read Shimomura's account of the attack, he makes
     reference to several flags.

     The SYN flag (shown as a capital ``S'' in tcpdump command output)
     indicates the initiation of a connection, and that an initial
     sequence number is included. When the first packet is sent from
     the client, only the SYN flag is set. When the server responds,
     both the SYN flag and the ACK flag, indicating that a valid
     acknowledgement is included, are set. From then on, the ACK flag
     will be set, showing that each packet includes an acknowledgement
     of a received packet.

     The PUSH (shown as a capital ``P'') flag means that the data in
     this packet should be pushed to the application, rathered than
     queued until more data arrives. The RESET (``R'') flag tells TCP
     to break (reset) the connection, and is sent when a client
     attempts to connect to a server application that is not running.
     In the attack, RESETs are used to close the half-open connections
     used to keep the server busy.

     The FIN bit (``F'') is used to close a connection. Each end of the
     connection sends a packet with the FIN flag, which must be
     acknowledged, so four packets are used to close a TCP connection.
     Of course in the attack you won't see two FIN packets, because the
     attacker never sees the responses from the target system, the X
     terminal.

     With this background, you are ready to read Shimomura's own
     description, if you haven't already. Essentially, the attack
     begins when several probes were launched from toad.com (a site
     registered by Nebula Consulting). Although I don't know this for
     sure, it is likely that toad.com had been broken into previously
     using other techniques.

     The probes, using finger, showmount, and rpcinfo (similar to
     probes from SATAN, but not automatic) apparently helped the
     attacker to determine a trust relationship between Shimomura's X
     terminal (actually another workstation used as an X terminal), and
     a local server. This was the real weakness exploited in the
     attack. Shimomura's systems trusted one another, using the trust
     mechanism exploited in the ``r'' commands like rsh and rcp.
     Although convenient, and safe behind a strong perimeter defense,
     trust has been used to break into systems for many years. The
     November 1988 Internet Worm exploited trust in its automated
     attacks.

     In the next phase of the attack, thirty TCP SYN packets are sent
     to the rlogin port of Shimomura's server. These packets come from
     an unused Internet address, and their initial sequence numbers are
     incremented by one instead of the more common 128,000. The purpose
     of these packets are to fill the queue on the server with
     half-open connections, so when the spoofing begins, the server
     won't be able to respond to the packets being sent as
     acknowledgements from the X terminal.

     Next, a system at Loyola University of Chicago (apollo.it.luc.edu)
     was used to probe the X terminal. Once again, a synthetic series
     of TCP packets (initial sequence numbers incremented by one) gets
     sent, but this time responses get sent back to a real site. It is
     the responses that the attacker is after, because each response
     contains an initial sequence number from the X terminal. In
     Shimomura's paper tcpdump labels the responses with
     x-terminal.shell > apollo.it.luc.edu.1000 S, indicating a packet
     with the SYN flag set. If we subtract the first initial sequence
     number from the second, 2021952000-2021824000, we get 128,000, a
     pattern that holds for all twenty probes. So now the attacker
     knows that the next initial sequence number will be 128,000
     greater than the previous one.

     The stage is now set for abusing the trust between the X terminal
     and the server. The attacker generates packets that appear to come
     from the server to open a TCP connection with the X terminal
     rshell daemon. The X terminal sends an acknowledgement back to the
     server, but this acknowledgement gets stuck in the queue. Next,
     the attacker generates the acknowledgement the server might have
     sent (if it had really been the server initiating the connection).
     Now there is an open TCP connection from the X terminal to the
     server, which is being spoofed by the server. Figure 1B shows how
     the packets actually traveled.

     Because the X terminal trusts the server, the attacker,
     masquerading as root, sends the command "echo + + >> /.rhosts" to
     the X terminal, extending trust to ANY root user with access to
     this system. Then the attacker closes the connection by sending a
     packet with FIN set, and acknowledging the FIN packet never seen
     from the X terminal. Finally, thirty RESETs are sent to the server
     to clear its queue. At this point, the server would send a RESET
     to the X terminal to close the rshell connection it never made
     (the one spoofed by the attacker), but it is now too late. The
     attacked can now log in as root on the X terminal using rlogin.

     There was more to the attack, but I'd like to save taking over TCP
     connections for another day. There is also a CERT advisory about
     this attack, which you can read.

     Copyright © 1995-1997 The McGraw-Hill Companies, Inc.
     All Rights Reserved.
     Edited by Becca Thomas / editor@unixworld.com




-------------------------------------------------------------------------------



Network Working Group                                        S. Bellovin
Request for Comments: 1948                                 AT&T Research
Category: Informational                                         May 1996

               Defending Against Sequence Number Attacks

Status of This Memo

   This memo provides information for the Internet community.  This memo
   does not specify an Internet standard of any kind.  Distribution of
   this memo is unlimited.

Abstract

   IP spoofing attacks based on sequence number spoofing have become a
   serious threat on the Internet (CERT Advisory CA-95:01).  While
   ubiquitous crypgraphic authentication is the right answer, we propose
   a simple modification to TCP implementations that should be a very
   substantial block to the current wave of attacks.

Overview and Rational

   In 1985, Morris [1] described a form of attack based on guessing what
   sequence numbers TCP [2] will use for new connections.  Briefly, the
   attacker gags a host trusted by the target, impersonates the IP
   address of the trusted host when talking to the target, and completes
   the 3-way handshake based on its guess at the next initial sequence
   number to be used.  An ordinary connection to the target is used to
   gather sequence number state information.  This entire sequence,
   coupled with address-based authentication, allows the attacker to
   execute commands on the target host.

   Clearly, the proper solution is cryptographic authentication [3,4].
   But it will quite a long time before that is deployed.  It has
   therefore been necessary for many sites to restrict use of protocols
   that rely on address-based authentication, such as rlogin and rsh.
   Unfortunately, the prevalence of "sniffer attacks" -- network
   eavesdropping (CERT Advisory CA-94:01) -- has rendered ordinary
   TELNET [5] very dangerous as well.  The Internet is thus left without
   a safe, secure mechanism for remote login.

   We propose a simple change to TCP implementations that will block
   most sequence number guessing attacks.  More precisely, such attacks
   will remain possible if and only if the Bad Guy already has the
   ability to launch even more devastating attacks.

Bellovin                     Informational                      [Page 1]
----------------------------------------------------------------------------

RFC 1948                Sequence Number Attacks                 May 1996

Details of the Attack

   In order to understand the particular case of sequence number
   guessing, one must look at the 3-way handshake used in the TCP open
   sequence [2].  Suppose client machine A wants to talk to rsh server
   B.  It sends the following message:

           A->B: SYN, ISNa

   That is, it sends a packet with the SYN ("synchronize sequence
   number") bit set and an initial sequence number ISNa.

   B replies with

           B->A: SYN, ISNb, ACK(ISNa)

   In addition to sending its own initial sequence number, it
   acknowledges A's.  Note that the actual numeric value ISNa must
   appear in the message.

   A concludes the handshake by sending

           A->B: ACK(ISNb)

   The initial sequence numbers are intended to be more or less random.
   More precisely, RFC 793 specifies that the 32-bit counter be
   incremented by 1 in the low-order position about every 4
   microseconds.  Instead, Berkeley-derived kernels increment it by a
   constant every second, and by another constant for each new
   connection.  Thus, if you open a connection to a machine, you know to
   a very high degree of confidence what sequence number it will use for
   its next connection.  And therein lies the attack.

   The attacker X first opens a real connection to its target B -- say,
   to the mail port or the TCP echo port.  This gives ISNb.  It then
   impersonates A and sends

        Ax->B: SYN, ISNx

   where "Ax" denotes a packet sent by X pretending to be A.

   B's response to X's original SYN (so to speak)

        B->A: SYN, ISNb', ACK(ISNx)

Bellovin                     Informational                      [Page 2]
----------------------------------------------------------------------------

RFC 1948                Sequence Number Attacks                 May 1996

   goes to the legitimate A, about which more anon.  X never sees that
   message but can still send

        Ax->B: ACK(ISNb')

   using the predicted value for ISNb'.  If the guess is right -- and
   usually it will be -- B's rsh server thinks it has a legitimate
   connection with A, when in fact X is sending the packets.  X can't
   see the output from this session, but it can execute commands as more
   or less any user -- and in that case, the game is over and X has won.

   There is a minor difficulty here.  If A sees B's message, it will
   realize that B is acknowledging something it never sent, and will
   send a RST packet in response to tear down the connection.  There are
   a variety of ways to prevent this; the easiest is to wait until the
   real A is down (possibly as a result of enemy action, of course).  In
   actual practice, X can gag A by exploiting a very common
   implementation bug; this is described below.

The Fix

   The choice of initial sequence numbers for a connection is not
   random.  Rather, it must be chosen so as to minimize the probability
   of old stale packets being accepted by new incarnations of the same
   connection [6, Appendix A].  Furthermore, implementations of TCP
   derived from 4.2BSD contain special code to deal with such
   reincarnations when the server end of the original connection is
   still in TIMEWAIT state [7, pp. 945].  Accordingly, simple
   randomization, as suggested in [8], will not work well.

   But duplicate packets, and hence the restrictions on the initial
   sequence number for reincarnations, are peculiar to individual
   connections.  That is, there is no connection, syntactic or semantic,
   between the sequence numbers used for two different connections.  We
   can prevent sequence number guessing attacks by giving each
   connection -- that is, each 4-tuple of <localhost, localport,
   remotehost, remoteport> -- a separate sequence number space.  Within
   each space, the initial sequence number is incremented according to
   [2]; however, there is no obvious relationship between the numbering
   in different spaces.

   The obvious way to do this is to maintain state for dead connections,
   and the easiest way to do that is to change the TCP state transition
   diagram so that both ends of all connections go to TIMEWAIT state.
   That would work, but it's inelegant and consumes storage space.
   Instead, we use the current 4 microsecond timer M and set

           ISN = M + F(localhost, localport, remotehost, remoteport).

Bellovin                     Informational                      [Page 3]
----------------------------------------------------------------------------

RFC 1948                Sequence Number Attacks                 May 1996

   It is vital that F not be computable from the outside, or an attacker
   could still guess at sequence numbers from the initial sequence
   number used for some other connection.  We therefore suggest that F
   be a cryptographic hash function of the connection-id and some secret
   data.  MD5 [9] is a good choice, since the code is widely available.
   The secret data can either be a true random number [10], or it can be
   the combination of some per-host secret and the boot time of the
   machine.  The boot time is included to ensure that the secret is
   changed on occasion.  Other data, such as the host's IP address and
   name, may be included in the hash as well; this eases administration
   by permitting a network of workstations to share the same secret data
   while still giving them separate sequence number spaces.  Our
   recommendation, in fact, is to use all three of these items: as
   random a number as the hardware can generate, an administratively-
   installed pass phrase, and the machine's IP address.  This allows for
   local choice on how secure the secret is.

   Note that the secret cannot easily be changed on a live machine.
   Doing so would change the initial sequence numbers used for
   reincarnated connections; to maintain safety, either dead connection
   state must be kept or a quiet time observed for two maximum segment
   lifetimes after such a change.

A Common TCP Bug

   As mentioned earlier, attackers using sequence number guessing have
   to "gag" the trusted machine first.  While a number of strategies are
   possible, most of the attacks detected thus far rely on an
   implementation bug.

   When SYN packets are received for a connection, the receiving system
   creates a new TCB in SYN-RCVD state.  To avoid overconsumption of
   resources, 4.2BSD-derived systems permit only a limited number of
   TCBs in this state per connection.  Once this limit is reached,
   future SYN packets for new connections are discarded; it is assumed
   that the client will retransmit them as needed.

   When a packet is received, the first thing that must be done is a
   search for the TCB for that connection.  If no TCB is found, the
   kernel searches for a "wild card" TCB used by servers to accept
   connections from all clients.  Unfortunately, in many kernels this
   code is invoked for any incoming packets, not just for initial SYN
   packets.  If the SYN-RCVD queue is full for the wildcard TCB, any new
   packets specifying just that host and port number will be discarded,
   even if they aren't SYN packets.

Bellovin                     Informational                      [Page 4]
----------------------------------------------------------------------------

RFC 1948                Sequence Number Attacks                 May 1996

   To gag a host, then, the attacker sends a few dozen SYN packets to
   the rlogin port from different port numbers on some non-existent
   machine.  This fills up the SYN-RCVD queue, while the SYN+ACK packets
   go off to the bit bucket.  The attack on the target machine then
   appears to come from the rlogin port on the trusted machine.  The
   replies -- the SYN+ACKs from the target -- will be perceived as
   packets belonging to a full queue, and will be dropped silently.
   This could be avoided if the full queue code checked for the ACK bit,
   which cannot legally be on for legitimate open requests.  If it is
   on, RST should be sent in reply.

Security Considerations

   Good sequence numbers are not a replacement for cryptographic
   authentication.  At best, they're a palliative measure.

   An eavesdropper who can observe the initial messages for a connection
   can determine its sequence number state, and may still be able to
   launch sequence number guessing attacks by impersonating that
   connection.  However, such an eavesdropper can also hijack existing
   connections [11], so the incremental threat isn't that high.  Still,
   since the offset between a fake connection and a given real
   connection will be more or less constant for the lifetime of the
   secret, it is important to ensure that attackers can never capture
   such packets.  Typical attacks that could disclose them include both
   eavesdropping and the variety of routing attacks discussed in [8].

   If random numbers are used as the sole source of the secret, they
   MUST be chosen in accordance with the recommendations given in [10].

Acknowledgments

   Matt Blaze and Jim Ellis contributed some crucial ideas to this RFC.
   Frank Kastenholz contributed constructive comments to this memo.

References

   [1]  R.T. Morris, "A Weakness in the 4.2BSD UNIX TCP/IP Software",
        CSTR 117, 1985, AT&T Bell Laboratories, Murray Hill, NJ.

   [2]  Postel, J., "Transmission Control Protocol", STD 7, RFC 793,
        September 1981.

   [3]  Kohl, J., and C. Neuman, "The Kerberos Network Authentication
        Service (V5)", RFC 1510, September 1993.

   [4]  Atkinson, R., "Security Architecture for the Internet
        Protocol", RFC 1825, August 1995.

Bellovin                     Informational                      [Page 5]
----------------------------------------------------------------------------

RFC 1948                Sequence Number Attacks                 May 1996

   [5]  Postel, J., and J. Reynolds, "Telnet Protocol Specification",
        STD 8, RFC 854, May 1983.

   [6]  Jacobson, V., Braden, R., and L. Zhang, "TCP Extension for
        High-Speed Paths", RFC 1885, October 1990.

   [7]  G.R. Wright, W. R. Stevens, "TCP/IP Illustrated, Volume 2",
        1995.  Addison-Wesley.

   [8]  S. Bellovin, "Security Problems in the TCP/IP Protocol Suite",
        April 1989, Computer Communications Review, vol. 19, no. 2, pp.
        32-48.

   [9]  Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321,
        April 1992.

   [10] Eastlake, D., Crocker, S., and J. Schiller, "Randomness
        Recommendations for Security", RFC 1750, December 1994.

   [11] L. Joncheray, "A Simple Active Attack Against TCP, 1995, Proc.
        Fifth Usenix UNIX Security Symposium.

Author's Address

   Steven M. Bellovin
   AT&T Research
   600 Mountain Avenue
   Murray Hill, NJ  07974

   Phone: (908) 582-5886
   EMail: smb@research.att.com

----------------------------------------------------------------------------

