, and the keys K0, and K1, the
plaintext P= 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 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 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 7
Internet Draft Nov 2000
This variant of the mode still authenticates the whole
ciphertext i.e. C=. 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=
is generated as follows:
Jutla 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=
, and the keys K0, and K1, the
plaintext P= 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 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 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 11