On Randomizing Hash Functions to Strengthen the Security of Digital Signatures.

Praveen Gauravaram (Author)

    Research output: Non-textual formSound/Visual production (digital)Research

    239 Downloads (Pure)

    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å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
    Publication date2009
    DOIs
    Publication statusPublished - 2009
    EventAdvances in Cryptology - EUROCRYPT 2009 : 28th 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 : 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques
    Number28
    CityCologne, Germany
    Period01/01/2009 → …

    Keywords

    • Digital signatures,Hash functions,Davies-Meyer, Randomized hashing

    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