Internet Engineering Task Force                          David Wetherall                              Neil Spring
INTERNET DRAFT                                           David Wetherall
draft-ietf-tsvwg-tcp-nonce-01.txt                              David Ely
draft-ietf-tsvwg-tcp-nonce-00.txt                            Neil Spring
                                                University of Washington
                                                           January,
                                                              July, 2001
                                                 Expires: July,  January, 2001

                    Robust ECN Signaling with Nonces

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

Abstract

   This note describes the ECN-nonce, a simple modification to ECN that
   protects against accidental or malicious concealment of marked
   packets from the TCP sender. This is valuable because it  It improves the robustness of
   congestion control by preventing receivers from exploiting ECN to
   gaining
   gain an unfair share of the network bandwidth.  The mechanism ECN-nonce uses a
   slightly different encoding than the existing
   two ECN bits ECT codepoints in the ECN field of the IP header, and also requires one additional bit a
   new flag in the TCP header.  It is computationally efficient for both
   routers and hosts.

1. Introduction

   The correct operation of ECN requires the cooperation of the receiver
   to return Congestion Experienced signals to the sender, but the
   protocol lacks a mechanism to enforce this cooperation.  This raises
   the possibility that an unscrupulous or poorly implemented receiver
   could always clear ECN-Echo and simply not return congestion signals
   to the sender.  This in turn would give the receivers receiver a performance advantage
   at the expense of competing connections that behave properly.  More
   generally, any device along the path (NAT box, firewall, QOS
   bandwidth shapers, and so forth) could remove congestion marks with
   impunity.

   The above behaviors may or may not constitute a threat to the
   operation of congestion control in the Internet.  However, given of the
   central role of congestion control, we feel it is prudent to design the ECN
   signaling loop to be robust against as many threats as possible.  In
   this way way, ECN can provide a clear incentive for improvement over the
   prior state-of-the-art without potential incentives for abuse. In this note, we show how this can be achieved
   while at the same time keeping the protocol simple and efficient.

   Our signaling  The
   ECN-nonce is a simple, efficient mechanism uses random one bit quantities to allow eliminate the potential
   abuse of ECN.

   The ECN-nonce enables the sender to verify that the receiver has implemented correct behavior of
   the ECN signaling
   correctly receiver and that there is no other interference that
   conceals marked (or dropped) packets in the signaling path. This provides
   protection  The ECN-
   nonce protects against both implementation errors and deliberate
   abuse.
   In developing the nonce signaling mechanism we met the following
   goals:  The ECN-nonce:

     - It provides catches a misbehaving receiver with a high probability, and never
       implicates an additional check but innocent receiver.

     - does not change other aspects of ECN, and nor does it reduce the
       benefits of ECN for behaving receivers.

     - It catches a misbehaving receiver with a high probability, and
       never convicts an innocent receiver

     - It is cheap in terms of both per-packet overhead (one TCP header bit
       more than the existing ECN mechanism) flag) and
       processing requirements.

     - It is simple and, to the best of our knowledge, not prone to other attacks
       attacks.

   We also note that use of the ECN-nonce has two additional benefits,
   even when only drop-tail routers are used.  First, packet drops
   cannot be concealed from the sender.  Second, it prevents optimistic
   acknowledgements [Savage], in which TCP segments are acknowledged
   before they have been received.  These benefits also serve to
   increase the robustness of congestion control from attacks.  We do
   not elaborate on these benefits in this draft.

   The rest of this note draft describes the mechanism, first with ECN-nonce.  We present an
   overview
   and then in terms of more followed by detailed behavior at senders, routers senders and receivers.

   The keywords MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD,
   SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL, when they appear in this
   document, are to be interpreted as described in [RFC2119].

2. Overview of Solution

   Our scheme

   The ECN-nonce builds on the existing ECN-Echo and CWR signaling
   mechanism.  Familiarity with ECN [ECN] is assumed in this note. Also, for assumed.  For simplicity,
   we describe our scheme the ECN-nonce in one direction only, though it is run in
   both directions in parallel.

   In

   The ECN protocol for TCP remains unchanged, except for the definition
   of a nutshell, our approach new field in the TCP header.  As in [ECN], ECT(0) or ECT(1)
   (ECN-Capable Transport) is set in the ECN field of the IP header on
   outgoing packets. Congested routers change this field to detect misbehavior by attaching a
   random one bit nonce value to packets at CE
   (Congestion Experienced).  When TCP receivers notice CE, the ECE
   (ECN-Echo) flag is set in subsequent acknowledgements until receiving
   a CWR (Congestion Window Reduced) flag.  The CWR flag is sent on new
   data whenever the sender reacts to congestion.

   The ECN-nonce adds to this protocol, and having
   acknowledgments from enables the receiver echo to
   demonstrate to the nonce information sender that segments being acknowledged were
   received unmarked.  A random one-bit value (a nonce) is
   received. At routers, packet marking becomes encoded in
   the process two ECT codepoints.  The one-bit sum of erasing these nonces is returned
   in a TCP header flag, the nonce value. Therefore, once a packet has been sum (NS) bit.  Packet marking erases
   the nonce value in the ECT codepoints because CE overwrites both ECN
   IP header bits.  Since each nonce is required to calculate the sum,
   the correct nonce sum implies receipt of only unmarked packets.  Not
   only are receivers prevented from concealing marked by a
   router, it packets, middle-
   boxes along the network path cannot be unmarked by any party unmark a packet without
   successfully guessing the value of the erased original nonce. Thus receipt of correct nonce
   information from the receiver provides the sender with a
   probabilistic proof-of- receipt check for unmarked packets.

   The check
   is used by the TCP sender to can verify that the ECN-Echo bit is being
   set correctly and nonce sum returned by the receiver to
   ensure that congestion indications in the form of marked (or dropped)
   packets are not being concealed.  Because the nonce sum is only one
   bit of
   information is returned with each acknowledgement, long, senders have a 50-50 chance of catching a lying receiver every time they perform
   whenever an acknowledgement conceals a
   check. mark.  Because the check for each
   acknowledgement is an independent
   trial it is highly likely that trial, cheaters will be caught
   quickly if there are repeated packet marks.

   There are several areas congestion signals.

   The following paragraphs describe aspects of detail missing from the preceding high-
   level description. We mention those areas to complete the overview.

   First, the nonce values are echoed ECN-nonce protocol
   in the form of nonce sums. greater detail.

   Each acknowledgement carries a nonce sum sum, which is carried in an acknowledgement, and represents the one bit sum (XOR
   (exclusive-or, or parity) of nonces over the byte range represented
   by the acknowledgement.  To understand why the  The sum is used, rather than
   individual echoes, consider the following argument. If used because not every packet
   were reliably ACKed, then is
   acknowledged individually, nor are packets acknowledged reliably.  If
   a sum were not used, the nonce carried in the an unmarked packet could simply be echoed. This would probabilistically echoed
   to prove to the sender that the receiver received the packet and the individual packet was arrived unmarked.
   However, ACKs since these acks are not carried across the network reliably,
   and not every packet is ACKed. In this case, reliably delivered, the sender cannot
   could not distinguish a lost ACK from one that was never sent in
   order to conceal a marked packet. It would require additional mechanism,
   beyond that used in TCP, to convey the nonce bits reliably. Instead,
   we send the  The nonce sum that corresponds to the cumulative ACK. This
   sum prevents individual
   marked packets from being concealed by not acknowledging them. Note that because they
   Because the nonce and nonce sum are both one bit quantities, the sum
   is no easier to guess than the individual nonces.

   Second, resynchronization of  We show the sender and receiver nonce
   sum calculation below in Figure 1.

       Sender             Receiver
                            initial sum = 1
         -- 1:4 ECT(0)  --> NS = 1 + 0(1:4) = 1(:4)
         <- ACK 4, NS=1 ---
         -- 4:8 ECT(1)  --> NS = 1(:4) + 1(4:8) = 0(:8)
         <- ACK 8, NS=0 ---
         -- 8:12 ECT(1)  -> NS = 0(:8) + 1(8:12) = 1(:12)
         <- ACK 12, NS=1 --
         -- 12:16 ECT(1) -> NS = 1(:12) + 1(12:16) = 0(:16)
         <- ACK 16, NS=0 --
      Figure 1: The calculation of nonce sums is needed
   after at the receiver.

   After congestion has occurred and packets have been marked. marked or lost,
   resynchronization of the sender and receiver nonce sums is needed.
   When packets are marked, the nonce is cleared, and the sum of the
   nonces at the receiver will no longer reflect match the sum at the sender. While
   this is conceptually fixed by having the receiver send a series of
   partial sums for the ranges of unmarked packets that it has received,
   this solution is clumsy because the required range information is not
   already being sent.  Fortunately, there is a simple solution that
   does not require range information because ECN congestion indications
   do not need to indicate the particular packets that were marked. We
   observe that once
   Once nonces have been lost, the difference between sender and
   receiver nonce sums will be fixed is constant until there is further loss.  This
   means that it is possible to resynchronize the sender and receiver
   after congestion by having the sender set its nonce sum to that of
   the receiver.  Because congestion indications do not need to be
   conveyed more frequently than once per round trip, we suspend the sender
   suspends checking while the CWR signal is being delivered and acknowledged by
   the receiver. We reset the sender resets
   its nonce sum to the receiver sum receiver's when new data is acknowledged.  This scheme is simple and
   has the benefit that the receiver is not explicitly involved in the re-
   synchronization
   re-synchronization process.

   Third, we need to reconcile the nonces  The resynchronization process is shown
   in Figure 2 below.  Note that are sent with packet with
   acknowledgements the nonce sum returned in ACK 12 (NS=0)
   differs from that cover byte ranges. Acknowledged byte boundaries
   need not match in the transmitted boundaries, previous example (NS=1), and during retransmissions
   information can be resent with different byte boundaries. To handle
   these factors, we compute nonces and nonce sums using an underlying
   mapping of byte ranges it continues to
   differ for ACK 16.

       Sender              Receiver
                               initial sum = 1
         -- 1:4 ECT(0)       -> NS = 1 + 0(1:4) = 1(:4)
         <- ACK 4, NS=1      --
         -- 4:8 ECT(1) -> CE -> NS = 1(:4) + ?(4:8) = 1(:8)
         <- ACK 8, ECE NS=1  --
         -- 8:12 ECT(1), CWR -> NS = 1(:8) + 1(8:12) = 0(:12)
         <- ACK 12, NS=0     --
         -- 12:16 ECT(1)     -> NS = 0(:12) + 1(12:16) = 1(:16)
         <- ACK 16, NS=1     --
      Figure 2: The calculation of nonce values. Both sender and sums at the receiver
   understand this mapping, when a
       packet (4:8) is marked.  The receiver may calculate the wrong
       nonce sum when the original nonce information is lost after a
       packet is marked.

   Third, we need to reconcile that nonces are sent with packets but
   acknowledgements cover byte ranges.  Acknowledged byte boundaries
   need not match the transmitted boundaries, and information can convert to be
   retransmitted in packets with different byte boundaries.  However,
   ECN is disabled for retransmissions, so can carry no nonce.  Since
   retransmissions are associated with congestion events, nonce checking
   is suspended until after CWR is acknowledged and from the nonces
   carried on individual packets. congestion event
   is over.

   The next sections describe the detailed behavior of senders, routers
   and receivers. We start receivers, starting with sender transmit behavior, and work our
   way then around
   the ECN signaling loop until we arrive back at sender
   receive behavior. Comments in parenthesis highlight the changes
   between the nonce mechanism loop, and the existing ECN specification. finish with sender acknowledgement
   processing.

3. Sender Behavior (Transmit)

   Senders in our scheme manage CWR and ECN-Echo as before.  In addition addition, they must
   place nonces on packets as they are transmitted and check the
   validity of the nonce sums on packets in acknowledgments as they are received.
   This section describes the transmit process.

   To place a one bit nonce value on every ECN-capable IP packet requires first packet, the
   sender uses the two ECT codepoints: ECT(0) represents a nonce of
   all 0,
   and ECT(1) a way to encode these bits nonce of 1.  As in IP packets. We use ECN, retransmissions are not ECN-
   capable, so carry no nonce.

   The sender maintains a mapping from each packet's end sequence number
   to the following
   encoding of expected nonce sum (not the ECN bits to identify different packet states. This
   encoding must be understood by all ECN capable senders, routers, and
   receivers in our scheme. (The second state below is currently unused nonce placed in the existing ECN specification, while original
   transmission) in the other states retain
   their existing meanings.)

       00 = ECN incapable

       10 = ECN capable, unmarked (nonce = 0)

       01 = ECN capable, unmarked (nonce = 1)

       11 = ECN capable, marked (nonce lost)

   Next, we require a simple way to map nonces to transmitted TCP
   packets in a manner that is compatible with checking the nonce sum on
   received TCP acknowledgements. This is complicated by several
   factors. Nonces are sent per packet but acknowledgements cover byte
   ranges acknowledgement bearing that do not necessarily correspond sequence number.

4. Router Behavior

   Routers behave as specified in [ECN-draft].  By marking packets to
   signal congestion, the original packet
   ranges; this value of the nonce, in ECT(0) or
   ECT(1), is removed.  Neither the receiver nor any other party can depend on implementation buffering strategies. In
   unmark the case of retransmissions, packet without successfully guessing the boundary value of retransmitted packets
   need not correspond to the
   original transmissions either (because of
   path MTU changes, retransmission batching, nonce.

5. Receiver Behavior (Receive and so forth). Finally,
   there is ambiguity at Transmit)

   ECN-nonce receivers maintain the sender nonce sum as to whether in-order packets arrive
   and return the original or
   retransmitted packet was received. It is important that our
   implementation behave correctly even current nonce sum in these rare cases so that a
   receiver each acknowledgement.  Receiver
   behavior is never incorrectly labeled as misbehaving.

   We associate nonce values with byte ranges instead of individual otherwise unchanged from [ECN-draft].

   As packets to avoid these difficulties.  Starting are removed from the initial
   sequence number, each block queue of SMSS bytes (the maximum segment size)
   in out-of-order packets to be
   acknowledged, the TCP byte stream is associated with a single pseudorandom nonce
   bit. is recovered from the IP header.  The byte range of nonce
   is added to the packet determines what current nonce value it
   will carry. If sum as the packet, either original or a retransmission, spans
   multiple blocks, we use acknowledgement sequence
   number is advanced for the block in which recent packet.

   In the final byte case of the
   packet resides to determine which marked packets, one or more nonce value values may be
   unknown to transmit with the
   packet.  A series of small packets will carry receiver.  In this case the same missing nonce values are
   ignored when calculating the sum (or equivalently a value
   until an entire block's worth of SMSS bytes has been transmitted.
   This zero is a useful tradeoff because sending partial packets makes a
   flow less likely to cause congestion. Since no packet can carry more
   than SMSS bytes, each block's nonce bit
   assumed) and ECN-Echo will be set to signal congestion to the sender.

   Returning the nonce sum corresponding to a given acknowledgement is
   straightforward.  It is carried in at least
   one packet.

   The following table provides an example of how we decompose a byte
   stream into blocks and how we assign nonce values single "NS" (Nonce Sum) bit in
   the TCP header.  This bit is adjacent to each block
   (assuming a block size the CWR and ECN-Echo bits,
   set as Bit 7 in the Reserved field of 1460 bytes):

   ------------------------------------------------------- the TCP header, as shown below:

           0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
         +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
         |               | Bytes:               | 1...1460 C | 1461...2920 E | 2921 ... 4380 U |
   ------------------------------------------------------- A | Nonce: P |    1 R |      1 S |       0 F |
   -------------------------------------------------------
         | Nonce Sum: Header Length |    1    Reserved   |      0 W |       1 C |
   -------------------------------------------------------

4. Router Behavior

   Routers must be able to identify packets sent by ECN capable
   transports R | C | S | S | Y | I |
         |               |               | R | E | G | K | H | T | N | N |
         +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

      Figure 3: The old definition of bytes 13 and mark them if indicated by active queue management. To
   mark packets, routers change either 14 of the unmarked states to the
   single marked state. (The operation TCP Header.

           0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
         +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
         |               |           | N | C | E | U | A | P | R | S | F |
         | Header Length | Reserved  | S | W | C | R | C | S | S | Y | I |
         |               |           |   | R | E | G | K | H | T | N | N |
         +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

      Figure 4: The new definition of marking has changed only in
   that routers now need to recognize two states as meaning not marked bytes 13 and so 14 of the TCP Header.

   The initial nonce sum is still straightforward.) This erases 1, and is included in the state SYN/ACK and ACK of
   the
   original nonce carried with three way TCP handshake.  This allows the packet, which is key other endpoint to our scheme.
   Neither infer
   nonce support, but is not a negotiation, in that the receiver nor any other party can now unmark the packet
   without successfully guessing the value of the original nonce.

5. Receiver Behavior (Receive and Transmit)

   In addition to distinguishing marked and unmarked packets and setting
   the ECN- Echo flag as before, receivers in our scheme maintain a
   nonce sum as packets arrive, and return the sum that corresponds to a
   particular acknowledgment with the acknowledgment.

   To maintain the nonce sum, receivers use the same mapping as the
   sender to convert the nonces carried in unmarked packets to the
   nonces of the underlying blocks. These nonce values are summed over
   the byte range covered by the acknowledgement. Computing this sum
   correctly when packets of size SMSS are sent requires that all
   packets up to the one acknowledged be received. New sums are computed
   by taking the old value and XORing it with a new nonce. That is, the
   sum is also a one bit quantity, and old nonce state does not
   SYN/ACK need to
   be maintained.

   In the case of marked packets, one or more nonce values may be
   unknown to the receiver. In this case the missing nonce values are
   ignored when calculating the sum (or equivalently a value of zero not check if NS is
   assumed) and ECN-Echo will be set to signal congestion to the sender.

   Returning the nonce sum corresponding decide whether to a given acknowledgement is
   straightforward. It is carried in a single bit in the TCP header.
   (This bit is set NS in addition the CWR and ECN-Echo bits and would require
   one of the reserved bits to be allocated.)
   These nonce sums are checked for validity at
   the sender, as described
   below. subsequent ACK.

6. Sender Behavior (Receive)

   This section completes the description of sender behavior by
   describing how senders check the validity of the nonce sums.

   Checking is straightforward and

   The nonce sum is performed every time checked when an acknowledgement of new data is
   received, except during congestion recovery. Given
   the byte range covered by an acknowledgement and the mapping between
   bytes and nonces, the sender is able to compute the correct nonce
   sum. Minimal sender state is needed to do this because old nonce
   values can be discarded as acknowledgments and the sum advance.
   Checking consists of simply comparing recovery when additional ECN-Echo
   signals would be ignored.  Checking consists of comparing the correct
   nonce sum and stored in a buffer to that carried in the acknowledgement. acknowledgement,
   with a correction described in the following subsection.

   If ECN-Echo is not set, the receiver claims to have received no
   marked packets, and can therefore compute and return the correct
   nonce sum.  To
   cheat, conceal a mark, the receiver must successfully guess
   the sum of the nonces that it did not receive (because receive, because at least one
   packet was marked and the corresponding nonce was erased). erased.  Provided
   the individual nonces are equally likely to be 0 or 1, their sum is
   equally likely to be 0 or 1.  In other words, any guess is equally
   likely to be wrong and has a 50-50 chance of being caught by the
   sender.  Because each
   acknowledgement (that covers a new block) acknowledgement is an independent trial, a
   cheating receiver is highly likely to be caught after a small number of
   lies.

   If ECN-Echo is set, the receiver is sending a congestion signal and
   it is not necessary to check the nonce sum.  The congestion window
   will be halved, CWR will be set on the next packet with new data
   sent, and ECN-Echo will be cleared once the CWR signal is received. received,
   as in [ECN-draft].  During this recovery process, the sum may be
   incorrect because one or more nonces were not received.  This does
   not matter during recovery, because TCP invokes congestion mechanisms
   at most once per RTT, whether there are one or more losses during
   that period. However,
   after

6.1 Resynchronization After Loss or Mark

   After recovery, it is necessary to re-synchronize the sender and
   receiver nonce sums so that further acknowledgments can be checked.
   If might be possible to send the missing nonces to the receiver, but
   this would be cumbersome because TCP lacks the mechanism to do so
   conveniently. Instead, we observe that if there are no more marked
   packets,
   When the sender and receiver sums should differ by a constant
   amount. receiver's sum is incorrect, it will remain incorrect until
   further loss.
    This leads to a simple re-synchronization mechanism where the sender
   resets its nonce sum to that of the receiver when it receives an
   acknowledgment for new data sent after the congestion window was
   reduced.  In most instances,  When responding to explicit congestion signals, this will
   be the first acknowledgement without the ECN-Echo flag set.

   A separate issue set: the
   acknowledgement of the packet containing the CWR flag.

       Sender              Receiver
                                initial sum = 1
         -- 1:4 ECT(0)       -> NS = 1 + 0(1:4) = 1(:4)
         <- ACK 4, NS=1      --
         -- 4:8 ECT(1) -> LOST
         -- 8:12 ECT(1)      -> nonce sum calculation deferred
                                  until in-order data received
         <- ACK 4, NS=0      --
         -- 12:16 ECT(1)     -> nonce sum calculation deferred
         <- ACK 4, NS=0      --
         -- 4:8 retransmit   -> NS = 1(:4) + ?(4:8) +
                                     1(8:12) + 1(12:16) = 1(:16)
         <- ACK 16, NS=1     --
         -- 16:20 ECT(1) CWR ->
         <- ACK 20, NS=0     -- NS = 1(:16) + 1(16:20) = 0(:20)

      Figure 5: The calculation of nonce sums at the receiver when a
       packet is lost, and resynchronization after loss.  The nonce sum
       is not changed until the penalty for misbehavior that cumulative acknowledgement is caught advanced.

   In practice, resynchronization can be accomplished by
   checking.  During normal operation, both with storing a bit
   that has the value one if the expected nonce sum stored by the sender
   and without packet
   marks the received nonce sum in the acknowledgement of CWR differ, and drops, no misbehavior will
   zero otherwise.  This synchronization offset bit can then be uncovered unless some party
   after used in
   the marking router is behaving incorrectly. A simple remedy comparison between expected nonce sum and received nonce sum.

   The sender should ignore the nonce sum returned on any
   acknowledgements bearing the ECN-echo flag.

   Finally, in
   this case would be ECN, senders can choose not to disable indicate ECN at the sender, that is, not mark capability on
   some packets for any reason.  An ECN-nonce sender must resynchronize
   after sending such ECN-incapable packets, as ECN capable. This simultaneously deprives the receiver of though a CWR had been
   sent with the benefits of ECN and relieves first new data after the ECN-incapable packets.  The
   sender loses protection for any unacknowledged packets until
   resynchronization occurs.

6.2 Sender Behavior - Incorrect Nonce Received

   The sender's response to an incorrect nonce is a matter of policy.
   It is separate from the checking mechanism and does not need to monitor be
   handled uniformly by senders.

   If the receiver. However, an additional consideration is receiver has never sent a non-zero nonce sum, the sender can
   infer that the receiver does not understand the nonce, and rate limit
   the connection, place it in a lower-priority queue, or cease setting
   ECT in outgoing segments.

   If the received nonce
   checking mechanism provides sum has been set in a previous acknowledgement,
   the sender might infer that a network device has interfered with
   correct ECN signaling between ECN-nonce supporting endpoints.  The
   minimum response to an incorrect nonce is the same as the response to
   a received ECE.  However, to compensate for hidden congestion
   signals, the sender might reduce the congestion window to one segment
   and cease setting ECT in outgoing segments. An incorrect nonce sum is
   a sign of misbehavior or error between ECN-nonce supporting
   endpoints.

6.2.1 Using the ECN-nonce to Protect Against Other Misbehaviors

   The ECN-nonce can provide robustness beyond checking that marked
   packets are signaled to the sender.  It also ensures that dropped
   packets cannot be concealed from the sender (because their nonces
   have been lost).  Drops could potentially be concealed by a faulty
   TCP implementation, certain attacks, or even a hypothetical a TCP
   accelerator.  Such an accelerator willing to could gamble that it can either
   successfully ``fast start'' to a preset bandwidth quickly, retry with
   another connection, or provide reliability at the application level.
   If robustness against these faults is considered valuable (as opposed also desired, then the ECN-
   nonce should not be disabled.  Instead, reducing the congestion
   window to one, or using a low-priority queue, would penalize faulty
   operation while providing continued checking.

   The ECN-nonce can also detect misbehavior in Eifel [Eifel-draft], a
   recently proposed mechanism for removing the retransmission ambiguity
   to improve TCP performance.  A misbehaving receiver might claim to
   have received only original transmissions to convince the sender to
   undo congestion actions.  Since retransmissions are sent without ECT,
   and thus no nonce, returning the correct nonce sum confirms that only
   original transmissions were received.

7. Interactions
7.1 Path MTU Discovery

   Because a receiver could reconstruct the original nonce from unmarked
   fragments to conceal a mark on a fragment, senders SHOULD set the
   Don't Fragment bit and use Path MTU discovery.  This contrasts with
   [ECN-draft], which says that ECN-capable packets MAY have the DF bit
   set.  Some senders may not be able to use Path MTU discovery
   successfully because ICMP messages are blocked by middle-boxes on the
   return path.  The ECN-nonce cannot protect against misbehaving
   receivers that receive marked fragments, so some protection is lost
   by disabling Path MTU discovery.

   When responding to a small path MTU, the sender will retransmit a
   smaller frame in place of a larger one.  Since these smaller packets
   are retransmissions, they will be ECN-incapable and bear no nonce.
   The sender should resynchronize on the first newly transmitted
   packet.

7.2 SACK

   Selective acknowledgements allow receivers to acknowledge out of
   order segments as an optimization.  It is not necessary to modify the
   selective acknowledgment option to fit per-range nonce sums, because
   SACKs cannot be used by a receiver to hide a congestion signal.  The
   nonce sum corresponds only to the data acknowledged by the cumulative
   acknowledgement.

7.3 IPv6

   Although the IPv4 header is protected by a checksum, this is not the
   case with IPv6, making undetected bit errors in the IPv6 header more
   likely.  Bit errors that compromise the integrity of the congestion
   notification fields may cause an incorrect nonce to be received, and
   an incorrect nonce sum to simply
   detecting be returned.

8. Security Considerations

   The random one-bit nonces need not be from a faulty ECN implementation) then it is cryptographic-quality
   pseudo-random number generator.  A strong random number generator
   would compromise performance.  Consequently, the sequence of random
   nonces should not clear that be used for any other purpose.

   Conversely, the
   nonce mechanism pseudo-random bit sequence should not be turned off. Instead, generated by
   a penalty such as
   reducing linear feedback shift register [Schneier], or similar scheme that
   would allow an adversary who has seen several previous bits to infer
   the generation function and thus its future output.

   Although the ECN-nonce protects against concealment of congestion window by a factor
   signals and optimistic acknowledgement, it provides no additional
   protection for the integrity of 4 may the connection.

9. IANA Considerations

   The Nonce Sum (NS) is carried in a reserved TCP header bit that must
   be preferable. allocated.  This would provide continued checking while punishing faulty
   operation. Luckily, document describes the use of Bit 7, adjacent to
   the other header bits used by ECN.

   The codepoint for the NS flag in the TCP header is specified by the
   Standards Action of this issue RFC, as is separate required by RFC 2780. When this
   draft is published as an RFC, IANA should add the following to the
   registry for "TCP Header Flags":

   RFC xxx defines bit 7 from the checking
   mechanism and does not need Reserved field to be handled uniformly by senders.

7. used for the
   Nonce Sum, as follows:

         0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
       +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
       |               |           | N | C | E | U | A | P | R | S | F |
       | Header Length | Reserved  | S | W | C | R | C | S | S | Y | I |
       |               |           |   | R | E | G | K | H | T | N | N |
       +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

       TCP Header Flags

       Bit      Name                                    Reference
       ---      ----                                    ---------
        7        NS (Nonce Sum)                         [RFC xxx]

10. Conclusion

   We have described

   The ECN-nonce is a simple modification to the ECN signaling mechanism
   that improves its ECN's robustness by preventing receivers from
   concealing marked (or dropped) packets.  The intent of this work is
   to help improve the robustness of congestion control in the Internet.
   The modification is retains the character and simplicity of existing ECN
   signaling.  It is also practical for deployment in the Internet.  It requires two bits in
   uses the IP header (ECT ECT(0) and CE with a slightly
   different encoding) ECT(1) codepoints and one additional bit in the TCP header flag (as
   well as CWR and ECN-Echo) and has simple processing rules.

10. References

  [ECN]  "The ECN Web Page", URL "http://www-
   nrg.ee.lbl.gov/floyd/ecn.html".
  [ECN-draft] K. Ramakrishnan, S. Floyd, and D. Black.  The addition of
   explicit congestion notification (ECN) to IP.  draft-ietf-tsvwg-
   ecn-04.txt
  [Eifel-draft] R. Ludwig. The Eifel Algorithm for TCP.  draft-ietf-
   tsvwg-tcp-eifel-alg-00.txt
  [B97] Bradner, S., "Key words for use in RFCs to Indicate Requirement
   Levels", BCP 14, RFC 2119, March 1997.
  [Savage] S. Savage, N. Cardwell, D. Wetherall, T. Anderson.  TCP
   congestion control with a misbehaving receiver. SIGCOMM CCR, October
   1999.
  [Schneier] Bruce Schneier. Applied Cryptography, 2nd ed., 1996

Acknowledgements

   This note grew out of research done by Stefan Savage, David Ely,
   David Wetherall, Tom Anderson and Neil Spring.  We are very grateful
   for feedback and assistance from Sally Floyd.

Authors' Addresses

   Neil Spring
   Email: nspring@cs.washington.edu

   David Wetherall
   Email: djw@cs.washington.edu
   Phone +1 (206) 616 4367

   David Ely
   Email: ely@cs.washington.edu

   Neil Spring
   Email: nspring@cs.washington.edu

   Computer Science and Engineering, 352350
   University of Washington
   Seattle, WA 98195-2350

   Send comments by electronic mail to all three authors.

   This draft was created in January July 2001.
   It expires July 2001. January 2002.