Abstract
We examine a natural, but non-tight, reductionist security proof for deterministic message authentication code (MAC) schemes in the multi-user setting. If security parameters for the MAC scheme are selected without accounting for the non-tightness in the reduction, then the MAC scheme is shown to provide a level of security that is less than desirable in the multi-user setting. We find similar deficiencies in the security assurances provided by non-tight proofs when we analyze some protocols in the literature including ones for network authentication and aggregate MACs. Our observations call into question the practical value of non-tight reductionist security proofs. We also exhibit attacks on authenticated encryption schemes, disk encryption schemes, and stream ciphers in the multi-user setting.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alexi, W., Chor, B., Goldreich, O., Schnorr, C.P.: RSA and Rabin functions: Certain parts are as hard as the whole. SIAM J. Computing 17, 194–209 (1988)
Bellare, M., Boldyreva, A., Micali, S.: Public-Key Encryption in a Multi-User Setting: Security Proofs and Improvements. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 259–274. Springer, Heidelberg (2000)
Bellare, M., Canetti, R., Krawczyk, H.: Keying Hash Functions for Message Authentication. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 1–15. Springer, Heidelberg (1996)
Bellare, M., Rogaway, P.: Entity Authentication and Key Distribution. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 232–249. Springer, Heidelberg (1994)
Bellare, M., Rogaway, P.: The Exact Security of Digital Signatures - How to Sign with RSA and Rabin. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 399–416. Springer, Heidelberg (1996)
Bernstein, D.: The Poly1305-AES Message-Authentication Code. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 32–49. Springer, Heidelberg (2005)
Bernstein, D.: Proving Tight Security for Rabin-Williams Signatures. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 70–87. Springer, Heidelberg (2008)
Bhaskar, R., Herranz, J., Laguillaumie, F.: Aggregate designated verifier signatures and application to secure routing. Int. J. Security and Networks 2, 192–201 (2007)
Biham, E.: How to decrypt or even substitute DES-encrypted messages in 228 steps. Information Processing Letters 84, 117–124 (2002)
Biryukov, A., Mukhopadhyay, S., Sarkar, P.: Improved Time-Memory Trade-Offs with Multiple Data. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 110–127. Springer, Heidelberg (2006)
Biryukov, A., Shamir, A.: Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 1–13. Springer, Heidelberg (2000)
Black, J.A., Rogaway, P.: CBC MACs for Arbitrary-Length Messages: The Three-Key Constructions. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 197–215. Springer, Heidelberg (2000)
Blake-Wilson, S., Johnson, D., Menezes, A.: Key Agreement Protocols and Their Security Analysis. In: Darnell, M.J. (ed.) Cryptography and Coding 1997. LNCS, vol. 1355, pp. 30–45. Springer, Heidelberg (1997), http://www.cacr.math.uwaterloo.ca/techreports/1997/corr97-17.ps
Blum, L., Blum, M., Shub, M.: A simple unpredictable pseudo-random number generator. SIAM J. Computing 15, 364–383 (1986)
Boneh, D., Boyen, X.: Efficient Selective-ID Secure Identity-Based Encryption without Random Oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004)
Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. SIAM J. Computing 32, 586–615 (2003)
Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (2003)
Boyen, X.: A tapestry of identity-based encryption: practical frameworks compared. Int. J. Applied Cryptography 1, 3–21 (2008)
Boyen, X., Martin, L.: Identity-based cryptography standard (IBCS) #1: Supersingular curve implementations of the BF and BB1 cryptosystems. IETF RFC 5091 (2007)
Canetti, R., Krawczyk, H.: Analysis of Key-Exchange Protocols and their Use for Building Secure Channels. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 453–474. Springer, Heidelberg (2001), Full version at http://eprint.iacr.org/2001/040
Chan, H., Perrig, A., Song, D.: Secure hierarchical in-network aggregation in sensor networks. In: CCS 2006, pp. 278–287 (2006)
Chen, L., Cheng, Z.: Security Proof of Sakai-Kasahara’s Identity-Based Encryption Scheme. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 442–459. Springer, Heidelberg (2005)
Coron, J.-S.: On the Exact Security of Full Domain Hash. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 229–235. Springer, Heidelberg (2000)
Coron, J.-S.: Optimal Security Proofs for PSS and Other Signature Schemes. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 272–287. Springer, Heidelberg (2002)
Damgård, I.: A “Proof-Reading” of Some Issues in Cryptography. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 2–11. Springer, Heidelberg (2007)
Dang, Q.: Recommendation for applications using approved hash algorithms. NIST Special Publication 800-107 (2009)
Dworkin, M.: Recommendation for block cipher modes of operation: Methods and techniques. NIST Special Publication 800-38A (2001)
Dworkin, M.: Recommendation for block cipher modes of operation: The CMAC mode for authentication. NIST Special Publication 800-38B (2005)
Eastlake, D., Crocker, S., Schiller, J.: Randomness recommendations for security. IETF RFC 1750 (1994)
The eSTREAM project, http://www.ecrypt.eu.org/stream/
Eikemeier, O., Fischlin, M., Götzmann, J.-F., Lehmann, A., Schröder, D., Schröder, P., Wagner, D.: History-Free Aggregate Message Authentication Codes. In: Garay, J.A., De Prisco, R. (eds.) SCN 2010. LNCS, vol. 6280, pp. 309–328. Springer, Heidelberg (2010)
FIPS 180-3, Secure Hash Standard (SHS), Federal Information Processing Standards Publication 180-3, National Institute of Standards and Technology (2008)
FIPS 198-1, The Keyed-Hash Message Authentication Code (HMAC), Federal Information Processing Standards Publication 198, National Institute of Standards and Technology (2008)
Galindo, D.: Boneh-Franklin Identity Based Encryption Revisited. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 791–802. Springer, Heidelberg (2005)
Gentry, C., Halevi, S.: Hierarchical Identity Based Encryption with Polynomially Many Levels. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 437–456. Springer, Heidelberg (2009)
Goldreich, O.: On the Foundations of Modern Cryptography. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 46–74. Springer, Heidelberg (1997)
Halevi, S., Rogaway, P.: A Tweakable Enciphering Mode. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 482–499. Springer, Heidelberg (2003)
Halevi, S., Rogaway, P.: A Parallelizable Enciphering Mode. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 292–304. Springer, Heidelberg (2004)
Hellman, M.: A cryptanalytic time-memory trade-off. IEEE Trans. Info. Th. 26, 401–406 (1980)
Hong, J., Sarkar, P.: New Applications of Time Memory Data Tradeoffs. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 353–372. Springer, Heidelberg (2005)
Jakobsson, M., Sako, K., Impagliazzo, R.: Designated Verifier Proofs and their Applications. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 143–154. Springer, Heidelberg (1996)
Katz, J., Lindell, A.: Aggregate Message Authentication Codes. In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 155–169. Springer, Heidelberg (2008)
Katz, J., Wang, N.: Efficiency improvements for signature schemes with tight security reductions. In: CCS 2003, pp. 155–164 (2003)
Kelly, S., Frankel, S.: Using HMAC-SHA-256, HMAC-SHA-384, and HMAC-SHA-512 with IPsec. IETF RFC 4868 (2007)
Kent, S., Atkinson, R.: IP authentication header. IETF RFC 4302 (2005)
Koblitz, N., Menezes, A.: Another look at “provable security”. J. Cryptology 20, 3–37 (2007)
Koblitz, N., Menezes, A.: Another Look at “Provable Security”. II. In: Barua, R., Lange, T. (eds.) INDOCRYPT 2006. LNCS, vol. 4329, pp. 148–175. Springer, Heidelberg (2006)
Krawczyk, H.: HMQV: A High-Performance Secure Diffie-Hellman Protocol. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 546–566. Springer, Heidelberg (2005), Full version at http://eprint.iacr.org/2005/176
Kurosawa, K., Iwata, T.: TMAC: Two-Key CBC MAC. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 33–49. Springer, Heidelberg (2003)
LaMacchia, B., Lauter, K., Mityagin, A.: Stronger Security of Authenticated Key Exchange. In: Susilo, W., Liu, J.K., Mu, Y. (eds.) ProvSec 2007. LNCS, vol. 4784, pp. 1–16. Springer, Heidelberg (2007)
Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., Waters, B.: Sequential Aggregate Signatures and Multisignatures without Random Oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 465–485. Springer, Heidelberg (2006)
Luby, M.: Pseudorandomness and Cryptographic Applications. Princeton University Press (1996)
McGrew, D.A., Viega, J.: The Security and Performance of the Galois/Counter Mode (GCM) of Operation. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 343–355. Springer, Heidelberg (2004)
Menezes, A., Smart, N.: Security of signature schemes in the multi-user setting. Designs, Codes and Cryptography 33, 261–274 (2004)
Menezes, A., Ustaoglu, B.: Security arguments for the UM key agreement protocol in the NIST SP 800-56A standard. In: ASIACCS 2008, pp. 261–270 (2008)
National Security Agency, SKIPJACK and KEA algorithm specification, Version 2.0 (May 29, 1998)
Paillier, P., Vergnaud, D.: Discrete-Log-Based Signatures May Not Be Equivalent to Discrete Log. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 1–20. Springer, Heidelberg (2005)
Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. J. Cryptology 13, 361–396 (2000)
Rogaway, P.: Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 16–31. Springer, Heidelberg (2004)
Rogaway, P.: OCB: Background, http://www.cs.ucdavis.edu/~rogaway/ocb/ocb-faq.htm
Rogaway, P., Bellare, M., Black, J.: OCB: A block-cipher mode of operation for efficient authenticated encryption. ACM Trans. Information and System Security 6, 365–403 (2003)
Rogaway, P., Shrimpton, T.: A Provable-Security Treatment of the Key-Wrap Problem. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 373–390. Springer, Heidelberg (2006), Full version at http://eprint.iacr.org/2006/221
Sarkar, P.: Pseudo-random functions and parallelizable modes of operations of a block cipher. IEEE Trans. Info. Th. 56, 4025–4037 (2010)
Sarkar, P.: Tweakable enciphering schemes using only the encryption function of a block cipher. Inf. Process. Lett. 111, 945–955 (2011)
Schäge, S.: Tight Proofs for Signature Schemes without Random Oracles. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 189–206. Springer, Heidelberg (2011)
Schnorr, C.: Efficient signature generation for smart cards. J. Cryptology 4, 161–174 (1991)
Shin, J.: Enhancing privacy in cryptographic protocols, Ph.D. thesis, University of Maryland (2009)
Sidorenko, A., Schoenmakers, B.: Concrete Security of the Blum-Blum-Shub Pseudorandom Generator. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 355–375. Springer, Heidelberg (2005)
Song, J.H., Poovendran, R., Lee, J., Iwata, T.: The AES-CMAC algorithm. IETF RFC 4493 (2006)
Ustaoglu, B.: Obtaining a secure and efficient key agreement protocol from (H)MQV and NAXOS. Designs, Codes and Cryptography 46, 329–342 (2008)
van Oorschot, P., Wiener, M.: Parallel collision search with cryptanalytic applications. J. Cryptology 12, 1–28 (1999)
Young, A., Yung, M.: Malicious Cryptography: Exposing Cryptovirology. Wiley (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chatterjee, S., Menezes, A., Sarkar, P. (2012). Another Look at Tightness. In: Miri, A., Vaudenay, S. (eds) Selected Areas in Cryptography. SAC 2011. Lecture Notes in Computer Science, vol 7118. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28496-0_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-28496-0_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28495-3
Online ISBN: 978-3-642-28496-0
eBook Packages: Computer ScienceComputer Science (R0)