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

Versions: 00 01                                                         
Network Working Group                           W A Simpson [DayDreamer]
Internet Draft
expires in six months                                          July 1998


                 ESP with Cipher Block CheckSums (CBCS)
                       draft-simpson-cbcs-01.txt


Status of this Memo

   This document is an Internet-Draft.  Internet Drafts are working doc-
   uments of the Internet Engineering Task Force (IETF), its Areas, and
   its Working Groups.  Note that other groups may also distribute work-
   ing 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 not appropriate to use Internet Drafts as refer-
   ence material, or to cite them other than as a ``working draft'' or
   ``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 (Northern Europe)
      ftp.nis.garr.it (Southern Europe)
      ftp.ietf.org (Eastern USA)
      ftp.isi.edu (Western USA)
      munnari.oz.au (Pacific Rim)

   Distribution of this memo is unlimited.

Copyright Notice

   Copyright (C) William Allen Simpson (1994-1995, 1997-1998).  All
   Rights Reserved.

Abstract

   This document describes the Cipher Block Chaining mode with addi-
   tional single or double parallel CheckSums for integrity, used with a
   number of Internet Encapsulating Security Payload (ESP) transforms.
   This version is described in terms of 64-bit block ciphers, but can
   be expanded to other block sizes.




Simpson                   expires in six months                 [Page i]


DRAFT                           CBCS mode                      July 1998


1.  Introduction

   The Encapsulating Security Payload (ESP) [RFC-1827x] provides confi-
   dentiality for IP datagrams by encrypting the payload data to be pro-
   tected.  This specification describes the ESP use of the Cipher Block
   Chaining (CBC) mode, with an added checksum for integrity.

   CBC is used to mask patterns of identical blocks within the same
   datagram.  Together with an Initialization Variable (IV) that is dif-
   ferent for every datagram, identical plaintext payloads will each
   encrypt to different ciphertext payloads.  As an added benefit, when
   the cipher output is effectively random in appearance (a characteris-
   tic of a good cipher), masking the plaintext with previous ciphertext
   will easily strengthen the entropy of the next input to the cipher.

   A pair of checksums are added to detect changes to the ciphertext,
   providing a modest degree of integrity in a single pass over the
   data, rather than using a separate pass with a stronger algorithm.
   This combination is intended to be reasonably simple to implement,
   either serially in software or in parallel hardware for performance.

   Although a simple checksum over multiple blocks would not normally be
   considered cryptographically secure, the use of a cipher in the mid-
   dle provides a background of highly random internal chaining.  These
   random blocks are used as a masking function to inhibit determination
   of the internal state of the checksums.

   CBC was first defined for DES in [FIPS-81], and generalized by
   [ISO-8732] and [ISO/IEC-10116].  For a technical exposition on CBC,
   see [MOV97].  For more explanation and implementation information for
   CBC, and a useful comparison with other modes of operation, see
   [Schneier95].

   Although this algorithm is described in terms of 64-bit (8 byte)
   blocks with 128-bit (16 byte) internal chaining values, this could be
   expanded to other block sizes.


1.1.  Design Goals

   Unlike the CBC stream orientation, CBCS is intended from its incep-
   tion to be used with the Internet Protocol (IP) datagram network.
   This environment provides specific limitations on the scope of vul-
   nerability.

   Each IP datagram has a length limitation of 576 bytes, unless a
   larger size is explicitly indicated by the transport layer.  Future
   IP versions extend this length to 1500 bytes.  The CBCS integrity is



Simpson                   expires in six months                 [Page 1]


DRAFT                           CBCS mode                      July 1998


   designed to reliably detect any multiple bit change within the
   11,680-bit payload, with an order of at least 1/2**16 probability of
   failure.  This is considerably stronger than the 1/2**7 probability
   provided by the IP, TCP and UDP checksums.

   Given that ESP provides a Sequence Number range of 2**32-1, and the
   window of acceptable values is in the range 2**5 to 2**8, CBCS is
   intended to be computationally infeasible to predictably and unde-
   tectably modify a datagram in transit during the time provided by the
   communication bandwidth-delay product.

   Software processing cost should be less than half as much as crypto-
   graphic hashing algorithms (such as MD5 or SHA1) on a little-endian
   machine, much better on a 32-bit big-endian machine, and nearly neg-
   ligible on a 64-bit big-endian machine.

   Hardware performance will benefit from the removal of multiple algo-
   rithm passes over the same data.  The hardware resources required are
   considerably less than required for MD5 or SHA1.


1.2.  Primary CheckSum

   The primary checksum involves feed-forward through the encryption
   function, in the same fashion as CBC, through XOR with the plaintext.
   Any single or multiple bit change in a cipher block (or the datagram
   IV) will result in a large unpredicatable change to all following
   cipher blocks.

   The primary checksum may be used alone.  Its strength is based on an
   integrity secret-key, the related blocksize of the cipher, and is
   dependent on the strength of the cipher itself.


1.3.  Secondary CheckSum

   The secondary checksum involves only the checksum of successive
   ciphertext blocks.  Any single bit change in a cipher block (or the
   datagram IV) will result in a small unpredicatable change to all fol-
   lowing cipher blocks.  Multiple bit changes in carefully chosen pairs
   can be used to reduce the unpredictability.

   The secondary checksum is probably too weak to be used alone.  Its
   strength is based on an integrity secret-key, the related blocksize
   of the cipher, and the unpredictability of the cipher output.

   However, it can be combined with the primary checksum to double the
   amount of internal chaining for the integrity function.



Simpson                   expires in six months                 [Page 2]


DRAFT                           CBCS mode                      July 1998


2.  Description

              IVa     P1              P2              Pi
               |      |               |               |
            +-----+   v   +-----+     v   +-----+     v
        Sa->|  S  |->(X)->|  S  |->->(X)->|  S  |->->(X)->
            +-----+   |   +-----+     |   +-----+     |
                      v      ^        v      ^        v
                   +-----+   ^     +-----+   ^     +-----+
                k->|  E  |   ^  k->|  E  |   ^  k->|  E  |
                   +-----+   ^     +-----+   ^     +-----+
                      |      ^        |      ^        |
              IVb     +->->->+        +->->->+        +->->->
               |      |               |               |
            +-----+   v   +-----+     v   +-----+     v
        Sb->|  S  |->(X)->|  S  |->->(X)->|  S  |->->(X)->
            +-----+   |   +-----+     |   +-----+     |
                      v      ^        v      ^        v
                      +->->->+        +->->->+        +->->->
                      |               |               |
                      C1              C2              Ci

   The Cipher Block CheckSums (CBCS) mode is a simple variant of the CBC
   mode [RFC-wwww].

   For each datagram, the checksums are initialized with separate seeds
   (Sa, Sb).  An Initialization Variable (IV) is split into two parts
   (IVa, IVb) which are separately summed into the primary and secondary
   checksums respectively.

   The primary checksum output XOR masks (X) the first plaintext block
   (P1).  The keyed encryption function (Ek) is followed by another XOR
   mask (X) with the secondary checksum output, which generates the
   ciphertext (C1) for the block.

   For successive blocks, the previous output of the encryption function
   (before masking) is summed into the primary checksum, and the previ-
   ous ciphertext block (after masking) is summed into the secondary
   checksum.  The primary checksum output XOR masks (X) the current
   plaintext (Pi).  The keyed encryption function (Ek) is followed by
   another XOR mask (X) with the secondary checksum output, which gener-
   ates the ciphertext (Ci) for that block.









Simpson                   expires in six months                 [Page 3]


DRAFT                           CBCS mode                      July 1998


                      C1              C2              Ci
                      |               |               |
              IVb     +->->->+        +->->->+        +->->->
               |      |      v        |      v        |
            +-----+   v   +-----+     v   +-----+     v
        Sb->|  S  |->(X)->|  S  |->->(X)->|  S  |->->(X)->
            +-----+   |   +-----+     |   +-----+     |
                      v               v               v
                      +->->->+        +->->->+        +->->->
                      v      v        v      v        v
                   +-----+   v     +-----+   v     +-----+
                k->|  D  |   v  k->|  D  |   v  k->|  D  |
                   +-----+   v     +-----+   v     +-----+
              IVa     v      v        v      v        v
               |      |      v        |      v        |
            +-----+   v   +-----+     v   +-----+     v
        Sa->|  S  |->(X)->|  S  |->->(X)->|  S  |->->(X)->
            +-----+   |   +-----+     |   +-----+     |
                      P1              P2              Pi

   To decrypt, the order of the manipulations is reversed (as shown).

   Design Notes:

      The (X) is a crude symbol indicating XOR of the two blocks, but
      the checksum block is passed unaltered to the next checksum stage.

      The checksums could be seeded with the encryption key.  However,
      additional keying material is relatively easy to generate, and
      should provide an increase in the security of the integrity check.

      Commonly, only one IV of the block size is available.  The check-
      sums could both use the same IV, but separate IVs should provide
      an increase in the security.

      Using the plaintext was considered as the addend to the secondary
      checksum, but this was rejected in fear of revealing some bits of
      the plaintext, or a cipher relationship between the plaintext and
      the ciphertext.


3.  Initialization Variable

   CBCS requires an Initialization Variable (IV).  The IV conceals ini-
   tial blocks that repeat in multiple datagrams.

   For ESP, each datagram generates its IV from material carried in the
   datagram.  This ensures that decryption of the received datagram can



Simpson                   expires in six months                 [Page 4]


DRAFT                           CBCS mode                      July 1998


   be performed, even when some datagrams are lost, duplicated, or re-
   ordered in transit.

   For 64-bit block ciphers:

      The primary 64-bit IVa is generated from the 32-bit Security
      Parameters Index (SPI) field followed by (concatenated with) the
      32-bit Sequence Number (SN) field.  Then, the bit-wise complement
      of the 32-bit Sequence Number (SN) value is XOR'd with the first
      32-bits (SPI):

         (SPI ^ -SN) || SN

      The secondary 64-bit IVb is the complement of IVa:

         (-SPI ^ SN) || -SN

      The SPI and SN are processed in big-endian order.  That is, the
      most significant byte is the first byte in network transmission
      order.

   Security Notes:

      Each IV is intended to be unique over the lifetime of the ESP
      cipher session-key(s).  A counter is most commonly used to gener-
      ate the IV, providing an easy method to prevent repetition.

      However, cryptanalysis might be aided by the rare serendipitous
      occurrence when the counter repeatedly changes in exactly the same
      fashion as corresponding bit positions in the first block.  Design
      of specific IV generation techniques must take this into account.

      Ideally, the IV would be based on explicit fields carried in each
      datagram, but generated pseudo-randomly and protected from disclo-
      sure [VK83].  This completely protects the first block from unde-
      tectable modification.

      Incorporating the ESP Security Parameters Index (SPI) and the
      anti-replay ESP Sequence Number (SN) together can provide both
      uniqueness and mutual protection between the first block and the
      ESP header.  Modification of the SPI to alter the decryption
      key(s) will prevent correct decryption of the first block.  Modi-
      fication of the SN to avoid anti-replay measures will also prevent
      correct decryption of the first block.  The first block is most
      likely to contain datagram headers required for delivery.
      Attempts to modify the IV to deliberately redirect transport head-
      ers will also likely be detected by the transport checksums.




Simpson                   expires in six months                 [Page 5]


DRAFT                           CBCS mode                      July 1998


      Inclusion of the bit-wise complement of SN ensures that bit
      changes are reflected twice in the IV.

      The checksum step with an undisclosed seed is intended to generate
      unpredictable initial values.


4.  Integrity

   Unlike CBC alone, CBCS provides integrity for the datagram.  A single
   ciphertext bit change will affect the current block, and every fol-
   lowing block.  The final checksum will give a highly probable indica-
   tion of the alteration.


4.1.  CheckSum Steps

   The checksum summation functions are calculated in three steps:

   1) addition modulo 2**N with end around carry;

   2) count of the number of 1-bits in the sum;

   3) left circular rotation of the sum by the bit count.

   This technique can be generalized to both 32-bit and 64-bit regis-
   ters, over block sizes of 64-bits, 96-bits, 128-bits, and more.

   All checksum operations are processed in big-endian order.  That is,
   the first byte of a block in transmission order is treated as the
   most significant byte for addition and left circular rotation.

   Design Notes:

      End around carry is a common feature of protocol checksums.  For
      example, for 2**8, 254 + 1 -> 255, 255 + 1 -> 1.


4.2.  Single 32-bit CheckSum (CBCS1-32)

   For ESP with only a primary 64-bit checksum, an optional 32-bit
   Authenticator (when provided) is calculated in six final steps:

   a) add and rotate a 64-bit count of the number of processed bits,
      including the IV, as described for the checksum;

   b) split the checksum into two 32-bit halves;




Simpson                   expires in six months                 [Page 6]


DRAFT                           CBCS mode                      July 1998


   c) multiply the two 32-bit halves, yielding a 64-bit product;

   d) rotate the product by its bit count, as described for the check-
      sum;

   e) split the product again into two 32-bit halves;

   f) XOR the 32-bit halves, yielding a final 32-bit Authenticator
      value.

   The Authenticator is deposited in big-endian order.  That is, the
   most significant byte is the first byte in network transmission
   order.

   Design Notes:

      The multiply is intended to confuse and diffuse the semi-
      independent halves, while the rotations and XOR prevent determina-
      tion of the final internal state of the checksum.


4.3.  Double 32-bit CheckSum (CBCS2-32)

   For ESP with both primary and secondary 64-bit checksums, an optional
   32-bit Authenticator (when provided) is calculated in seven final
   steps:

   a) to each checksum, add and rotate a 64-bit count of the number of
      processed bits, including the IV, as described for the checksum;

   b) add and rotate the two checksums, as described for the checksum;

   c) split the 64-bit sum into two 32-bit halves;

   d) multiply the two 32-bit halves, yielding a 64-bit product;

   e) rotate the product by its bit count, as described for the check-
      sum;

   f) split the product again into two 32-bit halves;

   g) XOR the 32-bit halves, yielding a final 32-bit Authenticator
      value.

   The Authenticator is deposited in big-endian order.  That is, the
   most significant byte is the first byte in network transmission
   order.




Simpson                   expires in six months                 [Page 7]


DRAFT                           CBCS mode                      July 1998


   Design Notes:

      The addition and multiply are intended to confuse and diffuse the
      independent checksums, in much the same fashion as the Single
      32-bit CheckSum.


4.4.  Double 64-bit CheckSum (CBCS2-64)

   For ESP with both primary and secondary 64-bit checksums, an optional
   64-bit Authenticator (when provided) is calculated in five final
   steps:

   a) to each checksum, add and rotate a 64-bit count of the number of
      processed bits, including the IV, as described for the checksum;

   b) multiply the two checksums, yielding a 128-bit product;

   c) split the product into two 64-bit halves;

   d) rotate each half of the product by its bit count, as described for
      the checksum;

   e) add the halves modulo 2**64 with end around carry, yielding a
      final 64-bit Authenticator value.

   The Authenticator is deposited in big-endian order.  That is, the
   most significant byte is the first byte in network transmission
   order.

   Design Notes:

      The larger multiply is intended to more effectively diffuse the
      checksums, while the rotations and addition prevent determination
      of the final internal state of the checksums.


5.  Collisions

   This checksum technique is hoped to prevent linear cryptanalysis by
   incorporating a non-linear rotation function.  In case this hope
   proves illusive, the analysis in [RFC-wwww] should be considered.









Simpson                   expires in six months                 [Page 8]


DRAFT                           CBCS mode                      July 1998


A.  Rotation Probability

   Assuming that the cipher produces a uniformly random distribution,
   the probability for rotation in 32-bits (4,294,967,296) is:

       0, 32:           1
       1, 31:          32
       2, 30:         496
       3, 29:       4,960
       4, 28:      35,960
       5, 27:     201,376
       6, 26:     906,192
       7, 25:   3,365,856
       8, 24:  10,518,300
       9, 23:  28,048,800
      10, 22:  64,512,240
      11, 21: 129,024,480
      12, 20: 225,792,840
      13, 19: 347,373,600
      14, 18: 471,435,600
      15, 17: 565,722,720
          16: 601,080,390


B.  Code Samples

   Here are a few extracts of code to illustrate basic concepts, based
   on examples graciously provided by Niels Provos.


B.1.  Bit Count

   When a population count is not natively available in the machine
   instructions, adding the counts per byte can be significantly faster
   than testing each bit.  Machines with byte extract and translate
   instructions will improve performance.















Simpson                   expires in six months                 [Page 9]


DRAFT                           CBCS mode                      July 1998


      uint8 bit8ones[] =
      {   /*  1   2   3   4   5   6   7   8   9   a   b   c   d   e   f */
          0,  1,  1,  2,  1,  2,  2,  3,  1,  2,  2,  3,  2,  3,  3,  4,
          1,  2,  2,  3,  2,  3,  3,  4,  2,  3,  3,  4,  3,  4,  4,  5,
          1,  2,  2,  3,  2,  3,  3,  4,  2,  3,  3,  4,  3,  4,  4,  5,
          2,  3,  3,  4,  3,  4,  4,  5,  3,  4,  4,  5,  4,  5,  5,  6,
          1,  2,  2,  3,  2,  3,  3,  4,  2,  3,  3,  4,  3,  4,  4,  5,
          2,  3,  3,  4,  3,  4,  4,  5,  3,  4,  4,  5,  4,  5,  5,  6,
          2,  3,  3,  4,  3,  4,  4,  5,  3,  4,  4,  5,  4,  5,  5,  6,
          3,  4,  4,  5,  4,  5,  5,  6,  4,  5,  5,  6,  5,  6,  6,  7,

          1,  2,  2,  3,  2,  3,  3,  4,  2,  3,  3,  4,  3,  4,  4,  5,
          2,  3,  3,  4,  3,  4,  4,  5,  3,  4,  4,  5,  4,  5,  5,  6,
          2,  3,  3,  4,  3,  4,  4,  5,  3,  4,  4,  5,  4,  5,  5,  6,
          3,  4,  4,  5,  4,  5,  5,  6,  4,  5,  5,  6,  5,  6,  6,  7,
          2,  3,  3,  4,  3,  4,  4,  5,  3,  4,  4,  5,  4,  5,  5,  6,
          3,  4,  4,  5,  4,  5,  5,  6,  4,  5,  5,  6,  5,  6,  6,  7,
          3,  4,  4,  5,  4,  5,  5,  6,  4,  5,  5,  6,  5,  6,  6,  7,
          4,  5,  5,  6,  5,  6,  6,  7,  5,  6,  6,  7,  6,  7,  7,  8,
      };

      static int
      bit32count( uint32 n )
      {
          int result = bit8ones[ n & 0xff ];
          n >>= 8;
          result += bit8ones[ n & 0xff ];
          n >>= 8;
          result += bit8ones[ n & 0xff ];
          n >>= 8;
          return (result + bit8ones[ n & 0xff ]);
      }


B.2.  Variable Rotation

   When a rotation is not natively available in the machine instruc-
   tions, it can be emulated with an appropriate combination of shifts.
   Where a fixed shift is faster than a variable shift, 65 switch-cases
   can improve performance.











Simpson                   expires in six months                [Page 10]


DRAFT                           CBCS mode                      July 1998


      static void
      bit64rotation32( uint32 *cs )
      {
          uint32 csy = cs[1];
          uint32 csz = cs[0];
          int bcv = bit32count(csz) + bit32count(csy);

          if ( bcv < 32 )
          {
              /* 0..31 */
              cs[0] = (csz << bcv) | (csy >> (32-bcv));
              cs[1] = (csy << bcv) | (csz >> (32-bcv));
          }
          else if ( bcv == 32 )
          {
              /* fast swap */
              cs[0] = csy;
              cs[1] = csz;
          }
          else
          {
              /* 33..64 swap */
              cs[0] = (csy << (bcv-32)) | (csz >> (64-bcv));
              cs[1] = (csz << (bcv-32)) | (csy >> (64-bcv));
          }
      }


B.3.  Addition with End Around Carry

   Addition with carry is usually natively available in the machine
   instructions.



















Simpson                   expires in six months                [Page 11]


DRAFT                           CBCS mode                      July 1998


      static void
      bit64addition32( uint32 *cs, uint32 *addend )
      {
          uint32 topy = cs[1] | addend[1];
          uint32 topz = cs[0] | addend[0];

          cs[0] += addend[0];
          if ( cs[0] < topz )
          {
              cs[1]++;
          }
          cs[1] += addend[1];
          if ( cs[1] < topy )
          {
              cs[0]++;
          }
      }


Operational Considerations

   The specification provides only a few manually configurable parame-
   ters:

   Primary Seed
      A primary seed is configured in order prior to any keys.  The
      value is the same size as the block size of the cipher algorithm.

   Secondary Seed
      An optional secondary seed is configured in order following any
      keys.  The value is the same size as the block size of the cipher
      algorithm.

   The configured seed values are interpreted in big-endian order.  That
   is, the most significant byte of the seed is the leading byte.
















Simpson                   expires in six months                [Page 12]


DRAFT                           CBCS mode                      July 1998


Security Considerations

   Specific security limitations are described as notes in the relevant
   sections.


Acknowledgements

   Some of the text of this specification was derived from earlier work
   by William Allen Simpson and Perry Metzger in multiple Request for
   Comments.

   The checksum technique is based upon a common use of the CDC 6000
   series 60-bit registers for "normal" protocols.  Fortuitously, those
   machines featured both fast variable rotate and a population count
   instruction.

   Niels Provos and David Wagner provided useful critiques of earlier
   versions of this document.


References

   [ISO-8732]  "Banking -- Key management (wholesale)", International
               Organization for Standardization, 1988.

   [ISO/IEC-10116]
               "Information Processing -- Modes of Operation for an n-
               bit block cipher algorithm", International Organization
               for Standardization, 1991.

   [FIPS-81]   US National Bureau of Standards, "DES Modes of Opera-
               tion", Federal Information Processing Standard Publica-
               tion 81, December 1980.

   [MOV97]     Menezes, A.J., van Oorschot, P., and Vanstone, S., "Hand-
               book of Applied Cryptography", CRC Press, 1997.

   [RFC-1827x] Simpson, W., "IP Encapsulating Security Protocol (ESP)
               for implementors", work in progress.

   [RFC-wwww]  Simpson, W.A, "ESP with Cipher Block Chaining (CBC)",
               work in progress.

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




Simpson                   expires in six months                [Page 13]


DRAFT                           CBCS mode                      July 1998


Contacts

   Comments about this document should be discussed on the ipsec@tis.com
   mailing list.

   Questions about this document can also be directed to:

      William Allen Simpson
      DayDreamer
      Computer Systems Consulting Services
      1384 Fontaine
      Madison Heights, Michigan  48071

          wsimpson@UMich.edu
          wsimpson@GreenDragon.com (preferred)



Full Copyright Statement

   Copyright (C) William Allen Simpson (1994-1995, 1997-1998).  All
   Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works.  However, this doc-
   ument itself may not be modified in any way, except as required to
   translate it into languages other than English.

   This document and the information contained herein is provided on an
   "AS IS" basis and the author(s) DISCLAIM ALL WARRANTIES, EXPRESS OR
   IMPLIED, INCLUDING (BUT NOT LIMITED TO) ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.














Simpson                   expires in six months                [Page 14]