Network Working Group IPsec Working Group
INTERNET DRAFT C.S. Jutla, IBM
November 2000
Expiration Date: May 2001
A Parallelizable Authenticated Encryption Algorithm
for IPsec
<draft-jutla-ietf-ipsec-esp-iapm-00.txt>
Status of this Memo
This document is an Internet-Draft and is in full con-
formance with all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet
Engineering Task Force (IETF), its areas, and its work-
ing 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 inap-
propriate 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.
Abstract
This document describes a new authenticated encryption
mode of operation of block ciphers called "Integrity
Aware Parallelizable Mode (IAPM)" which is simple,
efficient, highly parallelizable, and provably secure.
One of the main features distinguishing the new mode
(IAPM) from existing modes is that along with providing
confidentiality of the payload, the new mode also pro-
vides authenticity of the payload. This is particularly
relevant to the ESP security protocol of IPsec.
The mode IAPM has the same provable security as CBC
(for confidentiality) and CBC-MAC (for authentication).
IAPM has a critical path of only two block cipher invo-
cations, leading to highly parallel implementations.
Moreover, for serial implementations the new mode of
operation offers twice the throughput of CBC plus CBC-
MAC, as it achieves the additional property of authen-
tication with little extra expense.
Jutla <draft-jutla-ietf-ipsec-esp-iapm-00.txt> 1
Table of Contents
1. Introduction ....................................... 3
2. Integrity Aware Parallelizable Mode (IAPM) ......... 4
2.1. Generating the Pairwise Independent Set ..... 5
2.2. Generating the random vector r .............. 6
2.3. Keys ........................................ 6
2.4. Security Considerations ..................... 6
3. ESP Header Authentication .......................... 7
4. Further Variants .................................. 8
4.1. Generating the Pairwise Differentially
Uniform Set ...................................... 9
5. Intellectual Property Issues ....................... 10
6. Acknowledgments .................................... 10
7. References ......................................... 10
8. Author's Address ................................... 11
Jutla <draft-jutla-ietf-ipsec-esp-iapm-00.txt> 2
Internet Draft Nov 2000
1. Introduction
In this document we propose a new mode of operation for
symmetric key block cipher algorithms. Modes of opera-
tion are relevant to IPSEC (RFC 2401) as they are used
to implement the security protocols in IPSEC. One of
the main features distinguishing the new mode of opera-
tion from existing modes is that along with providing
confidentiality of the payload, it also provides
authenticity of the payload. In other words, the new
mode is not just a mode of operation for encryption,
but a mode of operation for authenticated encryption.
The new mode achieves the additional property with lit-
tle extra overhead.
The new mode which we refer to as "Integrity Aware
Parallelizable Mode (IAPM)" is highly parallelizable,
as the name suggests. In fact, IAPM has critical path
of only two block cipher invocations. By one estimate,
a hardware implementation of the IAPM mode on a single
board (housing 1000 block cipher units) achieves
terabits/sec of authenticated encryption. Moreover,
there is no penalty for doing a serial implementation
of this mode. In fact, a serial implementation is
expected to be almost twice as fast as doing encryp-
tion with Cipher Block Chaining (CBC) ([ANSI],[NBS])
mode and a separate authentication with CBC-MAC.
The new mode is highly relevant to IPsec, as one of the
most prevalent security protocols in IPsec (the Encap-
sulating Security Payload) recommends both encryption
and integrity protection (see [Bel],[CGHK]). The
default IPsec algorithms are DES in CBC mode of opera-
tion, and HMAC-MD5 ([BCH]). However, as the standard
currently stands, the goal of authenticated encryption
is achieved by employing DES in CBC mode and then
authenticating using HMAC-MD5 in a separate pass. The
new mode achieves both goals in a single pass, and more
importantly offers highly parallel implementations.
Although, parallelizable modes of operation for encryp-
tion were well known, e.g. the counter mode, there was
no mode known for authentication which could achieve
this level of parallelism. The authentication code
Jutla <draft-jutla-ietf-ipsec-esp-iapm-00.txt> 3
Internet Draft Nov 2000
UMAC [BHKKR] does have an inherent parallelism, but it
suffers from requiring too much key material (or a
pseudorandom number generator to expand the key).
The new mode IAPM also comes with proofs of security
[Jut], assuming that the underlying block cipher is
secure. For confidentiality, the mode has the same
provable security as CBC. For authentication, the mode
has the same provable security as CBC-MAC.
2. Integrity Aware Parallelizable Mode (IAPM)
Let n be the block size of the underlying block cipher.
For example, DES ([FIPS]) has block size 64 bits, and
AES has block size 128 bits. If the block cipher
requires keys of length k, then this mode requires two
keys of length k. Let these keys be called K0 and K1.
We will use Encrypt(K,B) to denote the n bit result
produced by the underlying block cipher when a block B
of size n bits is encrypted using key K. Similarly, we
will use Decrypt(K,B) to denote the n bit result pro-
duced by the underlying block cipher (in decrypt mode)
when a block B of size n bits is decrypted using key K.
The payload to be encrypted P, is divided into blocks
of length n each. Let these blocks be
P[1],P[2],...,P[m-1]. We will assume that the payload
is sufficiently padded as is provisioned in IPSEC. An n
bit random initial vector r is chosen (see section 2.2
for more details). Using the key K0, this random vector
is used to prepare (m+1) new pair-wise independent n-
bit random vectors S[0],S[1],...,S[m]. Assume for now
the following declaration of a procedure to generate
such a set S:
procedure pairwise_independent_set(in r, m, K0; out S);
A proposed standard definition of the above pro-
cedure is given in section 2.1.
Given the plaintext payload P of (m-1) blocks, random
vector r, the keys K0, and K1, the cipher text C=
<C[0],C[1],...,C[m]> is generated as follows:
invoke pairwise_independent_set(r,m,K0,S)
M[0]= r
N[0]= Encrypt(K1,M[0])
C[0]= N[0]
Jutla <draft-jutla-ietf-ipsec-esp-iapm-00.txt> 4
Internet Draft Nov 2000
for i= 1 to m-1 do
M[i]= P[i] xor S[i]
N[i]= Encrypt(K1,M[i])
C[i]= N[i] xor S[i]
end for
checksum = P[1] xor P[2] xor ... xor P[m-1]
M[m]= checksum xor S[m]
N[m]= Encrypt(K1,M[m])
C[m]= N[m] xor S[0]
Note that S[0] is used in the last block. Also note
that the ciphertext has two more blocks than the plain-
text; one corresponding to the random vector r, and one
corresponding to the checksum. The operation xor above
is the bit-wise exclusive or operation.
Given the ciphertext payload C of (m+1) blocks, C=
<C[0],C[1],...,C[m]>, and the keys K0, and K1, the
plaintext P= <P[1],P[2],...,P[m-1]> is generated as
follows (along with an authentication test):
N[0]= C[0]
M[0]= Decrypt(K1,N[0])
r= M[0]
invoke pairwise_independent_set(r,m,K0,S)
for i= 1 to m-1 do
N[i]= C[i] xor S[i]
M[i]= Decrypt(K1,N[i])
P[i]= M[i] xor S[i]
end for
checksum = P[1] xor P[2] xor ... xor P[m-1]
N[m]= C[m] xor S[0]
M[m]= Decrypt(K1,N[m])
P[m]= M[m] xor S[m]
Integrity = (P[m] == checksum)
2.1. Generating the Pairwise Independent Set
The pairwise independent set can be generated by a sim-
ple algebraic method involving arithmetic modulo a
prime p. For this purpose, a standard prime p should be
chosen for each block size. The proposed standard prime
for block size 64 bits is p = 2^64-257. The proposed
standard prime for block size 128 bits is p= 2^128-159.
Here is the proposed definition of the procedure
pairwise_indepedent_set for 128 bit block size ciphers:
Jutla <draft-jutla-ietf-ipsec-esp-iapm-00.txt> 5
Internet Draft Nov 2000
procedure pairwise_independent_set(in r, m, K0; out S)
{
a= Encrypt(K0,r+1)
b= Encrypt(K0,r+2)
if (b > (2^128 - 159))
then b = (b + 159) mod 2^128
S[0]= a
for i= 1 to m do
S[i]= (S[i-1] + b ) mod 2^128
if (b > S[i]) S[i] = (S[i] + 159) mod 2^128
end for
}
The condition (b > S[i]) is equivalent to checking if
a carry was produced off the most significant bit in
the previous addition.
2.2. Generating the random vector r
The algorithm as described in section 2 calls for a
random vector r. Sometimes, this random vector is
called initial vector (IV). The algorithm doesn't
require the random vector to be random (in the sense of
uniformly distributed etc.), but different for each
payload. This can be easily achieved in ESP (Encapsu-
lating Security Payload) as the ESP Header requires a
sequence number (which is a unique number for each
packet, till the key is refreshed). In ESP the standard
sequence number is a 32 bit quantity. If the key is not
going to be used for more than 2^32 different payloads,
then clearly, the sequence number can serve the purpose
of r. However, we recommend that the other 32 bits be
assigned a random number how so ever chosen (for 64
bit block ciphers).
2.3. Keys
The mode as described in section 2 requires two dif-
ferent keys K0, K1 of k bits each, where k is the
length of the key required by the underlying block
cipher. The mode of operation remains secure even if
the keys K0 and K1 are same. However, we recommend that
different independent keys be chosen.
2.4. Security Considerations
The mode IAPM proposed in section 2, like CBC, employs
a block cipher. A mode of operation allows a longer
payload to be encrypted/authenticated, using an
Jutla <draft-jutla-ietf-ipsec-esp-iapm-00.txt> 6
Internet Draft Nov 2000
underlying block cipher like DES. There are no proofs
of security of block ciphers; a block cipher is
regarded secure if it has been tested against all known
attacks and cryptanalytic tools. However, once one
assumes that a block cipher is secure, the security of
modes of operation like CBC, CBC-MAC and IAPM can be
proven. In simple terms, if a block cipher of block
size n bits is considered secure for usage of upto 2^n
blocks, then it is useful to prove that the block
cipher used in a mode to encrypt longer messages (i.e.
longer than one block, and now security refers to
secrecy of the whole message), is still secure for
usage of upto 2^(n/2) total blocks. Here, the total
blocks refers to sum of the number of blocks over all
messages.
The mode of operation CBC (Cipher Chain Blocking) was
proven secure in [BDJR] in this sense. Similarly, the
authentication scheme CBC-MAC was proven secure in
[BKR]. Both these proofs assume that the underlying
block cipher is secure.
Similarly, assuming that the underlying block cipher is
secure, the mode IAPM has the same security bound for
confidentiality as CBC, and the same security bound for
authentication as CBC-MAC (see [Jut] for proofs of
security).
3. ESP Header Authentication
The ESP protocol requires that even the ESP header be
authenticated. In paritcular, the ESP header contains
the sequence number of the packet which needs to be
authenticated, otherwise the ESP protocol is prone to
replay attacks. However, the ESP header is transmitted
unencrypted. It is sent unencrypted, partly because it
has other information as to which encryption algorithm
to use, but also because most implementations keep a
window of sequence numbers, and can discard a packet
with a repeated sequence number even before
decryption/authentication. The mode as proposed in
section 2, authenticates only the ciphertext, and thus
the sequence number was sent encrypted. However, the
mode in section 2 can be modified so that the block
C[0] instead of being an encryption of r, can be r
itself. This was observed in [Rog]. In other words,
C[0]=r
Jutla <draft-jutla-ietf-ipsec-esp-iapm-00.txt> 7
Internet Draft Nov 2000
This variant of the mode still authenticates the whole
ciphertext i.e. C=<C[0],C[1],...,C[m]>. In other words,
any change in the ciphertext will be detected on
decryption as integrity failure. Thus, r is transmitted
unencrypted, but still authenticated. The proofs of
security in [Jut] continue to hold for this variant.
Since, r contains the sequence number, the crucial por-
tion of the ESP header which needed to be authenticated
is indeed authenticated.
The block C[0] can then be made part of the ESP header
itself. The last block C[m] can be placed in the "MAC"
field of the ESP packet.
4. Further Variants
For smaller payloads, the generation of two random
numbers a, b in the procedure pairwise_independent_set
maybe expensive. This concern was expressed in [GD],
where they had a solution which generated only one ran-
dom number a. Here we propose another variant of the
IPAM mode of section 2 which only requires generating
one random number a. This variant instead of using a
pairwise independent set S, uses a pairwise differen-
tially uniform set. The security bounds as mentioned in
section 2.4, and the proofs in [Jut] continue to hold
for this variant. More precisely, this variant has the
same security bounds as CBC (for confidentiality) and
CBC-MAC (for authentication). The solution in [GD] pro-
vides a slightly weaker security bound than CBC and
CBC-MAC.
Assume for now the following declaration of a procedure
to generate a pairwise differentially uniform set S:
procedure pairwise_diff_uniform_set(in r, m, K0; out
S);
A proposed standard definition of the above procedure
is given in section 4.1.
Given the plaintext payload P of (m-1) blocks, random
vector r, the keys K0, and K1, the cipher text C=
<C[0],C[1],...,C[m]> is generated as follows:
Jutla <draft-jutla-ietf-ipsec-esp-iapm-00.txt> 8
Internet Draft Nov 2000
invoke pairwise_diff_uniform_set(r,m,K0,S)
C[0]= r
for i= 1 to m-1 do
M[i]= P[i] + S[i]
N[i]= Encrypt(K1,M[i])
C[i]= N[i] + S[i]
end for
checksum = P[1] + P[2] + ... + P[m-1]
M[m]= checksum + S[m]
N[m]= Encrypt(K1,M[m])
C[m]= N[m] + S[0]
The operation "+" above is the n-bit integer addition
operation.
Given the ciphertext payload C of (m+1) blocks, C=
<C[0],C[1],...,C[m]>, and the keys K0, and K1, the
plaintext P= <P[1],P[2],...,P[m-1]> is generated as
follows (along with an authentication test):
r= C[0]
invoke pairwise_diff_uniform_set(r,m,K0,S)
for i= 1 to m-1 do
N[i]= C[i] - S[i]
M[i]= Decrypt(K1,N[i])
P[i]= M[i] - S[i]
end for
checksum = P[1] + P[2] + ... + P[m-1]
N[m]= C[m] - S[0]
M[m]= Decrypt(K1,N[m])
P[m]= M[m] - S[m]
Integrity = (P[m] == checksum)
The operation "-" above is the n-bit integer subtract-
ion operation.
4.1. Generating the Pairwise Differentially Uniform Set
Again, a standard prime p should be chosen for each
block size. The proposed standard prime for block size
64 bits is p = 2^64-257. The proposed standard prime
for block size 128 bits is p= 2^128-159. Here is the
proposed definition of the procedure
pairwise_diff_uniform_set for 128 bit block size
ciphers:
Jutla <draft-jutla-ietf-ipsec-esp-iapm-00.txt> 9
Internet Draft Nov 2000
procedure pairwise_diff_uniform_set(in r, m, K0; out S)
{
a= Encrypt(K0,r+1)
if (a > (2^128 - 159))
then a = (a + 159) mod 2^128
S[0]= a
for i= 1 to m do
S[i]= (S[i-1] + a ) mod 2^128
if (a > S[i]) S[i] = (S[i] + 159) mod 2^128
end for
}
5. Intellectual Property Issues
IBM has filed U.S. patents on this mode and its vari-
ants in April, 2000.
6. Acknowledgments
The author would like to thank Pau-Chen Cheng, J.R.
Rao, and Pankaj Rohatgi for helpful comments. The
author would also like to thank Don Coppersmith, Ron
Rivest and Pankaj Rohatgi for going through the secu-
rity proofs.
7. References
[ANSI] ANSI X3.106, ``American National Standard
for Information Systems - Data Encryption Algorithm -
Modes of Operation'', American National Standards
Institute, 1983.
[NBS] National Bureau of Standards, NBS FIPS PUB 81, ``DES
modes of operation'', U.S. Department of Commerce,
1980.
[FIPS] National Bureau of Standards, Data Encryption Stan-
dard, U.S.
Department of Commerce, FIPS 46 (1977)
[Bel] S. M. Bellovin, "Problem Areas for the IP Security
Protocols", Proc. of the 6th USENIX UNIX Security
Symp., Jul 1996
[BCH] M. Bellare, R. Canetti, H. Krawczyk, " Keyed Hash
Functions and Message Authentication", Advances in
Cryptology, Crypto 96, LNCS 1109, 1996.
Jutla <draft-jutla-ietf-ipsec-esp-iapm-00.txt> 10
Internet Draft Nov 2000
Expiration Date: May 2001
[BKR] M. Bellare, J. Kilian, P. Rogaway, ``The Security of
Cipher Block Chaining'', CRYPTO 94, LNCS 839, 1994
[BDJR] M. Bellare, A. Desai, E. Jokiph, P. Rogaway, ``A Con-
crete Security Treatment of Symmetric Encryption:
Analysis of the DES Modes of OPeration'', 38th IEEE
FOCS, 1997
[CGHK] P,-C. Cheng, J.A. Garay, A. Herzberg, H. Krawczyk, "A
security architecture for the internet protocol", IBM
Systems Journal, Vol 37, No. 1, 1998.
[GD] V. D. Gligor and P. Donescu, "Fast Encryption and
Authentication: XCBC Encryption and XECB Authentication
Modes", Symmetric Key Block Cipher Modes of Operation
Workshop, http://csrc.nist.gov/encryption/aes/modes/
[IPSEC] Security Architecture for the Internet Protocol, RFC
2401, http://www.ietf.org/rfc/rfc2401.txt
[Jut] C.S. Jutla, "Encryption Modes with Almost Free Message
Integrity", http://eprint.iacr.org/2000/039, August 1,
2000. Also, Symmetric Key Block Cipher Modes of Opera-
tion Wksp., http://csrc.nist.gov/encryption/aes/modes/
[Rog] P. Rogaway, "OCB Mode: Parallelizable Authenticated
Encryption", Symmetric Key Block Cipher Modes of Opera-
tion Wksp., http://csrc.nist.gov/encryption/aes/modes/
8. Author's Address
Charanjit S. Jutla
IBM T.J. Watson Research Center,
Yorktown Heights, NY 10598-704.
Phone: 914-784-7890
Email: csjutla@watson.ibm.com
Comments should be sent to the above e-mail address.
Jutla <draft-jutla-ietf-ipsec-esp-iapm-00.txt> 11