[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01

CFRG                                                    S.  Halevi (IBM)
Internet-Draft                                        H.  Krawczyk (IBM)
Expires: April 18, 2008                                 October 18, 2007


          Strengthening Digital Signatures via Randomized Hashing
                        draft-irtf-cfrg-rhash-01.txt

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   Copyright (C) The IETF Trust (2007).


Abstract

   This document describes a randomized hashing scheme consisting of a
   simple message randomization transform that when used as a front-end
   to regular hash-then-sign signature schemes, such as RSA and DSS,
   frees these signatures from their current vulnerability to off-line
   collision attacks against the underlying hash function.  The proposed
   mechanism can work with any hash function as-is and requires no
   change to the underlying signature algorithm. Incorporating this
   mechanism into existing applications requires changes that are
   comparable in their complexity to accommodating a new (deterministic)
   hash function such as SHA-256.

   Visit http://www.ee.technion.ac.il/~hugo/rhash/ for more information
   and updates on this work.








Halevi and Krawczyk                                             [Page 1]

Internet Draft        draft-irtf-cfrg-rhash-01.txt      October 18, 2007

1 Introduction

   The recent collision attacks against popular hash functions have a
   profound effect on the security of some applications of these
   functions, most notably digital signatures. In this document we
   propose a randomized mode of operation for hash functions that when
   used in conjunction with standardized hash-then-sign signature
   schemes (such as RSA or DSS) frees these schemes from their current
   essential dependency on full collision resistance. This mode of
   operation can work with any hash function and requires no change to
   the underlying signature algorithms. It consists of a simple message
   randomization transform, called RMX, which is fully specified in this
   document and used as a front-end to existing hash-then-sign signature
   schemes. The analysis in [HK06] shows that breaking a signature
   scheme that uses RMX requires solving a cryptanalytical problem
   related to finding second pre-images in the underlying compression
   function, and hence significantly harder than simply finding
   (off-line) collisions as in current attacks against standard
   signature schemes.

   The full specification of RMX is presented in Section 2. In a
   nutshell, RMX prepends to the message a random string ("salt") of one
   block, and then XORs (exclusive-or) the same random string with
   every block of the message itself (where a "block" is of the length
   specified by the underlying hash function or, if such block size is
   not defined by the hash function, it is the length of the salt).
   That is, if M=(M1, ...,Mn) where the Mi's are message blocks then:

            RMX(r,M) = (r, M1 XOR r, ..., Mn XOR  r).

   We note that the full specification of RMX includes a simple padding
   rule for the last message block; also, to save bandwidth and
   randomness, the scheme accommodates salt strings shorter than a full
   message block. RMX can be implemented either as a simple front-end
   interface to the iterated hash function, or it can be integrated with
   typical implementations of digest functions (in particular,
   Merkle-Damgard functions such as the SHA family) that read the
   message block by block and feed these successive blocks into the
   compression function.

   RMX can be used with any hash-then-sign scheme by replacing the
   message M in the original signature scheme with RMX(r,M), i.e.,
   instead of SIG(H(M)) a signature is computed as SIG(H(RMX(r,M))).
   The salt r is generated for each signature by the signer and
   transmitted to the verifier together with the message and signature.
   The verifier uses the regular verification procedure where the
   original digest function is applied to RMX(r,M) rather than to M.
   Note that only the signer needs to generate randomness, the verifier
   receives it with the message/signature. As said, off-line collision
   search is useless against a signature scheme that uses RMX. Rather,
   to break the signatures the attacker needs to solve a cryptanalytical
   problem close to finding second preimages (which is a much harder
   task than finding collisions, and it has to be done on a

Halevi and Krawczyk                                             [Page 2]

Internet Draft        draft-irtf-cfrg-rhash-01.txt      October 18, 2007

   per-signature basis rather than off-line). Importantly, to gain this
   security advantage the value of r must be unpredictable to the
   attacker until the full content of the message to be signed is
   determined; we recommend that the length of r be at least 128 bits.

   The use of RMX and its application to signatures do not depend on the
   way the salt r is transmitted; therefore, different applications may
   choose different ways to transport r. This is analogous to the use of
   the IV in CBC encryption: the definition of CBC specifies how to use
   a block cipher to encrypt any-length message given the value of an
   IV, but leaves it up to the application to decide how to transmit the
   IV. In Section 4 we report on some experimental implementations of
   RMX (openssl, NSS/Firefox, and XML signatures), and discuss some
   options for the transport of the salt in applications using RMX. In
   particular, we suggest a mechanism that can be shared by applications
   that use algorithm identifiers (as per X.509), namely, transporting
   the salt as a parameter of the algorithm identifier.

   It is important to note that the use of RMX in the context of digital
   signatures does not require changes in signature standards such as
   PKCS#1 (RSA) or FIPS 186 (DSS). Furthermore, an important conclusion
   of initial implementation experience with RMX is that the complexity
   of implementing and deploying RMX in the context of digital
   signatures is comparable to the effort needed to upgrade existing
   systems to use a new deterministic hash function, such as SHA256.
   Moreover, once the mechanisms are in place to deal with such upgrade
   (cf. [BR05]), supporting RMX becomes a relatively simple matter (see
   Section 4 and the references there).

   We stress that our proposal is not intended as an alternative to the
   search for new, stronger hash functions to replace SHA-1 and MD5, but
   it is rather intended to complement this effort by providing a
   "safety net" for digital signatures in case a hash function in use is
   later found to be weaker than believed initially. Given our limited
   understanding of the best ways to build collision resistant hash
   functions, prudent engineering principles call for building
   cryptographic primitives that rely as little as possible on the
   strength of hash functions. Our work addresses this principle in the
   context of digital signatures and as such it resembles the effect of
   the HMAC design in the message authentication area.

   We refer the reader to the paper by these authors [HK06] for a more
   extensive description and rationale of the design of RMX, as well as
   an analysis of the cryptographic strength of the scheme (in that
   paper the scheme specified here, namely, applying RMX to the message
   before inputting it to the hash function, is referred to as the
   "eTCR construction").

   COMPATIBILITY WITH NIST's RANDOMIZED HASHING PUBLICATION [NIST].
   The present document is somewhat wider in scope than [NIST] which
   defines the same randomized hashing transform but provides less
   implementation guidance. Also, the specification here of the central
   RMX transform is slightly more general than [NIST], in particular it

Halevi and Krawczyk                                             [Page 3]

Internet Draft        draft-irtf-cfrg-rhash-01.txt      October 18, 2007

   allows for some hash-specific optimizations (especially for
   Merkle-Damgard and related hash functions). We anticipate that the
   final specifications of RMX in both documents (here and [NIST]) will
   be identical.

   IETF SCOPE. This Internet Draft is offered to the IETF community
   for consideration for standardization and adoption in protocols whose
   security heavily relies on digital signatures. The need for
   randomized hashing is especially acute in applications (e.g., PKIX,
   S/Mime) where non-repudiation or third-party-verifiability are
   crucial; however, it is recommended also as a general way of
   strengthening signatures in other applications. In particular,
   protocols that support hash agility (newer TLS versions, for example)
   should make provisions for the future use of randomized hashing (see
   Section 4 for some implementation guidance).

   Visit http://www.ee.technion.ac.il/~hugo/rhash/ for more information
   and updates on this work.

2 The Message Randomization Scheme RMX

   The RMX message randomization procedure is the core of the randomized
   hashing scheme and it is specified next. RMX takes as input a message
   M (to be signed) and a random salt value r, and outputs M', the
   transformed message that will be input into the hash-then-sign
   signature module.

   RMX should be seen as a mode of operation for hash functions, and as
   such it may depend on some of the parameters of the underlying hash
   function such as a block length or the hash function's  padding
   mechanism. Specifically, the RMX definition uses two parameters,
   block_length and pad_length, that may depend on the underlying hash
   function.

   The first, block_length, is used by RMX to determine the expansion of
   the input salt r into an internal salt value r'. RMX sets
   block_length to the block length of the underlying hash function
   (e.g., it will be 512 for SHA-256). However, if this hash function
   does not define a block length (or if this length is less that 128
   bits) then block_length is set to the length of the salt value r
   input to RMX.  (This provision for a non-blockwise hash function is
   due to NIST's desire [NIST] to accommodate any, possibly
   unconventional, hash function that may emerge in the future.)

   The parameter pad_length is used by RMX to determine the number of
   bits with which RMX pads the input message (RMX performs an internal
   padding in addition to any padding that may be defined by the
   underlying hash function). In all cases, pad_length is computed as a
   function of the length of the input message M (we denote this length
   by |M|) and possibly also as a function of block_length.

   After the description of RMX below, we present two concrete
   instantiations of pad_length: a generic function that does not assume

Halevi and Krawczyk                                             [Page 4]

Internet Draft        draft-irtf-cfrg-rhash-01.txt      October 18, 2007

   any structure on the underlying hash function (this is the same as
   the RMX mechanism defined in [NIST]), and a different instantiation
   that is optimized for Merkle-Damgard hash functions (where a block
   length is well defined). We expect the latter instantiation to be
   used with contemporary hash functions such as SHA-1 and SHA-2.
   (See discussion in Section 5 regarding the security advantages of
   using the second instantiation when the underlying hash function is a
   Merkle-Damgard iterated hash function.)

Specification of the RMX transform.

   Parameters:

     block_length    // Length of the internal salt value r' used in the
                     // algorithm
     pad_length      // A function to determine the number L of padding
                     // bits used internally by RMX (depends on |M|).

   Input:

     Message M, Salt r         // r is random of size at least 128 bits

   Output:

     Randomized Message M'     // input to hash function and signature

   1. Let r' be r concatenated with itself as many times as needed
      (last copy possibly truncated) to cover block_length bits

   2. Let L = pad_length(|M|)

   3. Define m to be a message obtained by concatenating the original
      message M, followed by L zeros and by two bytes containing the
      number L written in big-endian notation. That is:

      m = M || 0^L || L

   4. Define R to be the a string of the same length as m (i.e.,
      |M|+L+16 bits) composed by concatenating r' with itself as many
      times as needed (with the last copy of r' possibly truncated)

      R = (r' || r' || ... || r' || r') truncated to |M|+L+16 bits

   5. Define m' to be the bitwise XOR of m and R. That is:

      m' = m XOR R

   6. Define M' to be the concatenation of r' followed by m'. That is:

      M' = r' || m'

   7. Output M'


Halevi and Krawczyk                                             [Page 5]

Internet Draft        draft-irtf-cfrg-rhash-01.txt      October 18, 2007

   NOTE: While the description of RMX above treats the input message M
   as one unit, actual implementations of RMX do not need to buffer the
   whole message but can rather (as in a streaming scenario) read and
   process M block by block. The same is true for the output message M'
   that can be output block by block. This is particularly convenient
   when inputting M' into a hash function that reads its input
   block-by-block; in this case the RMX and hash computation can be
   pipelined. Also worth noting is that since the parameter (function)
   pad_length depends on the length of M, its value will usually be
   computed as part of the RMX procedure after the whole message is
   received.

   Next, we present two possible instantiations of the parameters pad
   length and block_length.

   GENERIC PARAMETERS. This definition can be used with any hash
   function regardless of its structure or iteration. It corresponds to
   the current randomized hashing definition in [NIST].

   Set block_length = |r| (i.e., r'=r).
   pad_length is set to:
       0              if |r'| <= 16+|M|
      |r'|-(16+|M|)   otherwise.

   PARAMETERS FOR MERKLE-DAMGARD HASHING. This specification of the
   parameters is intended for Merkle-Damgard hash functions (and related
   iterated functions) and it provides the maximal benefits of RMX for
   such functions (by maximizing the number of random bits XOR-ed to the
   last padded block). The specification is optimized by setting r' to
   be of the length of a hash block. We use b to denote this block
   length and c to denote the number of padding bits added by the
   underlying hash function (for the so-called MD-strengthening).
   For example, b=512, c=64 in SHA-256 and b=1024, c=128 in SHA-512.
   Specifically, in the Merkle-Damgard case we define:

   Set block_length to b.
   Let b' = |M| mod b and b''=b'+c+24.
   pad_length is set to:
      2b-b''     if b'' > b
      b-b''      otherwise

   (The first case corresponds to the cases where the hash function adds
   a full new padding block and hence pad_length = (b-b')+(b-24-c);
   in the other case pad_length = b-(b'+c+24)).)

   IMPLEMENTATION. As we already said, the definition of RMX allows for
   an implementation that acts as a simple front-end interface to the
   iterated hash function, or it can be integrated with typical
   implementations of digest functions that read the message block by
   block and feed these successive blocks into the compression function.
   We discuss more implementation issues in Section 4.



Halevi and Krawczyk                                             [Page 6]

Internet Draft        draft-irtf-cfrg-rhash-01.txt      October 18, 2007

3 Building Signatures using RMX

   The main purpose of randomized hashing, and specifically the RMX
   transform, is for use with digital signatures where RMX may preserve
   the security of the signatures even in the presence of off-line
   collision attacks.

   To compute a signature on a message M using the RMX transform with
   hash function H (e.g., SHA1, SHA2) and signature algorithm SIG (e.g.,
   RSA or DSA) one proceeds as follows (we assume pad_length and
   block_length are set by the hash function H):

   1. Choose a random value r as the input salt for the RMX transform
   (the length of r may be specified by an application or by the signer
   itself; in all cases, it has to be in the range [128,block_length]).

   2. Set M' = RMX(r,M) according to the RMX message randomization
   scheme defined in Section 2.

   3. Apply H to M'

   4. Sign the value H(M') using algorithm SIG to obtain a signature s.

   5. Transmit the salt r, message M and signature s to the receiving
   side.

   NOTE: For block-based iterative hash functions such as Merkle-Damgard
   Steps 2 and 3 are block-wise computations and can be interleaved (or
   pipelined). In these cases there is no need to wait for the full
   message M' to be computed out of r and M before starting the H
   computation. In a typical implementation one feeds each block of M
   into the RMX computation and then feeds the resultant block of M'
   into the hash function H.

   The verification procedure is defined similarly to the above: it
   receives the three elements r, M, s, computes M' = RMX(r,M) and
   provides the (randomized) message M' and signature s to the
   verification procedure (as before the RMX and hash computations can
   be pipelined).

   Note that the above procedure can be used with any signature scheme
   that follows the hash-then-sign paradigm including the two major
   standards: RSA (both deterministic and PSS encoding) [PKCS1] and
   DSS [DSS].

   To support RMX-enabled signatures as above, an application needs to
   satisfy two requirements: (1) the ability of the signer (not the
   verifier) to generate the random salt r; and (2) the ability of the
   application to accommodate the transmission of r. We expect most
   applications to meet requirement (1), and even more so given the
   increasing capabilities of computing devices. In particular, most
   cryptographic applications already require the ability to generate
   (pseudo) random bits for key generation, IV's, nonces, or

Halevi and Krawczyk                                             [Page 7]

Internet Draft        draft-irtf-cfrg-rhash-01.txt      October 18, 2007

   probabilistic signatures such as DSS. Moreover, note that it is only
   the signer that needs to generate randomness, not the verifier (see
   Section 5). As for (2), a great majority of applications can afford
   the sending of a few extra bytes of salt in addition to a message and
   signature. While different applications can accommodate the sending
   of the salt in different ways, we discuss a general mechanism that
   may work for many different application in Section 4. A few more
   comments are in order here:

   1. A receiver of a signature can only start to hash the message after
   it knows the salt. Hence, in applications where buffering the entire
   incoming message is impractical, it is necessary to send the salt
   before the message (rather than with the signature itself that is
   often transmitted after the message).

   Also, we stress that an application using RMX must ensure that an
   attacker cannot choose, or influence, the contents of the message to
   be signed after seeing the salt. Hence the salt, even if sent before
   the message, will be sent to the verifier only after the message to
   be signed has been fully determined.

   2. For extremely bandwidth-limited applications, one can sometime
   save on bandwidth by including the salt in the signature (even if it
   means sending the salt after the message). For example, with DSS
   signatures one can re-use the random component r = g^k that already
   exists in the signature as the hashing salt, thus preserving the
   original data size. It should be noted, however, that this means that
   the quantity r = g^k must be computed before computing the message
   digest (and kept secret until the message with which r will be used
   is fully determined).

   In the case of RSA-PSS [PKCS1] an approach similar to DSS can be used
   to save bandwidth (here the randomness used internally by the
   signature can be recovered by the recipient of the signature via the
   RSA-verification operation). The situation is more problematic with
   the deterministic RSA encoding of PKCS#1 v1.5 [PKCS1]; here the only
   way to preserve bandwidth is to include the salt r under the
   signature itself. That is, instead of applying the RSA operation
   solely to the result of the randomized hash operation one applies it
   to the concatenation of this result and the salt r. In this way, the
   recipient of the signature can recover the salt via the
   RSAverification procedure. This, however, requires a change in the
   message encoding of PKCS#1 v1.5, and hence less appealing as a
   general solution.

   3. Using an independent salt value has the additional advantage that
   it allows for the pre-computation of the randomized hash value. That
   is, one can choose r, compute d = H(RMX(r,M)) and store the triple
   (r, M, d), such that upon a request for a signature on M one computes
   the signature directly on the pre-computed d. Also, using an
   independent salt value supports multi-level hashing which is
   required, for example, in XML signatures [RMX].


Halevi and Krawczyk                                             [Page 8]

Internet Draft        draft-irtf-cfrg-rhash-01.txt      October 18, 2007

   4. One cannot overstate the importance of not disclosing the value of
   the salt r before a message to be signed is fully determined.
   However, while it will be the general case that a new random string
   is used for each signature, there is no impediment to reusing the
   same r for several messages as long as r is not disclosed before all
   these messages are fully determined (this may be appropriate for
   applications, maybe a CA, that sign a batch of messages before
   disclosing the signatures).

4 Implementation Notes

   The fact that one can use RMX while leaving the hash-then-sign
   module intact makes its adoption and implementation quite straight-
   forward. Our implementation experience shows that adding support for
   RMX to existing applications and software libraries entails the same
   complexity as adding a new deterministic hash function (e.g. SHA256).

   The one issue that requires attention is the transmission of the
   salt r, which needs to be done at the application level. Several
   experimental implementations of RMX deal with this issue. These
   include works of Boneh and Shao [BS06] for the NSS Library and the
   Firefox browser, by us [RMX] for the openssl library, and by McIntosh
   for XML signatures [RMX].  All these projects implemented RMX-enabled
   X.509 certificates, and in particular needed to specify how the salt
   r is communicated from the signer to the verifier of the certificate.
   The two alternatives that were considered are as follows:

   THE SALT AS PART OF THE SIGNATURE. A natural solution for
   transporting the salt with a signature is to append the salt to the
   signature itself (i.e., in this case the salt becomes an additional
   component of the signature string). As discussed in Section 3, this
   approach may require the buffering of the whole message at the sender
   or receiver, and hence it is less desirable as a general solution. In
   the specific case of certificates this buffering may be practical, in
   which case this transport solution is the one to require the smallest
   change to the certificate-handling code.

   THE SALT AS AN ALGORITHM PARAMETER. The projects mentioned above
   chose to implement a more general, and slightly more involved,
   option; i.e., to specify the salt as a parameter of the signature's
   algorithm identifier. For example, the certificate structure as
   defined in X.509 and RFC 3280 (PKIX) includes an AlgorithmIdentifier,
   whose ASN.1 definition is as follows:

   AlgorithmIdentifier ::= SEQUENCE {
        algorithm              OBJECT IDENTIFIER,
        parameters             ANY DEFINED BY algorithm OPTIONAL }

   This structure has an (optional) parameter that can be used to carry
   the value of the salt. One can define the signature algorithms that
   use RMX (e.g., OBJ rmxsha1WithRSAEncryption) to have a parameter of
   type OCTET STRING. The signing function would copy the salt that it
   used for hashing into that parameter, and the verification code will

Halevi and Krawczyk                                             [Page 9]

Internet Draft        draft-irtf-cfrg-rhash-01.txt      October 18, 2007

   extract it from there. (See above references for more details.)

   NOTE. A previous version of this document required to concatenate the
   salt r to the result of the randomized hash operation before signing;
   this resulted in the need to change encoding schemes for standards
   such as PKCS1. The current specification simplifies the scheme (and
   eases adoption) by dropping this requirement without jeopardizing
   the security.

5 Security Considerations

   This whole document is about security. Here we highlight some
   important rules to observe, and comment on some of the analysis work
   that backs up the security of the proposed mechanisms.

   Any application that implements digital signatures using the
   randomized hashing scheme described here must ensure that an attacker
   cannot choose, or influence, the contents of a message to be signed
   after seeing the random salt. In particular, the salt must be
   unpredictable by the attacker before the message is determined.
   Consequently, the input r to the RMX function must be generated by a
   strong random number generator, or by a cryptographically-strong
   pseudo-random generator, and should be of length at least 128 bits
   but no more than the parameter block_length. Note that it is only the
   signer who generates randomness; the verifier receives it as part of
   the signature (or message). For example, in the important case of
   certificates, the CA will generate randomness to sign a certificate
   but verifiers of the certificate (which may be many and computatio-
   nally restricted) do not need to generate randomness at all.

   We note that while it would have been advantageous to specify the RMX
   transform independently of any parameter of the hash function (such
   as in the "default" specification of RMX discussed at the end of
   Section 2), there are substantial advantages to synchronizing the RMX
   parameters with those of the underlying hash function. Specifically,
   for block-based iterative hash functions, such as Merkle-Damgard, it
   is best to align the (extended) salt r' defined by RMX with a full
   block of the hash function; this ensures that the r' value, that
   occupies the first block of M', is hashed into a randomized IV before
   starting the processing of the message m0 (this is not the case if r'
   and the beginning of m0 occupy the same block). Another reason to
   have the length of r' (i.e., block_length) be the same as a hash
   block length is that it allows for a more efficient implementation of
   RMX in the case of iterative hash functions (as noted in Section 2).

   Another hash-dependent parameter is the amount of padding RMX appends
   to message M, and which is determined by the function pad_length.
   This is best exemplified (and motivated) using Merkle-Damgard (M-D)
   hash functions. Recall that M-D functions specify a padding rule in
   which a pad of the form 100...0 is added to the end of a message
   followed by an encoding of the message length. When applied to a
   message whose length is (close to) an integral number of blocks this
   padding results in the addition of a full padding block by the M-D

Halevi and Krawczyk                                            [Page 10]

Internet Draft        draft-irtf-cfrg-rhash-01.txt      October 18, 2007

   processing. In the case of RMX, this padding block is added to M'
   after the RMX procedure has finished, and hence this added block is
   NOT randomized at all. Similarly, a message of length just slightly
   over an integral number of blocks will be padded by a M-D function to
   a full block, where only very few bits of that last block will be
   randomized by RMX. In these cases, the attacker has a predictable
   (i.e., little randomized) block to attack, thus reducing the level of
   security offered by the randomization scheme. We take care of these
   issues, i.e., maximizing the number of bits randomized by RMX in the
   last block, via the function pad_length. Specifically, for the case
   of M-D functions, this maximization is achieved using the
   implementation of pad_length presented at the end of Section 2.

   In general, it is best to consider the randomized hashing mechanism
   specified in this document as a mode of operation of hash functions.
   In this case, the dependency on specific parameters of the underlying
   hash function is natural and appropriate (similarly to the case of
   CBC mode where both the padding and the IV have lengths that depend
   on the block length of the underlying block cipher).

   ANALYSIS: The randomized hashing mechanism specified here is
   presented and analyzed in [HK06] (in that paper this scheme is
   referred to as the "eTCR construction"; the RMX scheme itself,
   instantiated for M-D functions, is presented in the full web version
   of the paper). We refer the reader to that document for the
   mathematical analysis. In a nutshell, it is shown that finding
   off-line collisions against the underlying hash function (as in
   recent attacks) is insufficient to break RMX-based signatures.
   Instead, an attacker against such signatures needs to solve a
   cryptanalytical problem much harder than finding off-line collisions,
   namely, one that is equivalent to a variant of second-preimage
   finding (called e-SPR in [HK06]). Thus, RMX provides a "safety net"
   for digital signatures in the case that the hash function in use
   turns out to be vulnerable to collision attacks. (It may be worth
   pointing out that if a hash function is collision resistant then the
   same hash function used with RMX is also e-SPR; hence, RMX schemes
   can only add security to a signature scheme, never decrease it.)

Acknowledgments.

   We thank Michael McIntosh, Dan Boneh and Weidong Shao for their RMX
   implementation work, and Mark Davis and Suresh Chari for their
   assistance with our own implementation. We are also indebted to Quynh
   Dang for documenting RMX for NIST and for many fruitful discussions
   on the subject.









Halevi and Krawczyk                                            [Page 11]

Internet Draft        draft-irtf-cfrg-rhash-01.txt      October 18, 2007

References

   [BR05] Steven M. Bellovin and Eric K. Rescorla, "Deploying a New Hash
          Algorithm", NDSS'06.
          http://www.cs.columbia.edu/~smb/papers/new-hash.pdf

   [BS06] Dan Boneh and Weidong Shao, "Randomized Hashing for Digital
          Certificates: Halevi-Krawczyk Hash, An implementation in
          Firefox". http://crypto.stanford.edu/firefox-rhash/

   [DSS]  Digital Signature Standard (DSS), FIPS 186, May 1994.

   [HK06] Shai Halevi and Hugo Krawczyk, "Strengthening Digital
          Signatures via Randomized Hashing", Crypto'2006.
          http://www.ee.technion.ac.il/~hugo/rhash/

   [RMX]  Shai Halevi and Hugo Krawczyk, "The RMX Transform and Digital
          Signatures". http://www.ee.technion.ac.il/~hugo/rhash/.

   [NIST] "Randomized Hashing Digital Signatures", NIST Special
          Publication SP 800-106, Draft, July 2007

   [PKCS1] PKCS #1 v2.1: RSA Cryptography Standard, RSA Laboratories,
           June 14, 2002


Full Copyright Statement

   Copyright (C) The IETF Trust (2007).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.













Halevi and Krawczyk                                           [Page 12]


Html markup produced by rfcmarkup 1.108, available from http://tools.ietf.org/tools/rfcmarkup/