Abstract
Digital signatures are often proven to be secure in the random oracle model while hash functions deviate more and more from this idealization. Liskov proposed to model a weak hash function by a random oracle together with another oracle allowing to break some properties of the hash function, e.g. a preimage oracle. To avoid the need for collision-resistance, Bellare and Rogaway proposed to use target collision resistant (TCR) randomized pre-hashing. Later, Halevi and Krawczyk suggested to use enhanced TCR (eTCR) hashing to avoid signing the random seed. To avoid the increase in signature length in the TCR construction, Mironov suggested to recycle some signing coins in the message preprocessing. In this paper, we develop and apply all those techniques. In particular, we obtain a generic preprocessing which allows to build strongly secure signature schemes when hashing is weak and the internal (textbook) signature is weakly secure. We model weak hashing by a preimage-tractable random oracle.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Shoup, V. (ed.): CRYPTO 2005. LNCS, vol. 3621. Springer, Heidelberg (2005)
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Deza, M., Manoussakis, I., Euler, R. (eds.) CCS ’93. LNCS, vol. 1120, pp. 62–73. ACM Press, New York (1996)
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.: Towards Making UOWHFs Practical. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 470–484. Springer, Heidelberg (1997)
Cramer, R., Shoup, V.: Signature Schemes Based on the Strong RSA Assumption. ACM Transactions on Information and System Security 3(3), 161–185 (2000)
Digital signature standard (DSS). Federal Information Processing Standard, Publication 186-2, U.S. Department of Commerce, NIST (2000)
Digital signature standard (DSS). Federal Information Processing Standard, Publication 186, U.S. Department of Commerce, NIST (1994)
ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31(4), 469–472 (1985)
Halevi, S., Krawczyk, H.: Strengthening Digital Signatures via Randomized Hashing. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 41–59. Springer, Heidelberg (2006)
Halevi, S., Krawczyk, H.: The RMX Transform and Digital Signatures (2006), http://www.ee.technion.ac.il/~hugo/rhash/
Housley, R., Ford, W., Polk, W., Solo, D.: RFC 2459: Internet X.509 Public Key Infrastructure Certificate and CRL Profile. IETF RFC Publication (1999)
Liskov, M.: Constructing an Ideal Hash Function from Weak Ideal Compression Functions. In: SAC ’06, pp. ???–?? (2006)
Mironov, I.: Collision-Resistant No More: Hash-and-Sign Paradigm Revisited. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 140–156. Springer, Heidelberg (2006)
Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: ACM Symposium on Theory of Computing, pp. 33–43 (1989)
Rivest, R.L.: The MD5 message digest algorithm. Technical Report Internet RFC-1321, IETF (1992)
Rivest, R.L., Shamir, A., Adleman, L.M.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21(2), 120–126 (1978)
Rivest, R.L.: The MD4 Message Digest Algorithm. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 303–311. Springer, Heidelberg (1991)
Rogaway, P.: Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys. In: Nguyen, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 221–228. Springer, Heidelberg (2006)
Secure hash standard. Federal Information Processing Standard, Publication 180, U.S. Department of Commerce, NIST (1993)
Secure hash standard. Federal Information Processing Standard, Publication 180-1, U.S. Department of Commerce, NIST (1995)
Shoup, V.: Sequences of Games: A Tool for Taming Complexity in Security Proofs. Cryptology ePrint Archive, Report 2004/332, http://eprint.iacr.org/
Wang, X., Yin, Y., Yu, H.: Finding collisions in the full SHA1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17–36. Springer, Heidelberg (2005)
Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19–35. Springer, Heidelberg (2005)
Wang, X., Yu, X., Yin, L.Y.: Efficient collision search attacks on SHA-0. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 1–16. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Pasini, S., Vaudenay, S. (2007). Hash-and-Sign with Weak Hashing Made Secure. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds) Information Security and Privacy. ACISP 2007. Lecture Notes in Computer Science, vol 4586. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73458-1_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-73458-1_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73457-4
Online ISBN: 978-3-540-73458-1
eBook Packages: Computer ScienceComputer Science (R0)