CFRG Working Group T. Krovetz INTERNET-DRAFT CSU Sacramento Expires December 2005 June 2005 The UMAC-AE Authenticated-Encryption Algorithm 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 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/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, a shared-key algorithm that simultaneously encrypts data using a block cipher in counter mode while also authenticating the data with UMAC. At its peak rate, using AES as the block cipher, UMAC-AE encrypts and authenticates data at a cost of about 10% more than simple encryption. UMAC is unencumbered by intellectual property claims and can be used freely. Pairing UMAC with a license-free block cipher, such as AES, provides fast and license-free authenticated encryption. T. Krovetz Expires December 2005 [Page 1] INTERNET-DRAFT UMAC-AE June 2005 1 Introduction An authenticated-encryption scheme allows parties who share a key to communicate in a way that ensures both privacy and authenticity. UMAC-AE achieves both 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 header data) is authenticated using UMAC. Both counter- mode encryption and UMAC are efficient, provably-secure, parallelizable and have been well studied [Modes, NESSIE, UMAC99, UMAC00]. The composition of encryption and message authentication algorithms has also been well studied [Order]. Several other authenticated-encryption schemes have been proposed for standardization [NIST Modes]. Both UMAC and counter-mode encryption require the services of a block cipher. Typically, AES will serve this role, but any block cipher with a block length of at least 128 bits will suffice. A single block cipher key is provided to UMAC-AE, and the key is safely used to initialize both encryption and authentication. The user is required to supply a new nonce N for each encryption. UMAC-AE allows a header H, or any other data that requires authentication but not encryption, to be specified when one encrypts. UMAC-AE encryption protects the privacy of plaintext data M, and the authenticity of header H, nonce N, and M. M and H can have any bitlength upto 2^54 and 2^64 bits, respectively. The ciphertext (C, T) one gets by encrypting M in the presence of H 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, depending on their security needs. UMAC-AE has many nice properties. UMAC-AE is on-line: one need not know the length of H or M to proceed with encryption, nor need one know the length of H or C to proceed with decryption. UMAC-AE is parallelizable: both the encryption and authentication of data can be done in any order at the granularity of the block cipher's block length. UMAC-AE enjoys provable security: the mode of operation is secure assuming that the underlying block cipher is secure. There are no known intellectual property restrictions on any aspect of UMAC-AE. AES and UMAC are defined in other documents [AES, UMAC 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 T. Krovetz Expires December 2005 [Page 2] INTERNET-DRAFT UMAC-AE June 2005 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. c^i The integer c raised to the i-th power. ceil(x) The smallest integer no smaller than x. bitlength(S) The length of string S in bits (eg, bitlength(101) = 3). zeros(n) The string made of n zero-bits. 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). str2num(S) The non-negative integer whose binary representation is the string S. More formally, if S is t bits long then str2num(S) = 2^{t-1} * S[1] + 2^{t-2} * S[2] + ... + 2^{1} * S[t-1] + S[t]. num2str(n,i) The i-bit string S such that str2num(S) = n. 3 UMAC-AE Parameters UMAC-AE requires the services of a block cipher and of UMAC. The selection of a block cipher defines the following constants and functions. BLOCKLEN The length of the plaintext block that the block cipher operates on. T. Krovetz Expires December 2005 [Page 3] INTERNET-DRAFT UMAC-AE June 2005 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 definition of UMAC involves the use of a block cipher [UMAC spec]. Hence, in UMAC-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. The present specification of UMAC-AE uses the same block cipher for both purposes. Unless specified otherwise, AES with 128-bit keys shall be used as the block cipher. AES and UMAC are defined in other documents [AES, UMAC Spec]. 4 Encryption: UMAC-AE-ENCRYPT This function computes a ciphertext and authentication tag when given a message, header, nonce and key. Function name: UMAC-AE-ENCRYPT Input: K, string of KEYLEN bits // Key N, string of BLOCKLEN - 48 bits // Nonce H, string of no more than 2^64 bits // Header M, string of no more than 2^54 bits // Plaintext 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. // // Break M into blocks // m = max(1,ceil(bitlength(M) / BLOCKLEN)) Let M_1, M_2, ..., M_m be strings such that M = M_1 || M_2 || ... || M_m and bitlength(M_i) = BLOCKLEN for all 0 < i < m. // T. Krovetz Expires December 2005 [Page 4] INTERNET-DRAFT UMAC-AE June 2005 // Initialize auxiliary data // UMACKey = ENCIPHER(K,zeros(BLOCKLEN)) ctr = 0 // // Encrypt blocks // for i = 1 to m do ctr = ctr + 1 Temp = ENCIPHER(K, N || num2str(ctr, 48)) C_i = M_i xor Temp[1..bitlength(M_i)] end for C = C_1 || C_2 || ... || C_m // // Compute authentication tag // hpadlength = (256 - (bitlength(H) mod 256)) mod 256 cpadlength = (256 - (bitlength(C) mod 256)) mod 256 UMACData = H || zeros(hpadlen) || C || zeros(cpadlen) || num2str(bitlength(H), 64) || num2str(bitlength(C), 64) T = UMAC(UMACKey, UMACData, N, taglen/8) 5 Decryption: UMAC-AE-DECRYPT This function takes as input a ciphertext, header, authentication tag, nonce and key, and returns a plaintext and a determination as to whether the given tag is valid for the given ciphertext, header, nonce and key. Function name: UMAC-AE-DECRYPT Input: K, string of KEYLEN bits // Key N, string of BLOCKLEN - 48 bits // Nonce H, string of no more than 2^64 bits // Header C, string of no more than 2^54 bits // Ciphertext T, string of 32, 64, 96 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. // T. Krovetz Expires December 2005 [Page 5] INTERNET-DRAFT UMAC-AE June 2005 // Break C into blocks // m = max(1,ceil(bitlength(C) / BLOCKLEN)) Let C_1, C_2, ..., C_m be strings such that C = C_1 || C_2 || ... || C_m and bitlength(C_i) = BLOCKLEN for all 0 < i < m. // // Initialize auxiliary data // UMACKey = ENCIPHER(K,zeros(BLOCKLEN)) ctr = 0 // // Compute authentication tag // hpadlength = (256 - (bitlength(H) mod 256)) mod 256 cpadlength = (256 - (bitlength(C) mod 256)) mod 256 UMACData = H || zeros(hpadlen) || C || zeros(cpadlen) || num2str(bitlength(H), 64) || num2str(bitlength(C), 64) ValidTag = UMAC(UMACKey, UMACData, N, bitlength(T)/8) // // Decrypt blocks // for i = 1 to m do ctr = ctr + 1 Temp = ENCIPHER(K, N || num2str(ctr, 48)) M_i = C_i xor Temp[1..bitlength(C_i)] end for M = M_1 || M_2 || ... || M_m // // Compute results // if T = ValidTag then V = true else V = false end if 6 Security Considerations UMAC-AE achieves two security properties, message privacy and message authenticity. Privacy is "indistinguishability from random bits", meaning that an adversary is unable to distinguish UMAC-AE encryptions from an equal number of random bits. Authenticity is "authenticity of ciphertexts", meaning that an adversary is unable to T. Krovetz Expires December 2005 [Page 6] INTERNET-DRAFT UMAC-AE June 2005 produce any valid (N,H,C,T) quadruple that it has not already acquired. The privacy and the authenticity guarantee depend on the underlying block cipher being secure in the sense of a strong pseudorandom permutation. Thus if UMAC-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 UMAC-AE should be used with a conservatively designed, well-trusted block cipher, such as AES. The privacy properties of UMAC-AE degrade as per s^2 / 2^BLOCKLEN, where s is the total number of blocks that the adversary acquires, while the authenticity guarantees degrade as does t / 2^taglen, where t is the number of UMAC-AE invocations. The consequence of these formulas is that the proven security vanishes when s becomes as large as 2^{BLOCKLEN/2} or t becomes as large as 2^{taglen - 32}. Thus the user should never use a key to generate an amount of ciphertext that is near to, or exceeds, 2^{BLOCKLEN/2} blocks or invokes UMAC-AE anything near 2^{taglen - 32} times. Block ciphers typically have blocksizes of 64 or 128 bits, and the above restriction is a significant one if the blocklength is not more than 64 bits. Therefore UMAC-AE has been designed to work with a block cipher having a blocklength of at least 128 bits. The mode may then be used to encrypt upto 2^48 blocks (2^56 bits) or 2^{taglen - 32} total applications, keeping an adversary's chance to do damage at no more than about 2^{-32}. It is crucial that, as one encrypts strings, one does not repeat a nonce. The security definitions assume this, for both privacy and authenticity. The implementor must ensure that, with overwhelming probability, this assumption is achieved by the implementation that uses UMAC-AE. The nonce need not be secret, and a counter may be used for it. If two parties send UMAC-AE-encrypted messages to one another using the same key, then the space of nonces used by the two parties should be partitioned so that no nonce that could be used by one party to encrypt could be used by the other to encrypt. For example, one party could send data with odd nonces while the other sends data with even nonces. When a ciphertext decrypts as "invalid" it is the implementor's responsibility to make sure that no information beyond this fact is made adversarially available. UMAC-AE encryption produces a tag T of 32, 64, 96 or 128 bits. The length taglen of the tag used impacts the adversary's ability to forge: it will always be trivial for the adversary to forge with probability 2^{-taglen}. It is up to the application designer to choose an appropriate value for taglen. For typical applications, the value should be 64 or more. The taglen value should be T. Krovetz Expires December 2005 [Page 7] INTERNET-DRAFT UMAC-AE June 2005 determined at session setup and should be dictated by the message recipient. The taglen value is not authenticated by the UMAC-AE algorithm and one must ensure that an attacker can not convince a recipient to employ unreasonably short authentication tags. The UMAC-AE encryption scheme reveals 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 beyond UMAC-AE encryption (typically involving padding) would be necessary. 7 Acknowledgments Thanks to Hugo Krawczyk for valuable comments. This document shares some text with "draft-krovetz-ocb-00.txt", an Internet-Draft written by Ted Krovetz and Phil Rogaway. 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. [UMAC Spec] T. Krovetz (Editor), "UMAC: Message authentication code using universal hashing", Internet-Draft, draft-krovetz- umac-03.txt, 2004. Informative References [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. [NESSIE] New European Schemes for Signatures, Integrity, and Encryption, http://www.cryptonessie.org/. [NIST Modes] NIST Computer Security Resource Center, Symmetric Key Block Cipher Modes of Operation, T. Krovetz Expires December 2005 [Page 8] INTERNET-DRAFT UMAC-AE June 2005 http://www.nist.gov/modes/. [Order] H. Krawczyk, "The order of encryption and authentication for protecting communications", Advances in Cryptology - CRYPTO 2001, Lecture Notes in Computer Science, Springer, 2001. [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. 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 (2005). 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 December 2005 [Page 9]