On randomizing hash functions to strengthen the security of digital signatures

Praveen Gauravaram, Lars Ramkilde Knudsen

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    Abstract

    Halevi and Krawczyk proposed a message randomization algorithm called RMX as a front-end tool to the hash-then-sign digital signature schemes such as DSS and RSA in order to free their reliance on the collision resistance property of the hash functions. They have shown that to forge a RMX-hash-then-sign signature scheme, one has to solve a cryptanalytical task which is related to finding second preimages for the hash function. In this article, we will show how to use Dean's method of finding expandable messages for finding a second preimage in the Merkle-Damg{\aa}rd hash function to existentially forge a signature scheme based on a $t$-bit RMX-hash function which uses the Davies-Meyer compression functions (e.g., MD4, MD5, SHA family) in $2^{t/2}$ chosen messages plus $2^{t/2+1}$ off-line operations of the compression function and similar amount of memory. This forgery attack also works on the signature schemes that use Davies-Meyer schemes and a variant of RMX published by NIST in its Draft Special Publication (SP) 800-106. We discuss some important applications of our attack.
    Original languageEnglish
    Title of host publicationProceedings of Eurocrypt-2009
    EditorsAntoine Joux
    Number of pages609
    Volume5479
    Place of PublicationBerlin Heidelberg New York
    PublisherSpringer
    Publication date2009
    Pages88-105
    ISBN (Print)978-3-642-01000-2
    Publication statusPublished - 2009
    EventAdvances in Cryptology-EUROCRYPT 2009 : Annual International Conference on the Theory and Applications of Cryptographic Techniques - Cologne, Germany
    Duration: 1 Jan 2009 → …
    Conference number: 28

    Conference

    ConferenceAdvances in Cryptology-EUROCRYPT 2009 : Annual International Conference on the Theory and Applications of Cryptographic Techniques
    Number28
    CityCologne, Germany
    Period01/01/2009 → …
    SeriesLecture Notes in Computer Science
    Number5479
    ISSN0302-9743

    Bibliographical note

    One of the (out of three) candidate papers for the best paper award.

    Keywords

    • Davies-Meyer
    • Hash functions
    • Randomized Hashing
    • Digital signatures

    Fingerprint Dive into the research topics of 'On randomizing hash functions to strengthen the security of digital signatures'. Together they form a unique fingerprint.

    Cite this