[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01

INTERNET DRAFT          EXPIRES JAN 1999        INTERNET DRAFT
Network Working Group                                         G. Caronni
INTERNET DRAFT                                              M. Waldvogel
                                                  TIK, ETHZ, Switzerland
Category: Informational                                        July 1998


                        The ESP Stream Transform
                     <draft-caronni-esp-stream-01.txt>



Status of This Memo

This document is an Internet-Draft.  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."

To view the entire list of current Internet-Drafts, please check
the "1id-abstracts.txt" listing contained in the Internet-Drafts
Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net
(Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au
(Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu
(US West Coast).


Distribution of this document is unlimited.


Abstract
--------
This document describes a security transform providing privacy and
optional replay protection through Encapsulating Secure Payload (ESP).
The transform defines how to use ESP in conjunction with byte-oriented
stream ciphers, such as RC4 or SEAL. These stream ciphers offer strong
encryption with comparatively low computational demands, and are thus
favorable for multimedia bulk data or environments where the computing
power needed per packet should be low.





Table of Contents
-----------------
1.   Introduction
1.1.   Conventions
1.2.   Cipher Overview
2.   Payload Format
2.1.   Stream Offset
2.2.   Replay Protection Using the Stream Offset
2.3.   Authentication Issues
3.   Encryption
4.   Decryption
5.   Security Considerations
6.   Implementation Details



Caronni, Waldvogel           Informational                      [Page 1]


6.1.   Summary of Limits
6.2.   Technical Notes
7.   Acknowledgements
8.   References
9.   Author Addresses

1.  Introduction
----------------
The mechanisms presented in this document provide confidentiality and
optional replay protection for IP datagrams, using the Encapsulating
Security Payload (ESP) [RFC1827] format. Although ESP may also provide
data integrity and authenticity, 'esp-stream' only offers encryption.

This document assumes that the reader is familiar with the related docu-
ment "Security Architecture for the Internet Protocol" [RFC1825], which
defines the overall security plan for IP and provides important back-
ground. Additionally, familiarity with "IP Encapsulating Security Pay-
load (ESP)" [RFC1827] is required, as some of the mechanisms employed
here are described in greater depth in that document.

1.1.  Conventions
-----------------
There are a few conventions we followed in this document that the reader
should be aware of:

a) Whenever it is said that something is ``LIMITED'', the appropriate
   maximum and minimum values plus a set of recommended values are given
   in section 6.1.

b) The meanings of capitalized ``MUST'', ``MUST NOT'', ``SHOULD'', and
   ``MAY'' apply as declared in [RFC1825].

c) Variables and constants in pseudo code are in ALL CAPITALS, to
   clearly distinguish actual code symbols from the description of the
   action.

1.2.  Cipher Overview
---------------------
Fast algorithms, such as RC4 (devised by Ron Rivest) or SEAL (by Phil
Rogaway and Don Coppersmith) are very efficient and easily understand-
able symmetric additive stream ciphers with a large internal state. The
efficiency with which they operate make them ideal candidates for
encrypting/decrypting high-throughput, low-latency data streams in
software with relatively low CPU usage or just whenever low CPU overhead
for security is needed. Such data streams are very common in modern
multi-media applications who transmit video data and/or high quality
audio data. RC4 has been used (together with SKIP prototypes) to encrypt
interactive video connections over IP. Resulting quality was adequate



Caronni, Waldvogel           Informational                      [Page 2]


and acceptable.

For all stream ciphers, key lengths of up to and including 128 bits MUST
be supported by the implementation, although any particular key may be
shorter. Longer keys are strongly recommended.

RC4 allows for key sizes of up to 256 bytes. The key is used to permute
the values of 0 to 255 in an array of 256 entries, thus creating the
internal state for the pseudo random generator, whose output is used as
a one time pad for encryption/decryption. The initial state after keying
can thus be one out of 256! states, being equivalent to about 1676 bits
key state.

SEAL supports position-dependent key setup, expects 160 bits of key
material and allows initializing at any 32 bit offset into the stream.
SEAL may in certain environments be even faster than RC4. Key setup in
SEAL is much more expensive, as SHA is employed to generate the internal
state.

For more details about RC4, SEAL, and about using other stream ciphers,
refer to [Schn96]. Please note that SEAL is being patented by IBM, and
RC4, although interoperable code is available, is a proprietary algo-
rithm of RSA Data Security Inc. RC4 is trademarked by RSA DSI, anybody
contemplating its use should contact them.

2.  Payload Format
------------------
The following diagram describes the basic format of IP packets contain-
ing the 'esp-stream' header and data. The selection of the actual stream
cipher and the key to be used has to take place on a upper layer.

|<----           Plain                ---->|<----  Encrypted  ---->|
+-----------+-----------------+------------+----------------+------+
| IP Header | IP Ext. Headers | ESP Header | Encrypted Data | Type |
+-----------+-----------------+------------+----------------+------+


A more detailed diagram of the format of the particular ESP Header
(labelled ``E'' in the left column shown in diagram below) to be used
with stream ciphers and the data following it (Data labelled ``D'', Type
labelled ``T'') is given below, together with a short description of
every field.

  |1 2 3 4 5 6 7 8|1 2 3 4 5 6 7 8|1 2 3 4 5 6 7 8|1 2 3 4 5 6 7 8|
- +---------------+---------------+---------------+---------------+
E |                Security Parameters Index (SPI)                |
E +---------------------------------------------------------------+
E |                        Stream Offset                          |



Caronni, Waldvogel           Informational                      [Page 3]


- +---------------------------------------------------------------+
D |                                                               |
D :       Encrypted Payload Data (arbitrary number of bytes)      :
D |                                                               |
D |                               +---------------+---------------+
T |                               | Payload Type  |
- +-------------------------------+---------------+

Notes
-----
Security Parameters Index (SPI)
     A 32-bit value identifying the Security Parameters for this
     datagram (network order). The value MUST NOT be zero.

Stream Offset (32 bits, optionally 64 bits)
     Indicates the number of data bytes already encrypted under the
     current key for this cipher before this packet was encrypted. This
     value is stored in network order (most significant octet first)
     [RFC1700]. For details, see section 2.1.

Encrypted Payload Data (arbitrary number of bytes)
     Encapsulated IP or other protocol data, encrypted. No padding is
     required.

Payload Type (8 bits)
     Contains the encrypted type of the next protocol header in the
     encrypted payload data. Up-to-date values of the IP
     Protocol/Payload are specified in the most recent "Assigned
     Numbers" [RFC1700]. This value is encrypted together with the pay-
     load, and may only be examined after decryption.

2.1.  Stream Offset
-------------------
The recommended Stream Offset field size is 32 bits. Applications MAY
however choose to implement a 64 bit Stream Offset field. It is the task
of the upper layer (e.g. the key management protocol) to decide which of
the two solutions is being used for a given connection. See also section
6.2.

Current stream ciphers were not designed for integration in IP.  There-
fore, provisions for detecting and handling out of order delivery,
duplicate or missing packets must be taken additionally. The Stream
Offset field is used at the receiving end to prepare the ciphers inter-
nal state such that decrypting is possible even in case of abovemen-
tioned events.

To make this possible, the receiver MUST be able to accept packets with
Stream Offset being a LIMITED number of bytes ahead or before the



Caronni, Waldvogel           Informational                      [Page 4]


previously received Stream Offset.

The sender MUST count all bytes encrypted before the first byte in this
packet is encrypted and send this value as this packet's Stream Offset.
The counter MUST be initialized with zero when the encryption key is
used the first time. It MUST be reset to zero if and only if the
encrypting key changes. It MUST NOT be reset at any other time.  Espe-
cially, it MUST NOT be allowed to wrap around to zero, the encryption
key MUST be changed instead. It is most important (see security con-
siderations in section 5), that no encrypting key is used with the same
Stream Offset twice. Thus, after the encrypting key has been changed,
the probability for its reuse MUST be as small as practically feasible.
Ideally, an old encryption key SHOULD NOT be reused ever.

The sender MAY encrypt a LIMITED number of dummy bytes between packets,
although this is discouraged, because it would use more cache space at
the receiver.

2.2.  Replay Protection Using the Stream Offset
-----------------------------------------------
Since the sender creates Stream Offsets so that for any two packets
encrypted with the same key their ranges [Stream Offset .. (Stream
Offset + Encrypted Bytes in Packet - 1)] are free of intersections, the
receiver may optionally check this range independence to protect against
replay attacks. The receiving end may independently decide whether
replay protection is to be performed or not, it is not mandatory that
the sender be involved in this decision. Doing replay protection on the
receiving side is strongly recommended.

To achieve Replay Protection, the receiver has to remember the ``holes''
in the Stream where incoming packets may still be accepted. For each
currently employed key, a LIMITED list of valid Stream Offset ranges has
to be stored. They cover the range starting from the end of the
`highest' received packet up to the maximum offset, and ranges where
packets have not yet been delivered (e.g. were lost in transit or will
be delivered out of order). In section 4 we will give pseudo code that
implements replay protection for the receiving end, at the same time
allowing for reception of out of order packets.

2.3.  Authentication Issues
---------------------------
Authentication is not included into the 'esp-stream' transform, mainly
because of the following points:

a) The main reason to employ stream ciphers such as RC4 or SEAL is the
   remarkable speed of these algorithms. MD5 software speeds are ade-
   quate for commonly deployed LAN and WAN links, but reportedly are too
   slow for newer link technologies [RFC1810]. If faster implementations



Caronni, Waldvogel           Informational                      [Page 5]


   emerge, their use is strongly recommended, as encryption without
   authentication offers only a very limited amount of security.

b) Authentication may be chosen as an orthogonal transform in addition
   to this transform, so users have the ability to choose the authenti-
   cation that best fits necessities in speed and security at runtime.

3.  Encryption
--------------
Procedural description of the encryption process:

Encrypt packet:
    Prepare sufficient space before and after the payload;
    Append a Payload Type byte describing the type of encapsulated data;
    Store the SPI in the SPI field;
    Get the current internal state associated with this security association;
    Store the number of data bytes already encrypted with the current key
      into the Stream Offset field;
    Encrypt the payload and the Payload Type byte, updating the internal state;
    Generate outer headers such as AH or IP;
    Send packet;

4.  Decryption
--------------
Pseudo code to allow efficient handling of out of order packet reception
and packet loss including replay protection is given below.  To remember
the range of Stream Offsets already used by the received packets, a set
of 3-tuples for each packet key is stored. It contains start of used
range, end of used range (=start+length, effectively being start of next
expected packet), and cipher internal state associated with the Stream
Offset of the packet that would immediately follow.

If no protection against replay attacks is required, the following
pseudo code may be simplified. We strongly recommend using replay pro-
tection, as the additional cost is low and the benefits are large.

FORWARD_SEEK_LIMIT and STATE_CACHE_ENTRIES are defined in section 6.1,
DATA_SIZE includes the actual Payload size and the one byte Payload Type
field.

Key initialization (input: KEY):
    Set INTERNAL_STATE to the result of prepare_key(KEY);
    Store tuple (0, 0, INTERNAL_STATE);
    Return;

Decrypt packet (input: ESP_HEADER, ESP_DATA, DATA_LENGTH):
    Process all outer headers;
    Set START to Stream Offset found in ESP_HEADER;



Caronni, Waldvogel           Informational                      [Page 6]


    Set END to START + DATA_LENGTH;
    If intersection between [START..END] and any stored range {
        Drop packet and return; // Replay, garbage, or duplicate packet
    }
    Set PREDECESSOR to tuple with biggest end <= START;
    If no PREDECESSOR was found {
        Drop packet and return; // Packet too old
    }
    If START minus PREDECESSOR.END is greater than FORWARD_SEEK_LIMIT {
        Drop packet and return; // Too far out in ``future'' key stream
    }
    If START equals PREDECESSOR.END {
        Set WORK to PREDECESSOR;
    } else {
        // Seek forward to a new IV
        Duplicate of PREDECESSOR.IV, call it TEMP_IV;
        Run rc4 on PREDECESSOR.END-START dummy bytes
          with TEMP_IV, updating it;
        Store new tuple WORK = (START, START, TEMP_IV);
    }
    // We have a tuple just preceding ours,
    // extend it by our newly received range
    decrypt with WORK.IV, updating the IV;
    Set WORK.END to END;
    If there is a tuple NEIGHBOR whose start == END {
        // join the two ranges into one
        Set NEIGHBOR.START to WORK.START;
        Delete WORK;
    }
    If more than STATE_CACHE_ENTRIES tuples are stored {
        // delete the first (oldest) hole.
        Set START of the first remaining tuple to 0;
    }
    Get Payload Type;
    If Payload Type is valid {
        Process packet according to payload type and return;
    } else {
        Drop the packet and return;
    }


It is suggested that a new tuple (with extended range) is only stored if
the incoming packet is correctly authenticated. Alternatively, if no
authentication is required, it may also be stored if the packet decrypts
correctly (i.e. passes some integrity tests, such as a valid TCP or UDP
checksum in inner headers). This is to prevent denial of service attacks
involving excessive seeking in the key stream. In the case a packet
fails the verification the packet MUST be dropped.



Caronni, Waldvogel           Informational                      [Page 7]


5.  Security Considerations
---------------------------
One goal of this document is to allow different implementors of the
stream cipher RC4 to interoperate securely. Some of the security con-
siderations discussed here hold true for other ciphers.

Do NOT re-use key material. Do not use previous keys to generate new
keys, but use a reliable and well-initialized random number generator to
generate new keys. See [RFC1750] for additional information. If you do
re-use key material, the security of a stream cipher is instantly lost.

Remove all information belonging to old keys whenever they become
invalid, including information held in caches, especially the ``hole''
cache. The key management protocol in the upper layer has to decide when
a key becomes invalid.

As pointed out in [Roos95], there are classes of weak keys (especially
those whose first two bytes are two's complements of each other), which
SHOULD be avoided in RC4.

Since the first few bytes generated after the initial setup of the RC4
are those easiest cryptanalized and broken (see [Roos95a, Roos95b]), we
recommend that the sender SHOULD encrypt a LIMITED number of dummy bytes
(updating the internal state and the Stream Offset accordingly) before
starting to send packets. Receivers must be prepared to accept a first
packet with a Stream Offset that is equal to a LIMITED number of bytes
above zero.

We strongly recommend using authentication if your security requirements
are high and you want to protect against active attacks, such as those
described in [Bell96]. This paper also gives a good overview over the
risks and open security problems that need to be taken into considera-
tion.

6.  Implementation Details
--------------------------
6.1.  Summary of Limits
-----------------------
In the following table we show up to three values or ranges for every
variable: the minimum supported number (what each implementation MUST
support), some recommended values (what implementations SHOULD use), and
a maximum that MUST NOT be exceeded. The column ``Who'' indicates
whether the sender (S) or the recipient (R) or both need to support
these limits. Values are given in bytes, except where otherwise noted.



Name                          Who   Minimum   Recommended   Maximum



Caronni, Waldvogel           Informational                      [Page 8]


                                     (MUST)      (SHOULD)
Key length (bits)             SR        128   128 .. 2048      2048
Initial forward seek          S           0    16 .. 1024       64K
Initial forward seek          R         64K
Forward seek per packet       R               32K .. 200K      512K
Backward history              R               16K .. 100K
State cache entries per key   R                   4 .. 16


Notes
-----
Key length
     indicates the number of bits that an implementation must support,
     although the use of shorter keys may be required in certain cir-
     cumstances.

Initial forward seek
     indicates the number of bytes the sender should seek forward before
     encrypting the first packet. The receiver must accept a packet
     encrypted with a new key with Stream Offsets going up to the value
     of ``initial forward seek''. Be aware that the first packet
     encrypted with the new key can get lost, so that senders can not
     exploit the full limit on ``initial forward seek'' that receivers
     have.

Forward seek per packet
     indicates the amount of bytes that the receivers allows the Stream
     Offset of two succeeding packets to be apart, thus restricting the
     amount of forward or backward seeking that may be performed.  Oth-
     erwise, a denial of service attack could be easily mounted by forc-
     ing the receiver to do exhaustive seeking in the cipher key stream.

Backward history
     indicates the amount of past bytes for which the receiver should be
     able to reconstruct the internal state of any ``hole'' (needed for
     out of order delivery).

State cache entries per key
     is the recommended number of previous internal states a receiver
     should keep. Under normal circumstances this is enough to provide
     good coverage of swapped and delayed packets.

6.2.  Technical Notes
---------------------
To prevent getting a blocked channel whenever packets are received out
of order, receivers SHOULD maintain multiple internal states for the
stream cipher, and handle these conditions gracefully.




Caronni, Waldvogel           Informational                      [Page 9]


It is also suggested, that the stream cipher is rekeyed frequently
(after short amounts of elapsed time) so that connections can easily
recover after excessive blocks of data have been lost. Otherwise the
limit on forward seeking at the receiving end might block the connec-
tion.

Seeking forward by n bytes in the cipher keystream is identical to
encrypting that many dummy bytes. Forward seeks may be optimized by
creating a dedicated procedure which only implements the relevant parts
of the algorithm. Sophisticated solutions may want to add the capability
for backward seeking in algorithms where this is possible (such as RC4),
and can then use the nearest stored state to seek to the needed posi-
tion. When algorithms (such as SEAL) are used, where the current posi-
tion in the stream can be set, use of this functionality is strongly
encouraged.

A Stream Offset field with a size of 32 bits wraps around about once
every 15 minutes for e. g. multimedia traffic of about 40 Mbit/sec as it
was observed during a distance learning project with several high-
quality audio/video streams at ETHZ. In view of these figures, and with
the increase in throughput that may be expected in the future, it seems
thus reasonable to optionally allow the use of a 64 bit Stream Offset
field. Larger Stream Offset fields do not make sense, given the short
life time of bulk data keying material.

Various other ciphers could be used together with this draft, even block
ciphers such as DES in CFB or OFB mode, where the Stream Offset would be
used as an initialisation vector. The key management solution that wants
to employ stream ciphers needs to specify e.g. the following data:
Traffic Encryption
Algorithm Number  Algorithm Name   Key Size   Stream Offset Size
7                 RC4              128        64 bit
8                 RC4              40         32 bit
9                 SEAL             128        32 bit
This is an example only, relevant information may be found in the
specifications for key management solutions.

7.  Acknowledgements
--------------------
We express our gratitude to Ron Rivest for pointing out legal aspects
relating to our original `alleged RC4' draft, and, nevertheless, for
devising such a simple and elegant cipher such as RC4.

In no particular order we would also like to thank the following people
for various important contributions, source code, comments and all other
kinds of involvement: Ran Atkinson, Christian Schneider, Michael Hauber,
Ashar Aziz, Tom Markson, Martin Patterson, Josef Reveane, Rich Skrenta,
Roy Schneider, Derek Palma, Terry Davis, and the authors of the RFCs



Caronni, Waldvogel           Informational                     [Page 10]


1826, 1828 and 1851 (see References below), from which many ideas were
used.


8.  References
--------------

Bell96  S. Bellovin, "Problem Areas for the IP Security Protocols", sub-
        mitted to the Sixth USENIX Unix Security Conference, draft
        available from ftp://ftp.research.att.com/dist/smb/badesp.ps.

RFC1700 J. Reynolds, J. Postel, "ASSIGNED NUMBERS", 10/20/1994, RFC
        1700.

RFC1750 D. Eastlake, S. Crocker, J. Schiller, "Randomness Recommenda-
        tions for Security", 12/29/1994, RFC 1750.

RFC1810 J. Touch, "Report on MD5 Performance", 06/21/1995, RFC 1810.

RFC1825 R. Atkinson, "Security Architecture for the Internet Protocol",
        08/09/1995, RFC 1825.

RFC1826 R. Atkinson, "IP Authentication Header", 08/09/1995, RFC 1826.

RFC1827 R. Atkinson, "IP Encapsulating Security Payload (ESP)",
        08/09/1995, RFC 1827.

RFC1828 P. Metzger, W. Simpson, "IP Authentication using Keyed MD5",
        08/09/1995, RFC 1828.

RFC1851 P. Metzger, P. Karn, W. Simpson, "The ESP Triple DES-CBC
        Transform", 10/02/1995, RFC 1851.

Roos95a A. Roos <andrewr@vironix.co.za>, "Weak Keys in RC4", Posted to
        the Cypherpunks mailing list on Sep 22, 1995, see
        http://turing.vironix.co.za/public/andrewr/WeakKeys1.htm

Roos95b A. Roos <andrewr@vironix.co.za>, "Weak Keys in RC4", Posted to
        the Cypherpunks mailing list on Sep 29, 1995, see
        http://turing.vironix.co.za/public/andrewr/WeakKeys2.htm

Schn96  B. Schneier, "Applied Cryptography: Protcols, Algorithms, and
        Source Code in C (second edition)", John Wiley & Sons, New York,
        1996.

9.  Author addresses
--------------------
Questions and comments about this memo can be directed to:



Caronni, Waldvogel           Informational                     [Page 11]

   Germano Caronni (formerly with:)
   Computer Engineering and Networks Laboratory
   Swiss Federal Institute of Technology (ETH)
   ETH Zentrum
   CH-8092 Zurich

   gec@acm.org


   Marcel Waldvogel
   Computer Engineering and Networks Laboratory
   Swiss Federal Institute of Technology (ETH)
   ETH Zentrum
   CH-8092 Zurich

   waldvogel@tik.ee.ethz.ch
INTERNET DRAFT          EXPIRES JAN 1999                INTERNET DRAFT


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/