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 (Comparison with CBC and explicit IV). Moreover, the counter mode allows parallelisation and precomputation of most of the processing (Speed evaluation).

Table of Contents

1.  Overview
1.1  Description of the counter mode
1.2  Terminology
2.  Counter
2.1  Counter construction
2.2  Counter Uniqueness
3.  Encryption and decryption
3.1  Counter initialization
3.2  Pad's length computation
3.3  Generate N_BLK blocks of pad
3.4  Apply the pad
4.  Assumptions and limitations
4.1  relation to anti-replay
4.2  relation to authentication algorithms
4.3  relation to encryption algorithms
5.  Performance Evaluation
5.1  Speed evaluation
5.2  Space evaluation
5.2.1  Comparison with CBC and explicit IV
6.  Application to cipher algorithms
6.1  Mode of operations
6.2  Key size
6.3  Weak keys
6.4  block size and padding
6.5  rounds
7.  Security considerations
8.  Acknowledgement
§  References
§  Author's Address
A.  block size smaller than 64bit
§  Full Copyright Statement

1. Overview

We present the counter mode in ESP independently of any specific block cipher algorithms. Examples are given using DES, 3DES, and AES (Application to cipher algorithms). 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 Description of the counter mode 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 (Space evaluation). CBC with explicit IV (RFC2405[5] or AES-CBC[11]) has an overhead 28% to 109% larger depending on the SA parameters (Comparison with CBC and explicit IV). It allows precomputation and parallelisation (Speed evaluation). Both encryption and decryption of the payloads in counter mode use the encryption function of the chosen cipher (Encryption and decryption). 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 (Counter) doesn't need to be secret. The processing of the i-th block of a packet is:

• Ci = Pi xor E( counter + i ) for the encryption
• Pi = Trunc(n,Ci xor E( counter + i )) for the decryption

With the following notation:

• E() is the encryption function of a block cipher (e.g DES).
• Ci is the i-th block of the encrypted packet.
• 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]).
• The Trunc(x,y) function truncates the x first bytes of the y value.
• counter is a counter incremented at each block (Counter).

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 (Counter construction). The security relies on its uniqueness (Counter Uniqueness) 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 block size smaller than 64bit, 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.

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 (Counter Uniqueness) 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:

• The ESP sequence number is strictly increasing and so, is unique per packet (RFC2406.3.3.3[6]).
• 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 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 (relation to anti-replay), not to expect authentication from it (relation to authentication algorithms) and not to use a differentially weak encryption algorithm (relation to encryption algorithms).

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 (Counter Uniqueness).

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 (Speed evaluation) and in space because it doesn't need explicit IV or padding (Space evaluation).

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.

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]).

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 Overview.

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 (Counter Uniqueness).

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).

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:

• 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.
• 3DES WORK: found an authoritative source
• AES has no known weak keys, at the time of writing this memo.

6.4 block size and padding

The counter mode doesn't require the plaintext to be block aligned (Encryption and decryption). 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.

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).

7. Security considerations

WORK: to write

8. Acknowledgement

We would like to acknowledge Zach Brown for his contribution to the edition of this document.

References

Author's Address

Appendix A. block size smaller than 64bit

• WORK: to write

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.