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 &egr; {0,1}• using \lceil |M|/n\rceil + 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 session 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: K.Aoki and H.Lipmaa.Fast implementations f AES candidates.Third AES Candidate Conference, New York City,USA,Apr 2000,pp.106 -120. www.tml.hut../ ~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: 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
• 10: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 11: 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
• 12: V.Gligor and P.Donescu.Fast encryption and authentication:XCBC encryption and XECB authentication modes.Manuscript,Aug 18,2000. Frmerly available from www.eng.umd.edu/ ~gligor.
• 13: V.Gligor and P.Donescu.Fast encryption and authentication:XCBC encryption and XECB authentication modes.Contribution t NIST,Oct 27, 2000.csrc.nist.gov/encryption/aes/modes
• 14: V.Gligor and P.Donescu.Fast encryption and authentication:XCBC encryption and XECB authentication modes.Contribution t NIST.Mar 30, 2001,rev.Apr 20,2001. csrc.nist.gov/encryption/modes/prop sedmodes
• 15: 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
• 16: S.Goldwasser and S.Micali.Probabilistic encryption.Journal of Computer and System Sciences vol.28,Apr 1984,pp.270 -299.
• 17: S.Halevi.An observation regarding Jutla 's m des of operation.Cryptology ePrint archive,reference number 2001/015,submitted Feb 22,2001,revised Apr 2,2001.eprint.iacr.org
• 18: C.Jutla.Encryption modes with almost free message integrity.Cryptology ePrint archive,rep rt 2000/039, Aug 1,2000.eprint.iacr.org
• 19: C.Jutla.Encryption modes with almost free message integrity.Contribution t NIST.Undated manuscript, appearing Oct 2000 at csrc.nist.gov/encryption/modes/workshop1
• 20: C.Jutla.Encryption modes with almost free message integrity.Contribution t NIST.P sted May 24,2001 at csrc.nist.gov/encryption/modes/proposedmodes
• 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: 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
• 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: 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
• 25: H.Lipmaa.Personal communications,Jul 2001. Further information at www.tcs.hut../ ~helger
• 26: 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]
• 27: M.Matyas and S.Matyas.Cryptography: A new dimension in computer data security. John Wiley & Sons,New Y rk,1982.
• 28: RSA Laboratories.PKCS #1:RSA encryption standard,Version 1.5,Nov 1993;and PKCS #1:RSA cryptography speci .cations,Version 2.0,Sep 1998, B.Kaliski and J.Staddon. www.rsasecurity.com/rsalabs/pkcs/pkcs-1
• 29: J.Steiner,C.Neuman,and J.Schiller.Kerberos:an authentication service for open network systems. Proceedings of the Winter 1988 Usenix Conference pp.191 -201,1988.
• 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: P.Rogaway.OCB m de:Parallelizable authenticated encryption.Contribution t NIST,Oct 16,2000. (Preliminary version of the OCB algorithm.) csrc.nist.gov/encryption/modes/workshop1
• 32: P.Rogaway (submitter)and M.Bellare,J.Black, and T.Krovetz (auxiliary submitters).OCB m de. Contribution t NIST.Cryptology ePrint archive, rep rt 2001/26,Apr 1,2001,revised Apr 18,2001. ePrint.iacr.org and csrc.nist.gov/encryption/modes/proposedmodes.
• 33: 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]
• 34: US National Institute f Standards.Specification for the Advanced Encryption Standard (AES).Draft Federal Information Processing Standards,Feb 28, 2001.Based n:J.Daemen and V.Rijmen,AES Proposal:Rijndael.Sep 3,1999.www.nist.gov/aes

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Performance, Security

Keywords:
AES, authenticity, block ciphers, cryptography, encryption, integrity, modes of operation, provable security, standards