Authenticated-encryption with associated-data

ABSTRACT

When a message is transformed into a ciphertext in a way designed to protect both its privacy and authenticity, there may be additional information, such as a packet header, that travels alongside the ciphertext (at least conceptually) and must get authenticated with it. We formalize and investigate this authenticated-encryption with associated-data (AEAD) problem. Though the problem has long been addressed in cryptographic practice, it was never provided a definition or even a name. We do this, and go on to look at efficient solutions for AEAD, both in general and for the authenticated-encryption scheme OCB. For the general setting we study two simple ways to turn an authenticated-encryption scheme that does not support associated-data into one that does: nonce stealing and ciphertext translation. For the case of OCB we construct an AEAD-scheme by combining OCB and the pseudorandom function PMAC, using the same key for both algorithms. We prove that, despite "interaction" between the two schemes when using a common key, the combination is sound. We also consider achieving AEAD by the generic composition of a nonce-based, privacy-only encryption scheme and a pseudorandom function.

REFERENCES

• 1: 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
• 2: 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]
• 3: 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
• 4: 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
• 5: John Black , Phillip Rogaway, A Block-Cipher Mode of Operation for Parallelizable Message Authentication, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.384-397, May 02, 2002
• 6: N. Cam-Winget and J. Walker. Personal communications, June 2001.
• 7: L. Carter and M. Wegman. Universal hash functions. J. of Computer and System Sciences, vol. 18, pp. 143--154, 1979.
• 8: Jean-Sébastien Coron , Marc Joye , David Naccache , Pascal Paillier, Universal Padding Schemes for RSA, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.226-241, August 18-22, 2002
• 9: 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
• 10: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 11: S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, vol. 28, April 1984, pp. 270--299.
• 12: Stuart Haber , Benny Pinkas, Securely combining public-key cryptosystems, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502013]
• 13: P. Hawkes and G. Rose. A mode of operation with partial encryption and message integrity (PEMI). Manuscript, 2002.
• 14: Jakob Jonsson, On the Security of CTR + CBC-MAC, Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography, p.76-93, August 15-16, 2002
• 15: 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
• 16: B. Kaliski. Personal communication, May 2001.
• 17: 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
• 18: J. Kilian and P. Rogaway. How to protect DES against exhaustive key search (an analysis of DESX). J. of Cryptology, vol. 14, no. 1, pp. 17--35, 2001. Earlier version in CRYPTO '96.
• 19: Hugo Krawczyk, LFSR-based Hashing and Authentication, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.129-139, August 21-25, 1994
• 20: R. Rivest. Personal communications, Aug 2001.
• 21: P. Rogaway. Authenticated-encryption with associated-data. Full version of this paper. Available from www.cs.ucdavis.edu/rogaway
• 22: 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]
• 23: D. Whiting, R. Housley, and N. Ferguson. Counter with CBC-MAC (CCM). Submission to NIST, June 2002. csrc.nist.gov/encryption/modes

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Algorithms, Security, Standardization, Theory

Keywords:
OCB, associated-data problem, authenticated-encryption, block-cipher usage, key separation, modes of operation