Network Working Group P Metzger
Internet Draft Piermont
W A Simpson
Daydreamer
D A Wagner
Berkeley
expires in six months February 1996
The ESP DES-CBC plus MD5 Transform
draft-simpson-esp-des1md5-01.txt
Status of this Memo
This document is a submission to the IP Security Working Group of the
Internet Engineering Task Force (IETF). Comments should be submitted
to the ipsec@ans.net mailing list.
Distribution of this memo is unlimited.
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 (Europe)
ds.internic.net (US East Coast)
ftp.isi.edu (US West Coast)
munnari.oz.au (Pacific Rim)
M, S & W expires in six months [Page i]
DRAFT ESP DES-CBC-MD5 February 1996
Abstract
This document describes use of DES-CBC for privacy, plus MD5 for
integrity, in the IP Encapsulating Security Payload (ESP).
M, S & W expires in six months [Page ii]
DRAFT ESP DES-CBC-MD5 February 1996
1. Introduction
The Encapsulating Security Payload (ESP) [RFC-1827] provides confi-
dentiality for IP datagrams by encrypting the payload data to be pro-
tected. Some transforms may also provide integrity.
This specification describes the ESP use of the Cipher Block Chaining
(CBC) mode of the US Data Encryption Standard (DES) algorithm
[FIPS-46, FIPS-46-1, FIPS-74, FIPS-81], together with Message Digest
5 (MD5) [RFC-1321].
The usual combination of ESP and AH [RFC-1826] can do this task just
as well. The primary benefit of this transform is that it saves 4
octets.
This document assumes that the reader is familiar with the related
document "Security Architecture for the Internet Protocol"
[RFC-1825], that defines the overall security plan for IP, and pro-
vides important background for this specification.
1.1. Keys
There are two keys used by this transform.
The secret DES key shared between the communicating parties is eight
octets (64-bits) in length. This key consists of a 56-bit quantity
used by the DES algorithm. The 56-bit key is stored as a 64-bit
quantity, with the least significant bit of each octet used as a par-
ity bit.
The secret MD5 key shared between the communicating parties SHOULD be
a cryptographically strong random number, not a guessable string of
any sort.
The MD5 key is not constrained by this transform to any particular
size. Lengths of up to 128-bits MUST be supported by the implementa-
tion, although any particular key may be shorter. Longer keys are
encouraged.
The two keys MUST appear to be unrelated. Knowing the value of one
key SHOULD NOT give an adversary an opportunity to calculate the
other key.
M, S & W expires in six months [Page 1]
DRAFT ESP DES-CBC-MD5 February 1996
Implementation Notes:
Using the same key(s) (or overlapping portion of the same overall
key) allows an attack exploiting mathematical relationships
between the different algorithms that might reveal some portion of
the session-key(s). Never-the-less, there is no known interaction
between the MD5 and DES-CBC algorithms.
Some implementors might adopt a strategy of systematically reveal-
ing some bits of the transform keys (to satisfy US export require-
ments for at most 40-bit secrecy algorithms). This is not recom-
mended; but if it is necessary, implementors MUST reveal only DES
key bits and not MD5 key bits. The independence of the two keys
is necessary for security.
1.2. Replay Protection
This transform provides replay protection: cryptographically secure
at-most-once best-effort datagram delivery. In other words, when an
adversary resends an earlier intercepted IP datagram, the recipient
will detect the attempt.
Each implementation maintains a counter. This counter serves both to
generate a per-message unique IV for DES, and also as a sequence num-
ber to provide replay protection.
When sending, the counter MUST be initialized to 0 for the first
datagram, and MUST be incremented (as a 32-bit unsigned integer)
after each datagram is sent.
On receipt, the sequence number is checked against a list of previ-
ously accepted numbers. There is no requirement that datagrams
arrive in order. As each datagram arrives, the sequence number is
stored so that it won't be accepted again.
Implementation Notes:
The exact algorithm is implementation dependent, but it MUST
reject datagrams with duplicate sequence numbers, and should make
a best effort to accept as many valid (non-duplicate) datagrams as
possible.
A full 2**32 element array storing the status of each sequence
number received is probably impractical. The following simple
algorithm is one possible improvement.
A low-water mark L is maintained; sequence numbers less than
M, S & W expires in six months [Page 2]
DRAFT ESP DES-CBC-MD5 February 1996
(earlier than) the low-water mark are automatically rejected.
A fixed window size W is chosen, according to storage constraints.
An array A[L..L+W-1] of size W is maintained, where each element
maintains the state (stale or fresh) of the corresponding sequence
number.
The following steps are applied to each incoming sequence number
S:
1. If S < L
drop the datagram.
2. If S < L+W and A[S] == stale
drop the datagram.
3. If S < L+W and A[S] == fresh
set A[S] = stale and accept the datagram.
(note: S > L+W-1)
4. If A[L] == stale
Let x = L;
While A[x] == stale
Do set x = x + 1.
Let y = L;
Let L = x.
(shift the array A[] down by y-L elements in memory if necessary,
so now A[] has the new bounds L..L+W-1)
Set A[j] = fresh for y+W-1 < j < L+W.
Goto Step 1.
(note: S > L+W-1 and A[L] == fresh)
5. Let y = L;
Let L = S-W+1.
(shift the array A[] down by y-L elements in memory if necessary,
so now A[] has the new bounds L..L+W-1 i.e. L..S)
Set A[j] = fresh for y+W-1 < j < L+W.
Set A[S] = stale and accept the datagram.
Two invariants are maintained in this algorithm. First, all
sequence numbers S < L are stale. Second, all sequence numbers S
> L+W-1 are fresh.
Note that step 5 forgets some state information, and may cause
M, S & W expires in six months [Page 3]
DRAFT ESP DES-CBC-MD5 February 1996
out-of-order datagrams which were sent earlier but received later
to be (incorrectly) judged stale and dropped. Though this algo-
rithm may inadvertenly reject a fresh datagram as stale, the
important point is that it will never accept a replayed datagram.
An implementation may wish to go through with step 5 only for
packets that pass the authentication verification.
This is only one possible algorithm; implementators may choose
another, so long as it rejects replayed datagrams with duplicate
sequence numbers.
1.3. Initialization Vector
This mode of DES requires an Initialization Vector (IV) that is eight
octets (64-bits) in length.
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 re-ordered in
transit.
The IV is generated from the SPI and Sequence fields. An MD5 hash is
calculated over the following concatenated values:
+ the DES key (8 octets including parity bits),
+ the SPI (4 octets),
+ the Sequence (4 octets),
+ the MD5 key (variable length).
The most significant 64-bits of the generated hash are used for the
final IV.
1.4. Data Size
The DES algorithm operates on blocks of eight octets (64-bits). This
often requires padding after the end of the unencrypted payload data.
Both input and output result in the same number of octets. This
facilitates in-place encryption and decryption.
MD5's 128-bit output is naturally 64-bit aligned. There is no fur-
ther padding of the Authentication Data field.
On receipt, if the length of the data to be decrypted is not an inte-
gral multiple of eight octets, then an error is indicated, as
M, S & W expires in six months [Page 4]
DRAFT ESP DES-CBC-MD5 February 1996
described in [RFC-1825].
1.5. Performance
In general, DES software speeds are considerably slower than MD5
software, while DES hardware is considerably faster than MD5 hard-
ware.
MD5 software speeds are adequate for commonly deployed LAN and WAN
links, but reportedly are too slow for newer link technologies
[RFC-1810].
Phil Karn has tuned DES software to achieve 10.45 Mbps with a 90 MHz
Pentium. Other DES speed estimates may be found at [Schneier95, p
279].
M, S & W expires in six months [Page 5]
DRAFT ESP DES-CBC-MD5 February 1996
2. Payload Format
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Security Parameters Index (SPI) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sequence |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Payload Data ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
... Padding | Pad Length | Payload Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Authentication Data ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Security Parameters Index (SPI)
4 octets. Identifies the Security Parameters for
this datagram. The value MUST NOT be zero.
Sequence 4 octets. Provides replay prevention, and a seed
for calculating the final IV, as described earlier.
Payload Data variable.
Prior to encryption and after decryption, this field
begins with the IP Protocol/Payload header specified
in the Payload Type field. Note that in the case of
IP-in-IP encapsulation (Payload Type 4), this will
be another IP header.
Padding 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 eight octet boundary.
After decryption, it MUST be ignored.
Pad Length 1 octet. 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 7, but
may be up to 255 to permit hiding of the actual data
length.
M, S & W expires in six months [Page 6]
DRAFT ESP DES-CBC-MD5 February 1996
This field is opaque. That is, the value is set
prior to encryption, and is examined only after
decryption.
Payload Type 1 octet. 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,
indicating IP-in-IP encapsulation.
Authentication Data
16 octets. Filled with the result of the MD5 calcu-
lation.
M, S & W expires in six months [Page 7]
DRAFT ESP DES-CBC-MD5 February 1996
3. Algorithm
In DES-CBC, each plaintext block is XOR'd with the previous cipher-
text block, and the DES encryption function is applied to yield the
ciphertext for the current block. This provides for re-
synchronization when datagrams are lost.
For more explanation and implementation information for DES, see
[Schneier95].
3.1. Encryption
Append zero or more octets of (preferably random) padding to the
plaintext, to make its modulo 8 length equal to 6. For example, if
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
identifying the protocol header that begins the payload.
Provide an appropriate Initialization Vector (IV), as described ear-
lier.
Encrypt the payload with DES in CBC mode, producing a ciphertext of
the same length.
Octets are mapped to DES blocks in network order (most significant
octet first) [RFC-1700]. Octet 0 (modulo 8) of the payload corre-
sponds to bits 1-8 of the 64-bit DES input block, while octet 7 (mod-
ulo 8) corresponds to bits 57-64 of the DES input block.
Add the indicated SPI and Sequence in front of the Payload Data.
Append the Authentication Data, calculated over the SPI, Sequence,
Payload Data, padding, Pad Length, and Payload Type.
Construct an appropriate IP datagram for the target Destination. The
Total/Payload Length in the encapsulating IP Header reflects the
length of the encrypted data, plus the SPI, Sequence, padding, Pad
Length, Payload Type, and Authentication Data.
M, S & W expires in six months [Page 8]
DRAFT ESP DES-CBC-MD5 February 1996
3.2. Decryption
First, the SPI field is examined. This is used as an index into the
local Security Parameter table to find the negotiated parameters and
decryption key.
The Authentication Data is verified and removed.
The SPI and Sequence fields are removed, and an appropriate 64-bit IV
value is constructed.
The encrypted part of the payload is decrypted using DES 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.
3.3. Authentication
The 128-bit digest is calculated as described in [RFC-1321]. The
specification of MD5 includes a portable 'C' programming language
description of the MD5 algorithm.
The form of the authenticated message is
MD5( key, keyfill, MD5( key, keyfill, data, MD5fill), MD5fill )
First, the variable length secret authentication key is filled to the
next 512-bit boundary, using the same pad with length technique
defined for MD5.
Second, the filled key is concatenated with (immediately followed by)
the SPI, Sequence, Payload Data, padding, Pad Length, and Payload
Type.
A trailing pad with length to the next 512-bit boundary for the
entire message is added by MD5 itself. The 128-bit MD5 digest is
calculated.
M, S & W expires in six months [Page 9]
DRAFT ESP DES-CBC-MD5 February 1996
Third, the filled key is again concatenated with (immediately fol-
lowed by) the previous digest.
A trailing pad with length to the next 512-bit boundary for the
entire message is added by MD5 itself. The 128-bit MD5 digest is
calculated, and the result is inserted into the Authentication Data
field.
Discussion:
The leading copy of the key is padded in order to facilitate copy-
ing of the key at machine boundaries without requiring re-
alignment of the following datagram. The padding technique
includes a length that protects arbitrary length keys. Filling to
the MD5 block size also allows the key to be prehashed to avoid
the physical copy in some implementations. It is further sug-
gested that this might protect against some forms of cryptanaly-
sis, although no such weakness is yet known in keyed MD5 [KR95].
When the implementation adds the keys and padding in place before
and after the IP datagram, care must be taken that the keys and/or
padding are not sent over the link by the link driver.
M, S & W expires in six months [Page 10]
DRAFT ESP DES-CBC-MD5 February 1996
A. Deriving Independent Keys
This algorithm is suggested for those implementors that desire to
configure only one master key, and derive two apparently indepen-
dent keys.
The master key shall be considered the key of this transform. The
master key length MUST be between 56 and 128 bits; larger values
are recommended.
DES key: PK = most significant 64-bits of MD5("DES", master key).
The 3-byte ASCII string "DES" is followed by (concatenated with)
the master key. That is hashed with the MD5 cryptographic hash,
and PK is the first 8 bytes (64-bits) of the hash output. The
least significant bits of DK are discarded, and replaced by the
appropriate DES parity check bits. The result is the DES privacy
key.
MKL = length of the master key in bits.
MD5 key: AK = most significant MKL bits of MD5("MD5", master key).
The 3-byte ASCII string "MD5" is followed by (concatenated with)
the master key. That is hashed with the MD5 cryptographic hash,
and AK is the first MKL bits of the hash output. This ensures
that the length of the authentication key accurately reflects its
entropy. The result is the MD5 authentication key.
Design Notes:
Any appropriate pair of strings may be used in place of "DES"
and "MD5".
This transform does not provide more than 56 bits of confiden-
tiality, regardless of the size of the master key. This
derivation provides only as many bits of message authentication
as the minimum of {master key length, 128-bits}.
This simple key scheduling algorithm will not work with a hard-
ware token that must generate the DES key itself (a la Clip-
per).
M, S & W expires in six months [Page 11]
DRAFT ESP DES-CBC-MD5 February 1996
Security Considerations
Users need to understand that the quality of the security provided
by this specification depends completely on the strength of the
DES and MD5 algorithms, the correctness of the algorithm's imple-
mentation, the security of the key management mechanism and its
implementation, the strength of the key [CN94], and upon the cor-
rectness of the implementations in all of the participating nodes.
MD5
At the time of writing of this document, it is known to be pos-
sible to produce collisions in the compression function of MD5
[dBB93]. There is not yet a known method to exploit these col-
lisions to attack MD5 in practice, but this fact is disturbing
to some authors [Schneier95].
It has also recently been determined [vOW94] that it is possi-
ble to build a machine for $10 Million that could find two cho-
sen text variants with a common MD5 hash value. However, it is
unclear whether this attack is applicable to a keyed MD5 trans-
form.
This attack requires approximately 24 days. The same form of
attack is useful on any iterated n-bit hash function, and the
time is entirely due to the 128-bit length of the MD5 hash.
Although there is no substantial weakness for most IP security
applications, it should be recognized that current technology
is catching up to the 128-bit hash length used by MD5. Appli-
cations requiring extremely high levels of security may wish to
move in the near future to algorithms with longer hash lengths.
DES
Among other considerations, applications may wish to take care
not to select weak keys, although the odds of picking one at
random are low [Schneier95, p 280].
At the time of writing of this document, [BS93] demonstrated a
differential cryptanalysis based chosen-plaintext attack
requiring 2**47 plaintext-ciphertext pairs, and [Matsui94]
demonstrated a linear cryptanalysis based known-plaintext
attack requiring only 2**43 plaintext-ciphertext pairs.
Although these attacks are not considered practical, they must
be taken into account.
More disturbingly, [Weiner94] has shown the design of a DES
M, S & W expires in six months [Page 12]
DRAFT ESP DES-CBC-MD5 February 1996
cracking machine costing $1 Million that can crack one key
every 3.5 hours. This is an extremely practical attack.
One or two blocks of known plaintext suffice to recover a DES
key. Because IP datagrams typically begin with a block of
known and/or guessable header text, frequent key changes will
not protect against this attack.
It is suggested that DES is not a good encryption algorithm for
the protection of even moderate value information in the face
of such equipment. Triple DES is probably a better choice for
such purposes.
However, despite these potential risks, the level of privacy
provided by use of ESP DES-CBC in the Internet environment is
far greater than sending the datagram as cleartext.
Acknowledgements
Some of the text of this specification was derived from work by
Randall Atkinson for the SIP, SIPP, and IPv6 Working Groups.
This basic concept and use of DES and MD5 were derived in large
part from the work done for SNMPv2 [RFC-1446].
Much of the implementation details were derived from work by Phil
Karn.
Bart Preneel suggested the hash protection of the IV, to render it
impossible to correlate with subsequent IVs.
David Wagner was responsible for the description of replay preven-
tion.
The message authentication mechanism is based on one of the vari-
ants discussed in [KR95].
M, S & W expires in six months [Page 13]
DRAFT ESP DES-CBC-MD5 February 1996
References
[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.
[dBB93] den Boer, B., and Bosselaers, A., "Collisions for the
Compression function of MD5", Advances in Cryptology --
Eurocrypt '93 Proceedings, Berlin: Springer-Verlag 1994
[FIPS-46]
US National Bureau of Standards, "Data Encryption Stan-
dard", Federal Information Processing Standard (FIPS)
Publication 46, January 1977.
[FIPS-46-1]
US National Bureau of Standards, "Data Encryption Stan-
dard", Federal Information Processing Standard (FIPS)
Publication 46-1, January 1988.
[FIPS-74]
US National Bureau of Standards, "Guidelines for Imple-
menting 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) Publica-
tion 81, December 1980.
[KR95] Kaliski, B., and Robshaw, M., "Message authentication
with MD5", CryptoBytes (RSA Labs Technical Newsletter),
vol.1 no.1, Spring 1995.
[Matsui94]
Matsui, M., "Linear Cryptanalysis method dor DES Cipher,"
Advances in Cryptology -- Eurocrypt '93 Proceedings,
Berlin: Springer-Verlag, 1994.
[RFC-1321]
Rivest, R., "The MD5 Message-Digest Algorithm", RFC-1321,
DDN Network Information Center, April 1992.
M, S & W expires in six months [Page 14]
DRAFT ESP DES-CBC-MD5 February 1996
[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.
[RFC-1810]
Touch, J., "Report on MD5 Performance", USC/Information
Sciences Institute, June 1995.
[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.
[Schneier95]
Schneier, B., "Applied Cryptography Second Edition", John
Wiley & Sons, New York, NY, 1995. ISBN 0-471-12845-7
[Weiner94]
Wiener, M.J., "Efficient DES Key Search", School of Com-
puter Science, Carleton University, Ottawa, Canada,
TR-244, May 1994. Presented at the Rump Session of
Crypto '93.
[vOW94] van Oorschot, P. C., and Wiener, M. J., "Parallel Colli-
sion Search with Applications to Hash Functions and Dis-
crete Logarithms", Proceedings of the 2nd ACM Conf. Com-
puter and Communications Security, Fairfax, VA, November
1994.
M, S & W expires in six months [Page 15]
DRAFT ESP DES-CBC-MD5 February 1996
Author's Address
Questions about this memo can also be directed to:
Perry Metzger
Piermont Information Systems Inc.
160 Cabrini Blvd., Suite #2
New York, NY 10033
perry@piermont.com
William Allen Simpson
Daydreamer
Computer Systems Consulting Services
1384 Fontaine
Madison Heights, Michigan 48071
Bill.Simpson@um.cc.umich.edu
bsimpson@MorningStar.com (prefered)