Network Working Group J. Etienne
Internet-Draft May 14, 2001
Expires: November 12, 2001
The counter-mode and its use with ESP
draft-etienne-ipsec-esp-ctr-mode-00.txt
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
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."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on November 12, 2001.
Copyright Notice
Copyright (C) The Internet Society (2001). All Rights Reserved.
Abstract
This memo presents the use of the counter mode in the context of ESP
and specifies its application to DES, 3DES and AES. The counter mode
significantly reduces the ESP space overhead compared to the standard
CBC with explicit IV (Section 5.2.1). Moreover, the counter mode
allows parallelisation and precomputation of most of the processing
(Section 5.1).
Etienne Expires November 12, 2001 [Page 1]
Internet-Draft counter mode with ESP May 2001
Table of Contents
1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Description of the counter mode . . . . . . . . . . . . . . 3
1.2 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Counter . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 Counter construction . . . . . . . . . . . . . . . . . . . . 4
2.2 Counter Uniqueness . . . . . . . . . . . . . . . . . . . . . 5
3. Encryption and decryption . . . . . . . . . . . . . . . . . 5
3.1 Counter initialization . . . . . . . . . . . . . . . . . . . 6
3.2 Pad's length computation . . . . . . . . . . . . . . . . . . 6
3.3 Generate N_BLK blocks of pad . . . . . . . . . . . . . . . . 6
3.4 Apply the pad . . . . . . . . . . . . . . . . . . . . . . . 6
4. Assumptions and limitations . . . . . . . . . . . . . . . . 6
4.1 relation to anti-replay . . . . . . . . . . . . . . . . . . 6
4.2 relation to authentication algorithms . . . . . . . . . . . 7
4.3 relation to encryption algorithms . . . . . . . . . . . . . 7
5. Performance Evaluation . . . . . . . . . . . . . . . . . . . 7
5.1 Speed evaluation . . . . . . . . . . . . . . . . . . . . . . 7
5.2 Space evaluation . . . . . . . . . . . . . . . . . . . . . . 8
5.2.1 Comparison with CBC and explicit IV . . . . . . . . . . . . 8
6. Application to cipher algorithms . . . . . . . . . . . . . . 8
6.1 Mode of operations . . . . . . . . . . . . . . . . . . . . . 8
6.2 Key size . . . . . . . . . . . . . . . . . . . . . . . . . . 9
6.3 Weak keys . . . . . . . . . . . . . . . . . . . . . . . . . 9
6.4 block size and padding . . . . . . . . . . . . . . . . . . . 10
6.5 rounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7. Security considerations . . . . . . . . . . . . . . . . . . 10
8. Acknowledgement . . . . . . . . . . . . . . . . . . . . . . 11
References . . . . . . . . . . . . . . . . . . . . . . . . . 11
Author's Address . . . . . . . . . . . . . . . . . . . . . . 12
A. block size smaller than 64bit . . . . . . . . . . . . . . . 12
Full Copyright Statement . . . . . . . . . . . . . . . . . . 13
Etienne Expires November 12, 2001 [Page 2]
Internet-Draft counter mode with ESP May 2001
1. Overview
We present the counter mode in ESP independently of any specific
block cipher algorithms. Examples are given using DES, 3DES, and AES
(Section 6). This memo does not explain the cryptographic principals
behind the security of the counter mode, see [13] for details.
Briefly, the counter mode uses an unique counter that is shared by
both peers. This counter is used to generate a pad, which is X-ORed
with plaintext to obtain ciphertext. The pad appears as a pseudo-
random bitfield. It is a concatenation of blocks, each of them being
the encryption of an incremented counter (see Section 1.1 for more
details).
The counter mode is intended to add little overhead, be efficiently
processed, and be easily implemented: It doesn't add any space
overhead to ESP (Section 5.2). CBC with explicit IV (RFC2405 [5] or
AES-CBC [11]) has an overhead 28% to 109% larger depending on the SA
parameters (Section 5.2.1). It allows precomputation and
parallelisation (Section 5.1). Both encryption and decryption of the
payloads in counter mode use the encryption function of the chosen
cipher (Section 3). This reduces the software required, which aids
in optimization of both hardware and software implementations.
1.1 Description of the counter mode
Counter mode adds the need to share a counter in addition to sharing
the usual secret key. Note that the counter (Section 2) doesn't need
to be secret. The processing of the i-th block of a packet is:
o Ci = Pi xor E( counter + i ) for the encryption
o Pi = Trunc(n,Ci xor E( counter + i )) for the decryption
With the following notation:
o E() is the encryption function of a block cipher (e.g DES).
o Ci is the i-th block of the encrypted packet.
o Pi is the n first bytes of the i-th block of the plain packet.
The value of n is between 1 and the block size. This assumes the
data length is exchanged out of band, in our case it is computed
from the ip total length (RFC0791.3.1 [1]).
o The Trunc(x,y) function truncates the x first bytes of the y
value.
Etienne Expires November 12, 2001 [Page 3]
Internet-Draft counter mode with ESP May 2001
o counter is a counter incremented at each block (Section 2).
1.2 Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in rfc2119 [2].
In this memo, the term pad is unrelated to the padding length field
present in the ESP header (RFC2406.2 [6]).
2. Counter
The counter is the core of this mode of operation (Section 2.1). The
security relies on its uniqueness (Section 2.2) for any block
encrypted with a given ESP key.
We assume the block size is at least 64 bits long. We believe it is
reasonable as most block ciphers match this requirement. In Appendix
A, we suggest possible modifications for block ciphers with a block
size smaller than 64-bit.
2.1 Counter construction
The counter is composed of the counter block which includes the
effective counter:
1. The counter block is as large as the cipher block size and is
stored in network order. It is the input of the block cipher
during the pad computation. The 64 least significant bits are
called the effective counter. The bits of the counter block
outside the effective counter are zeroed.
2. The effective counter is then separated into the ESP sequence
number which resides in 32 most significant bits, and the block
index which resides in the 32 least significant bits.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ESP Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Block Index |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure: The effective counter
Etienne Expires November 12, 2001 [Page 4]
Internet-Draft counter mode with ESP May 2001
ESP sequence number: 32-bit strictly increasing number stored in
network order. It is a field of the ESP header (RFC2406.2.2 [6])
used to prevent an attacker from replaying packets. Each ESP
datagram contains a unique sequence number.
Block index: 32-bit unsigned integer coded in network order. It is
the block index inside a single packet. The first block of a
packet has the index 0, the next has 1 and so on.
2.2 Counter Uniqueness
The counter MUST be unique (Section 2.2) for any block encrypted by a
given ESP key or an attacker could XOR 2 cipher blocks and obtain a
XOR of the 2 corresponding blocks of plaintext. We believe our
counter matches this requirement because:
o The ESP sequence number is strictly increasing and so, is unique
per packet (RFC2406.3.3.3 [6]).
o The block index MUST be never cycle during the processing of a
packet. It MUST be equal to and greater than the largest possible
packet divided by the block size of the cipher. ESP is applicable
to IPv4 and IPv6 (RFC2406.3.1 [6]). The size of the biggest IPv4
packet is 64 Kbyte (RFC0791.3.1 [1]). For IPv6, it is 64 Kbyte
(RFC2460.3 [9]) without option, and can go up to 4 Mbyte with the
jumbo option (RFC2675 [10]). In the worst case of a maximally
sized 4MByte packet and the smallest block size of 64 bits, the
block index must be at least 29-bit. A 32-bit value is guaranteed
not to cycle, the unused three bits are considered a reasonable
overhead allowing for simplicity of implementation.
The block index does not overflow in a packet, and each packet
contains an ESP sequence number that is unique per key. So the
sequence number and block index tuple is unique per key.
3. Encryption and decryption
This section explains the encryption and decryption using the counter
mode. The two operations use the exact same code which simplifies
the implementation and reduces the memory footprint. In this
section, the term source text describe the plaintext for a encryption
and ciphertext for an encryption. The steps for encrypting or
decrypting are initializing the counter, computing the pad's length,
generating N_BLK blocks of pad and, then, applying the pad to the
source text.
Note that the pad generation and its application may be interleaved
Etienne Expires November 12, 2001 [Page 5]
Internet-Draft counter mode with ESP May 2001
to save resources.
3.1 Counter initialization
The counter block is initialized in 3 step: First, any bit more
significant than the 64th is zeroed (applicable only if the block is
larger than 64-bit). Second, the ESP sequence number is copied from
the ESP header to the 32 most significant bit of the effective
counter. Last, the block index is zeroed.
3.2 Pad's length computation
Before operating on a packet of PKT_LEN bytes, a pad of N_BLK blocks
must be generated with:
N_BLK = Floor( (PKT_LEN + BLK_SIZE -1) / BLK_SIZE )
BLK_SIZE is the cipher block size and Floor(X) returns the largest
integer not greater than X. The pad may be longer than the source
text up to BLK_SIZE-1 byte.
3.3 Generate N_BLK blocks of pad
For each block of pad, the corresponding counter is encrypted with
the cipher algorithm to become a block of pad. After generating any
block, except the last, the block index MUST be incremented. As the
block index is large enough for any packet length and block size, it
won't overflow the ESP sequence number and there is no need to handle
a multi-precision addition on 32-bit CPU.
3.4 Apply the pad
Each byte of the source text is XORed with the byte of the pad with
the same offset. Thus, the source text doesn't need to be block
aligned.
4. Assumptions and limitations
Using the counter mode assumes to enable the anti-replay for this SA
(Section 4.1), not to expect authentication from it (Section 4.2) and
not to use a differentially weak encryption algorithm (Section 4.3).
4.1 relation to anti-replay
The anti-replay (RFC2406.3.3.3 [6]) MUST be enabled. The ESP
sequence number is the base of the counter and if the sequence number
rolls over, the counter would be reused. This would be a flaw
because the counter must be unique under the lifetime of a key
Etienne Expires November 12, 2001 [Page 6]
Internet-Draft counter mode with ESP May 2001
(Section 2.2).
We believe that required anti-replay support is reasonable because it
adds negligible processing overhead and prevents attackers from
replaying packets.
4.2 relation to authentication algorithms
Like CBC and other common modes [12], the counter mode doesn't insure
integrity or authentication. It isn't a goal of the mode of
operation. In ESP, the authentication is optional (RFC2406.3.2.2
[6]). If integrity or authentication are desired, the authentication
algorithm MUST NOT be NULL.
There are no known issues regarding interactions between DES, 3DES or
AES in counter mode with any authentication algorithms.
4.3 relation to encryption algorithms
The encryption algorithm MUST NOT be differentially weak. As the
counter mode is based on the encryption of a counter, an attacker may
obtain many pairs of plaintext/ciphertext with low hamming distance
between the plaintext and performs a differential cryptanalysis
attack [17]. We believe it is a reasonable requirement as it isn't a
goal of the mode of operation to fix the cipher's flaw.
WORK: status of DES, 3DES, AES
5. Performance Evaluation
The counter mode is very efficient in speed thanks to parallelisation
and precomputation (Section 5.1) and in space because it doesn't need
explicit IV or padding (Section 5.2).
5.1 Speed evaluation
The computation is parallelisable i.e. two blocks can be computed
independently. An implementation may take advantages of this to
increase it speed. In software, it is possible to use pipelining,
large number of registers or SIMD instructions. Moreover, the
hardware can be more fully used thanks to the fine grain
parallelisation.
The computation may be preprocessed. Most of the processing time is
due to the encryption algorithm in the pad calculation. The ESP
sequence number is predictable and the pad values don't depend on the
source text. So, the pad can be precomputed even before receiving
the packet.
Etienne Expires November 12, 2001 [Page 7]
Internet-Draft counter mode with ESP May 2001
5.2 Space evaluation
The counter mode is very efficient from a space viewpoint: It doesn't
need explicit IV or padding. So it can be done in place.
5.2.1 Comparison with CBC and explicit IV
CBC with explicit IV (RFC2405 [5]) is the current MUST for the ESP
encryption (RFC2406.5 [6]). But it requires including an explicit IV
in the output which adds an additional block of bytes to the output.
It also requires aligning the plaintext to the cipher block size,
which adds half the block size, on average, to the output. This
implies that the counter mode will see a savings of one and a half
times the block size in comparison.
The following table presents the overhead size in bytes according to
the SA parameters (i.e. cryptography and ESP mode). The unit is the
byte and the percentages are compared to same cipher using the
counter mode. The IPv4 header typically uses 20-byte (RFC0791.3.1
[1]). The ESP header and footer uses 10-byte (RFC2406.2 [6]) and the
default authentication is a 96-bit MAC, so 12 bytes long (RFC2403 [3]
or RFC2404 [4]).
+================================================================+
| SA \ Avg Overhead | cipher | ESP tunnel | ESP transport |
+===================+=============+==============+===============+
|(DES-CTR | AES-CTR)| | 20+10+12= | 10 + 12 = |
| +HMAC-MD5-96 | 0 | 42 | 22 |
+----------------------------------------------------------------+
| DES-CBC-EXP-IV | | | |
| + HMAC-MD5-96 | 12 | 54 (+28%) | 34 (+54%) |
+----------------------------------------------------------------+
| AES-CBC-EXP-IV | | | |
| + HMAC-MD5-96 | 24 | 66 (+57%) | 46 (+109%) |
+================================================================+
Figure: Overhead comparison in bytes for IPv4
6. Application to cipher algorithms
This section describes the use of DES, 3DES (FIPS-46-3 [14]) and AES
(FIPS-AES [15]) with the counter mode. Mode, key size, weak keys,
block size, and rounds are documented for each cipher.
6.1 Mode of operations
In this memo, all the encryption algorithms are used in counter mode.
An overview can be found in Section 1.
Etienne Expires November 12, 2001 [Page 8]
Internet-Draft counter mode with ESP May 2001
A chaining mode must conceal the patterns in the plaintext inside a
single packet and between several packets without compromising the
security of the underlying cipher. We believe the CTR-mode matches
these requirements as the counter is unique for any block encrypted
by a given key (Section 2.2).
6.2 Key size
The key size may hint at the security of an encryption algorithm,
assuming it is the weakest link. Some algorithms offer variable key
size (e.g AES) while others offer only a fixed size (e.g. DES,
3DES).
+============+======================+===========+
| Algorithm | Key Sizes (bits) | Default |
+============+======================+===========+
| AES | 128, 192, 256 | 128 |
+------------+----------------------+-----------+
| DES | 64 | 64 |
+------------+----------------------+-----------+
| 3DES | 192 | 192 |
+------------+----------------------+-----------+
Figure: key size for various ciphers
6.3 Weak keys
The cryptographic community is still debating whether or not to check
for weak keys. Critics of key checking argue that it increases the
complexity of the system, leading to an increases probability of
flaws. Moreover, if the weak keys of a cipher algorithm consume a
non negligible part of its key space, it may be considered flawed and
should not be used. Proponents make the practical argument that any
additional safety that can be checked at a reasonable price should be
done.
To follow the current trend in ESP standards (RFC2405.4 [5]), weak
key checks SHOULD be performed. If such a key is found, the key
SHOULD be rejected and a new SA requested. The weak keys for DES,
3DES and AES are:
o DES has 4 weak keys and 12 semi-weak keys (RFC2409.A [7] or FIPS-
74 sec.3.6 [16]) , which amount to 2^-52 of the key space.
o 3DES WORK: found an authoritative source
o AES has no known weak keys, at the time of writing this memo.
Etienne Expires November 12, 2001 [Page 9]
Internet-Draft counter mode with ESP May 2001
6.4 block size and padding
The counter mode doesn't require the plaintext to be block aligned
(Section 3). The block size may be different depending on the
algorithm. Older ciphers (e.g. DES, 3DES) tend to have 64-bit block
while recent ones (e.g. AES) have 128-bit block.
+============+===============+
| Algorithm | Block size |
+============+===============+
| AES | 128 |
+------------+---------------+
| DES | 64 |
+------------+---------------+
| 3DES | 64 |
+------------+---------------+
Figure: block size per algorithm
6.5 rounds
Most block cipher algorithms are based on an atomic function, like
that found in a feistel network, applied several times. A single
application is called a round and the number of rounds may be
correlated with the security of the system. This number may be
negotiable (e.g AES) or fixed (e.g. DES, 3DES) and it may be
dependent on the key size (e.g. AES).
+============+===============+=======================+
| Algorithm | Negotiable? | Default # of Rounds |
+============+===============+=======================+
| | | 10 for 128-bit key |
| AES | Yes | 12 for 192-bit key |
| | | 14 for 256-bit key |
+------------+---------------+-----------------------+
| DES | No | 16 |
+------------+---------------+-----------------------+
| 3DES | No | 48 |
+------------+---------------+-----------------------+
Figure: number of rounds per algorithm
7. Security considerations
WORK: to write
Etienne Expires November 12, 2001 [Page 10]
Internet-Draft counter mode with ESP May 2001
8. Acknowledgement
We would like to acknowledge Zach Brown for his contribution to the
edition of this document.
References
[1] Postel, J., "Internet Protocol", STD 5, RFC 791, Sep 1981.
[2] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
[3] Madson, C. and R. Glenn, "The Use of HMAC-MD5-96 within ESP and
AH", RFC 2403, November 1998.
[4] Madson, C. and R. Glenn, "The Use of HMAC-SHA-1-96 within ESP
and AH", RFC 2404, November 1998.
[5] Madson, C. and N. Doraswamy, "The ESP DES-CBC Cipher Algorithm
With Explicit IV", RFC 2405, November 1998.
[6] Kent, S. and R. Atkinson, "IP Encapsulating Security Payload
(ESP)", RFC 2406, November 1998.
[7] Harkins, D. and D. Carrel, "The Internet Key Exchange (IKE)",
RFC 2409, November 1998.
[8] Pereira, R. and R. Adams, "The ESP CBC-Mode Cipher Algorithms",
RFC 2451, November 1998.
[9] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6)
Specification", RFC 2460, December 1998.
[10] Borman, D., Deering, S. and R. Hinden, "IPv6 Jumbograms", RFC
2675, August 1999.
[11] Frankel, S., Glenn, R. and S. Kelly, "The AES Cipher Algorithm
and Its Use With IPsec", draft-ietf-ipsec-ciph-aes-cbc-01.txt
Work In Progress, Nov 2000.
[12] Bellovin, S., "Problem Areas for the IP Security Protocol",
Usenix Unix Security Symposium 6th, Jul 1996.
[13] Lipmaa, H., Rogaway, P. and D. Wagner, "CTR-MODE encryption",
Comment on mode of operations NIST, Jan 2001.
[14] NIST, , "Data encryption standard (DES)", FIPS 46-3, Oct 1999.
Etienne Expires November 12, 2001 [Page 11]
Internet-Draft counter mode with ESP May 2001
[15] NIST, , "Advanced Encryption Standard (AES)", FIPS not yet
published, summer 2001.
[16] NIST, , "Guidelines for implementing and using the nbs data
encryption standard", FIPS 74, Apr 1981.
[17] Biham, E. and A. Shamir, "Differential Cryptanalysis of DES-
like cryptosystems", Journal of Cryptology Vol 4, Jan 1991.
Author's Address
Jerome Etienne
EMail: jme@off.net
URI: http://www.off.net/~jme
Appendix A. block size smaller than 64bit
o WORK: to write
Etienne Expires November 12, 2001 [Page 12]
Internet-Draft counter mode with ESP May 2001
Full Copyright Statement
Copyright (C) The Internet Society (2001). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
Etienne Expires November 12, 2001 [Page 13]