Internet Draft R. Moskowitz, TruSecure September 2001 J. Walker, Intel Expiration Date: April 2002 The AES128 OCB Mode of Operation and Its Use With IPsec draft-moskowitz-aes128-ocb-00.txt 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/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Table of Contents 1. Abstract...........................................................1 2. Conventions used in this document..................................2 3. Introduction.......................................................2 3.1. Licensing........................................................2 4. Understanding OCB..................................................3 4.1. OCB's properties.................................................3 4.2. OCB mode Description.............................................4 5. OCB rules in ESP...................................................5 5.1. Padding..........................................................5 5.2. The Nonce........................................................6 5.3. The Authentication Tag...........................................6 5.4. Keying Material for AES128-OCB...................................6 6. Security Considerations............................................6 7. IANA Considerations................................................7 8. ICANN Considerations...............................................7 9. References.........................................................7 10. Acknowledgments...................................................8 APPENDIX A. Test Vectors for AES128...................................8 11. Author's Address..................................................9 12. Copyright Statement...............................................9 1. Abstract Moskowitz, Walker 1 INTERNET DRAFT September 2001 This document describes the use of the AES Cipher Algorithm with 128 bit key in Offset CodeBook (OCB) Mode, with an implicit IV, as a confidentiality mechanism within the context of the IPsec Encapsulating Security Payload [ESP]. OCB is a parallelizable block-cipher mode of operation that simultaneously provides privacy and authenticity. 2. Conventions used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC-2119]. 3. Introduction OCB is a block-cipher mode of operation. It simultaneously provides both privacy and authenticity. A scheme, which accomplishes both of these goals, is called an authenticated-encryption scheme. OCB was designed largely in response to NIST's modes-of-operation activities. It is follow-on work to Charanjit Jutla's IAPM [IAPM]. In the past, when one wanted both privacy and authenticity, the usual thing to do was to separately encrypt and compute a MAC. The encryption provides privacy and the MAC provides authenticity. One needs to be careful to properly combine an encryption scheme and a MAC [AE]. Still, the approach, done right, is clean and correct. But the cost to get privacy+authenticity in this way is about the cost to encrypt plus the cost to MAC. If one is encrypting and MACing in a conventional way, like CBC encryption + the CBC MAC, the cost for privacy+authenticity is about twice the cost for privacy alone. Thus people have often hoped for a simple and cheap way to get message authenticity as an incidental adjunct to message privacy. Usually they have failed. What makes OCB interesting is that it provably achieves both privacy and authenticity, and it accomplishes this in way that is almost as cheap as getting privacy alone. OCB is patented by its creator, Phillip Rogaway and there is a licensing fee. However, the properties of OCB make it very attractive in many applications of ESP. This document describes the ESP use of the AES 128 bit key Cipher Algorithm in Offset CodeBook (OCB) Mode, with an implicit IV, drawn from the ESP Sequence Number and SPI. 3.1. Licensing Phillip Rogaway is the owner of pending US patent application number is 09/918,615 (filed 7/30/2001), which is the basis for the subject Moskowitz, Walker 2 INTERNET DRAFT September 2001 matter of this Internet Draft. He will license this IP under fair, reasonable, and non-discriminatory terms. All companies will be offered the same license agreement. [IP] 4. Understanding OCB Authenticated-encryption schemes are new to IPsec; thus it is valuable to understand OCB as an authenticated-encryption scheme. 4.1. OCB's properties OCB has been designed to simultaneously have the following properties: 1. OCB is an authenticated-encryption scheme: encrypted messages are both private and authenticated. 2. Very strong forms of privacy are achieved: what cryptographers call "indistinguishability under chosen-ciphertext attack" and "non-malleability under chosen-ciphertext attacks". These strong properties make OCB easier to correctly use in protocols than standard privacy modes. 3. OCB is fully parallelizable. Thus it will have ever-faster implementations as machines offer up more and more parallelism, and it is good for encrypting messages in hardware at the highest network speeds. 4. OCB works with any block cipher. 5. OCB makes a nearly optimal number of block-cipher calls: \lceil |M|/n \rceil + 2. 6. OCB avoids the need for a random IV (a nonce is enough). 7. OCB uses only a single block-cipher key. 8. Key setup in OCB is very cheap (typically one block-cipher call, plus a few shifts and conditional xors). 9. OCB doesn't need much memory to run (and a memory-stingy implementation doesn't give up much speed). 10. OCB generates a sequence of offsets, which it does in a very cheap way. Each offset is computed from the previous one either by xoring the previous offset by a value looked up in a small table (e.g., a few 128-bit words) or by doing a few shifts and xors. 11. OCB can encrypt messages of any bit length. Messages don't have to be a multiple of the block length, and no separate padding regime is needed. 12. Messages of all lengths are treated in a single, uniform manner. 13. The length of an OCB ciphertext is the same as the length of the plaintext (discounting the nonce and the "tag"). In particular, no bits are wasted due to padding. 14. OCB is nearly endian-neutral: the scheme can be implemented just as fast on a big-endian machine or a little-endian machine. 15. OCB avoids 128-bit addition (which is endian-biased and can be expensive in software or dedicated hardware). It uses xors instead. Moskowitz, Walker 3 INTERNET DRAFT September 2001 16. OCB is simple to understand and implement. It uses GF(2^128) arithmetic and a Gray code, but it all comes down to some xors and shifts. One doesn't have to understand the mathematics to implement the scheme. 17. OCB is provably secure. It provably meets its goals, as long as the underlying block cipher meets standard cryptographic assumptions. 4.2. OCB mode Description First a little notation. Where L is a 128-bit string, write L<<1 for the left shift of L by 1 bit (where the first bit vanishes and a 0 comes into the last bit). Write L>>1 for the right shift of L by 1 bit (where the last bit vanishes and a 0 comes into the first bit). For a nonzero number i, let ntz(i) be the number of trailing 0-bits in the binary representation of i (so, for example, ntz(20)=2, because 20 is 10100 in binary, which ends in two zeros). Let 0 be a block of zeros(128). Let len(i) be the integer i written in binary as a 128-bit string. When A is a string of at most 128 bits, let A0* be A followed by the minimum number of 0-bits (possibly none) to get you to 128 total bits. Let M be the message to encrypt-with-authenticity, and let K be the OCB encryption key, which is just an AES key. AES(K,X) denotes the ciphertext for X under AES key K. Let Nonce be the 128-bit nonce to use. Let L be AES(K, 0). Define L(0) be L and, for i>0, let L(i) be L<<1 if the first bit of L(i-1) is 0, and let L(i) be (L(i-1)<<1) xor 0x00000000000000000000000000000087 otherwise. Let L(-1) be L>>1 if the last bit of L is 0, and let L(-1) be L>>1 xor 0x80000000000000000000000000000043 otherwise. Break the message M into blocks M[1]M[2]...M[m] where each block except the last one has 128 bits. The last one may have fewer than 128 bits (but it has 0 bits only if the message M is empty). Now encrypt as follows, the parameter taglen is fixed to 64 bits for this implementation of OCB. function ocb-aes-encrypt(K, Nonce, M) begin Partition M into M[1] ... M[m] Offset = AES(K, Nonce xor L) Checksum = ZERO for i = 1 to m-1 do begin Offset = Offset xor L(ntz(i)) Checksum = Checksum xor M[i] C[i] = Offset xor AES(K, M[i] xor Offset) end Offset = Offset xor L(ntz(m)) Pad = AES (K, len(M[m]) xor L(-1) xor Offset) C[m] = M[m] xor (the first |M[m]| bits of Pad) Checksum = Checksum xor Pad xor C[m]0* FullTag = AES(K, Checksum xor Offset) Tag = the taglen-bit prefix of FullTag return C[1]... C[m-1] C[m] Tag Moskowitz, Walker 4 INTERNET DRAFT September 2001 end The phrase "Partition M into M[1]...M[m]" means: Let m = max{1, \lceil |M|/128 \rceil} Let M[1], ..., M[m] be the (unique) strings such that M[1] ... M[m] = M and |M[i]|=128 for all i September 2001 padding, Pad Length, and the Next Header MUST be concatenated with the cleartext before encrypting, as per ESP rules. That is encrypt: Cleartext || padding || Pad Length || Next Header 5.2. The Nonce The 128 bit Nonce is constructed by concatenating the SPI with the Sequence Number along with 64 zeros: Nonce ::= (SPI || Seq# || 0x0000000000000000) where the sequence number Seq# is encoded as a big-Endian value. Thus the Nonce is implicit. It does not present any overhead in the ESP Payload Data. Additionally, since the SPI and Sequence Number are part of the Nonce, they have been silently authenticated for free. This method of authenticating data associated with OCB- encrypted data is discussed in [ADP]. 5.3. The Authentication Tag The Authentication Tag MUST be 64 bits long. "OCB Mode" [OCB] states that an adversary will be able to forge a valid ciphertext with probability 2^(-taglen). Thus 64 is appropriate for ESP usage. 5.4. Keying Material for AES128-OCB Provide 128 bits as the encrypting and authenticating key size to the keying material extraction process. Discard the authentication keying material, using only the encrypting keying material. 6. Security Considerations OCB is a new mode of operation. Its strength is based on the strength of the underlying cipher. That is, the claim [OCB] is made, with proofs, that if OCB is broken, the underlying cipher is broken. By using AES128 as the underlying cipher, there is a high level of assurance that the underlying cipher will not be broken anytime soon and thus OCB is not breakable. OCB Mode assumes that a nonce is used only once with each key. In order to meet its security guarantees, implementations using OCB mode must take precautions to meet this constraint. This effectively rules out using the Nonce derivation method described here for manually keyed ESP sessions. Moskowitz, Walker 6 INTERNET DRAFT September 2001 As noted above, the nonce construction protects the ESP SPI and sequence number of undetected alteration. Since AES128-OCB provides indistinguishability under chosen ciphertext attack, its security guarantees are stronger than those for the traditional ESP compositional construction, which provides only indistinguishability under chosen plaintext attack. The security of both the OCB privacy and authenticity guarantees decay as O(s^2/2^128), where s is the total number of 16-byte blocks encrypted under a single key. Since the maximum message size a typical medium can support is 1500 bytes, the total number of blocks that can be sent before the ESP sequence space is exhausted is about 2^7*2^32 = 2^39 blocks. This means that transmitting 2^32 maximally sized OCB protected ESP packets will increase an adversaryÆs chances of breaking the OCB key by about 1 in 2^50 over seeing a single block encrypted under the key. 7. IANA Considerations IANA has assigned ESP transform number XX to AES128-OCB. 8. ICANN Considerations There are no ICANN considerations here. 9. References [RFC-2119], Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, March 1997. [ESP], Kent, S., and Atkinson, R., "IP Encapsulating Security Payload", RFC 2406, November 1998. [AE], Bellare, M., and Namprempre, C., "Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm", http://www-cse.ucsd.edu/users/mihir/papers/oem.html, September 2000. [ADP], Rogaway, P., unpublished manuscript, September 2001. [IAPM], Jutla, C. S., "Encryption Modes with Almost Free Message Integrity", Advances in Cryptology - EUROCRYPT 2001. Lecture Notes in Computer Science, vol. 2045, B. Pfitzmann, ed., Springer-Verlag, 2001. [IP], Rogaway, P., "OCB: Licensing", http://www.cs.ucdavis.edu/~rogaway Moskowitz, Walker 7 INTERNET DRAFT September 2001 [OCB], Rogaway, P., Bellare, M., Black, J., and Krovetz, T., "OCB: A Block-Cipher Mode of Operation for Efficient Authenticated Encryption". Eighth ACM Conference on Computer and Communications Security (CCS-8), ACM Press, 2001. http://www.cs.ucdavis.edu/~rogaway 10. Acknowledgments The text for this specification draws heavily from papers on OCB by Phillip Rogaway. In fact I did extensive cutting and pasting with some editing. If there are errors in the presentation or readability, the errors are mine and not PhilÆs. The impetus to develop this draft came out of discussions at IEEE 802.11i meetings where the properties of OCB in ESP were compared with other AES modes of operations. APPENDIX A. Test Vectors for AES128 Test case OCB-AES-128-0B Key 000102030405060708090a0b0c0d0e0f Nonce 00000000000000000000000000000001 Plaintext Ciphertext Tag 15d37dd7c890d5d6acab927bc0dc60ee Test case OCB-AES-128-3B Key 000102030405060708090a0b0c0d0e0f Nonce 00000000000000000000000000000001 Plaintext 000102 Ciphertext fcd37d Tag 02254739a5e3565ae2dcd62c659746ba Test case OCB-AES-128-16B Key 000102030405060708090a0b0c0d0e0f Nonce 00000000000000000000000000000001 Plaintext 000102030405060708090a0b0c0d0e0f Ciphertext 37df8ce15b489bf31d0fc44da1faf6d6 Tag dfb763ebdb5f0e719c7b4161808004df Test case OCB-AES-128-20B Key 000102030405060708090a0b0c0d0e0f Nonce 00000000000000000000000000000001 Plaintext 000102030405060708090a0b0c0d0e0f10111213 Ciphertext 01a075f0d815b1a4e9c881a1bcffc3eb7003eb55 Tag 753084144eb63b770b063c2e23cda0bb Test case OCB-AES-128-32B Key 000102030405060708090a0b0c0d0e0f Nonce 00000000000000000000000000000001 Plaintext 000102030405060708090a0b0c0d0e0f Moskowitz, Walker 8 INTERNET DRAFT September 2001 101112131415161718191a1b1c1d1e1f Ciphertext 01a075f0d815b1a4e9c881a1bcffc3eb 4afcbb7fedc08ca8654c6d304d1612fa Tag c14cbf2c1a1f1c3c137eadea1f2f2fcf Test case OCB-AES-128-34B Key 000102030405060708090a0b0c0d0e0f Nonce 00000000000000000000000000000001 Plaintext 000102030405060708090a0b0c0d0e0f 101112131415161718191a1b1c1d1e1f2021 Ciphertext 01a075f0d815b1a4e9c881a1bcffc3eb d4903dd0025ba4aa837c74f121b0260fa95d Tag cf8341bb10820ccf14bdec56b8d7d6ab Test case OCB-AES-128-1000B Key 000102030405060708090a0b0c0d0e0f Nonce 00000000000000000000000000000001 Plaintext 00000000000000000000 ... 00000000000000000000 [1000 bytes] Ciphertext 4c9b676705ff2df05503 ... 2f8d1496a60048e2b971 [1000 bytes] Tag ab335f725475e33e90ab8c1e4891596d 11. Author's Address Robert Moskowitz TruSecure Corporation 1200 Walnut Bottom Rd. Carlisle, PA 17013 Email: rgm@trusecure.com Jesse Walker Intel Corporation 2111 N.E. 25th Avenue Hillsboro, Oregon 97229 Email: jesse.walker@intel.com 12. Copyright Statement Copyright (c) The Internet Society (2001). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be Moskowitz, Walker 9 INTERNET DRAFT September 2001 followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS 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. Moskowitz, Walker 10