Randomized Hashing and Digital Signatures

by Shai Halevi and Hugo Krawczyk

Recent attacks on collision resistant hash functions (CRHF) are threatening the security of some cryptographic applications, most notably digital signatures. In this work we propose to complement the search for better CRHFs by adopting a simple randomization technique that protects digital signatures against collision attacks on their underlying hash functions. When combined with iterative hash functions (e.g., SHA-1, SHA2) and standard signature algorithms (e.g., RSA, DSS) one obtains signature schemes whose security is preserved even after collisions have been found in the underlying hash functions.

We formally show that just finding collisions is not sufficient in order to break the resultant signatures: instead the attacker needs to solve a much harder cryptanalytical problem, closer to finding second-preimages. Hence our scheme serves as a SAFETY NET, in case the hash functions that we use turn out to be less resilient to collision search than initially thought.

Our method works with any signature scheme based on the standard hash-then-sign paradigm and any iterative hash function. It comprises a simple message randomization scheme, called RMX, that is applied to a message before signing. The output of this randomization is input directly to the hash-then-sign mechanism without further changes. The randomization uses a short random string ("salt") chosen anew with each signature and transported in addition to the signed message and signature.

RMX is as simple as it gets... ... as evidenced by this picture:

If you want to learn more, here are some relevant documents.

Documents and Implementations:
Strengthening Digital Signatures via Randomized Hashing. This paper presents the design and theory of the proposed scheme, as well as a detailed specification, named RMX, for use in actual implementations and standardization. (An extended abstract of this paper appears in the proceedings of Crypto'06.)

The RMX Transform and Digital Signatures. This document describes our implementation experience with the RMX scheme in several important contexts. It includes details of our experience with integrating our scheme into openssl, as well as the use of our scheme for signing and verifying digital certificates (also in the context of openssl). It also describes an implementation in the context of XML signatures. (A short presentation on these aspects of our work was given in the 2nd NIST Hash Workshop, August 2006.)

Randomized Hashing for Digital Certificates: An implementation in Firefox by Dan Boneh and Weidong Shao from Stanford University.

IMPLEMENTATION SUMMARY co-authored with Dan Boneh, Mike McIntosh and Weidong Shao.

Internet Draft: draft-irtf-cfrg-rhash-01.txt .

Further Work and Standardization.
Our implementation experience shows that the complexity of implementing and deploying our randomized scheme is not significantly greater than the complexity already involved in the definition, adoption and deployment of a new hash function. Given that efforts to accomodate the adoption of new functions are underway, we believe that this is also the right time to introduce the new (but very simple) randomization techniques to standards and applications. We will be happy to hear from people interested in helping to make this happen (or just interested to learn more about the proposal).

NEW!! NIST Publishes Special Publication 800-106 (Draft) "Randomized Hashing Digital Signatures". that documents our basic randomization technique for use with digital signatures.
We believe that the trade-off between simplicity and added security presented by this proposal makes it a very valuable mechanism to adopt. We should not wait for the next round of cryptanalytical advances to regret not having done this earlier.