Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

On Hash Functions Using Checksums

Published

Author(s)

Praveen Gauruvarum, John M. Kelsey, L. Knudsen, S. Thomsen

Abstract

We analyse the security of iterated hash functions that compute an input dependent checksum which is processed as part of the hash computation. We show that a large class of such schemes, including those using non-linear or even one- way checksum functions, is not secure against the second preimage attack of Kelsey and Schneier, the herding attack of Kelsey and Kohno, and the ulticollision attack of Joux. Our attacks also apply to a large class of cascaded hash functions. Our second preimage attacks on the cascaded hash functions improve the results of Joux presented at Crypto '04. We also apply our attacks to the MD2 and GOST hash functions. Our second preimage attacks on the MD2 and GOST hash functions improve the previous best known short-cut second preimage attacks on these hash functions by factors of at least 2^26 and 2^54, respectively. Our herding and multicollision attacks on the hash functions based on generic checksum functions (e.g., one-way) are a special case of the attacks on the cascaded iterated hash functions previously analysed by Dunkelman and Preneel and are not better than their attacks. On hash functions with easily invertible checksums, our multicollision and herding attacks (if the hash value is short as in MD2) are more efficient than those of Dunkelman and Preneel.
Citation
International Journal of Information Security
Volume
9
Issue
2

Keywords

Iterated hash functions, Checksums, Generic attacks, Merkle-Damgaard

Citation

Gauruvarum, P. , Kelsey, J. , Knudsen, L. and Thomsen, S. (2010), On Hash Functions Using Checksums, International Journal of Information Security, [online], https://doi.org/10.1007/s10207-009-0100-7 (Accessed June 21, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created March 31, 2010, Updated October 12, 2021