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]