CFRG Working Group T. Krovetz
INTERNET-DRAFT CSU Sacramento
Expires January 2007 July 2006
The UMAC-AE and VMAC-AE Authenticated-Encryption Algorithms
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Status of this Memo
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/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
This document specifies UMAC-AE and VMAC-AE, shared-key algorithms
that simultaneously encrypt data using a block cipher in counter mode
while also authenticating the resulting ciphertext and optional
associated data using UMAC or VMAC.
T. Krovetz Expires January 2007 [Page 1]
INTERNET-DRAFT UMAC-AE/VMAC-AE July 2006
1 Introduction
An authenticated-encryption scheme allows parties who share a secret
key to communicate in a way that ensures both privacy and
authenticity. UMAC-AE and VMAC-AE achieve these goals by combining
proven and efficient methods. Privacy is provided by a block cipher
in counter-mode, while authentication of the encrypted data, along
with optional unencrypted data, is achieved using UMAC or VMAC.
Counter-mode encryption, UMAC and VMAC are efficient, provably-
secure, parallelizable and have been well studied, as has the
composition of encryption and message authentication algorithms
[Comp, AEAD, Modes, UMAC00, UMAC99, VMAC].
Historically, if one desired both privacy and authentication, one
would encrypt using one key and authenticate using another.
Recently, schemes have been developed that integrate more closely the
two operations under the same key reducing key-management and memory
requirements. UMAC-AE and VMAC-AE keys are used exclusively to key
an underlying block cipher, and the use of the block cipher is
coordinated so that only a single key is needed for both encryption
and authentication.
The authenticated encryption algorithms accept several inputs in
addition to the plaintext M that is to be enrypted. Nonce N must be
unique for each encryption. Prologue data H, known before M is
encrypted, and epilogue data F, known after encryption of M begins,
can optionally be authenticated. Authenticated encryption protects
the privacy of M and the authenticity of H, F, N, and M. The result
(C, T) one gets by encrypting M in the presence of H and F consists
of a ciphertext C having the same length as M, plus an authentication
tag T. Communicating parties can choose to use 32-, 64-, 96- or
128-bit authentication tags (in UMAC-AE), or 64- or 128-bit
authentication tags (in VMAC-AE), depending on desired performance
and security levels. Shorter tags add less authentication cost to
the authenticated-encryption process, but provide less assurance of
authenticity.
UMAC and VMAC were designed with different goals. UMAC was designed
to perform optimally on processors that support well the
multiplication of 32-bit operands into 64-bit results, while VMAC was
designed to use less per-session memory than UMAC (about 900 fewer
bytes) and to perform optimally on processors that support well the
multiplication of 64-bit operands into 128-bit results. The choice
between UMAC-AE and VMAC-AE therefore should be made according to the
expected environment. The computational cost of UMAC-AE and VMAC-AE
is the cost of counter-mode encryption plus the cost of UMAC or VMAC,
which can add to the encryption cost as little as 0.5 CPU cycles per
byte of authenticated data (in the case of VMAC-AE, 2KB messages,
T. Krovetz Expires January 2007 [Page 2]
INTERNET-DRAFT UMAC-AE/VMAC-AE July 2006
64-bit authetication tags on an AMD Athlon 64).
UMAC and VMAC are defined in other documents [rfc4418, VMAC Spec].
2 Notation and Basic Operations
There are two types of variables used in this specification, strings
and integers. String variables are always written with an initial
upper-case letter while integer variables are written in all lower-
case. Functions, except for the simple ones defined in this section,
are written in all upper-case. Whenever a variable is followed by an
underscore ("_"), the underscore is intended to denote a subscript,
with the subscripted expression requiring evaluation to resolve the
meaning of the variable. For example, when i = 2, then M_i refers to
the variable M_2.
The following operations are used throughout the definition of UMAC-
AE and VMAC-AE.
c^i The integer c raised to the i-th power.
ceil(x) The smallest integer no smaller than x.
bitlen(S) The length of string S in bits (eg, bitlen(101) = 3).
S xor T The string that is the bitwise exclusive-or of S and
T. Strings S and T must have the same length.
S[i] The i-th bit of the string S (indices begin at 1).
S[i..j] The substring of S consisting of bits i through j.
S || T The string S concatenated with string T (eg, 000 ||
111 = 000111).
zeropad(S,n) The string S || P where P is the shortest (possibly
empty) string of zero-bits that makes S || P a multi-
ple of n bits in length.
num2str(n,i) The i-bit string S so that 2^{i-1} * S[1] + 2^{i-2} *
S[2] + ... + 2^{1} * S[i-1] + S[i] = n.
3 Parameters
UMAC-AE and VMAC-AE require the services of a block cipher and of
UMAC or VMAC, respectively. The selection of a block cipher defines
T. Krovetz Expires January 2007 [Page 3]
INTERNET-DRAFT UMAC-AE/VMAC-AE July 2006
the following constants and functions.
BLOCKLEN The length of the plaintext block that the block
cipher operates on.
KEYLEN The block cipher's key length, in bits.
ENCIPHER(K,P) The application of the block cipher on P (a string
of BLOCKLEN bits) using key K (a string of KEYLEN
bits).
As an example, if AES is used with 192-bit keys, then BLOCKLEN would
equal 128 (because AES employs 128-bit blocks), KEYLEN would equal
192, and ENCIPHER would refer to the AES function.
We note that the definitions of UMAC and VMAC also require the use of
a block cipher [rfc4418, VMAC Spec]. Hence, in UMAC-AE and VMAC-AE a
block cipher is used for two purposes: as the basis for the counter-
mode encryption of data and as part of the internal operation of UMAC
and VMAC. It is assumed that the block cipher selected for UMAC-AE
or VMAC-AE will also be selected for UMAC or VMAC, although this is
not a requirement. Unless specified otherwise, AES-128 will be the
default block cipher used in UMAC-AE and VMAC-AE.
4 UMAC-AE-ENCRYPT
Given key K and nonce N, this function encrypts plaintext M into
ciphertext C, and computes tag T which authenticates N, C and
associated data H and F. Encryption uses counter mode and
authentication uses UMAC.
Function name:
UMAC-AE-ENCRYPT
Input:
K, string of KEYLEN bits // Key
N, string with bitlength a multiple of // Nonce
8 but less than BLOCKLEN
H, string of no more than 2^64 bits // Header
M, string of no more than j bits where // Plaintext
j = min(2^64, BLOCKLEN * ((2^(BLOCKLEN-bitlen(N)))-1))
F, string of no more than 2^64 bits // Footer
taglen, integer 32, 64, 96 or 128 // Tag length requested
Output:
C, string of length equal to M // Ciphertext
T, string of taglen bits // Authentication tag
Compute C and T using the following algorithm.
T. Krovetz Expires January 2007 [Page 4]
INTERNET-DRAFT UMAC-AE/VMAC-AE July 2006
//
// Break M into blocks
//
m = max(1, ceil(bitlen(M) / BLOCKLEN))
Let M_1, M_2, ..., M_m be strings such that M = M_1 || M_2 || ...
|| M_m and bitlen(M_i) = BLOCKLEN for all 0 < i < m.
//
// Encrypt blocks
//
EKey = KDF(K, 0, KEYLEN/8) // KDF from Section 3.2 of [rfc4418]
for i = 1 to m do
Temp = ENCIPHER(EKey, N || num2str(i, BLOCKLEN-bitlen(N)))
C_i = M_i xor Temp[1..bitlen(M_i)]
end for
C = C_1 || C_2 || ... || C_m
//
// Compute authentication tag
//
UMACData = zeropad(H, 256) || zeropad(C, 256) || zeropad(F, 256) ||
num2str(bitlen(H), 64) || num2str(bitlen(C), 64) ||
num2str(bitlen(F), 64) || num2str(0, 64)
T = UMAC(K, UMACData, N, taglen/8)
5 UMAC-AE-DECRYPT
Given key K and nonce N, this function decrypts ciphertext C into
plaintext M, and determines whether tag T authenticates N, C and
associated data H and F. Decryption uses counter mode and
authentication uses UMAC.
Function name:
UMAC-AE-DECRYPT
Input:
K, string of KEYLEN bits // Key
N, string with bitlength a multiple of // Nonce
8 but less than BLOCKLEN
H, string of fewer than 2^64 bits // Header
C, string of fewer than j bits where // Ciphertext
j = min(2^64, BLOCKLEN * ((2^(BLOCKLEN-bitlen(N)))-1))
F, string of fewer than 2^64 bits // Footer
T, string of 32, 64, 96 or 128 bits // Authentication tag
Output:
M, string of length equal to C // Plaintext
V, boolean // Validity indicator
T. Krovetz Expires January 2007 [Page 5]
INTERNET-DRAFT UMAC-AE/VMAC-AE July 2006
Compute M and V using the following algorithm.
//
// Break C into blocks
//
m = max(1, ceil(bitlen(C) / BLOCKLEN))
Let C_1, C_2, ..., C_m be strings such that C = C_1 || C_2 || ...
|| C_m and bitlen(C_i) = BLOCKLEN for all 0 < i < m.
//
// Compute authentication tag and validity V
//
UMACData = zeropad(H, 256) || zeropad(C, 256) || zeropad(F, 256) ||
num2str(bitlen(H), 64) || num2str(bitlen(C), 64) ||
num2str(bitlen(F), 64) || num2str(0, 64)
if T = UMAC(K, UMACData, N, taglen/8) then
V = true
else
V = false
end if
//
// Decrypt blocks
//
EKey = KDF(K, 0, KEYLEN/8) // KDF from Section 3.2 of [rfc4418]
for i = 1 to m do
Temp = ENCIPHER(EKey, N || num2str(i, BLOCKLEN-bitlen(N)))
M_i = C_i xor Temp[1..bitlen(C_i)]
end for
M = M_1 || M_2 || ... || M_m
6 VMAC-AE-ENCRYPT
Given key K and nonce N, this function encrypts plaintext M into
ciphertext C, and computes tag T which authenticates N, C and
associated data H and F. Encryption uses counter mode and
authentication uses VMAC.
Function name:
VMAC-AE-ENCRYPT
Input:
K, string of KEYLEN bits // Key
N, string with bitlength a multiple of // Nonce
8 but less than BLOCKLEN, and N[1] = 0
H, string of fewer than 2^56 bits // Header
M, string of fewer than j bits where // Plaintext
j = min(2^64, BLOCKLEN * ((2^(BLOCKLEN-bitlen(N)))-1))
T. Krovetz Expires January 2007 [Page 6]
INTERNET-DRAFT UMAC-AE/VMAC-AE July 2006
F, string of fewer than 2^64 bits // Footer
taglen, integer 64 or 128 // Tag length requested
Output:
C, string of length equal to M // Ciphertext
T, string of taglen bits // Authentication tag
Compute C and T using the following algorithm.
//
// Break M into blocks
//
m = max(1, ceil(bitlen(M) / BLOCKLEN))
Let M_1, M_2, ..., M_m be strings such that M = M_1 || M_2 || ...
|| M_m and bitlen(M_i) = BLOCKLEN for all 0 < i < m.
//
// Encrypt blocks
//
for i = 1 to m do
Temp = ENCIPHER(K, N || num2str(i, BLOCKLEN-bitlen(N)))
C_i = M_i xor Temp[1..bitlen(M_i)]
end for
C = C_1 || C_2 || ... || C_m
//
// Compute authentication tag
//
VMACData = zeropad(H, 128) || zeropad(C, 128) ||
zeropad(F, 128) || num2str(bitlen(F) mod 128, 8) ||
num2str(bitlen(H), 56) || num2str(bitlen(C), 64)
T = VMAC(K, VMACData, N, taglen/8)
7 VMAC-AE-DECRYPT
Given key K and nonce N, this function decrypts ciphertext C into
plaintext M, and determines whether tag T authenticates N, C and
associated data H and F. Decryption uses counter mode and
authentication uses VMAC.
Function name:
VMAC-AE-DECRYPT
Input:
K, string of KEYLEN bits // Key
N, string with bitlength a multiple of // Nonce
8 but less than BLOCKLEN, and N[1] = 0
H, string of fewer than 2^56 bits // Header
T. Krovetz Expires January 2007 [Page 7]
INTERNET-DRAFT UMAC-AE/VMAC-AE July 2006
C, string of fewer than j bits where // Ciphertext
j = min(2^64, BLOCKLEN * ((2^(BLOCKLEN-bitlen(N)))-1))
F, string of fewer than 2^64 bits // Footer
T, string of 64 or 128 bits // Authentication tag
Output:
M, string of length equal to C // Plaintext
V, boolean // Validity indicator
Compute M and V using the following algorithm.
//
// Break C into blocks
//
m = max(1, ceil(bitlen(C) / BLOCKLEN))
Let C_1, C_2, ..., C_m be strings such that C = C_1 || C_2 || ...
|| C_m and bitlen(C_i) = BLOCKLEN for all 0 < i < m.
//
// Compute authentication tag and validity V
//
VMACData = zeropad(H, 128) || zeropad(C, 128) ||
zeropad(F, 128) || num2str(bitlen(F) mod 128, 8) ||
num2str(bitlen(H), 56) || num2str(bitlen(C), 64)
if T = VMAC(K, VMACData, N, taglen/8) then
V = true
else
V = false
end if
//
// Decrypt blocks
//
for i = 1 to m do
Temp = ENCIPHER(K, N || num2str(i, BLOCKLEN-bitlen(N)))
M_i = C_i xor Temp[1..bitlen(C_i)]
end for
M = M_1 || M_2 || ... || M_m
6 Security Considerations
UMAC-AE and VMAC-AE achieve two security properties: message privacy
and message (with associated data) authenticity. Privacy is in the
sense of "indistinguishability from random bits", meaning that an
adversary is unable to distinguish encryptions from an equal number
of random bits. Authenticity is in the sense of "authenticity of
ciphertexts with associated data", meaning that an adversary is
unable to produce any valid (N,H,F,C,T) quintuple that it has not
T. Krovetz Expires January 2007 [Page 8]
INTERNET-DRAFT UMAC-AE/VMAC-AE July 2006
already acquired. The privacy and the authenticity guarantees depend
on the underlying block cipher being secure in the sense of a strong
pseudorandom permutation. Thus if UMAC-AE or VMAC-AE is used with a
block cipher that is not secure as a strong pseudorandom permutation,
the security guarantees vanish. The need for the strong pseudorandom
permutation property means that only a conservatively designed, well-
trusted block cipher, such as AES, should be used [AES].
If UMAC-AE or VMAC-AE were instantiated using a random function
(producing outputs of length BLOCKLEN) rather than a block cipher,
the privacy properties would be unconditionally guaranteed, meaning
no adversary could distinguish encryptions from random bits. The
authenticity gurantees depend on the length of tag chosen. When
using tags of length 32i, each attempt by an aversary to produce a
new valid (N,H,F,C,T) may succeed with probability of about 1/2^30i.
Because UMAC-AE and VMAC-AE are instantiated with a block cipher
rather than a random function, one must add to an adversary's
probabilty of successful attack a term which measures how well the
block cipher approximates a random function. Over s invocations, an
adversary has about (s^2 / 2^BLOCKLEN + delta) probability of
distinguishing the output as coming from a random function or a
randomly-keyed block cipher, where s^2 / 2^BLOCKLEN is a birthday
bound and delta measures the quality of the block cipher used. For a
well-designed block cipher, delta will be insignificant. To esimate
an attackers chance of success one thus needs to evaluate (s^2 /
2^BLOCKLEN) + n/(2^30i) where s is the total number of block-cipher
calls (one for each BLOCKLEN bits of data encrypted plus one for each
tag generated) and n is the number of forgery attempts allowed. As a
concrete example, if one was using AES and 64-bit tags, and wanted a
successful attack to happen with probability no more than 1/2^40,
then it would suffice to keep both (s^2 / 2^128) and n/(2^60) less
than 1/2^41, which occurs when no more than 2^43 block-cipher calls
or 2^19 forgery attempts are made.
It is crucial that nonces are not allowed to repeat during encryption
or decryption. The security definitions assume this for both privacy
and authenticity, and the implementor must ensure that with
overwhelming probability nonces are not repeated by the
implementation. The nonce need not be secret, and a counter may be
used for it. If a nonce is seen twice by a receiver, no information
other than the fact that the nonce is a repeat should be given to the
sender.
UMAC-AE and VMAC-AE allow a variety of tag and nonce lengths to suit
differnt application needs. These lengths should be fixed, either by
negotiation or by convention, and then should not be allowed to
change for the duration of the communication session. The tag and
nonce lengths are not authenticated by the UMAC-AE or VMAC-AE
T. Krovetz Expires January 2007 [Page 9]
INTERNET-DRAFT UMAC-AE/VMAC-AE July 2006
algorithms, so one must take care that an attacker is not able to
manipulate the lengths to be used.
When a tag is found to be invalid it is the implementor's
responsibility to make sure that no information beyond this fact is
made available to the adversary. The UMAC-AE and VMAC-AE encryption
schemes reveal in the ciphertext the length of the plaintext.
Sometimes the length of the plaintext is a valuable piece of
information that should be hidden. For environments where "traffic
analysis" is a concern, techniques (typically involving padding)
would be necessary.
Further analysis of UMAC-AE and VMAC-AE can be found in the
references [AE].
Appendix - Test Vectors
These are not yet available.
References
Normative References
[AES] FIPS-197, "Advanced Encryption Standard (AES)", National
Institute of Standards and Technology, 2001.
[rfc4418] T. Krovetz (Editor), "UMAC: Message authentication code
using universal hashing", IETF, 2006.
[VMAC Spec] T. Krovetz, "VMAC: Message authentication code using
universal hashing", Internet-Draft, 2006.
Informative References
[AE] T. Krovetz, "Authenticated encryption with UMAC and
VMAC", to be submitted to International Conference on
Telecommunications and Networking - TeNe 06, 2006.
[AEAD] P. Rogaway, "Authenticated encryption with associated
data", ACM Conference on Computer and Communications
Security 2002 - CCS '02, pp. 98-107, ACM Press, 2002.
[Comp] M. Bellare, C. Namprempre, "Authenticated encryption:
Relations among notions and analysis of the generic
composition paradigm", Advances in Cryptology -
ASIACRYPT '00, LNCS vol. 1976, Springer-Verlag, 2000.
T. Krovetz Expires January 2007 [Page 10]
INTERNET-DRAFT UMAC-AE/VMAC-AE July 2006
[Modes] M. Bellare, A. Desai, E. Jokipii, P. Rogaway, "A
concrete security treatment of symmetric encryption:
Analysis of the DES modes of operation", Proceedings of
38th Annual Symposium on Foundations of Computer
Science, 1997.
[UMAC00] T. Krovetz, "Software-optimized universal hashing and
message authentication", UMI Dissertation Services,
2000.
[UMAC99] J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P.
Rogaway, "UMAC: Fast and provably secure message
authentication", Advances in Cryptology - CRYPTO '99,
LNCS vol. 1666, pp. 216-233, Springer-Verlag, 1999.
[VMAC] T. Krovetz, "Message authentication on 64-bit
architectures", submitted to Selected Areas of
Cryptography - SAC '06, Springer-Verlag, 2006.
Author Contact Information
Author's Address
Ted Krovetz
Department of Computer Science
California State University
Sacramento CA 95819
USA
EMail: tdk@acm.org
Full Copyright Statement
Copyright (C) The Internet Society (2006).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM 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.
T. Krovetz Expires January 2007 [Page 11]
INTERNET-DRAFT UMAC-AE/VMAC-AE July 2006
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the ISOC's procedures with respect to rights in ISOC Documents can
be found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at ietf-
ipr@ietf.org.
Acknowledgments
Thanks to Hugo Krawczyk for valuable comments. This document shares
some text with "draft-krovetz-ocb-00.txt", an expired Internet-Draft
written with Phil Rogaway. Funding for the RFC Editor function is
currently provided by the Internet Society.
T. Krovetz Expires January 2007 [Page 12]