On hash functions using checksums

Praveen Gauravaram, John Kelsey, Lars Ramkilde Knudsen, Søren Steffen Thomsen

    Research output: Book/ReportReportpeer-review

    748 Downloads (Pure)

    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 multicollision 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.
    Original languageEnglish
    Publication statusPublished - 2008
    SeriesMAT report
    Number2008-06

    Keywords

    • checksums
    • multicollisions
    • second preimage and herding attack
    • Iterated hash functions

    Fingerprint

    Dive into the research topics of 'On hash functions using checksums'. Together they form a unique fingerprint.

    Cite this