Abstract
This paper analyzes the security of a hash mode recently proposed by Yi and Lam. Given a block cipher with m-bit block size and 2m-bit key, they build a hash function with 2m-bit outputs that can hash messages as fast as the underlying block cipher can encrypt. This construction was conjectured to have ideal security, i.e., to resist all collision attacks faster than brute force. We disprove this conjecture by presenting a collision attack that is substantially faster than brute force and which could even be considered practical for typical security parameters.
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
L. Knudsen and X. Lai, “New attacks on all Double Block Length Hash Functions of Hash Rate 1, including the Parallel DM,” EUROCRYPT’94, Springer Verlag, LNCS 950.
L.R. Knudsen, X. Lai, and B. Preneel, “Attacks on fast double block length hash functions,” Journal of Cryptology, Winter 1998, vol.11, (no.1):59–72.
L. Knudsen and B. Preneel, “Hash Functions Based on Block Ciphers and Quaternary Codes,” ASIACRYPT’96, Springer Verlag, LNCS 1163.
X. Lai and L. Knudsen, “Attacks on Double Block Length Hash Functions,” Fast Software Encryption’ 93, Springer Verlag, LNCS 809.
K.M. Martin and C.J. Mitchell, “Analysis of hash function of Yi and Lam,” Electronics Letters, vol.34, no. 24, 1998, pp.2327–2328.
A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, 1997.
P.C. van Oorschot and M.J. Wiener, “Parallel Collision Search with Cryptanalytic Applications,” Journal of Cryptology, vol.12, no. 1, 1999, pp.1–28.
B. Preneel, “Analysis and design of cryptographic hash functions,” Doctoral dissertation, Katholieke Universiteit Leuven, 1993.
T. Satoh, M. Haga, and K. Kurosawa, “Towards Secure and Fast Hash Functions,” IEICE Trans. Fundamentals, vol. E82-A, no. 1, Jan. 1999.
X. Yi and K.-Y. Lam, “A new hash function based on block cipher,” ACISP’97, Second Australasian Conference on Information Security and Privacy, Springer, LNCS 1270.
X. Yi and K.-Y. Lam, “Hash function based on block cipher,” Electronics Letters, 6 Nov 1997, vol.33, (no.23):1938–1940, IEEE.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wagner, D. (2000). Cryptanalysis of the Yi-Lam Hash. In: Okamoto, T. (eds) Advances in Cryptology — ASIACRYPT 2000. ASIACRYPT 2000. Lecture Notes in Computer Science, vol 1976. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44448-3_37
Download citation
DOI: https://doi.org/10.1007/3-540-44448-3_37
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41404-9
Online ISBN: 978-3-540-44448-0
eBook Packages: Springer Book Archive