Skip to main content

NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.

Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.

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 October 16, 2025)

Issues

If you have any questions about this publication or are having problems accessing it, please contact [email protected].

Created March 31, 2010, Updated October 12, 2021
Was this page helpful?