Construction of secure and fast hash functions using nonbinary error-correcting codes

Lars Ramkilde Knudsen, Bart Preneel

    Research output: Contribution to journalJournal articleResearchpeer-review

    405 Downloads (Pure)


    This paper considers iterated hash functions. It proposes new constructions of fast and secure compression functions with nl-bit outputs for integers n>1 based on error-correcting codes and secure compression functions with l-bit outputs. This leads to simple and practical hash function constructions based on block ciphers such as the Data Encryption Standard (DES), where the key size is slightly smaller than the block size; IDEA, where the key size is twice the block size; Advanced Encryption Standard (AES), with a variable key size; and to MD4-like hash functions. Under reasonable assumptions about the underlying compression function and/or block cipher, it is proved that the new hash functions are collision resistant. More precisely, a lower bound is shown on the number of operations to find a collision as a function of the strength of the underlying compression function. Moreover, some new attacks are presented that essentially match the presented lower bounds. The constructions allow for a large degree of internal parallelism. The limits of this approach are studied in relation to bounds derived in coding theory.
    Original languageEnglish
    JournalI E E E Transactions on Information Theory
    Issue number9
    Pages (from-to)2524-2539
    Publication statusPublished - 2002

    Bibliographical note

    Copyright: 2002 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE

    Fingerprint Dive into the research topics of 'Construction of secure and fast hash functions using nonbinary error-correcting codes'. Together they form a unique fingerprint.

    Cite this