CFRG Working Group T. Krovetz INTERNET-DRAFT CSU Sacramento Expires September 2005 P. Rogaway UC Davis March 2005 The OCB Authenticated-Encryption Algorithm By submitting this Internet-Draft, we certify that any applicable patent or other IPR claims of which we are aware have been disclosed, or will be disclosed, and any of which we become aware will be disclosed, in accordance with RFC 3668 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 OCB 2.0, a shared-key encryption scheme combining privacy and authenticity. This blockcipher-based, single- pass mechanism provides privacy and authenticity for a message, plus authenticity for any associated header. It does this in the most simple and efficient way known. Krovetz, Rogaway Expires September 2005 [Page 1] INTERNET-DRAFT OCB March 2005 Table of Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Notation and Basic Operations . . . . . . . . . . . . . . . . . . 4 3 OCB Parameters . . . . . . . . . . . . . . . . . . . . . . . . . 5 4 Header Authentication: PMAC . . . . . . . . . . . . . . . . . . . 5 5 Encryption: OCB-ENCRYPT . . . . . . . . . . . . . . . . . . . . . 6 6 Decryption: OCB-DECRYPT . . . . . . . . . . . . . . . . . . . . . 8 7 Security Considerations . . . . . . . . . . . . . . . . . . . . . 9 8 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 11 Appendix - Test Vectors . . . . . . . . . . . . . . . . . . . . . . 11 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Author Contact Information . . . . . . . . . . . . . . . . . . . . . 13 Krovetz, Rogaway Expires September 2005 [Page 2] INTERNET-DRAFT OCB March 2005 1 Introduction An authenticated-encryption scheme allows parties who share a key to communicate in a way that ensures both privacy and authenticity. This document specifies the authenticated-encryption scheme OCB 2.0. The method is a refinement, based on work of Rogaway [Offsets], to Rogaway, Bellare, and Black's original OCB [OCB1]. The latter was, in turn, a refinement to Jutla's IAPM [Jutla]. Henceforth in this document, "OCB" is understood to mean OCB 2.0. OCB depends on a blockcipher, typically AES [AES]. Encryption and decryption employ a nonce N, which must be selected as a new value for each encryption. OCB allows a header H to be specified when one encrypts or decrypts a string. The plaintext message M and the header H can have any bitlength. The ciphertext (C, T) one gets by encrypting M in the presence of H consists of a ciphertext core C having the same length as M, plus an authentication tag T. If desired, the user may truncate T. OCB encryption protects the privacy of M and and the authenticity of H, N, and M. It does this using h + m + 2 blockcipher calls, where h is the blocklength of H and m is the blocklength of M. If H is fixed during a session then, after preprocessing, there is effectively no cost to have H authenticated, and the mode will use m + 2 blockcipher calls. OCB requires a single key K for the underlying blockcipher, and all blockcipher calls are keyed by K. OCB 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. OCB is parallelizable: the bulk of its blockcipher calls can be performed simultaneously. Computational work beyond blockcipher calls consists of a small and fixed number of logical operations per call. OCB enjoys provable security: the mode of operation is secure assuming that the underlying blockcipher is secure. Two characteristics differentiate OCB 2.0 from its predecessor. The first is the built-in capability of handling the header H, and the second is the simpler way in which offsets are computed. Pending patent applications submitted by Rogaway apply to OCB. Rogaway grants free and unrestricted use of his OCB-related intellectual property for code released under the GNU General Public License [GPL]. Further royalty-free uses are also available. Direct licensing inquiries to Rogaway. Two other parties, IBM and VDG Inc., are also known to have patent applications dealing with authenticated encryption. Krovetz, Rogaway Expires September 2005 [Page 3] INTERNET-DRAFT OCB March 2005 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 OCB. 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). S << n The string S shifted left n bit positions. More formally, S << n = S[n+1..bitlength(S)] || zeros(n). num2str(x, n) The n-bit binary representation of the integer x. More formally, the n-bit string S where x = S[1] * 2^{n-1} + S[2] * 2^{n-2} + ... + S[n] * 2^{0}. Only used when 0 <= x < 2^n. const(n) The lexicographically first n-bit string C among all strings that have a minimal possible number of "1" bits and which name a polynomial x^n + C[1] * x^{n-1} + ... + C[n-1] * x^1 + C[n] * x^0 that is irreducible over the field with two elements. In particular, const(128) = num2str(135, 128). For other values of n, refer to a standard table of Krovetz, Rogaway Expires September 2005 [Page 4] INTERNET-DRAFT OCB March 2005 irreducible polynomials [Irred]. times2(S) S << 1 if S[1] = 0, and (S << 1) xor const(bitlength(S)) if S[1] = 1. times3(S) times2(S) xor S 3 OCB Parameters OCB requires the services of a blockcipher. The selection of a blockcipher defines the following constants and functions. BLOCKLEN The length of the plaintext block that the block- cipher operates on. KEYLEN The blockcipher's key length, in bits. ENCIPHER(K,P) The application of the blockcipher on P (a string of BLOCKLEN bits) using key K (a string of KEYLEN bits). DECIPHER(K,C) The application of the inverse of the blockcipher on C (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, ENCIPHER would refer to the AES function, and DECIPHER would refer to its inverse. 4 Header Authentication: PMAC OCB has the ability to authenticate unencrypted data (a "header") at the same time that it authenticates and encrypts a message. The following function is central to providing this functionality. Function name: PMAC Input: K, string of KEYLEN bits H, string of any length // Header to co-authenticate Output: Auth, string of BLOCKLEN bits // Header authenticator Compute Auth using the following algorithm. Krovetz, Rogaway Expires September 2005 [Page 5] INTERNET-DRAFT OCB March 2005 // // Break H into blocks // m = max(1, ceil(bitlength(H) / BLOCKLEN)) Let H_1, H_2, ..., H_m be strings such that H = H_1 || H_2 || ... || H_m and bitlength(H_i) = BLOCKLEN for all 0 < i < m. // // Initialize strings used for offsets and checksums // Offset = ENCIPHER(K, zeros(BLOCKLEN)) Offset = times3(Offset) Offset = times3(Offset) Checksum = zeros(BLOCKLEN) // // Accumulate the first m - 1 blocks // for i = 1 to m - 1 do // Skip if m < 2 Offset = times2(Offset) Checksum = Checksum xor ENCIPHER(K, H_i xor Offset) end for // // Accumulate the final block // Offset = times2(Offset) if bitlength(H_m) = BLOCKLEN then Offset = times3(Offset) Checksum = Checksum xor H_m else Offset = times3(Offset) Offset = times3(Offset) Tmp = H_m || 1 || zeros(BLOCKLEN - (bitlength(H_m) + 1)) Checksum = Checksum xor Tmp end if // // Compute result // Auth = ENCIPHER(K, Offset xor Checksum) 5 Encryption: OCB-ENCRYPT This function computes a ciphertext and authentication tag when given a message, header, nonce and key. Krovetz, Rogaway Expires September 2005 [Page 6] INTERNET-DRAFT OCB March 2005 Function name: OCB-ENCRYPT Input: K, string of KEYLEN bits // Key N, string of BLOCKLEN bits // Nonce H, string of any length // Header M, string of any length // Plaintext Output: C, string of length equal to M // Ciphertext core T, string of BLOCKLEN 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. // // Initialize strings used for offsets and checksums // Offset = ENCIPHER(K,N) Checksum = zeros(BLOCKLEN) // // Encrypt and accumulate first m - 1 blocks // for i = 1 to m - 1 do // Skip if m < 2 Offset = times2(Offset) Checksum = Checksum xor M_i C_i = Offset xor ENCIPHER(K, M_i xor Offset) end for // // Encrypt and accumulate final block // Offset = times2(Offset) b = bitlength(M_m) // Value in 0..BLOCKLEN Pad = ENCIPHER(K, num2str(b, BLOCKLEN) xor Offset) C_m = M_m xor Pad[1..b] // Encrypt M_m Tmp = M_m || Pad[b+1..BLOCKLEN] Checksum = Checksum xor Tmp // // Compute authentication tag // Krovetz, Rogaway Expires September 2005 [Page 7] INTERNET-DRAFT OCB March 2005 Offset = times3(Offset) T = ENCIPHER(K, Checksum xor Offset) if bitlength(H) > 0 then T = T xor PMAC(K, H) end if // // Assemble the ciphertext // C = C_1 || C_2 || ... || C_m 6 Decryption: OCB-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: OCB-DECRYPT Input: K, string of KEYLEN bits // Key N, string of BLOCKLEN bits // Nonce H, string of any length // Header C, string of any length // Ciphertext core T, string of no more than BLOCKLEN bits // Authentication tag Output: M, string // Plaintext V, boolean // Validity indicator Compute M and V using the following algorithm. // // 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 strings used for offsets and checksums // Offset = ENCIPHER(K,N) Checksum = zeros(BLOCKLEN) // // Decrypt and accumulate first m - 1 blocks Krovetz, Rogaway Expires September 2005 [Page 8] INTERNET-DRAFT OCB March 2005 // for i = 1 to m - 1 do // Skip if a < 2 Offset = times2(Offset) M_i = Offset xor DECIPHER(K, C_i xor Offset) Checksum = Checksum xor M_i end for // // Decrypt and accumulate final block // Offset = times2(Offset) b = bitlength(C_m) // Value in 0..BLOCKLEN Pad = ENCIPHER(K, num2str(b, BLOCKLEN) xor Offset) M_m = C_m xor Pad[1..b] Tmp = M_m || Pad[b+1..BLOCKLEN] Checksum = Checksum xor Tmp // // Compute valid authentication tag // Offset = times3(Offset) FullValidTag = ENCIPHER(K, Offset xor Checksum) if bitlength(H) > 0 then FullValidTag = FullValidTag xor PMAC(K, H) end if // // Compute results // if T = FullValidTag[1..bitlength(T)] then V = true M = M_1 || M_2 || ... || M_m else V = false M = end if 7 Security Considerations OCB achieves two security properties, message privacy and message authenticity. Privacy is "indistinguishability from random bits", meaning that an adversary is unable to distinguish OCB-outputs from an equal number of random bits. Authenticity is "authenticity of ciphertexts", meaning that an adversary is unable to produce any valid (N,C,T) triple that it has not already acquired. The privacy and the authenticity guarantee depend on the underlying blockcipher being secure in the sense of a strong pseudorandom permutation. Thus Krovetz, Rogaway Expires September 2005 [Page 9] INTERNET-DRAFT OCB March 2005 if OCB is used with a blockcipher that is not secure as a strong pseudorandom permutation, the security guarantees vanish. The need for the strong pseudorandom permutation property means that OCB should be used with a conservatively designed, well-trusted blockcipher, such as AES. Both the privacy and the authenticity properties of OCB degrade as per s^2 / 2^BLOCKLEN, where s is the total number of blocks that the adversary acquires. The consequence of this formula is that the proven security vanishes when s becomes as large as 2^{BLOCKLEN/2}. Thus the user should never use a key to generate an amount of ciphertext that is near to, or exceeds, 2^{BLOCKLEN/2} blocks. Blockciphers 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 OCB should be used with a blockcipher having a blocklength of 128 bits. The mode may then be used to encrypt at most 2^48 blocks (2^56 bits), to ensure that s^2 / 2^128 will be at most 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 OCB. The nonce need not be secret, and a counter may be used for it. If two parties send OCB-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. 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. OCB encryption produces a tag T of BLOCKLEN bits. The user may choose to use a prefix of T. The length taglen of the prefix 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 determined at session setup and should be dictated by the message recipient. The taglen value is not authenticated by the OCB algorithm and one must ensure that an attacker can not convince a recipient to employ unreasonably short authentication tags. Timing attacks are not a part of the formal model and an implementation should take care to ensure that these are not damaging. To render timing attacks impotent, the amount of time to encrypt or decrypt a string should be independent of the key and the Krovetz, Rogaway Expires September 2005 [Page 10] INTERNET-DRAFT OCB March 2005 contents of the string. Implementations of times2(S) that employ a conditional for inspecting bit S[1] are particularly suspect and should be avoided. Power-usage attacks are likewise out of scope of the formal model, and should be considered for environments where they are threatening. The OCB 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 OCB encryption (typically involving padding) would be necessary. 8 Acknowledgments The design of the original OCB scheme [OCB1] was done while Phil Rogaway was at Chiang Mai University, Thailand. Follow-up work [Offsets] was done with support from NSF 0208842 and a gift from Cisco. Current funding for Rogaway is from the same NSF award and a gift from Intel. Appendix - Test Vectors The following test vectors have been developed for use in validating implementations of OCB. All strings are represented in hexadecimal (ie, 0F represents the bitstring 00001111). The blockcipher used in all cases is AES with a 128-bit keylength. The key (K) and nonce (N) for all vectors are K : 000102030405060708090A0B0C0D0E0F N : 000102030405060708090A0B0C0D0E0F The following is a collection of header (H) and message (M) pairs, and the ciphertext (C) and authentication tag (T) pairs generated for each defined . A blank entry indicates the empty string. H : M : C : T : BF3108130773AD5EC70EC69E7875A7B0 H : M : 0001020304050607 C : C636B3A868F429BB T : A45F5FDEA5C088D1D7C8BE37CABC8C5C H : Krovetz, Rogaway Expires September 2005 [Page 11] INTERNET-DRAFT OCB March 2005 M : 000102030405060708090A0B0C0D0E0F C : 52E48F5D19FE2D9869F0C4A4B3D2BE57 T : F7EE49AE7AA5B5E6645DB6B3966136F9 H : M : 000102030405060708090A0B0C0D0E0F1011121314151617 C : F75D6BC8B4DC8D66B836A2B08B32A636CC579E145D323BEB T : A1A50F822819D6E0A216784AC24AC84C H : M : 000102030405060708090A0B0C0D0E0F1011121314151617 18191A1B1C1D1E1F C : F75D6BC8B4DC8D66B836A2B08B32A636CEC3C55503757170 9DA25E1BB0421A27 T : 09CA6C73F0B5C6C5FD587122D75F2AA3 H : M : 000102030405060708090A0B0C0D0E0F1011121314151617 18191A1B1C1D1E1F2021222324252627 C : F75D6BC8B4DC8D66B836A2B08B32A6369F1CD3C5228D79FD 6C267F5F6AA7B231C7DFB9D59951AE9C T : 9DB0CDF880F73E3E10D4EB3217766688 H : 0001020304050607 M : 0001020304050607 C : C636B3A868F429BB T : 8D059589EC3B6AC00CA31624BC3AF2C6 H : 000102030405060708090A0B0C0D0E0F M : 000102030405060708090A0B0C0D0E0F C : 52E48F5D19FE2D9869F0C4A4B3D2BE57 T : 4DA4391BCAC39D278C7A3F1FD39041E6 H : 000102030405060708090A0B0C0D0E0F1011121314151617 M : 000102030405060708090A0B0C0D0E0F1011121314151617 C : F75D6BC8B4DC8D66B836A2B08B32A636CC579E145D323BEB T : 24B9AC3B9574D2202678E439D150F633 H : 000102030405060708090A0B0C0D0E0F1011121314151617 18191A1B1C1D1E1F M : 000102030405060708090A0B0C0D0E0F1011121314151617 18191A1B1C1D1E1F C : F75D6BC8B4DC8D66B836A2B08B32A636CEC3C55503757170 9DA25E1BB0421A27 T : 41A977C91D66F62C1E1FC30BC93823CA H : 000102030405060708090A0B0C0D0E0F1011121314151617 18191A1B1C1D1E1F2021222324252627 Krovetz, Rogaway Expires September 2005 [Page 12] INTERNET-DRAFT OCB March 2005 M : 000102030405060708090A0B0C0D0E0F1011121314151617 18191A1B1C1D1E1F2021222324252627 C : F75D6BC8B4DC8D66B836A2B08B32A6369F1CD3C5228D79FD 6C267F5F6AA7B231C7DFB9D59951AE9C T : 65A92715A028ACD4AE6AFF4BFAA0D396 References Normative References [AES] FIPS-197, "Advanced Encryption Standard (AES)", National Institute of Standards and Technology, 2001. [GPL] Free Software Foundation, "GNU General Public License", Version 2, http://www.gnu.org/copyleft/gpl.html, 1991. [Irred] G. Seroussi, "Table of low-weight binary irreducible polynomials", HP Labs Technical Report HPL-98-135, 1998. Informative References [Jutla] C. Jutla, "Encryption modes with almost free message integrity", Advances in Cryptology - EUROCRYPT 2001, Lecture Notes in Computer Science, vol. 2045, Springer, pp. 529-544, 2001. [OCB1] P. Rogaway, M. Bellare, and J. Black, "OCB: A block-cipher mode of operation for efficient authenticated encryption", ACM Transactions on Information and System Security, vol. 6, no. 3, pp. 365-403, 2003. [Offsets] P. Rogaway, "Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC", Advances in Cryptology - ASIACRYPT 2004. Lecture notes in Computer Science, vol. 3329, Springer, pp. 16-31, 2004. Author Contact Information Authors' Addresses Ted Krovetz Department of Computer Science California State University Sacramento CA 95819 USA Krovetz, Rogaway Expires September 2005 [Page 13] INTERNET-DRAFT OCB March 2005 EMail: tdk@acm.org Phillip Rogaway Department of Computer Science University of California Davis CA 95616 USA and Department of Computer Science Faculty of Science Chiang Mai University Chiang Mai 50200 THAILAND EMail: rogaway@cs.ucdavis.edu WWW: www.cs.ucdavis.edu/~rogaway 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. Krovetz, Rogaway Expires September 2005 [Page 14]