Internet DRAFT - draft-etienne-ipsec-esp-secret-iv
draft-etienne-ipsec-esp-secret-iv
Network Working Group J. Etienne
Internet-Draft May 23, 2001
Expires: November 21, 2001
Secret IV and its use with ESP
draft-etienne-ipsec-esp-secret-iv-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 21, 2001.
Copyright Notice
Copyright (C) The Internet Society (2001). All Rights Reserved.
Abstract
This memo presents a system of secret IV 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.
Etienne Expires November 21, 2001 [Page 1]
Internet-Draft Secret IV and its use with ESP May 2001
Table of Contents
1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Requirements . . . . . . . . . . . . . . . . . . . . . . . . 3
4. IV generation . . . . . . . . . . . . . . . . . . . . . . . 4
5. IV security properties . . . . . . . . . . . . . . . . . . . 4
5.1 Uniqueness of the secret IV . . . . . . . . . . . . . . . . 5
5.2 Hamming distance between secret IVs . . . . . . . . . . . . 5
5.3 Secrecy of the IV . . . . . . . . . . . . . . . . . . . . . 5
6. Performance evaluation . . . . . . . . . . . . . . . . . . . 5
6.1 processing performance . . . . . . . . . . . . . . . . . . . 6
6.2 space performance . . . . . . . . . . . . . . . . . . . . . 6
6.2.1 Comparison with explicit IV . . . . . . . . . . . . . . . . 6
7. limitations . . . . . . . . . . . . . . . . . . . . . . . . 7
7.1 relation to the anti-replay protection . . . . . . . . . . . 7
7.2 relation to differentially-weak ciphers . . . . . . . . . . 7
8. Security Considerations . . . . . . . . . . . . . . . . . . 8
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8
References . . . . . . . . . . . . . . . . . . . . . . . . . 8
Author's Address . . . . . . . . . . . . . . . . . . . . . . 9
A. Non-random explicit IV for RFC2405 . . . . . . . . . . . . . 9
B. Vulnerability of the random IV . . . . . . . . . . . . . . . 9
B.1 Consequences of an IV collision . . . . . . . . . . . . . . 10
C. Birthday attacks . . . . . . . . . . . . . . . . . . . . . . 10
Full Copyright Statement . . . . . . . . . . . . . . . . . . 11
Etienne Expires November 21, 2001 [Page 2]
Internet-Draft Secret IV and its use with ESP May 2001
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 IV
for the mode of operation. This document presents the secret IV
independently of block ciphers and mode of operations. Examples of
mode 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 (Section 6) which may be
attractive: better bandwidth usage and better security versus
slightly more CPU processing.
1. The secret IV is more secure than a random explicit IV because
the secret IV is secret (Section 5.3) and unique (Section 5.1).
DES CBC with random explicit IV (RFC2405.3 [5]) is the current
MUST for ESP encryption and it has security flaws based on the
colliding IVs (Appendix B).
2. The secret IV doesn't use any additional space in the encrypted
packet because it is directly derived from the ESP sequence
number (Section 4).
3. The secret IV consumes CPU to generate but its processing can be
parallelized and precomputed (Section 6.1).
This document gives the requirements which need to be meet by an IV
(Section 3), specifies its generations (Section 4), evaluates its
security (Section 5) and performance (Section 6) and explains its
limitations (Section 7).
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 MUST be unique during the lifetime of a key. If several
Etienne Expires November 21, 2001 [Page 3]
Internet-Draft Secret IV and its use with ESP May 2001
packets have the same IV, the attacker is able to learn
additional informations about the plaintext (Appendix B.1).
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
(Section 5.1), the hamming distance is high (Section 5.2) and it is
as large as the cipher block (Section 4).
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 32th 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 IV.
The generation is self contained i.e. it uses only existing
component of ESP: the sequence number, the encryption algorithm and
key. It requires the block size to be at least 32-bit long but it
isn't a significant constraint as we aren't aware of any block cipher
which doesn't match this requirement.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 0 |
~ (variable size equal to cipher block size - 32 bits) ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| ESP Sequence Number |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure: The plaintext of the IV
5. IV security properties
The secret IV is secure as it is guaranteed to be unique (Section
5.1), separated from other IVs by high-hamming distance (Section 5.2)
Etienne Expires November 21, 2001 [Page 4]
Internet-Draft Secret IV and its use with ESP May 2001
and is secret (Section 5.3).
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 (Appendix B). 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]) is ensured to be unique during the lifetime of a key assuming
the anti-replay protection is enabled (Section 7.1). Moreover the
derivation function is an block cipher which prevents collision by
guaranteeing that any plaintext has a unique ciphertext.
5.2 Hamming distance between secret IVs
[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 appears
unrelated to the plaintext to those who ignore 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
(Section 4).
5.3 Secrecy of the IV
The secrecy of the IV is useful against attacks requiring predictable
IV. In our case, it makes a differential cryptanalysis based on the
IV significantly harder (Section 7.2).
An attacker can try to obtain the IV from its source, i.e. the ESP
sequence number, or its destination, i.e. the first block of
ciphertext:
1. The IV is the ESP sequence number encrypted with the shared
secret key (Section 4). As the attacker ignores the key, he is
unable to regenerate the IV without breaking the 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/CPU. The bandwidth usage
Etienne Expires November 21, 2001 [Page 5]
Internet-Draft Secret IV and its use with ESP May 2001
is reduced (Section 6.2) but the CPU usage is slightly increased
(Section 6.1) because of the IV generation (Section 4).
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 space 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 (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]). 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.
+================================================================+
| SA \ Avg Overhead | cipher | ESP tunnel | ESP transport |
+===================+=============+==============+===============+
| DES-CBC-IMP-IV | | 20+10+12+4= | 10+12+4 = |
| + HMAC-MD5-96 | 4 | 46 | 26 |
+----------------------------------------------------------------+
| DES-CBC-EXP-IV | | | |
| + HMAC-MD5-96 | 12 | 54 (+17%) | 34 (+30%) |
+================================================================+
Figure: Overhead comparison in bytes with IPv4 and DES
Etienne Expires November 21, 2001 [Page 6]
Internet-Draft Secret IV and its use with ESP May 2001
+================================================================+
| SA \ Avg Overhead | cipher | ESP tunnel | ESP transport |
+===================+=============+==============+===============+
| AES-CBC-IMP-IV | | 20+10+12+8= | 10+12+8 = |
| + HMAC-MD5-96 | 8 | 50 | 30 |
+----------------------------------------------------------------+
| AES-CBC-EXP-IV | | | |
| + HMAC-MD5-96 | 24 | 66 (+32%) | 46 (+53%) |
+================================================================+
Figure: Overhead comparison in bytes with IPv4 and AES
7. limitations
Using the secret IV assumes to enable the anti-replay protection for
this SA (Section 7.1) and not to use cipher algorithms which are
extremely weak against differential cryptanalysis (Section 7.2).
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 (Section 5.1). We believe
that this requirement is reasonable because its overhead is
negligible and it prevents attackers from replaying packets as
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:
o 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]).
o 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.
Etienne Expires November 21, 2001 [Page 7]
Internet-Draft Secret IV and its use with ESP May 2001
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 (Section 5).
Moreover it isn't vulnerable to birthday attacks (Appendix C) like
random IVs required in RFC2405.3 [5] (Appendix B). Appendix A
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.
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] 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.
[8] Lipmaa, H., Rogaway, P. and D. Wagner, "CTR-MODE encryption",
Etienne Expires November 21, 2001 [Page 8]
Internet-Draft Secret IV and its use with ESP May 2001
Comment on mode of operations NIST, 2001.
[9] Diffie, W. and M. Hellman, "Privacy and Authentication: An
Introduction to Cryptography", Proceedings of the IEEE 67 pp.
397-427, 1979.
[10] Biham, E. and A. Shamir, "Differential Cryptanalysis of DES-
like cryptosystems", Journal of Cryptology Vol 4, Jan 1991.
[11] Menezes, A., Vanstone, S. and P. van Oorschot, "Handbook of
applied cryptography", CRC press , 1996.
[12] Stinson, D., "Cryptography: theory and practice", CRC press ,
1995.
[13] Bellovin, S., "Probable plaintext cryptanalysis of the IP
security protocols", Proceedings of the Symposium on Network
and Distributed System Security , Feb 1997.
[14] NIST, , "DES MODES OF OPERATION", FIPS 81, Dec 1980.
Author's Address
Jerome Etienne
EMail: jme@off.net
URI: http://www.off.net/~jme
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 (Appendix B) 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 (Section 5.3)
which may increase its vulnerability to differentially-weak ciphers
(Section 7.2).
The principle is to generate an IV as an secret IV (Section 4) 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 (Appendix C) i.e.
it is surprisingly likely that among a pool of packets at least two
Etienne Expires November 21, 2001 [Page 9]
Internet-Draft Secret IV and its use with ESP May 2001
have the same IV. Note that this attack doesn't require to break the
underlying cipher algorithm. Assuming the anti-replay protection is
enabled (Section 7.1), 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. Appendix B.1 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 (OFB, 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
Etienne Expires November 21, 2001 [Page 10]
Internet-Draft Secret IV and its use 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 21, 2001 [Page 11]
