Internet Draft October 1996 (Expires April 1997)
M. Sabin, Consultant
R. Monsour, Hi/fn Inc.
Combined 3DES-CBC, LZS Compression, HMAC, and Replay Prevention
ESP Transform
<draft-sabin-esp-des3-lzs-md5-00.txt>
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).
Abstract
This document proposes the "3DES-CBC-LZS-HMAC-Replay" security
transform for the IP Encapsulating Security Payload (ESP). The
proposed transform combines triple-DES encryption, LZS compression,
HMAC authentication, and replay prevention into a single packet
format. The transform is compatible with implementations that do not
support compression and with implementations that support only
single-DES encryption. Compression is performed prior to encryption,
which has the side benefit of reducing the amount of data that must
be encrypted.
This document is based on the IPsec Working Group's proposed
"Combined DES-CBC, HMAC, and Replay Prevention Security Transform,"
cited later in this document.
Acknowledgments
This memo is based on the document "Combined DES-CBC, HMAC, and
Replay Prevention Security Transform," by the IPsec Working Group, J.
Sabin, et al [Page 1]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
Hughes, editor [Hughes96]. Much of the text of that document is
repeated here, with details specific to LZS and triple-DES added.
The LZS details are similar to those in "PPP Stac LZS Compression
Protocol," by R. Friend and W. A. Simpson [RFC-1974].
Table of Contents
1. Introduction
2. Packet Format
3. Encode Procedure
4. Decode Procedure
5. Generating Key Material
6. Security Considerations
7. References
8. Author's Addresses
9. Appendix: Guidelines for Resetting Compression History
1. Introduction
Encrypted data is random in nature and not compressible. When an IP
packet is encrypted, the usual techniques for compressing it -- e.g.,
PPP compression -- do not work. If both compression and encryption
are desired, compression must be performed first.
1.1 Compression with ESP
ESP is well suited to combining compression with encryption, for a
variety of reasons:
- ESP is the place were encryption is applied to an IP packet.
It is straightforward to precede the encryption step by a
compression step. A side benefit of compressing the data first
is that the amount of data which must be encrypted is reduced.
In some implementations, compression is done in hardware and
encryption in software, and this represents a significant
reduction in software processing.
- ESP supports routing of opaque data. When a packet is
encrypted, intermediate nodes along a route are not able to
decrypt it. Nevertheless, the encrypted packet can be routed,
because ESP has been designed with this in mind. When a packet
is compressed within ESP, the situation is similar:
intermediate nodes are not able to decompress it (at least
without additional expense), but ESP ensures that the
compressed packet can be routed.
- ESP provides a security parameters index (SPI) that links a
packet to security parameters negotiated elsewhere. A
Sabin, et al [Page 2]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
destination node uses the SPI to look up the ESP transform
needed to decode an incoming packet. If compression details
are included in ESP transform specifications, a destination
node can also use the SPI to determine if a packet needs to be
decompressed, and if so, by what algorithm. Source and
destination nodes can maintain multiple compression histories
(described in a later section), one history for each SPI.
1.2 Background of LZS Compression
The LZS algorithm is a lossless compression method that uses a
sliding window of 2,048 bytes. During compression, redundant
sequences of data are replaced with tokens that represent those
sequences. During decompression, the original sequences are
substituted for the tokens, in such a way that the original data
is exactly recovered. LZS differs from lossy schemes, such as
those often used for video compression, that do not exactly
reproduce the original data.
Details of LZS formatting can be found in [ANSI94].
The efficiency of the LZS algorithm depends on the degree of
redundancy in the original data. A typical compression ratio for
disk files is 2:1. LZS achieves a compression ratio of 2.34:1 on
the University of Calgary Text Compression Corpus [Calgary].
The LZS algorithm is stateful. It maintains a "history" in which
compression information is stored. The compression operation
requires a "compression history" and the decompression operation a
"decompression history." Each of these histories is initialized to
a start state before any data is processed. Thereafter, as data
is compressed and decompressed, the two histories remain
synchronized, provided that the decompressor processes all the
data generated by the compressor, in the order in which it is
generated.
An LZS compression/decompression history pair can be reset to the
start state at any time. This can be used to restore
synchronization between compressor and decompressor when data
received by the decompressor has been lost or corrupted. This is
particularly important in IP, where the delivery of individual
packets is not guaranteed.
When LZS compression is applied to a block of data, it sometimes
happens that the "compressed" block is actually larger than the
original, uncompressed block. In IP, it would be undesirable to
transmit a block that has expanded in this way. Accordingly, when
LZS results in expansion, this specification calls for the
transmitter to send the uncompressed data instead of the
compressed data. The packet format includes a bit to signal the
Sabin, et al [Page 3]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
receiver that the packet contents are not compressed.
When the transmitter sends uncompressed data, it still updates its
compression history as if it had actually compressed the data.
This enhances its ability to compress future data. When the
receiver receives uncompressed data, it updates its decompression
history using the uncompressed data. This keeps the decompression
history in sync with the compression history.
An application can maintain multiple compression and/or
decompression processes by maintaining multiple histories, one
history for each process. Each process operates independently of
the others. This is useful in IPsec, since it allows each
security association (as indexed by the SPI) to have its own
history.
1.3 Licensing
Source and object licenses for LZS are available on a
non-discriminatory basis. Hardware implementations are also
available. For more information, contact Hi/fn at the address
listed with the authors' addresses.
1.4 3DES-CBC-LZS-HMAC-Replay ESP Transform
The transform proposed in this memo combines triple-DES in CBC
mode (3DES-CBC), LZS compression, HMAC authentication, and replay
prevention. The proposed transform is based heavily on the
transform presented in [Hughes96]. Much of the text from that
document has been repeated here.
The goals of the transform are: privacy; compression;
authenticity; integrity; and defense against replay.
- Privacy is provided by 3DES-CBC [RFC-1851], which is a
variant of conventional DES-CBC [FIPS-46] [FIPS-46-1] [FIPS-74]
[FIPS-81].
- Compression is provided by the LZS algorithm [ANSI94].
- Integrity is provided by HMAC [Krawczyk96].
- Authentication is provided since only the source and
destination know the HMAC key. If the HMAC is correct, it
proves that it must have been added by the source.
- Replay prevention is provided by the combination of a
constantly increasing count, the SPI and the HMAC key.
Integrity of the count is provided by the HMAC.
Sabin, et al [Page 4]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
3DES-CBC encryption uses a double-length key (112 bits) or a
triple-length key (168 bits). Triple-length is usually preferred for
security reasons, but some hardware devices only support
double-length. Accordingly, this transform supports both
double-length and triple-length keys as a negotiated parameter.
The transform also supports single-length keys (56 bits) as a
negotiated parameter. This makes it compatible with implementations
that only support conventional (i.e., single) DES-CBC.
1.5 Requirements Terminology
In this document, the words that are used to define the
significance of each particular requirement are usually
capitalized. These words are:
- MUST: This word, or the adjective "REQUIRED," means that the
item is an absolute requirement of the specification.
- SHOULD: This word, or the adjective "RECOMMENDED," means
that there might exist valid reasons in particular
circumstances to ignore this item, but the full implications
should be understood and the case carefully weighed before
taking a different course.
- MAY: This word, or the adjective "OPTIONAL," means that the
item is truly optional. One vendor might choose to include the
item because of a particular marketplace requirement or because
it enhances the product, while another vendor might omit the
item.
Sabin, et al [Page 5]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
2. Packet Format
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---
| Security Parameters Index (SPI) | ^
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| | |
| Initialization Vector (optional) | |
| | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ---
| Replay Prevention Field (count) | | ^
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
| |HMAC |
| Payload Data (compressed or uncompressed) | | |
| | | |
| +-+-+-+-+-+-+-+-| | |
| | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | 3DES
| Padding (0-7 bytes) | | CBC
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
| | Pad Length | CC | Payload Type | v |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--- |
| | |
| HMAC digest | |
| | v
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---
2.1 Security Parameters Index
This field contains a 32-bit value identifying the security
association for this packet. The value is negotiated at key setup
and MUST NOT be 0.
2.2 Initialization Vector
The use of an explicit initialization vector (IV) MAY be
negotiated. The purpose of this mode is to support devices that
automatically generate IV's and cannot operate using a constant
IV_key_.
This field is optional and is only used when an explicit IV is
negotiated during key exchange. This field contains random data
or the last ciphertext block of the previous packet.
2.3 Replay Prevention
This field contains an unsigned, 32-bit, incrementing counter.
The counter is initialized to a mutually agreed upon value (see
Sabin, et al [Page 6]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
the section on Generating Key Material).
2.3.1 Security Issues
To defend against replay attacks, the receiver verifies that
received packets have non-repeating counter values. The
simplest approach is for the receiver to reject any packet
whose counter has a value less than or equal to that of any
previously received packet. A consequence of this simple
approach is that out-of-order packets will be rejected.
Alternatively, the receiver MAY choose to operate with a window
of acceptable counter values: a packet will not be rejected if
its counter value is within some value M of the highest counter
value received so far, provided that the counter value has not
been seen before. For an example implementation of such a
strategy, see [Hughes96].
The counter is not allowed to cycle back to its starting value.
This requires that the key be changed before 2^32 packets have
been transmitted. The receiver rejects any packet whose
counter value indicates cycling back through the starting
value.
2.3.2 Compression Issues
In addition to defending against replay attacks, the counter
plays a role in the decompression of packets. When a packet is
received out of order, the receiver detects the misordering
because of the counter value. Because LZS is stateful, the
receiver may or may not be able to decompress the out-of-order
packet. If the history was reset by the transmitter
immediately prior to compressing the packet, the receiver can
decompress it, because decompression does not depend on any
previous packets. (The packet includes a flag in the CC field
that indicates whether or not the history was reset.) But if
the history was not reset by the transmitter immediately prior
to compressing the packet, the receiver cannot decompress it.
When a receiver is unable to decompress an out-of-order packet,
the simplest strategy for the receiver is to discard it.
Alternatively, a receiver MAY elect to use a windowing scheme
similar to that described in Section 2.3.1, in order to
accommodate a reasonable spread of out-of-order packets. Note
that if the windowing scheme is used, the receiver must queue
all packets that fall within the window but are not yet
decompressible. This makes it more expensive than the scheme
previously described, which only had to queue counter values.
Decompressing out-of-order packets is only an issue for the
Sabin, et al [Page 7]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
final destination of a packet. Intermediate nodes along a
route do not decompress packets and thus can handle packets in
any order.
2.4 Payload Data
The payload data is either compressed or uncompressed. The value
of the COMPRESSED bit of the CC field is set accordingly. The
payload field is an integral number of bytes in length.
2.5 Padding
The padding is used to align the subsequent "payload type" field
to end on a double-word boundary, counting from the start of the
replay field. Padding bytes SHOULD contain random data.
At a minimum, the number of padding bytes added must be enough to
align the payload type field on the next appropriate boundary.
However, the sender may choose to include additional padding, in
order to hide the actual length of the data. In general, the
sender can use any number of padding bytes in the range of 0-255,
provided that the required alignment is achieved.
2.6 Pad Length
This field indicates the number of padding bytes immediately
preceding it. The range of valid values is 0-255, where a value
of zero indicates the byte immediately preceding the pad length
field is the last byte of payload.
2.7 Compression Control
The Compression Control (CC) field is a single, bit-mapped byte.
The bits are numbered 7 (most significant) to 0 (least
significant). The following bits are defined:
2.7.1 COMPRESSED (bit 7)
This bit is set to 1 to indicate the payload is compressed. It
is cleared to 0 to indicate the payload is not compressed.
In implementations that do not support compression, this bit
is always cleard to 0.
Sabin, et al [Page 8]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
2.7.2 HIST_RESET (bit 6)
This bit is set to 1 to indicate that the compression history
associated with this packet's SPI was reset prior to processing
this packet's payload. In such a case, the receiver must reset
the corresponding decompression history prior to processing the
payload. If the payload is compressed, it can always be
decompressed, because compression is not based on any previous
history.
This bit is cleared to 0 to indicate that the compression
history associated with this packet's SPI was not reset prior
to transmitting the payload. If the payload is compressed, it
can only be decompressed if there have been no missed packets
since the last packet that had the bit set to 1. A packet that
cannot be decompressed because of missing packets is either
rejected or, if the implementation supports it, queued in the
hope that it can be decompressed when the missing packets
arrive.
The transmitter SHOULD adopt a policy of periodically resetting
the compression history and setting the HIST_RESET bit. This
allows a receiver that has missed packets to resynchronize its
decompressor. The details of such a policy are up to the
transmitter implementation. An attached appendix gives
guidelines.
The transmitter MUST flush the compressor each time it
transmits a compressed packet, regardless of whether or not it
resets the compression history. Flushing means that all data
going into the compressor is included in the output, i.e., no
data is held back in the hope of achieving better compression.
Flushing is necessary to prevent a packet's data from spilling
over into a later packet.
2.8 Payload Type
This field indicates the type of payload, using the IP
Protocol/Payload value. Values are described in [RFC-1700].
2.9 HMAC Digest
The HMAC digest is a 128-bit residue, calculated over the SPI,
replay, payload, padding, pad length, CC, and payload type.
Details of the calculation can be found in [Krawczyk96].
HMAC is a keyed algorithm based on MD5. It uses the HMAC key
described in the section on keys.
Sabin, et al [Page 9]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
3. Encode Procedure
For compression, the LZS algorithm is used.
For encryption, CBC chaining is used. The initialization vector is
either the contents of the IV field or the IV_key_:
IV or
IV_key_ count|x1 x2 x3
| | | |
|--------(+) ----------(+) ----------(+)
| | | | |
--------- | --------- | ---------
k1--| DES | | k1--| DES | | k1--| DES |
|encrypt| | |encrypt| | |encrypt|
--------- | --------- | ---------
| | | | |
--------- | --------- | ---------
k2--| DES | | k2--| DES | | k2--| DES |
|decrypt| | |decrypt| | |decrypt|
--------- | --------- | ---------
| | | | |
--------- | --------- | ---------
k3--| DES | | k3--| DES | | k3--| DES |
|encrypt| | |encrypt| | |encrypt|
--------- | --------- | ---------
|------| |------| |----...
| | |
y1 y2 y3
In the figure: count is the value in the replay prevention field;
x1, x2, x3 are the plaintext (x1 is 32 bits, all others are 64 bits);
y1, y2, y3 are the ciphertext; k1, k2, k3 are the 56-bit portions of
the triple-length key. (When a double-length key is used, k3 = k1.
When a single-length key is used, k3 = k2 = k1.)
The transform is carried out in the following steps:
i) If the transmitter chooses to reset the compression history,
it does so, and it sets the HIST_RESET bit of the CC field to 1.
Otherwise, it clears the HIST_RESET bit to 0.
ii) The transmitter decides whether or not to compress the
payload.
- If the transmitter chooses to compress the payload, the LZS
algorithm is applied. The resulting compressed data is
formatted according to [ANSI94]. The COMPRESSED bit of the CC
Sabin, et al [Page 10]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
field is set to 1.
- If the transmitter chooses not to compress the payload, the
COMPRESSED bit of the CC field is set to 0. The compression
history is updated with the uncompressed payload.
iii) The payload is encapsulated with the SPI, IV (if used),
replay, padding, pad length, CC, and payload type. The padding
and pad length are appropriately adjusted. The replay is
incremented by one from its previous value.
iv) The HMAC is calculated. The calculation uses the HMAC_key_
and spans the SPI, IV (if used), replay, payload, padding, pad
length, CC, and payload type. The result is placed in the HMAC
digest field.
v) The replay, payload, padding, pad length, CC, payload type,
and HMAC digest are encrypted using 3DES-CBC with the appropriate
DES_key_. The initialization vector is the IV field, if used, or
the appropriate IV_key_.
An implementation SHOULD monitor the results of the payload
compression operation and reject the operation if it results in
expansion. In such a case, the uncompressed payload SHOULD be
transmitted.
Sabin, et al [Page 11]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
4. Decode Procedure
For decryption, CBC chaining is used:
IV or
IV_key_ y1 y2 y3
| | | |
| |------- |------- |----...
| | | | | |
| --------- | --------- | ---------
| k3--| DES | | k3--| DES | | k3--| DES |
| |decrypt| | |decrypt| | |decrypt|
| --------- | --------- | ---------
| | | | | |
| --------- | --------- | ---------
| k2--| DES | | k2--| DES | | k2--| DES |
| |encrypt| | |encrypt| | |encrypt|
| --------- | --------- | ---------
| | | | | |
| --------- | --------- | ---------
| k1--| DES | | k1--| DES | | k1--| DES |
| |decrypt| | |decrypt| | |decrypt|
| --------- | --------- | ---------
| | | | | |
|---------(+) |---------(+) |---------(+)
| | |
(count|x1) x2 x3
For decompression, the LZS algorithm is used. The decompression
maintains a state variable "expected_count," which tracks the value
of count expected in the next packet. Expected_count is initialized
to the starting value of the replay count; this value was mutually
agreed upon, as described in the section on Generating Key Material.
In the procedure described here, it is assumed that out-of-order
packets are not queued for the purposes of decompression. Compressed
packets that cannot be immediately decompressed are discarded.
Implementations MAY choose a scheme that queues packets, allowing
some spread of out-of-order packets to be decompressed; this was
discussed in Section 2.3.2.
The transform is carried out in the following steps:
i) The replay, payload, padding, pad length, CC, payload type,
and HMAC digest are decrypted using 3DES-CBC and the appropriate
DES_key_. The initialization vector is the IV field, if used, or
the appropriate IV_key_.
ii) The count is checked for replay attack using the window
Sabin, et al [Page 12]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
algorithm discussed in Section 2.3.1. If the packet is duplicate
or too old, the packet is discarded.
iii) The HMAC is calculated. The calculation uses the HMAC_key_
and spans the SPI, IV (if used), replay, payload, padding, pad
length, CC, and payload type. The calculated digest is compared
against the decrypted digest at the end of the packet. If the two
do not match, the packet is discarded.
iv) The HIST_RESET bit of the CC is checked.
- If HIST_RESET = 1, the decompression history is reset, and
expected_count is set to (count + 1).
- If HIST_RESET = 0, the value of count is compared to
expected_count. If the two match, expected_count is set to
(count + 1). If the two do not match, expected_count is
unchanged; and if COMPRESSED = 1, the packet is discarded.
(Queuing out-of-order packets is not considered here, but an
implementation MAY choose to implement queuing instead of
immediate discard, as discussed in Section 2.3.2.)
v) The COMPRESSED bit of the CC is checked. If COMPRESSED = 1,
decompression is applied to the payload data. If COMPRESSED = 0,
decompression is not applied, and the decompression history is
updated with the uncompressed data.
An implementation MAY choose to perform a "sanity check" prior to the
above procedure. In the sanity check, the first block of data is
decrypted using the appropriate DES_key_ and IV_key_, and the
decrypted value of the replay count is checked. If the count is way
out of range -- e.g., more than 2^16 away from the expected value --
the packet is discarded as non-authentic. This helps defend against
clogging attacks, in which an attacker tries to tie up the receiver's
resources by having it decrypt meaningless packets. Note that if the
sanity check passes, the above procedure MUST still be performed.
5. Generating Key Material
The key management layer provides several negotiated parameters:
- The master secret K.
- The length of the DES symmetric keys: triple length (168 bits),
double length (112 bits), or single length (56 bits).
- Compression support: yes or no.
The master secret K is used to derive the following symmetric keys:
Sabin, et al [Page 13]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
DES_Key_I1, DES_Key_I2, and DES_Key_I3 are the three parts of the
triple-length DES key for traffic from the initiator -> responder.
When a double-length key is used, DES_Key_I3 = DES_Key_I1.
When a single-length key is used, DES_Key_I3 = DES_KEY_I2 =
DES_Key_I1.
DES_Key_R1, DES_Key_R2, and DES_Key_R3 are the three parts of the
triple-length DES key for traffic from the responder -> initiator.
When a double-length key is used, DES_Key_R3 = DES_Key_R1.
When a single-length key is used, DES_Key_R3 = DES_KEY_R2 =
DES_Key_R1.
HMAC_Key_I is the key for the HMAC Algorithm for traffic from the
initiator -> responder.
HMAC_Key_R is the key for the HMAC Algorithm for traffic from the
responder -> initiator.
IV_key_I is used to stop code book attacks on the first block for
traffic from the initiator -> responder.
IV_key_R is used to stop code book attacks on the first block for
traffic from the responder -> initiator.
RP_key_I is the initial value and wrap point for the replay
prevention field for traffic from the initiator -> responder.
RP_key_R is the initial value and wrap point for the replay
prevention field for traffic from the responder -> initiator.
The vertical bar symbol "|" is used to denote concatenation of bit
strings.
MD5(x|y) denotes the result of applying the MD5 function to the
concatenated bit strings x and y.
Truncate(x,n) denotes the result of truncating x to its first n bits.
IV_Key_I = Truncate(MD5( I_Pad_I | K ),64)
IV_Key_R = Truncate(MD5( I_Pad_R | K ),64)
HMAC_Key_I = MD5( H_Pad_I | K )
HMAC_Key_R = MD5( H_Pad_R | K )
RP_Key_I = Truncate(MD5( R_Pad_I | K ),32)
RP_Key_R = Truncate(MD5( R_Pad_R | K ),32)
For triple-length DES keys:
DES_Key_I1 = Truncate(MD5( D_Pad_I1 | K ),64)
DES_Key_I2 = Truncate(MD5( D_Pad_I2 | K ),64)
DES_Key_I3 = Truncate(MD5( D_Pad_I3 | K ),64)
DES_Key_R1 = Truncate(MD5( D_Pad_R1 | K ),64)
Sabin, et al [Page 14]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
DES_Key_R2 = Truncate(MD5( D_Pad_R2 | K ),64)
DES_Key_R3 = Truncate(MD5( D_Pad_R3 | K ),64)
For double-length DES keys:
DES_Key_I1 = Truncate(MD5( D_Pad_I1 | K ),64)
DES_Key_I2 = Truncate(MD5( D_Pad_I2 | K ),64)
DES_Key_I3 = DES_Key_I1
DES_Key_R1 = Truncate(MD5( D_Pad_R1 | K ),64)
DES_Key_R2 = Truncate(MD5( D_Pad_R2 | K ),64)
DES_Key_R3 = DES_Key_R1
For single-length DES keys:
DES_Key_I1 = Truncate(MD5( D_Pad_I1 | K ),64)
DES_Key_I3 = DES_Key_I2 = DES_Key_I1
DES_Key_R1 = Truncate(MD5( D_Pad_R1 | K ),64)
DES_Key_R3 = DES_Key_R2 = DES_Key_R1
Note: Each DES_Key_ is in the usual "7 bits plus parity" format,
which is why the above procedure generates 64 bits instead of 56
bits. The values of the parity bits in each DES_Key_ should either
be corrected or ignored.
Each _Pad_is a 512 bit string, as follows:
D_Pad_I1 = 0x5C repeated 64 times
D_Pad_I2 = 0xA3 repeated 64 times
D_Pad_I3 = 0xCA repeated 64 times
D_Pad_R1 = 0x3A repeated 64 times
D_Pad_R2 = 0xA5 repeated 64 times
D_Pad_R3 = 0xC3 repeated 64 times
I_Pad_I = 0xAC repeated 64 times
I_Pad_R = 0x55 repeated 64 times
H_Pad_I = 0x53 repeated 64 times
H_Pad_R = 0x3C repeated 64 times
R_Pad_I = 0x35 repeated 64 times
R_Pad_R = 0xCC repeated 64 times
(Implementation note: The 16 byte intermediate residuals can be
precalculated from these constants and stored to reduce processing
overhead.)
6. Security Considerations
The transform described in this draft is immune to the [Bellovin96]
attacks.
The implications of the size of K can be found in [Blaze96].
Sabin, et al [Page 15]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
7. References
[ANSI94] American National Standards Institute, Inc., "Data
Compression Method for Information Systems," ANSI X3.241-1994,
August 1994.
[Blaze96] Blaze, M., Diffie, W., Rivest, R., Schneir, B., Shimomura,
T., Thompson, E., Wiener, M., "Minimal Key Lengths for Symmetric
Ciphers to Provide Adequate Commercial Security,"
http://theory.lcs.mit.edu/~rivest/bsa-final-report.ascii, January
1996.
[Calgary] Text Compression Corpus, University of Calgary, available
at
ftp://ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus.
[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.
[Hughes96] Hughes, J. editor, "Combined DES-CBC, HMAC, and Replay
Prevention Security Transform," work-in-progress, available from
ftp://ds.internic.net/internet-drafts
/draft-ietf-ipsec-esp-des-md5-03.txt.
[Krawczyk96] Krawczyk, H., Bellare, M., Canetti, R., "HMAC-MD5:
Keyed-MD5 for Message Authentication," work-in-progress, available
from
ftp://ds.internic.net/internet-drafts
/draft-ietf-ipsec-hmac-md5-00.txt.
[RFC-1700] Reynolds, J., and Postel, J., "Assigned Numbers," STD 2,
RFC-1700, UCS/Information Sciences Institute, October 1994.
[RFC-1974] Friend, R., and Simpson, W.A., "PPP Stac LZS Compression
Protocol," RFC-1974, Stac Electronics, August 1996.
[RFC-1851] Karn, P., Metzger, P., and Simpson, W., "The ESP Triple
Sabin, et al [Page 16]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
DES Transform," RFC-1851, Qualcomm, September 1995.
8. Authors' Addresses
Michael Sabin
883 Mango Avenue
Sunnyvale, CA 94087
Email: mike.sabin@worldnet.att.net
Robert Monsour
Hi/fn Inc.
12636 High Bluff Drive
San Diego, CA 92130
Email: rmonsour@hifn.com
9. Appendix: Guidelines for Resetting Compression Histories
The following table offers some guidance on how frequently an LZS
compression history can be reset. The table considers two
parameters: "payload_bytes," the number of bytes in each payload; and
"reset_bytes," the number of bytes between history resets.
Reset_bytes is a multiple of payload_bytes, since an integer number
of payloads is processed between resets. Each entry in the table
shows the compression ratio that was achieved when compressing a test
file with the corresponding values of payload_bytes and reset_bytes.
The test file was the University of Calgary Text Compression Corpus
[Calgary]. The length of the file prior to compression was 3,278,000
bytes. When the entire file was compressed as a single payload, a
compression ratio of 2.34 resulted.
| reset_bytes
| 64 128 256 512 1024 2048 4096 8192 16384
------------+-----------------------------------------------------
packet_bytes|
64 | 1.18 1.26 1.37 1.48 1.61 1.74 1.84 1.89 1.92
128 | 1.28 1.40 1.53 1.67 1.82 1.93 1.99 2.03
256 | 1.43 1.56 1.71 1.86 1.98 2.05 2.08
512 | 1.58 1.73 1.89 2.01 2.08 2.11
1024 | 1.74 1.90 2.02 2.09 2.13
2048 | 1.91 2.03 2.10 2.14
4096 | 2.04 2.10 2.14
8192 | 2.11 2.14
16384 | 2.14
The table suggests that not there is not much degradation in
compression ratio if the compression history is reset after several
Sabin, et al [Page 17]
INTERNET DRAFT 3DES-CBC-LZS-HMAC-Replay ESP October 1996
thousand bytes have been processed. Resetting after less than 1,000
bytes is probably too soon -- the compression ratio degrades
significantly. But waiting longer than about 8,000 bytes gains
little -- the compression ratio does not increase much.
Sabin, et al [Page 18]