[Search] [pdf|bibtex] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02                                                      
Security Working Group                               IPsec Working Group
INTERNET-DRAFT                                         J. Hughes, Editor
                                                               June 1996
                                                   Expires in Six months

    Combined DES-CBC, HMAC and Replay Prevention Security Transform

Status of this Memo

   This document is a submission to the IETF Internet Protocol Security
   (IPSEC) Working Group. Comments are solicited and should be addressed
   to the working group mailing list (ipsec@tis.com) or to the editor.

   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 draft documents are 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 learn the current status of any Internet-Draft, please check the
   "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
   Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
   ftp.isi.edu (US West Coast).

   Distribution of this memo is unlimited.


   This draft describes a combination of privacy, authentication,
   integrity and replay prevention into a single packet format.

   This document is the result of significant work by several major
   contributors and the IPsec working group as a whole. These
   contributors, cited later in this document, provided many of the key
   technical details summarized in this document.

Hughes                                                          [Page 1]

RFC DRAFT                                                      June 1996


   This draft allows a combination of MD5 and DES-CBC. In addition to
   privacy, the goal of this transform is to ensure that the packet is
   authentic, can not be modified in transit, or replayed.

   For the purpose of this RFC, the terms conformance and compliance are

   The claims of privacy, integrity, authentication, and replay
   prevention are made in this draft. A good general text describing the
   methods and algorithm are in [Schneier95].

   Privacy is provided by DES-CBC [FIPS-46] [FIPS-46-1] [FIPS-74]

   Integrity is provided by HMAC [Krawczyk96].

   Authentication is provided since only the source and destination know
   the HMAC key. If the HMAC is correct, it proves that it must have
   been added by the source.

   Replay prevention is provided by the combination of a constantly
   increasing count, the SPI and the HMAC key. The integrity of the
   replay field is provided by the HMAC.

Hughes                                                          [Page 2]

RFC DRAFT                                                      June 1996

Packet Format

 |                Security Parameters Index (SPI)                | ^
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |  ---
 |                 Replay Prevention Field (count)               | |   ^
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |   |
 |                                                               | |   |
 ~                      Payload Data                             ~ |   |
 |                                                               |HMAC |
 +               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |  DES
 |               |         Padding (0-7 bytes)                   | |  CBC
 +-+-+-+-+-+-+-+-+               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |   |
 |                               |  Pad Length   | Payload Type  | v   |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---  |
 |                                                               |     |
 ~                        HMAC digest                            ~     |
 |                                                               |     v
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+    ---

Security Parameters Index

   This field is negotiated at key setup and shall not be 0 [RFC-1825]

Replay Prevention

   Replay Prevention is an unsigned 32 bit incrementing counter starting
   at a value of 1.

   The key (K, as described in a later section) must be changed
   frequently enough so that the counter is not allowed to wrap; in
   other words, the key must be changed before (2^32)-2 packets are
   transmitted using this key. For a given SPI, counter wrapping shall
   be considered to be a replay attack. (While a wrap is a replay
   attack, there is always the possibility that a packet can get
   duplicated, so the presence of a single or small number of duplicate
   packets is not an absolute indication of a replay attack.)

   The receiver must verify that for a given SPI the packets received
   have non-repeating (non-duplicate) counter values. This can be
   implemented as a simple increasing count test or the receiver may
   choose to accept out-of-order packets as long as it is guaranteed
   that packets can be received only once. For example, an
   implementation can use a sliding receive window, the size of which is
   an implementation detail. If such a receive window is supported, the
   receiver must ensure that it will accept packets within the current

Hughes                                                          [Page 3]

RFC DRAFT                                                      June 1996

   window only once, and reject any packets it receives with a value
   that is less than the lower bound of the window.

   An example may allow the most recent 32 packets to be allowed to
   arrive out of order. That is, these 32 packets can arrive in any
   sequence relative to each other except that these packets are
   guaranteed to arrive only once. Appendix A has actual code that
   implement a 32 packet replay window and a test routine. The purpose
   of this routine is to show how it could be implemented.


   The payload contains data that is described by the payload type
   field. This field is an integral number of bytes in length; the
   following padding and pad length fields will help provide alignment
   to a double word boundary.


   The padding (pad bytes and pad length field) is used to align the
   following "payload type" field to end on a double word boundary (when
   counting from the start of the replay field).

   Padding bytes may be initialized with random data.

   At a minimum, the number of pad bytes added must be enough to align
   the payload type field on the next appropriate boundary. However, the
   sender may choose to include additional padding, provided that the
   alignment is maintained. In total, the sender can add 0-255 bytes of

Pad Length

   The pad length field indicates the number of pad bytes immediately
   preceding it. The range of valid values is 0-255, where a value of
   zero indicates that the byte immediately preceding the pad length
   field is the last byte of the payload.

Hughes                                                          [Page 4]

RFC DRAFT                                                      June 1996

Payload Type

   Describes what the payload is. The values are described in:


HMAC Digest

   The HMAC digest is a 128 bit residue described in [Krawczyk96]. This
   covers the SPI, replay, payload, padding, pad length, payload type.

   HMAC is a keyed algorithm and shall use the HMAC key as described in
   the section on keys.

Encryption Transform Procedure

   CBC chaining with an IV_key is used.

       IV_key  count|x1           x2             x3
          |        |              |              |
          |-------(+)    --------(+)    --------(+)
                   |     |        |     |        |
                -------  |     -------  |     --------
             k--| DES |  |  k--| DES |  |  k--| DES  |
                -------  |     -------  |     --------
                   |     |        |     |        |
                   |-----|        |-----|        |----...
                   |              |              |
                   y1             y2             y3

   Where count is the Replay counter. x1, x2, x3 are the plaintext (x1
   is 32 bits, all others are 64 bits). y1, y2, y3 are the ciphertext.

   The process of this transformation is comprised of the following 3

      1. Taking the data and encapsulating it with the SPI, count, pad,
      pad length, and payload type.

      2. Calculating the HMAC using the HMAC_key and creating the digest
      from the SPI, count, data, pad, pad length, and payload type and
      placing the result into the HMAC digest field.

      3. Encrypting the count, data, pad, pad length, payload type, and
      HMAC digest using DES and the appropriate DES_key_ and IV_key.

Hughes                                                          [Page 5]

RFC DRAFT                                                      June 1996

      (Note that the first DES block is a combination of the count and
      the first word of plaintext.)

Decryption Transform Procedure

   CBC chaining with an IV_key is used.

        IV_key     y1             y2             y3
          |        |              |              |
          |        |------        |------        |----...
          |        |     |        |     |        |
          |     -------  |     -------  |     --------
          |  k--| DES |  |  k--| DES |  |  k--| DES  |
          |     -------  |     -------  |     --------
          |        |     |        |     |        |
          |-------(+)    |-------(+)    |-------(+)
                   |              |              |
              (count|x1)          x2             x3

   The process of this transformation is comprised of the following 4

      1. (Optional step) Decrypt the first bock of data using the
      appropriate DES_key and IV_key and then do a quick "sanity check"
      of the count. If the count has decreased below the window or has
      increased by more than 65k, then it is safe to discard this packet
      as either a replay, non-authentic or too old. If the count is
      within 65K, then the probability that the packet is authentic is
      65535/65536. (The following replay check and HMAC check are both
      still required).

      2. Decrypt the count (if not already done), data, pad, pad length,
      and payload type using DES and the appropriate DES_key_ and

      3. Calculate the HMAC using the HMAC_key and create the digest
      from the SPI, count, data, pad, pad length, and payload type and
      checking the result at digest at the end of the packet. If the
      digest is incorrect, discard the packet.

      4. Check the count using the window algorithm discussed above. If
      the packet is duplicate or too old, discard the packet.

Hughes                                                          [Page 6]

RFC DRAFT                                                      June 1996

Key Material

   The key K is provided by the key management layer. This key is used
   to derive the symmetric keys, they are:

      DES_Key_I is the DES key for traffic from the initiator ->

      DES_Key_R is the DES key for traffic from the responder ->

      HMAC_Key is the key for the HMAC Algorithm (This is the same for
      both directions, but since these are encrypted by different DES
      keys, then this is not a problem.)

      IV_key is used to stop code book attacks on the first block.

   The vertical bar symbol "|" is used to denote concatenation of bit

   MD5(x|y) denotes the result of applying the MD5 function to the
   concatenated bit strings x and y.

   Truncate(x,n) denotes the result of truncating x to its first n bits.

      DES_Key_I = Truncate(MD5( D_Pad_I | K ),64)
      DES_Key_R = Truncate(MD5( D_Pad_R | K ),64)
      IV_Key    = Truncate(MD5( I_Pad   | K ),64)
      HMAC_Key  =          MD5( H_Pad   | K )

   where each _Pad_is 512 bit string.

      D_Pad_I = 0x5C repeated 64 times.
      D_Pad_R = 0x3A repeated 64 times.
      I_Pad   = 0xAC repeated 64 times.
      H_Pad   = 0x53 repeated 64 times.

   (Implementation note, The 16 byte intermediate residuals can be
   precalculated from these constants and stored to reduce processing

Hughes                                                          [Page 7]

RFC DRAFT                                                      June 1996

Security Considerations

   The ESP-DES-HMAC-RP transform described in this draft is immune to
   the [Bellovin96] attacks. (AH [RFC-1826], in some modes, can also
   provide immunity to these attack.)

   The implications of the size of K can be found in [Blaze96].


   [Bellovin96] Bellovin, S., "Problem Areas for the IP Security
   Protocols", AT&T Research,
   ftp://ftp.research.att.com/dist/smb/badesp.ps, July, 1996.

   [FIPS-46] US National Bureau of Standards, "Data Encryption
   Standard", Federal Information Processing Standard (FIPS) Publication
   46, January 1977.

   [FIPS-46-1] US National Bureau of Standards, "Data Encryption
   Standard", Federal Information Processing Standard (FIPS) Publication
   46-1, January 1988.

   [FIPS-74] US National Bureau of Standards, "Guidelines for
   Implementing and Using the Data Encryption Standard", Federal
   Information Processing Standard (FIPS) Publication 74, April 1981.

   [FIPS-81] US National Bureau of Standards, "DES Modes of Operation"
   Federal Information Processing Standard (FIPS) Publication 81,
   December 1980.

   [Krawczyk96] Krawczyk, H., Bellare, M., Canetti, R., "HMAC-MD5:
   Keyed-MD5 for Message Authentication", work-in-progress,
   hmac-md5-00.txt, March, 1996

   [Maughan96] Maughan, D., Schertler, M. Internet Security Association
   and Key Management Protocol (ISAKMP), work-in-progress,
   isakmp-04.txt, February, 1996

   [Orman96] Orman, H., "The Oakley Key Determination Protocol", work-
   in-progress, http://info.internet.isi.edu:80/in-drafts/files/draft-
   ietf-ipsec-oakley-00.txt, February, 1996.

Hughes                                                          [Page 8]

RFC DRAFT                                                      June 1996

   [RFC-1825] Atkinson, R, "Security Architecture for the Internet
   Protocol", ftp://ds.internic.net/rfc/rfc1825.txt, August 1995.

   [RFC-1826] Atkinson, R, "IP Authentication Header",
   ftp://ds.internic.net/rfc/rfc1826.txt, August 1995.

   [Schneier95] Schneier, B., "Applied Cryptography Second Edition",
   John Wiley & Sons, New York, NY, 1995.  ISBN 0-471-12845-7

   [Blaze96] Blaze M., Diffie, W., Rivest, R., Schneier, B., Shimomura,
   T., Thompson, E., Wiener, M., "Minimal Key Lengths for Symmetric
   Ciphers to Provide Adequate Commercial Security",
   http://theory.lcs.mit.edu/~rivest/bsa-final-report.ascii, January,


   This document is the result of significant work by several major
   contributors. They include (in alphabetical order):

        Robert W. Baldwin
        RSA Labs.

        Kevin Kingdon
        RSA Labs

        Hugo Krawczyk
        IBM Corporation

        Perry Metzger
        Piermont Information Services

        Phil Rogaway
        University of California at Davis

        Bill Simpson
        Computer Systems Consulting Services

Hughes                                                          [Page 9]

RFC DRAFT                                                      June 1996

        David A Wagner
        University of California at Berkeley

   In addition, the contributions of the entire IPSEC Working Group are

   The IPsec working group can be contacted through the chairs:

        Ran Atkinson
        Cisco Systems

        Paul Lambert
        Oracle Corporation

Editor's Address

   James P. Hughes
   Network Systems Corporation

Hughes                                                         [Page 10]

RFC DRAFT                                                      June 1996

Appendix A

   This is a routine that implements a 32 packet window. This is
   intended on being an implementation sample.

#include <stdio.h>
#include <stdlib.h>
typedef unsigned long u_long;

enum {
    ReplayWindowSize = 32

u_long bitmap = 0;          /* session state - must be 32 bits */
u_long lastSeq = 0;         /* session state */

/* Returns 0 if packet disallowed, 1 if packet permitted */
int ChkReplayWindow(u_long seq);

int ChkReplayWindow(u_long seq) {
    u_long diff;

    if (seq == 0) return 0; /* first == 0 or wrapped */
    if (seq > lastSeq) {    /* new larger sequence number */
        diff = seq - lastSeq;
        if (diff < ReplayWindowSize) { /* In window */
            bitmap = (bitmap << diff) | 1; /* set bit for this packet */
        } else bitmap = 1;  /* This packet has a "way larger" */
        lastSeq = seq;
        return 1;           /* larger is good */
    diff = lastSeq - seq;
    if (diff >= ReplayWindowSize) return 0; /* too old or wrapped */
    if (bitmap & (1 << diff)) return 0; /* this packet already seen */
    bitmap |= (1 << diff);  /* mark as seen */
    return 1;               /* out of order but good */

Hughes                                                         [Page 11]

RFC DRAFT                                                      June 1996

char string_buffer[512];
#define STRING_BUFFER_SIZE sizeof(string_buffer)

int main() {
    int result;
    u_long last, current, bits;

    printf("Input initial state (bits in hex, last msgnum):\n");
    if (!fgets(string_buffer, STRING_BUFFER_SIZE, stdin)) exit(0);
    sscanf(string_buffer, "%lx %lu", &bits, &last);
    if (last != 0)
    bits |= 1;
    bitmap = bits;
    lastSeq = last;
    printf("bits:%08lx last:%lu\n", bitmap, lastSeq);
    printf("Input value to test (current):\n");

    while (1) {
        if (!fgets(string_buffer, STRING_BUFFER_SIZE, stdin)) break;
        sscanf(string_buffer, "%lu", &current);
        result = ChkReplayWindow(current);
        printf("%-3s", result ? "OK" : "BAD");
        printf(" bits:%08lx last:%lu\n", bitmap, lastSeq);
    return 0;

Hughes                                                         [Page 12]