Randomized Hashing and Digital Signatures
by Shai Halevi and Hugo Krawczyk
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.
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.
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
that documents our basic randomization
technique for use with digital signatures.