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 22, 2001.

Copyright Notice

Copyright (C) The Internet Society (2001). All Rights Reserved.

Abstract

This memo presents a system of secret IV use for ESP, based on the encryption of the sequence number. It doesn't add any space overhead in the packet and its generation can be parallelized and precomputed. Compared to the common explicit random IV (current MUST for ESP RFC2405.3[5], or AES-CBC.3[7]), it is more secure, saves bandwidth (e.g. 8 bytes with DES/3DES and 16 bytes with AES) but requires slightly more computation.

Table of Contents

1.  Overview
2.  Terminology
3.  Requirements
4.  IV generation
5.  IV security properties
5.1  Uniqueness of the secret IV
5.2  Hamming distance between secret IVs
5.3  Secrecy of the IV
6.  Performance evaluation
6.1  processing performance
6.2  network usage performance
6.2.1  Comparison with explicit IV
7.  limitations
7.1  relation to the anti-replay protection
7.2  relation to differentially-weak ciphers
8.  Security Considerations
9.  Acknowledgements
§  References
§  Author's Address
A.  Non-random explicit IV for RFC2405
B.  Vulnerability of the random IV
B.1  Consequences of an IV collision
C.  Birthday attacks
D.  Changes between 00 and 01
§  Full Copyright Statement

1. Overview

The basic principle of the secret IV is to encrypt the ESP sequence number (RFC2406.2.2[6]) and to use the resulting ciphertext as the IV for the mode of operation. This document presents the secret IV independently of block ciphers and mode of operations. Examples of modes of operations are given with the common modes advised by the NIST [14]: OFB, CBC and CFB (ECB isn't included as it doesn't need IV). Examples of block ciphers are given with DES and AES. A special attention is given to DES-CBC with explicit IV (RFC2405[5]) because it is the current MUST for ESP.

Compared to the common explicit random IV (RFC2405.3[5], or AES-CBC.3[7]), secret IV offers a tradeoff (Performance evaluation) which may be attractive: better bandwidth usage and better security at the price of greater CPU processing.

1. The secret IV is more secure than a random explicit IV because the secret IV is secret (Secrecy of the IV) and unique (Uniqueness of the secret IV). DES CBC with random explicit IV (RFC2405.3[5]) is the current MUST for ESP encryption and it has security flaws based on random IV collisions (Vulnerability of the random IV).
2. The secret IV doesn't use any additional space in the encrypted packet because it is directly derived from the ESP sequence number (IV generation).
3. The secret IV consumes CPU to generate but its processing can be parallelized and precomputed (processing performance).

This document gives the requirements which need to be met by an IV (Requirements), specifies its generations (IV generation), evaluates its security (IV security properties) and performance (Performance evaluation) and explains its limitations (limitations).

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

3. Requirements

The purpose of an IV is provide a nonce to the mode of operation in order to conceal the plaintext patterns inside a single packet and between several packets. We identified the following requirements:

1. The IV contained in a packet MUST be unique across all packets generated during the lifetime of a key. If several packets have the same IV, the attacker is able to learn additional informations about the plaintext (Consequences of an IV collision).
2. The IV MUST be as large as the cipher block because of the construction of the mode of operation.
3. The hamming distance between IVs SHOULD be high. If it isn't, the first block of the cipher's input will likely differ in just a few bit position and an attacker may use it against a differentially-weak cipher.

The secret IV meets these requirements: It is guaranteed to be unique (Uniqueness of the secret IV), the hamming distance is high (Hamming distance between secret IVs) and it is as large as the cipher block (IV generation).

4. IV generation

The IV is generated by copying the ESP sequence number to the least significant part of the block. Then, any bit more significant than the 32nd is zeroed and the block is encrypted with the same key and cipher algorithm used for the data (RFC2406.3.3.2[6]). The resulting ciphertext is exactly as large as a block and can be directly used as the IV.

The secret IV generation only uses known components of ESP: the sequence number, encryption algorithm, and key. It is self contained. It requires the block size to be at least 32 bits long but it isn't a significant constraint as we aren't aware of any block cipher which doesn't meet this requirement.

5. IV security properties

The secret IV is secure as it is guaranteed to be unique (Uniqueness of the secret IV), separated from other IVs by high-hamming distance (Hamming distance between secret IVs) and is secret (Secrecy of the IV).

5.1 Uniqueness of the secret IV

An IV is supposed to be a nonce and a failure in this assumption would create a security hole (Vulnerability of the random IV). The secret IV is guaranteed to be unique because it is derived from a unique number by a collision-free function. The ESP sequence numbers (RFC2406.2.2[6]) are ensured to be unique during the lifetime of a key assuming the anti-replay protection is enabled (relation to the anti-replay protection). Moreover the derivation function is a block cipher which prevents collision by guaranteeing that any plaintext has a unique ciphertext.

5.2 Hamming distance between secret IVs

Bellovin in [13], summarized in RFC2405.6[5], explains that low hamming distance between IVs may ease cryptanalysis attacks (e.g. differential ones [10]). Secret IV avoids this flaw because a block cipher is assumed to be a pseudo-random permutation i.e. the ciphertext can not be linked to its plaintext by those who do not have the key. Thus the IV looks random for an attacker and the hamming distance between IVs is high, even if the IV is derived from a low-Hamming distance source (IV generation).

5.3 Secrecy of the IV

The secrecy of the IV is useful against attacks that require predictable IV. In our case, it makes a differential cryptanalysis based on the IV significantly harder (relation to differentially-weak ciphers).

An attacker can try to obtain the IV by knowing the ESP sequeunce number that generated it or by deriving it from the first block of ciphertext:

1. The attacker is unable to generate the IV based on the ESP sequence number without the knowledge of the secret key or the ability to break the block cipher algorithm.
2. With CBC, OFB and CFB, the IV is encrypted before being included in the ciphertext so the attacker is unable to deduce it.

Thus the secret IV is guaranteed to be secret if the attacker is unable to break the cipher algorithm.

6. Performance evaluation

This secret IV offers a tradeoff bandwidth and CPU processing. The bandwidth usage is reduced (network usage performance) but the CPU processing is slightly increased (processing performance) because of the IV generation (IV generation).

6.1 processing performance

The IV generation can be precomputed because the ESP sequence numbers are easily predictable by the receiver. Implementors MAY compute the IVs using spare cycle and cache them to reduce the processing latency while processing packets.

The IV generation can be parallelized because the computation of each IV is independent from the others.

6.2 network usage performance

The secret IV doesn't add any space overhead because it is derived from the ESP sequence number which is already present in the packet (RFC2406.2[6]).

6.2.1 Comparison with explicit IV

CBC with explicit IV (RFC2405[5]) is the current MUST for the ESP encryption (RFC2406.5[6]). To require an explicit IV adds an additional block of bytes to the output. This implies that an secret IV will see a savings of the block size in comparison.

The following tables present the overhead size in bytes according to the SA parameters (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]). We assume the plain text must be block aligned because the current MUST (RFC2405[5]) uses CBC. This adds an average overhead of half of the block size.

7. limitations

Using the secret IV requires enabling anti-replay protection for this SA (relation to the anti-replay protection) and forbids the use of cipher algorithms that are extremly vulnerable to differential cryptanalysis (relation to differentially-weak ciphers).

7.1 relation to the anti-replay protection

The anti-replay (RFC2406.3.3.3[6]) MUST be enabled. The ESP sequence number is the base of the secret IV and if the sequence number rolls over, the IV would be reused (Uniqueness of the secret IV). We believe that this requirement is reasonable because its overhead is negligible and it prevents attackers from replaying packets as an additional benefit.

7.2 relation to differentially-weak ciphers

If the cipher algorithm is differentially-weak, an attacker may use the secret IV to obtain many ciphertexts with low hamming distance between the plaintext and performs a differential cryptanalysis [10]. It may be argued that differentially-weak ciphers should not be used and that the goal of the IV isn't to try, probably in vain, to fix a cipher's flaw. In any case, this attack is hard to apply to the secret IV because:

• It can't succeed if it requires more than 2^32 pairs. The attacker can obtain at most 2^32 pairs because the ESP sequence numbers MUST NOT cycle and is reset before the transmission of the 2^32nd packet (RFC2406.2.2[6]).
• The ESP sequence numbers are separated by low hamming distance but they are encrypted twice (once to generate the IV and once by the mode of operation) before being included in the ciphertext. It effectively doubles the number of rounds of the cipher and the differential cryptanalysis is typically harder as the number of rounds increases.

If the cipher is sufficiently differentially-weak to allow a differential cryptanalysis with only 2^32 secret IVs, each one being encrypted twice, it may be easier to attack the message ciphertext blocks which are significantly more and encrypted only once.

8. Security Considerations

The secret IV is secure as it is guaranteed to be unique, separated from other IVs by high-hamming distance and is secret (IV security properties). Moreover it isn't vulnerable to birthday attacks (Birthday attacks) like random IVs required in RFC2405.3[5] (Vulnerability of the random IV). Non-random explicit IV for RFC2405 describes a backward compatible method to fix this flaw.

9. Acknowledgements

The IV system presented in this memo is inspired from the counter mode, introduced by Diffie and Hellman in 1979 [9]. Lipmaa, Rogaway and Wagner present a comprehensive overview in [8]. The counter mode is a mode of operation based on the encryption of a counter and the secret IV may be seen as a single block of the counter mode pad.

We would like to acknowledge Adam Back for his help in understanding the mathematic involved in the birthday paradox and Zach Brown for his contribution to the edition of this document.

References

Author's Address

Appendix A. Non-random explicit IV for RFC2405

This section describes a backward compatible method to fix the security flaw due to the random IV (Vulnerability of the random IV) in RFC2405[5]. Implementors MAY use it when backward compatibility is required but they would have the additional processing of the secret IV, wouldn't gain the bandwidth and would lose the secrecy property (Secrecy of the IV) which may increase its vulnerability to differentially-weak ciphers (relation to differentially-weak ciphers).

The principle is to generate an IV as an secret IV (IV generation) and then to include it in each packet as specified in RFC2405.3[5]. Thus the IV is explicit but no more vulnerable to birthday attacks.

Appendix B. Vulnerability of the random IV

RFC2405.3[5], the current MUST for ESP, requires to use random IV but random IVs are vulnerable to birthday attacks (Birthday attacks) i.e. it is surprisingly likely that among a pool of packets at least two have the same IV. Note that this attack doesn't require to break the underlying cipher algorithm. Assuming the anti-replay protection is enabled (relation to the anti-replay protection), an attacker is able to gather 2^32 packets. With a 64-bit block cipher (e.g DES, 3DES), he has 40% chances to have at least two packets with the same IV.

It is a security weakness but a minor one. Consequences of an IV collision explains the consequences of an IV collision.

B.1 Consequences of an IV collision

The consequences of the collision depend on the mode of operation. We classify them in two classes: the modes which solely rely on the IV to hide the patterns inside a message (OFB) and the ones which additionally use the plaintext to distribute its potential variations along the ciphertext (CFB, CBC).

An IV collision with OFB is a huge security weakness because the attacker can XOR the colliding ciphertext and obtain an XOR of the two plaintexts of the whole messages (WORK: assuming they have the same size). For CFB, the attacker can obtain a XOR of the two plaintext too but only up to and including the first plaintext block which is different in both messages. For CBC, an IV collision reveals the common patterns of both packets up to and including the first different blocks.

Appendix C. Birthday attacks

work: todo. general introduction and application to ESP

Appendix D. Changes between 00 and 01

• spelling correction

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.