INTERNET-DRAFT B. W. Howard
Expires September 1, 1996 TimeStep Corporation
R. W. Baldwin
RSA Data Security, Inc.
March 1996
The ESP RC5-CBC Transform
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 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).
The filename for this document is draft-baldwin-esp-rc5-00.txt.
Acknowledgments
This document was based on Karn, P. , Metzger., P., and Simpson,
W. "The ESP DES-CBC Transform" [RFC-1827]. Much of the original
text remains, with the RC5 specific portions added. We would
also like to thank Paul Kierstead and Stephane Lacelle for their
contributions.
Table of Contents
Executive Summary
1. Introduction
2. Payload Format
3. Algorithms
4. Security and Performance Considerations
References & Addresses of Authors
Executive Summary
This document describes the RC5-CBC security transform for the IP
Encapsulating Security Payload (ESP) based on the DES-CBC
transform described in RFC-1829 and RFC-1827. The RC5 cipher
allows for greater performance, security and exportability than
the DES cipher. A companion document [Baldwin96] describes RC5
in sufficient detail to construct interoperable systems.
draft-00 The ESP RC5-CBC Transform March 1996
1. Introduction
The Encapsulating Security Payload (ESP) [RFC-1827] provides
confidentiality for IP datagrams by encrypting the payload data to be
protected. This specification describes the use of the Cipher Block
Chaining (CBC) mode of RC5 which is described in [Baldwin96]. Much of
the text and ideas in this document were lifted directly from RFC 1829
by P. Karn, P. Metzger and W. Simpson.
Implementation of this transform is optional within the context of ESP
as only the DES-CBC transform is mandatory (RFC 1829).
This document assumes that the reader is familiar with the related
document "Security Architecture for the Internet Protocol" [RFC-1825],
which defines the overall security plan for IP, and provides important
background for this specification.
1.1 Background on RC5
The RC5 encryption algorithm was developed by Ron Rivest of RSA Data
Security Inc. in order to address the need for a high-performance
software ciphering alternative to DES. [Baldwin96] describes RC5-CBC
algorithm which expects the data size to be a multiple of the block
size. A second option, referred to as RC5-CBC-Pad proposes a standard
way of padding input such that arbitrary input sizes can be encrypted.
For the purposes of this proposal, the RC5-CBC algorithm is used, and
padding is added in a similar way as proposed in RFC-1829 for DES-CBC.
1.2 RC5 Parameters
Unlike the Data Encryption Standard, RC5 can be configured for varying
levels of security. The key size is variable, as are the number of
rounds and the data block size. In general, greater key sizes and
more rounds lead to greater security. Data block size is a parameter
intended to be used to efficiently accommodate various machine
architectures.
1.3. Initialization Vector (IV)
The CBC mode requires an IV for its operation. Each datagram contains
its own IV. Including the IV in each datagram ensures that decryption
of each received datagram can be performed, even when other datagrams
are dropped, or datagrams are reordered in transit.
The IV size depends on the data block size chosen (see 1.4 below).
Although IVs may exceed 64 bits, only 64-bit IVs and padded 32-bit IVs
are supported by this proposal.
The method for selection of IV values is implementation dependent.
Howard, Baldwin [Page 2]
draft-00 The ESP RC5-CBC Transform March 1996
1.4 RC5 Parameter Selection
Although it is recognized that essentially any combination of
parameters is possible, in order to simplify this proposal, this draft
offers two options, one for export, and one for domestic use. For
reference in this document, RC5_keySize, RC5_rounds and
RC5_dataBlockSize refer to each of the three parameter choices of key
bits, cipher rounds and data block size in octets respectively.
It is assumed that the key management mechanism negotiates the three
parameters. Although any parameter choices could be supported and
negotiated, compliant implementations must support the domestic and
export versions as follows:
Export:
RC5_keySize: 40 bits
RC5_rounds: 12
RC5_dataBlockSize: 8 octets
Domestic:
RC5_keySize: 128 bits
RC5_rounds: 12
RC5_dataBlockSize: 8 octets
1.4. Payload Length
The RC5 algorithm operates on blocks of a specific size, designated by
the RC5_dataBlockSize parameter. This often requires padding after
the end of the unencrypted payload data.
Both input and output result in the same number of octets, which
facilitates in-place encryption and decryption.
On receipt, if the length of the data to be decrypted is not an
integral multiple of RC5_dataBlockSize octets, then an error is
indicated, as described in [RFC-1825].
1.5. Performance
RC5 shines above DES and many other encryption algorithms with respect
to software performance. As such, it is an excellent candidate since
IP security will often be from workstations or laptops where hardware
accelerators are an unlikely option. Performance figures may be added
in future revisions of this document.
Howard, Baldwin [Page 3]
draft-00 The ESP RC5-CBC Transform March 1996
2. Payload Format
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---+-+-+-+
| Security Parameters Index (SPI) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Initialization Vector (IV) ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Payload Data ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
... Padding | Pad Length | Payload Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Security Parameters Index (SPI)
A 32-bit value identifying the Security Parameters for this datagram.
The value MUST NOT be zero.
Initialization Vector (IV)
The size of this field is variable, although its size is constant for
all RC5-CBC datagrams with the same SPI and IP Destination. Octets
are sent in network order such that the octet of the IV that is
transmitted first is XOR'ed with the octet of the payload data that is
transmitted first, and so on [RFC-1700].
The IV size MUST be a multiple of 32-bits. Sizes of 32 and 64 bits
are required to be supported. The use of other sizes is beyond the
scope of this specification. The size is expected to be indicated by
the key management mechanism.
When the size is 32-bits, a 64-bit IV is formed from the 32-bit value
followed by (concatenated with) the bit-wise complement of the 32-bit
value. This field size is most common, as it aligns the Payload Data
for both 32-bit and 64-bit processing.
It is the intent that the value not repeat during the lifetime of the
encryption session key. Even when a full 64-bit IV is used, the
session key SHOULD be changed at least as frequently as 2**32
datagrams.
Payload Data
The size of this field is variable.
Prior to encryption and after decryption, this field begins with the
IP Protocol/Payload header specified in the Payload Type field. Note
Howard, Baldwin [Page 4]
draft-00 The ESP RC5-CBC Transform March 1996
that in the case of IP-in-IP encapsulation (Payload Type 4), this will
be another IP header.
Howard, Baldwin [Page 5]
draft-00 The ESP RC5-CBC Transform March 1996
Padding
The size of this field is variable.
Prior to encryption, it is filled with unspecified implementation
dependent (preferably random) values, to align the Pad Length and
Payload Type fields at an RC5_dataBlockSize octet boundary.
After decryption, it MUST be ignored.
Pad Length
This field indicates the size of the Padding field. It does not
include the Pad Length and Payload Type fields. The value typically
ranges from 0 to (RC5_dataBlockSize-1), but may be up to 255 to permit
hiding of the actual data length.
This field is opaque. That is, the value is set prior to encryption,
and is examined only after decryption.
Payload Type
This field indicates the contents of the Payload Data field, using the
IP Protocol/Payload value. Up-to-date values of the IP
Protocol/Payload are specified in the most recent "Assigned Numbers"
[RFC-1700].
This field is opaque. That is, the value is set prior to encryption,
and is examined only after decryption.
For example, when encrypting an entire IP datagram (Tunnel- Mode),
this field will contain the value 4, which indicates IP-in-IP
encapsulation.
Howard, Baldwin [Page 6]
draft-00 The ESP RC5-CBC Transform March 1996
3. Algorithms
Block Ciphers (such as DES and RC5) can be used in a Cipher-Block
Chaining mode where the base encryption function is applied to the XOR
of each plaintext block with the previous ciphertext block to yield
the ciphertext for the current block. This provides for re-
synchronization when datagrams are lost.
For more explanation, see [Schneier94]; or see [Baldwin96] for more
specific details of CBC as it relates to RC5.
3.1. Encryption
Append zero or more octets of (preferably random) padding to the
plaintext, to make its length modulo RC5_dataBlockSize equal to 6.
For example if the RC5_dataBlockSize were 8 and the plaintext length
is 41, 5 octets of padding are added.
Append a Pad Length octet containing the number of padding octets just
added.
Append a Payload Type octet containing the IP Protocol/Payload value
which identifies the protocol header that begins the payload.
Provide an Initialization Vector (IV) of the size indicated by the
SPI.
Encrypt the payload with RC5 in CBC mode, producing a ciphertext of
the same length.
Octets are encrypted in network order [RFC-1700]. Octet 0 (modulo 8)
of the payload corresponds to first byte of input to an RC5-CBC block,
while octet 7 (modulo 8) corresponds to the last byte of input to an
RC5 block. See [baldwin96] for details on RC5-CBC.
Construct an appropriate IP datagram for the target Destination, with
the indicated SPI, IV, and payload.
The Total/Payload Length in the encapsulating IP Header reflects the
length of the encrypted data, plus the SPI, IV, padding, Pad Length,
and Payload Type octets.
Howard, Baldwin [Page 7]
draft-00 The ESP RC5-CBC Transform March 1996
3.2. Decryption
First, the SPI field is removed and examined. This is used as an
index into the local Security Parameter table to find the negotiated
parameters and decryption key.
The negotiated form of the IV determines the size of the IV field.
These octets are removed, and an appropriate 64-bit IV value is
constructed.
The encrypted part of the payload is decrypted using RC5 in the CBC
mode.
The Payload Type is removed and examined. If it is unrecognized, the
payload is discarded with an appropriate ICMP message.
The Pad Length is removed and examined. The specified number of pad
octets are removed from the end of the decrypted payload, and the IP
Total/Payload Length is adjusted accordingly.
The IP Header(s) and the remaining portion of the decrypted payload
are passed to the protocol receive routine specified by the Payload
Type field.
4. Security and Performance Considerations
The security of RC5 is dependent on the key length and number of
rounds. In general, twelve rounds are adequate for RC5 with 64 bit
blocks for any given key length. The performance of RC5 is in
proportion to the number of rounds, and is not affected by the key
size.
In the case of a 40-bit key, [Baldwin96] recommends the use of salt
bits and a strong digesting algorithm to produce 128-bit keys (in a
2^40 element key-space). This has the advantage of thwarting attacks
which precompute key-search tables based on 40 bits. This option is
not used in this proposal since the mechanism for agreeing upon such
keys would be handled by the key-negotiation phase, not during the
encapsulation phase.
As of March 1996, RC5 using a 40-bit key had not yet been approved for
general export from the United States or Canada. There is reason for
optimism, however, judging from past approvals of other 40-bit
algorithms.
Howard, Baldwin [Page 8]
draft-00 The ESP RC5-CBC Transform March 1996
References
[Baldwin96] Baldwin, R.W., and Rivest R.L., "The RC5, RC5-CBC, RC5-
CBC-Pad, and RC5-CTS Algorithms", RSA Data Security Inc., March
1996.
[Bell95] Bellovin, S., "An Issue With DES-CBC When Used Without
Strong Integrity", Proceedings of the 32nd IETF, Danvers, MA,
April 1995.
[BS93] Biham, E., and Shamir, A., "Differential Cryptanalysis of the
Data Encryption Standard", Berlin: Springer-Verlag, 1993.
[CN94] Carroll, J.M., and Nudiati, S., "On Weak Keys and Weak Data:
Foiling the Two Nemeses", Cryptologia, Vol. 18 No. 23 pp. 253-280,
July 1994.
[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.
[Matsui94] Matsui, M., "Linear Cryptanalysis method dor DES Cipher,"
Advances in Cryptology -- Eurocrypt '93 Proceedings, Berlin:
Springer-Verlag, 1994.
[RFC-1446] Galvin, J., and McCloghrie, K., "Security Protocols for
Version 2 of the Simple Network Management Protocol (SNMPv2)",
RFC-1446, DDN Network Information Center, April 1993.
[RFC-1700] Reynolds, J., and Postel, J., "Assigned Numbers", STD 2,
RFC-1700, USC/Information Sciences Institute, October 1994.
[RFC-1800] Postel, J., "Internet Official Protocol Standards", STD 1,
RFC-1800, USC/Information Sciences Institute, July 1995.
Howard, Baldwin [Page 9]
draft-00 The ESP RC5-CBC Transform March 1996
[RFC-1825] Atkinson, R., "Security Architecture for the Internet
Protocol", RFC-1825, Naval Research Laboratory, July 1995.
[RFC-1826] Atkinson, R., "IP Authentication Header", RFC-1826, Naval
Research Laboratory, July 1995.
[RFC-1827] Atkinson, R., "IP Encapsulating Security Protocol (ESP)",
RFC-1827, Naval Research Laboratory, July 1995.
[RFC-1829] Karn, P. , Metzger., P., and Simpson, W. "The ESP DES-CBC
Transform" RFC-1827, Naval Research Laboratory, August 1995.
[Schneier94] Schneier, B., "Applied Cryptography", John Wiley & Sons,
New York, NY, 1994. ISBN 0-471-59756-2
[Weiner94] Wiener, M.J., "Efficient DES Key Search", School of
Computer Science, Carleton University, Ottawa, Canada, TR-244, May
1994. Presented at the Rump Session of Crypto '93.
Addresses of Authors
Brett W. Howard
TimeStep Corporation
359 Terry Fox Drive
Nepean, Ontario
Canada K2H 6K3
Phone: (613) 599-3610 x4554
Fax: (613) 599-3617
Email: bretth@timestep.com
Robert W. Baldwin
RSA Data Security, Inc.
100 Marine Parkway
Redwood City, CA 94065
Phone: (415) 595-8782
Fax: (415) 595-1873
Email: baldwin@rsa.com, or baldwin@lcs.mit.edu
This internet-draft that expires on September 1, 1996.
Howard, Baldwin [Page 10]