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

Lars Ramkilde Knudsen, Bart Preneel

    Research output: Contribution to journalJournal articleResearchpeer-review

    284 Downloads (Pure)

    Abstract

    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
    Volume48
    Issue number9
    Pages (from-to)2524-2539
    ISSN0018-9448
    DOIs
    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

    Cite this

    @article{d3d7c08d0234460389737043297cbcc5,
    title = "Construction of secure and fast hash functions using nonbinary error-correcting codes",
    abstract = "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.",
    author = "Knudsen, {Lars Ramkilde} and Bart Preneel",
    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",
    year = "2002",
    doi = "10.1109/TIT.2002.801402",
    language = "English",
    volume = "48",
    pages = "2524--2539",
    journal = "I E E E Transactions on Information Theory",
    issn = "0018-9448",
    publisher = "Institute of Electrical and Electronics Engineers",
    number = "9",

    }

    Construction of secure and fast hash functions using nonbinary error-correcting codes. / Knudsen, Lars Ramkilde; Preneel, Bart.

    In: I E E E Transactions on Information Theory, Vol. 48, No. 9, 2002, p. 2524-2539.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

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

    AU - Knudsen, Lars Ramkilde

    AU - Preneel, Bart

    N1 - 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

    PY - 2002

    Y1 - 2002

    N2 - 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.

    AB - 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.

    U2 - 10.1109/TIT.2002.801402

    DO - 10.1109/TIT.2002.801402

    M3 - Journal article

    VL - 48

    SP - 2524

    EP - 2539

    JO - I E E E Transactions on Information Theory

    JF - I E E E Transactions on Information Theory

    SN - 0018-9448

    IS - 9

    ER -