Internet Info 1997 December/Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso/drafts/draft_ietf_i/draft-ietf-ipsec-ciph-cbc-00.txt

Text File | 1997-10-02 | 26KB | 776 lines

Internet Engineering Task Force                             R. Pereira
IP Security Working Group                         TimeStep Corporation
Internet Draft                                                R. Adams
Expires in six months                               cisco Systems Inc.
                                                    September 30, 1997



                  The ESP CBC-Mode Cipher Algorithms
                  <draft-ietf-ipsec-ciph-cbc-00.txt>



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 ([e-mail]) 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 obsolete 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.

Abstract

   This document describes how to use CBC-mode cipher algorithms with
   the IPSec ESP (Encapsulating Security Payload) Protocol.  It not
   only clearly states how to use certain cipher algorithms, but also
   how to use all CBC-mode cipher algorithms.








R. Pereira, R. Adams                                          [Page 1]
Internet Draft    The ESP CBC-Mode Cipher Algorithms            Oct-97


Table of Contents

   1. Introduction...................................................2
     1.1 Specification of Requirements...............................2
   2. Cipher Algorithms..............................................3
     2.1 Mode........................................................3
     2.2 Key Size....................................................3
     2.3 Weak Keys...................................................4
     2.4 Block Size and Padding......................................5
     2.5 Rounds......................................................6
     2.6 Backgrounds.................................................6
     2.7 Performance.................................................9
   3. ESP Payload...................................................10
     3.1 ESP Environmental Considerations...........................10
     3.2 Keying Material............................................10
   4. Security Considerations.......................................11
   5. References....................................................11
   6. Acknowledgments...............................................12
   7. Editors' Addresses............................................13
   8. Internet Draft Notes..........................................13


1. Introduction

   The Encapsulating Security Payload (ESP) [Kent97] provides
   confidentiality for IP datagrams by encrypting the payload data to
   be protected.  This specification describes the ESP use of CBC-mode
   cipher algorithms.

   While this document does no describe the use of the default cipher
   algorithm DES, the reader should be familiar with that document.
   [Madson97]

   It is assumed that the reader is familiar with the terms and
   concepts described in the "Security Architecture for the Internet
   Protocol" [Atkinson95], "IP Security Document Roadmap" [Thayer97],
   and "IP Encapsulating Security Payload (ESP)" [Kent97] documents.

   Furthermore, this document is a companion to [Kent97] and MUST be
   read in its context.


1.1 Specification of Requirements

   The keywords "MUST", "MUST NOT", "REQUIRED", "SHOULD", "SHOULD
   NOT", and "MAY" that appear in this document are to be interpreted
   as described in [Bradner97].





R. Pereira, R. Adams                                          [Page 2]
Internet Draft    The ESP CBC-Mode Cipher Algorithms            Oct-97


2. Cipher Algorithms

   All symmetric block cipher algorithms share common characteristics
   and variables.  These include mode, key size, weak keys, block
   size, and rounds.  All of which will be explained below.

   While this document illustrates certain cipher algorithms such as
   Blowfish [Schneier93], CAST-128 [Adams97], 3DES, IDEA [Lai], and
   RC5 [Baldwin96], any other block cipher algorithm may be used with
   ESP if all of the variables described within this document are
   clearly defined.


2.1 Mode

   All symmetric block cipher algorithms described or insinuated
   within this document use Cipher Block Chaining (CBC) mode.  This
   mode requires an Initialization Vectors (IV) that is the same size
   as the block size.  The IV is used to scramble the initial block
   that is the same as other initial block in other datagrams.
   Without an IV, these initial blocks would all have the same
   ciphertext, since they all use the same key.

   The IV is XORÆd with the first plaintext block, before it is
   encrypted.  Then for successive blocks, the previous ciphertext
   block is XORÆd with the current plaintext, before it is encrypted.

   More information on CBC mode can be obtained in [Schneier95].


2.2 Key Size

   Some cipher algorithms allow for variable sized keys, while other
   only allow a specific key size.  The length of the key correlates
   with the strength of that algorithm, thus larger keys are always
   harder to break than shorter ones.

   This document stipulates that all key sizes MUST be a multiple of 8
   bits.

   +==============+==================+=================+==========+
   | Algorithm    | Key Sizes (bits) | Popular Sizes   | Default  |
   +==============+==================+=================+==========+
   | CAST-128 [1] | 40 to 128        | 40, 64, 80, 128 | 128      |
   +--------------+------------------+-----------------+----------+
   | RC5          | 40 to 2040       | 40, 128, 160    | 128      |
   +--------------+------------------+-----------------+----------+
   | IDEA         | 128              | 128             | 128      |
   +--------------+------------------+-----------------+----------+
   | Blowfish     | 40 to 448        | 128             | 128      |



R. Pereira, R. Adams                                          [Page 3]
Internet Draft    The ESP CBC-Mode Cipher Algorithms            Oct-97


   +--------------+------------------+-----------------+----------+
   | 3DES [2]     | 192              | 192             | 192      |
   +--------------+------------------+-----------------+----------+

   Notes:

   [1] With CAST-128, keys less than 128 bits MUST be padded with
   zeros in the rightmost, or least significant, positions out to 128
   bits since the CAST-128 key schedule assumes an input key of 128
   bits.  Thus if you had a key with a size of 80 bits æ3B5D831CFEÆ,
   it would be padded to produce a key with a size of 128 bits
   æ3B5D831CFE000000Æ.

   [2] The first 3DES key is taken from the first 64 bits, the second
   from the next 64 bits, and the third from the last 64 bits.
   Implementations SHOULD take into consideration the parity bits when
   initially accepting a new set of keys.

   The reader should note that the minimum key size for all of the
   above cipher algorithms is 40 bits, and that the authors strongly
   advise that implementations do NOT use key sizes smaller than 40
   bits.


2.3 Weak Keys

   Some cipher algorithms have weak keys or keys that MUST not be used
   due to their weak nature.  [Kent97] describes what to do when such
   a key size is generated.

   CAST-128:

   No known weak keys.


   RC5:

   No known weak keys when used with 16 rounds.


   IDEA:

   IDEA has weak keys of the following form [Crypto93]:

            0000,0000,0x00,0000,0000,000x,xxxx,x000

   where "x" can be any hexadecimal number.




R. Pereira, R. Adams                                          [Page 4]
Internet Draft    The ESP CBC-Mode Cipher Algorithms            Oct-97


   Keys of this form guarantee the value of bit-wise XOR of resultant
   ciphertext pairs from the bit-wise XOR of certain plaintext pairs.


   Blowfish:

   Weak keys for Blowfish have been discovered.  Weak keys are keys
   that produce the identical entries in a given S-box.
   Unfortunately, there is no way to test for weak keys before the S-
   box values are generated.  However, the chances of randomly
   generating such a key are small.


   3DES:

   DES has 64 known weak keys, including so-called semi-weak keys and
   possibly-weak keys [Schneier95, pp 280-282].  The likelihood of
   picking one at random is negligible.

   For DES-EDE3, there is no known need to reject weak or
   complementation keys.  Any weakness is obviated by the other keys.

   However, if the first two or last two independent 64-bit keys are
   equal (k1 == k2 or k2 == k3), then the 3DES operation is simply the
   same as DES.  Implementers MUST reject keys that exhibit this
   property.


2.4 Block Size and Padding

   All of the algorithms described in this document use a block size
   of eight octets (64 bits).

   Padding is used to align the payload type and pad length octets as
   specified in [Kent97].  Padding must be sufficient to align the
   data to be encrypted to an eight octet (64 bit) boundary.















R. Pereira, R. Adams                                          [Page 5]
Internet Draft    The ESP CBC-Mode Cipher Algorithms            Oct-97





2.5 Rounds

   This variable determines how many times a block is encrypted.
   While this variable MAY be negotiated, a default value MUST always
   exist when it is not negotiated.

   +====================+============+======================+
   | Algorithm          | Negotiable | Default Rounds       |
   +====================+============+======================+
   | CAST-128           | No         | key<=80 bits, 12     |
   |                    |            | key>80 bits, 16      |
   +--------------------+------------+----------------------+
   | RC5                | No         | 16                   |
   +--------------------+------------+----------------------+
   | IDEA [1]           | 4, 8       | 8                    |
   +--------------------+------------+----------------------+
   | Blowfish           | No         | 16                   |
   +--------------------+------------+----------------------+
   | 3DES               | No         | 48 (16x3)            |
   +--------------------+------------+----------------------+

   Notes:
   [1] Although there are no known attacks against four round IDEA,
   those choosing to use four round IDEA for performance reasons, may
   wish shorten key lifetimes via site specific policy.


2.6 Backgrounds

   CAST-128:

   The CAST design procedure was originally developed by Carlisle
   Adams and Stafford Travares at QueenÆs University, Kingston,
   Ontario, Canada.  Subsequent enhancements have been made over the
   years by Carlisle Adams and Michael Wiener of Entrust Technologies.
   CAST-128 is the result of applying the CAST Design Procedure as
   outlined in [Adams97].


   RC5:

   The RC5 encryption algorithm was developed by Ron Rivest for RSA
   Data Security Inc. in order to address the need for a high-
   performance software and hardware ciphering alternative to DES.





R. Pereira, R. Adams                                          [Page 6]
Internet Draft    The ESP CBC-Mode Cipher Algorithms            Oct-97


   IDEA:

   Xuejia Lai and James Massey developed the IDEA (International Data
   Encryption Algorithm) algorithm.  The algorithm is described in
   detail in [Lai] and [Schneier].

   The IDEA algorithm is patented in Europe and in the United States
   with patent application pending in Japan.  Licenses are required
   for commercial uses of IDEA.

   For patent and licensing information, contact:

         Ascom Systec AG, Dept. CMVV
         Gewerbepark, CH-5506
         Magenwil, Switzerland
         Phone: [phone]
         Fax: [phone]
         [e-mail]
         http://www.ascom.ch/Web/systec/policy/normal/exhibit1.html


   Blowfish:

   Bruce Schneier of Counterpane Systems developed the Blowfish block
   cipher algorithm.  The algorithm is described in detail in
   [Schneier93], [Schneier95] and [Schneier].


   3DES:

   This DES variant, colloquially known as "Triple DES" or as DES-
   EDE3, processes each block three times, each time with a different
   key.  This technique of using more than one DES operation was
   proposed in [Tuchman79].
















R. Pereira, R. Adams                                          [Page 7]
Internet Draft    The ESP CBC-Mode Cipher Algorithms            Oct-97


                        P1             P2             Pi
                         |              |              |
                  IV->->(X)    +>->->->(X)    +>->->->(X)
                         v     ^        v     ^        v
                      +-----+  ^     +-----+  ^     +-----+
                  k1->|  E  |  ^ k1->|  E  |  ^ k1->|  E  |
                      +-----+  ^     +-----+  ^     +-----+
                         |     ^        |     ^        |
                         v     ^        v     ^        v
                      +-----+  ^     +-----+  ^     +-----+
                  k2->|  D  |  ^ k2->|  D  |  ^ k2->|  D  |
                      +-----+  ^     +-----+  ^     +-----+
                         |     ^        |     ^        |
                         v     ^        v     ^        v
                      +-----+  ^     +-----+  ^     +-----+
                  k3->|  E  |  ^ k3->|  E  |  ^ k3->|  E  |
                      +-----+  ^     +-----+  ^     +-----+
                         |     ^        |     ^        |
                         +>->->+        +>->->+        +>->->
                         |              |              |
                         C1             C2             Ci

   The DES-EDE3-CBC algorithm is a simple variant of the DES-CBC
   algorithm [FIPS-46].  The "outer" chaining technique is used.

   In DES-EDE3-CBC, an Initialization Vector (IV) is XOR'd with the
   first 64-bit (8 byte) plaintext block (P1).  The keyed DES function
   is iterated three times, an encryption (Ek1) followed by a
   decryption (Dk2) followed by an encryption (Ek3), and generates the
   ciphertext (C1) for the block.  Each iteration uses an independent
   key: k1, k2 and k3.

   For successive blocks, the previous ciphertext block is XOR'd with
   the current plaintext (Pi).  The keyed DES-EDE3 encryption function
   generates the ciphertext (Ci) for that block.

   To decrypt, the order of the functions is reversed: decrypt with
   k3, encrypt with k2, decrypt with k1, and XOR the previous
   ciphertext block.

   Note that when all three keys (k1, k2 and k3) are the same, DES-
   EDE3-CBC is equivalent to DES-CBC.  This property allows the DES-
   EDE3 hardware implementations to operate in DES mode without
   modification.

   For more explanation and implementation information for Triple DES,
   see [Schneier95].



R. Pereira, R. Adams                                          [Page 8]
Internet Draft    The ESP CBC-Mode Cipher Algorithms            Oct-97


2.7 Performance

   For a comparison table of the speed of any of these and other
   cipher algorithms, please see [Schneier97].

   CAST-128:

   CAST runs approximately 3 times faster than a highly optimized DES
   implementation and runs 5-6 times faster than the DES
   implementations found in typical applications.  This is based on a
   non optimized C++ implementation of CAST-128.  It can therefore be
   tuned to give even higher performance, if this is required.

   The following performance tests were run on a Pentium 90 MHz
   running the Windows NT operating system using 20 Kbyte buffers and
   do not include file I/O.  The DES-CBC implementation was not
   optimized for a 32 bit environment.

   CAST-128 64 bit key CBC encryption ............ 2,640,000 bytes/sec
   DES CBC encryption .............................. 504,000 bytes/sec


   RC5:

   Benchmark numbers from RSA Data Security suggest that RC5-CBC runs
   about twice as fast as Eric Young's DES-CBC implementation from
   SSLeay on the popular 32-bit CPUs.


   IDEA:

   Normal eight round IDEA is approximately twice as fast as DES on
   386 and 486 processors.  However on a Pentium, both eight round
   IDEA and 56 bit key, 16 round DES require about the same number of
   clock cycles per byte encrypted.  Four round IDEA is twice as fast
   as eight round IDEA.


   Blowfish:

   Blowfish is designed to encrypt data very efficiently on 32 bit
   processors.   Although setting up the keys for Blowfish is complex
   and time consuming, actual encryption is efficient.  Sixteen round
   Blowfish uses only 18 clock cycles per byte encrypted on a Pentium
   versus 45 clock cycles for 16 round DES with a 56 bit key, and 108
   for 48 round Triple-DES.





R. Pereira, R. Adams                                          [Page 9]
Internet Draft    The ESP CBC-Mode Cipher Algorithms            Oct-97


   3DES:

   Triple DES is approximately 2.5 times slower than "single" DES
   (rather than 3 times), because inner permutations may be removed.
   Phil Karn has tuned DES-EDE3-CBC software to achieve 6.22 Mbps with
   a 133 MHz Pentium.  Other DES speed estimates may be found at
   [Schneier, page 279].


3. ESP Payload

   The ESP payload is made up of the IV followed by raw cipher-text.
   Thus the payload field, as defined in [Kent97], is broken down
   according to the following diagram:

   +---------------+---------------+---------------+---------------+
   |                                                               |
   +               Initialization Vector (8 octets)                +
   |                                                               |
   +---------------+---------------+---------------+---------------+
   |                                                               |
   ~              Encrypted Payload (variable length)              ~
   |                                                               |
   +---------------------------------------------------------------+
    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

   The IV field MUST be same size as the block size of the cipher
   algorithm being used.  The IV SHOULD be chosen at random.  Common
   practice is to use random data for the first IV and the last block
   of encrypted data from an encryption process as the IV for the next
   encryption process.


3.1 ESP Environmental Considerations

   Currently, there are no known issues regarding interactions between
   these algorithms and other aspects of ESP, such as use of certain
   authentication schemes.


3.2 Keying Material

   The minimum number of bits sent from the key exchange protocol to
   this ESP algorithm must be greater or equal to the key size.

   The cipherÆs encryption and decryption key is taken from the first
   <x> bits of the keying material, where <x> represents the required
   key size.





R. Pereira, R. Adams                                         [Page 10]
Internet Draft    The ESP CBC-Mode Cipher Algorithms            Oct-97


4. Security Considerations

   Care should be taken when using small key sizes.  Smaller key sizes
   of 56 bits and below make brute force type attacks practical
   regardless of the cipher algorithm used.  It is therefore
   recommended for variable sized keyed algorithms, that the key size
   be at least 80 bits.  Use of key sizes less than 80 bits is
   permitted, but careful considerations should be taken before its
   use.

   For further security considerations, the reader is encouraged to
   read the documents that describe the actual cipher algorithms.


5. References

   [Adams97] Adams, C., "The CAST-128 Encryption AlgorithmÆ                                                          Æ, RFC2144,
   1997.

   [Atkinson95] Atkinson, R., "Security Architecture for the Internet
   Protocol", draft-ietf-ipsec-arch-sec-01

   [Baldwin96] Baldwin, R.W., Rivest, R., "The RC5, RC5-CBC, RC5-CBC-
   Pad, and RC5-CTS Algorithms", RFC2040, October 1996

   [Bradner97] Bradner, S., "Key words for use in RFCs to indicate
   Requirement Levels", RFC2119, March 1997

   [Crypto93] Daeman, J., Govaerts, R., Vandewalle, J., "Weak Keys for
   IDEA", Advances in Cryptology, CRYPTO 93 Proceedings, Springer-
   Verlag, pp. 224-230.

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

   [Kent97] Kent, S., Atkinson, R., "IP Encapsulating Security Payload
   (ESP)", draft-ietf-ipsec-esp-v2-00

   [Lai] Lai, X. "On the Design and Security of Block Ciphers", ETH
   Series in Information Processing, v. 1, Konstanz: Hartung-Gorre
   Verlag, 1992.

   [Madson97] Madson, C., Dorswamy, N., "The ESP DES-CBC Cipher
   Algorithm With Explicit IV", draft-ietf-ipsec-ciph-des-expiv-00

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




R. Pereira, R. Adams                                         [Page 11]
Internet Draft    The ESP CBC-Mode Cipher Algorithms            Oct-97


   [Schneier93] Schneier, B., "Description of a New Variable-Length
   Key, 64-Bit Block Cipher", from "Fast Software Encryption,
   Cambridge Security Workshop Proceedings", Springer-Verlag, 1994,
   pp. 191-204. http://www.counterpane.com/bfsverlag.html

   [Schneier95] Schneier, B., "The Blowfish Encryption Algorithm - One
   Year Later", Dr. Dobb's Journal, September 1995,
   http://www.counterpane.com/bfdobsoyl.html

   [Schneier97] Scheier, B. "Speed Comparisons of Block Ciphers on a
   Pentium." February 1997, http://www.counterpane.com/speed.html

   [Thayer97] R. Thayer, N. Doraswamy, R. Glenn, "IP Security Document
   Roadmap", draft-ietf-ipsec-doc-roadmap-00

   [Tuchman79] Tuchman, W, "Hellman Presents No Shortcut Solutions to
   DES", IEEE Spectrum, v. 16 n. 7, July 1979, pp. 40-41.


6. Acknowledgments

   This document is a merger of most of the ESP cipher algorithm
   documents.  This merger was done to facilitate greater
   understanding of the commonality of all of the ESP algorithms and
   to further the development of these algorithm within ESP.

   The content of this document is based on suggestions originally
   from Stephen Kent and subsequent discussions from the IPSec mailing
   list as well as other IPSec drafts.

   For CAST, special thanks to Carlisle Adams and Paul Van Oorschot
   both of Entrust Technologies who provided input and review.

   For 3DES, thanks to all of the editors of the previous ESP 3DES
   documents; W. Simpson, N. Doraswamy, P. Metzger, and P. Karn.

   For RC5, thanks to Brett Howard from TimeStep for his original
   work.













R. Pereira, R. Adams                                         [Page 12]
Internet Draft    The ESP CBC-Mode Cipher Algorithms            Oct-97


7. Editors' Addresses

     Roy Pereira
     <[e-mail]>
     TimeStep Corporation
     [phone] x 4808

     Rob Adams
     <[e-mail]>
     cisco Systems Inc.
     [phone]

     Contributors:

     Robert W. Baldwin
     <[e-mail]> or <[e-mail]>
     RSA Data Security, Inc.
     [phone]

     Greg Carter
     <[e-mail]>
     Entrust Technologies
     [phone]

     Rodney Thayer
     [e-mail]
     Sable Technology Corporation
     [phone]

   The IPSec working group can be contacted via the IPSec working
   group's mailing list ([e-mail]) or through its chairs:

     Robert Moskowitz
     [e-mail]
     Chrysler Corporation

     Theodore Y. TsÆo
     [e-mail]
     Massachusetts Institute of Technology


8. Internet Draft Notes

   This document obsoletes the following documents:
     draft-ietf-ipsec-ciph-cast-128cbc-00.txt, R. Pereira, G. Carter
     draft-ietf-ipsec-ciph-rc5-cbc-00.txt, R. Pereira, R. Baldwin
     draft-ietf-ipsec-ciph-3des-expiv-00.txt, R. Pereira, R. Thayer
     draft-ietf-ipsec-ciph-idea-cbc-00.txt, R. Adams
     draft-ietf-ipsec-ciph-blowfish-cbc-00.txt, R. Adams



R. Pereira, R. Adams                                         [Page 13]
Internet Draft    The ESP CBC-Mode Cipher Algorithms            Oct-97



   The key size for IDEA was restricted for "ease of use" purposes.
   Furthermore, the use of setting the sub-keys directly was removed,
   again for ease of use.

   IDEAÆs weak key derivation was removed as it is the responsibility
   of the  ESP document to describe actions when there is a weak key.

   DES-CBC could be part of this document with very little effort.
   Should it be?








































R. Pereira, R. Adams                                         [Page 14]