OCB: A block-cipher mode of operation for efficient authenticated encryption

ABSTRACT

We describe a parallelizable block-cipher mode of operation that simultaneously provides privacy and authenticity. OCB encrypts-and-authenticates a nonempty string M ∈ {0, 1}* using ⌈&vertbar;M&vertbar;/n⌉ + 2 block-cipher invocations, where n is the block length of the underlying block cipher. Additional overhead is small. OCB refines a scheme, IAPM, suggested by Charanjit Jutla. Desirable properties of OCB include the ability to encrypt a bit string of arbitrary length into a ciphertext of minimal length, cheap offset calculations, cheap key setup, a single underlying cryptographic key, no extended-precision addition, a nearly optimal number of block-cipher calls, and no requirement for a random IV. We prove OCB secure, quantifying the adversary's ability to violate the mode's privacy or authenticity in terms of the quality of its block cipher as a pseudorandom permutation (PRP) or as a strong PRP, respectively.

REFERENCES

• 1: Jee Hea An , Mihir Bellare, Does Encryption with Redundancy Provide Authenticity?, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.512-528, May 06-10, 2001
• 2: Aoki, K. and Lipmaa, H. 2000. Fast implementations of AES candidates. In The 3rd Advanced Encryption Standard Candidate Conference. National Institute of Standards and Technology, New York, NY, USA, 106--120. See www.tml.hut.fi/∼helger.
• 3: Mihir Bellare , Anand Desai , Eron Jokipii , Phillip Rogaway, A Concrete Security Treatment of Symmetric Encryption, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.394, October 19-22, 1997
• 4: Mihir Bellare , Anand Desai , David Pointcheval , Phillip Rogaway, Relations Among Notions of Security for Public-Key Encryption Schemes, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.26-45, August 23-27, 1998
• 5: Mihir Bellare , Roch Guérin , Phillip Rogaway, XOR MACs: New Methods for Message Authentication Using Finite Pseudorandom Functions, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.15-28, August 27-31, 1995
• 6: Mihir Bellare , Joe Kilian , Phillip Rogaway, The security of the cipher block chaining message authentication code, Journal of Computer and System Sciences, v.61 n.3, p.362-399, Dec. 2000 [doi>10.1006/jcss.1999.1694]
• 7: Mihir Bellare , Chanathip Namprempre, Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.531-545, December 03-07, 2000
• 8: Mihir Bellare , Phillip Rogaway, Encode-Then-Encipher Encryption: How to Exploit Nonces or Redundancy in Plaintexts for Efficient Cryptography, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.317-330, December 03-07, 2000
• 9: John Black , Hector Urtubia, Side-Channel Attacks on Symmetric Encryption Schemes: The Case for Authenticated Encryption, Proceedings of the 11th USENIX Security Symposium, p.327-338, August 05-09, 2002
• 10: Daniel Bleichenbacher, Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.1-12, August 23-27, 1998
• 11: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 12: Virgil D. Gligor , Pompiliu Donescu, Integrity-Aware PCBC Encryption Schemes, Proceedings of the 7th International Workshop on Security Protocols, p.153-171, April 19-21, 1999
• 13: Gligor, V. and Donescu, P. 2000a. Fast encryption and authentication: XCBC encryption and XECB authentication modes. Manuscript, Aug. 18. See www.eng.umd.edu/∼gligor.
• 14: Gligor, V. and Donescu, P. 2000b. Fast encryption and authentication: XCBC encryption and XECB authentication modes. Contribution to NIST, Oct 27, 2000. See csrc.nist.gov/encryption/aes/modes.
• 15: Gligor, V. and Donescu, P. 2000c. Fast encryption and authentication: XCBC encryption and XECB authentication modes. Contribution to NIST, Mar 30, 2001, rev. Apr 20, 2001. See csrc.nist.gov/encryption/aes/proposedmodes.
• 16: Virgil D. Gligor , Pompiliu Donescu, Fast Encryption and Authentication: XCBC Encryption and XECB Authentication Modes, Revised Papers from the 8th International Workshop on Fast Software Encryption, p.92-108, April 02-04, 2001
• 17: Goldwasser, S. and Micali, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, 270--299.
• 18: Halevi, S. 2001. An observation regarding Jutla's modes of operation. Cryptology ePrint archive, reference number 2001/015, submitted Feb. 22, 2001, revised Apr. 2, 2001. See eprint.iacr.org.
• 19: Jutla, C. 2000a. Encryption modes with almost free message integrity. Cryptology ePrint archive, reference number 2000/039, Aug. 1, 2000. See eprint.iacr.org.
• 20: Jutla, C. 2000b. Encryption modes with almost free message integrity. Contribution to NIST. Undated manuscript, appearing Oct. 2000 at csrc.nist.gov/encryption/modes/workshop1.
• 21: Charanjit S. Jutla, Encryption Modes with Almost Free Message Integrity, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.529-544, May 06-10, 2001
• 22: Jutla, C. 2001b. Encryption modes with almost free message integrity. Contribution to NIST. Undated manuscript, posted May 24, 2001 at NIST web site csrc.nist.gov/encryption/modes/proposedmodes.
• 23: Jonathan Katz , Moti Yung, Complete characterization of security notions for probabilistic private-key encryption, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.245-254, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335335]
• 24: Jonathan Katz , Moti Yung, Unforgeable Encryption and Chosen Ciphertext Secure Modes of Operation, Proceedings of the 7th International Workshop on Fast Software Encryption, p.284-299, April 10-12, 2000
• 25: Hugo Krawczyk, The Order of Encryption and Authentication for Protecting Communications (or: How Secure Is SSL?), Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.310-331, August 19-23, 2001
• 26: Lipmaa, H. 2001. Personal communications. July 2001. Further information available at www.tml.hut.fi/∼helger.
• 27: Michael Luby , Charles Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, v.17 n.2, p.373-386, April 1988 [doi>10.1137/0217022]
• 28: James Manger, A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.230-238, August 19-23, 2001
• 29: Meyer, C. H. and Matyas, S. M. 1982. Cryptography: A New Dimension in Computer Data Security. John Wiley and Sons, New York.
• 30: Bart Preneel, Cryptographic Primitives for Information Authentication - State of the Art, State of the Art in Applied Cryptography, Course on Computer Security and Industrial Cryptography - Revised Lectures, p.49-104, June 03-06, 1997
• 31: Rogaway, P. 2000. OCB mode: Parallelizable authenticated encryption. Contribution to NIST, Oct. 16, 2000 (Preliminary version of the OCB algorithm). See csrc.nist.gov/encryption/ modes/workshop1.
• 32: Phillip Rogaway, Authenticated-encryption with associated-data, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586125]
• 33: Rogaway, P., Bellare, M., Black, J., and Krovetz, T. 2001a. OCB mode. Contribution to NIST, Apr. 1, 2001, revised Apr. 18, 2001. See csrc.nist.gov/encryption/modes/proposedmodes.
• 34: Phillip Rogaway , Mihir Bellare , John Black , Ted Krovetz, OCB: a block-cipher mode of operation for efficient authenticated encryption, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502011]
• 35: RSA Laboratories. 1998. PKCS #1: RSA encryption standard, Version 1.5, PKCS #1: RSA cryptography specifications, Version 2.0, Sep. 1998, B. Kaliski and J. Staddon. See www.rsasecurity. com/rsalabs/pkcs/pkcs-1.
• 36: Schroeppel, R. 2001. Personal communications.
• 37: Steiner, J., Neuman, C., and Schiller, J. 1988. Kerberos: an authentication service for open network systems. In Proceedings of the Winter 1988 Usenix Conference. USENIX Association, 191--201.
• 38: US National Institute of Standards. 2001. Specification for the Advanced Encryption Standard (AES). Federal Information Processing Standards Publication 197. Based on J. Daemen and V. Rijmen, AES Proposal: Rijndael. Sep. 3, 1999. See www.nist.gov/aes.
• 39: Serge Vaudenay, Security Flaws Induced by CBC Padding - Applications to SSL, IPSEC, WTLS ..., Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.534-546, May 02, 2002

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Performance, Security, Theory

Keywords:
AES, authenticity, block-cipher usage, cryptography, encryption, integrity, modes of operation, provable security, standards