Re: [tcpm] tcp-auth-opt issue: replay protection

Eric Rescorla <> Thu, 31 July 2008 00:16 UTC

Return-Path: <>
Received: from [] (localhost []) by (Postfix) with ESMTP id DA4DC3A6B5A; Wed, 30 Jul 2008 17:16:05 -0700 (PDT)
Received: from localhost (localhost []) by (Postfix) with ESMTP id AB8263A6B42 for <>; Wed, 30 Jul 2008 17:16:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.484
X-Spam-Status: No, score=-0.484 tagged_above=-999 required=5 tests=[AWL=0.011, BAYES_00=-2.599, FH_RELAY_NODNS=1.451, HELO_MISMATCH_COM=0.553, RDNS_NONE=0.1]
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id OjuO0+JkEE2n for <>; Wed, 30 Jul 2008 17:16:03 -0700 (PDT)
Received: from (unknown []) by (Postfix) with ESMTP id 9A97F3A69D7 for <>; Wed, 30 Jul 2008 17:16:03 -0700 (PDT)
Received: from kilo-2.local (localhost []) by (Postfix) with ESMTP id 6511C4D5E34; Wed, 30 Jul 2008 17:16:09 -0700 (PDT)
Date: Wed, 30 Jul 2008 17:16:09 -0700
From: Eric Rescorla <>
To: Joe Touch <touch@ISI.EDU>
In-Reply-To: <>
References: <> <> <> <> <> <> <> <> <> <>
User-Agent: Wanderlust/2.15.5 (Almost Unreal) Emacs/22.1 Mule/5.0 (SAKAKI)
MIME-Version: 1.0 (generated by SEMI 1.14.6 - "Maruoka")
Message-Id: <>
Subject: Re: [tcpm] tcp-auth-opt issue: replay protection
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: TCP Maintenance and Minor Extensions Working Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit

At Wed, 30 Jul 2008 15:22:38 -0700,
Joe Touch wrote:

> 2. include an extended sequence number (ESN) inside TCP-AO
> 	ESN starts at 0
> 	increment ESN when the TCP sequence number rolls over*
> 	passed ESN to the encryption algorithm as part of the MAC'd data
> 3. have TCP-AO ask the KMS to add a new key for the connection when the
> sequence number rolls over (actually just before, e.g., 2^31 rolls over)
> - ------------------------------------
> #2 is internal to TCP-AO, i.e., it requires no 'callback' to the KMS
> There appears to be a synchronization issue here - exactly when is the
> ESN incremented? Suppose endpoints A and B; there are two ESNs - ESN_ab
> and ESN_ba:
> 	A increments ESN_ab when A receives an ack from B w/seqno > 2^31
> 	B increments ESN_ab when B sends an ack to A w/seqno > 2^31
> 	B increments ESN_ba when B receives an ack from A w/seqno > 2^31
> 	A increments ESN_ba when A sends an ack to B w/seqno > 2^31
> i.e., the ESN is incremented when the reverse channel succeeds; we can't
> use the forward channel, since one side would change the ESN in ways the
> other would never notice (it wouldn't decode it)
> Given that algorithm, every ESN increment would trash data in transit
> from A-B. Is there an algorithm that does not do this?

I'm sorry, but I don't understand the issue. The ESN dosn't have to
move monotonically forward, any more than the packet sequence numbers
do. You assign bytes sequence numbers in a 64-bit rather than 32-bit
space and only transmit the low-order 32 bits in the packet.

By way of illustration, let's work in 16-bit space with an 8-bit
sequence number in the packet. 

1. A transmits bytes 0x00f0 - 0x0101  (packet sn 0xf0)  [lost]
2. A transmits bytes 0x0101 - 0x0111  (packet sn 0x01)
3. A retransmits bytes 0x00f0 - 0x0101 (packet sn 0xf0)

> #3 allows packets to be reordered without loss during key rollover, and
> is not susceptible to the burst-losses of #2
> Note that #2 should not 'insert a key into the TSAD' - that interface
> should be under the exclusive control of the KMS - at which point asking
> the KMS to keep that info (or bury it in the TSAD where the KMS can
> refer to it) seems sufficient.

Well, again I think this whole notion of the TSAD is an abstraction
which is confusing rather than clarifying. Let's try walking through
the situation we actually have to deal with right now.

1. The user configures a single static key that applies to 
   all connections between some set of host/port quartets
2. When a connection is instantiated, that single static key
   has to somehow get diversified into a per-connection key
   that gets attached to that connection.
3. If the user configures a new key, that needs to get noticed
   and a new set of diversified per-connection keys needs to
   be attached.

Thinking of this as a database with various portions of the system
having read/write access seems to me only to confuse the issue.

I suggest we discuss what bits on the wire we expect to have
and then we can discuss what model is best to describe it.

1. The user establishes a key, which we'll call key 9 with value K_9
   and sets it for all connections between* (remote) and (local).

2. Host sends a SYN to with ISN X.
   This packet is protected with a key computed as:

   k_i = PRF(K_9,, 911,, 555, X, 0).
   This packet has key-id 9.

3. Host sends a SYN/ACK to
   with ISN Y.

   This packet is protected with a key computed as:

   k_j = PRF(K_9,, 555,, 911, Y, X).
   This packet has key-id 9.

4. Host sends an ACK to with ISN X.
   This packet is protected with a key computed as:

   k_k = PRF(K_9,, 911,, 555, X, Y).
   This packet has key-id 9.

Future packets from -> are protected
with k_k. Packets in the reverse direction are protected with


5. Host sends an packet to with a
   sequence number of 0xfffffff0 and length 32. 
   This packet is protected with key k_k and bears key-id 9.

6. Host sends a packet to with 
   a sequence number of 0x00000010 (the successor to packet

   This packet is protected with a key computed as:

   k_l = PRF(k_k,, 911,, 555, X, Y).
   This packet has key-id 9.

7. The packet sent in 5 is lost and so must be retransmitted.
   It is protected with key k_k.

So, two salient points:
1. When the sequence number is in the region of 0 (more precisely
   while there are unacked segments on both sides of the region),
   then the sides must maintain two keys and arrange to use
   the appropriate one.
2. The same key-id is used in the packet regardless of the which
   key is being used to protect the traffic. It refers to the
   static key from which the traffic keys were diversified.

We could tell a similar story about ESN handling, except you would
use the same traffic keys, but move the high order word up and down

Do you disagree that this is the right thing to have in the packets?

tcpm mailing list