Abstract
A signature scheme constructed according to the hash-and-sign paradigm—hash the message and then sign the hash, symbolically σ(H(M))—is no more secure than the hash function H against a collision-finding attack. Recent attacks on standard hash functions call the paradigm into question. It is well known that a simple modification of the hash-and-sign paradigm may replace the collision-resistant hash with a weaker primitive—a target-collision resistant hash function (also known as a universal one-way hash, UOWHF). The signer generates a random key k and outputs the pair (k,σ(k||H k (M))) as a signature on M. The apparent problem with this approach is the increase in the signature size. In this paper we demonstrate that for three concrete signature schemes, DSA, PSS-RSA, and Cramer-Shoup, the message can be hashed simultaneously with computing the signature, using one of the signature’s components as the key for the hash function. We prove that our constructions are as secure as the originals for DSA and PSS-RSA in the random oracle model and for the Cramer-Shoup signature scheme in the standard model.
Chapter PDF
Similar content being viewed by others
References
Biham, E., Chen, R., Joux, A., Carribault, P., Lemuet, C., Jalby, W.: Collisions of SHA-0 and reduced SHA-1. In: Cramer [Cra05], pp. 36–57 (2005)
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)
Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo random bits. In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, November 3–5, 1982, pp. 112–117. IEEE, Los Alamitos (1982)
Barić, N., Pfitzmann, B.: Collision-free accumulators and fail-stop signature schemes without trees. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 480–494. Springer, Heidelberg (1997)
Brickell, E.F., Pointcheval, D., Vaudenay, S., Yung, M.: Design validations for discrete logarithm based signature schemes. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 276–292. Springer, Heidelberg (2000)
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
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)
Bellare, M., Rogaway, P.: Collision-resistant hashing: Towards making UOWHFs practical. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 470–484. Springer, Heidelberg (1997)
Brassard, G. (ed.): CRYPTO 1989. LNCS, vol. 435. Springer, Heidelberg (1990)
Coron, J.-S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damgård revisited: How to construct a hash function. In: Shoup [Sho05], pp. 430–448 (2005)
Brown, D.R.L.: Generic groups, collision resistance, and ECDSA. Designs, Codes and Cryptography 35(1), 119–152 (2005)
Coron, J.-S.: Optimal security proofs for PSS and other signature schemes. In: Knudsen [Knu02], pp. 272–287 (2002)
Cramer, R. (ed.): EUROCRYPT 2005. LNCS, vol. 3494. Springer, Heidelberg (2005)
Cramer, R., Shoup, V.: Signature schemes based on the strong RSA assumption. ACM Trans. on Information and System Security (TISSEC) 3(3), 161–185 (2000)
Damgård, I.: A design principle for hash functions. In: Brassard [Bra90], pp. 416–427 (1990)
Dodis, Y., Oliveira, R., Pietrzak, K.: On the generic insecurity of the full domain hash. In: Shoup [Sho05], pp. 449–466 (2005)
Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Fischlin, M.: The Cramer-Shoup Strong-RSA signature scheme revisited. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 116–129. Springer, Heidelberg (2002)
Gennaro, R., Halevi, S., Rabin, T.: Secure hash-and-sign signatures without the random oracle. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 123–139. Springer, Heidelberg (1999)
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing 17, 281–308 (1988)
Halevi, S., Krawczyk, H.: Strengthening digital signatures via randomized hashing. Internet-Draft, Crypto Forum Research Group (May 2005)
Halevi, S., Krawczyk, H.: Strengthening digital signatures via randomized hashing. In: Talk at Cryptographic Hash Workshop (NIST), October 31–November 1 (2005)
Knudsen, L.R. (ed.): EUROCRYPT 2002. LNCS, vol. 2332. Springer, Heidelberg (2002)
Hong, D., Preneel, B., Lee, S.: Higher order universal oneway hash functions. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 201–213. Springer, Heidelberg (2004)
Kelsey, J., Schneier, B.: Second preimages on n-bit hash functions for much less than 2n work. In: Cramer [Cra05], pp. 474–490 (2005)
Merkle, R.C.: One way hash functions and DES. In: Brassard [Bra90], pp. 428–446 (1990)
Mironov, I.: Hash functions: From Merkle-Damgåard to Shoup. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 166–181. Springer, Heidelberg (2001)
NESSIE Consortium. Performance of optimized implementations of the NESSIE primitives, version 2.0. Deliverable report D21, NES/DOC/TEC/WP6/D21/2 (February 2003)
NIST. Secure hash standard. FIPS PUB 180-1, National Institute of Standards and Technology (April 1995)
Nakajima, J., Matsui, M.: Performance analysis and parallel implementation of dedicated hash functions. In: Knudsen [Knu02], pp. 165–180 (2002)
Nguyen, P.Q., Shparlinski, I.E.: The insecurity of the digital signature algorithm with partially known nonces. J. Cryptology 15(3), 151–176 (2002)
Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, May 15–17, pp. 33–43 (1989)
Preneel, B. (ed.): EUROCRYPT 2000. LNCS, vol. 1807. Springer, Heidelberg (2000)
Paillier, P., Vergnaud, D.: Discrete-log-based signatures not be equivalent to discrete log. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 1–20. Springer, Heidelberg (2005)
Rivest, R.L.: The MD4 message digest algorithm. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 303–311. Springer, Heidelberg (1991)
Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, May 14–16, pp. 387–394 (1990)
Sarkar, P.: Masking based domain extenders for UOWHFs: Bounds and constructions. Cryptology ePrint Archive, Report 2003/225 (2003), http://eprint.iacr.org/
Shoup, V.: A composition theorem for universal one-way hash functions. In: Preneel [Pre00], pp. 445–452 (2000)
Shoup, V.: Using hash functions as a hedge against chosen ciphertext attack. In: Preneel [Pre00], pp. 275–288 (2000)
Shoup, V.: Sequences of games: a tool for taming complexity in security proofs. Cryptology ePrint Archive, Report 2004/332 (2004), http://eprint.iacr.org/
Shoup, V. (ed.): CRYPTO 2005. LNCS, vol. 3621. Springer, Heidelberg (2005)
Simon, D.R.: Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334–345. Springer, Heidelberg (1998)
Schweinberger, T., Shoup, V.: ACE: The advanced cryptographic engine (2000) (manuscript), http://shoup.net/papers/ace.pdf
Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer [Cra05], pp. 19–35 (2005)
Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup [Sho05], pp. 17–36 (2005)
Wang, X., Yu, H., Yin, Y.L.: Efficient collision search attacks on SHA-0. In: Shoup [Sho05], pp. 1–16 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mironov, I. (2006). Collision-Resistant No More: Hash-and-Sign Paradigm Revisited. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds) Public Key Cryptography - PKC 2006. PKC 2006. Lecture Notes in Computer Science, vol 3958. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11745853_10
Download citation
DOI: https://doi.org/10.1007/11745853_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33851-2
Online ISBN: 978-3-540-33852-9
eBook Packages: Computer ScienceComputer Science (R0)