idnits 2.17.1 draft-irtf-cfrg-rhash-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 13. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 609. ** The document seems to lack an RFC 3979 Section 5, para. 1 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 2 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 3 IPR Disclosure Invitation. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack an Authors' Addresses Section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 464: '... ANY DEFINED BY algorithm OPTIONAL }...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 18, 2007) is 6035 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. 'BR05' -- Possible downref: Non-RFC (?) normative reference: ref. 'BS06' -- Possible downref: Non-RFC (?) normative reference: ref. 'DSS' -- Possible downref: Non-RFC (?) normative reference: ref. 'HK06' -- Possible downref: Non-RFC (?) normative reference: ref. 'RMX' -- Possible downref: Non-RFC (?) normative reference: ref. 'NIST' -- Possible downref: Non-RFC (?) normative reference: ref. 'PKCS1' Summary: 8 errors (**), 0 flaws (~~), 2 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 CFRG S. Halevi (IBM) 2 Internet-Draft H. Krawczyk (IBM) 3 Expires: April 18, 2008 October 18, 2007 5 Strengthening Digital Signatures via Randomized Hashing 6 draft-irtf-cfrg-rhash-01.txt 8 Status of this Memo 10 By submitting this Internet-Draft, each author represents that any 11 applicable patent or other IPR claims of which he or she is aware 12 have been or will be disclosed, and any of which he or she becomes 13 aware will be disclosed, in accordance with Section 6 of BCP 79. 15 Internet-Drafts are working documents of the Internet Engineering 16 Task Force (IETF), its areas, and its working groups. Note that 17 other groups may also distribute working documents as Internet- 18 Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet-Drafts as reference 23 material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt. 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 Copyright (C) The IETF Trust (2007). 33 Abstract 35 This document describes a randomized hashing scheme consisting of a 36 simple message randomization transform that when used as a front-end 37 to regular hash-then-sign signature schemes, such as RSA and DSS, 38 frees these signatures from their current vulnerability to off-line 39 collision attacks against the underlying hash function. The proposed 40 mechanism can work with any hash function as-is and requires no 41 change to the underlying signature algorithm. Incorporating this 42 mechanism into existing applications requires changes that are 43 comparable in their complexity to accommodating a new (deterministic) 44 hash function such as SHA-256. 46 Visit http://www.ee.technion.ac.il/~hugo/rhash/ for more information 47 and updates on this work. 49 1 Introduction 51 The recent collision attacks against popular hash functions have a 52 profound effect on the security of some applications of these 53 functions, most notably digital signatures. In this document we 54 propose a randomized mode of operation for hash functions that when 55 used in conjunction with standardized hash-then-sign signature 56 schemes (such as RSA or DSS) frees these schemes from their current 57 essential dependency on full collision resistance. This mode of 58 operation can work with any hash function and requires no change to 59 the underlying signature algorithms. It consists of a simple message 60 randomization transform, called RMX, which is fully specified in this 61 document and used as a front-end to existing hash-then-sign signature 62 schemes. The analysis in [HK06] shows that breaking a signature 63 scheme that uses RMX requires solving a cryptanalytical problem 64 related to finding second pre-images in the underlying compression 65 function, and hence significantly harder than simply finding 66 (off-line) collisions as in current attacks against standard 67 signature schemes. 69 The full specification of RMX is presented in Section 2. In a 70 nutshell, RMX prepends to the message a random string ("salt") of one 71 block, and then XORs (exclusive-or) the same random string with 72 every block of the message itself (where a "block" is of the length 73 specified by the underlying hash function or, if such block size is 74 not defined by the hash function, it is the length of the salt). 75 That is, if M=(M1, ...,Mn) where the Mi's are message blocks then: 77 RMX(r,M) = (r, M1 XOR r, ..., Mn XOR r). 79 We note that the full specification of RMX includes a simple padding 80 rule for the last message block; also, to save bandwidth and 81 randomness, the scheme accommodates salt strings shorter than a full 82 message block. RMX can be implemented either as a simple front-end 83 interface to the iterated hash function, or it can be integrated with 84 typical implementations of digest functions (in particular, 85 Merkle-Damgard functions such as the SHA family) that read the 86 message block by block and feed these successive blocks into the 87 compression function. 89 RMX can be used with any hash-then-sign scheme by replacing the 90 message M in the original signature scheme with RMX(r,M), i.e., 91 instead of SIG(H(M)) a signature is computed as SIG(H(RMX(r,M))). 92 The salt r is generated for each signature by the signer and 93 transmitted to the verifier together with the message and signature. 94 The verifier uses the regular verification procedure where the 95 original digest function is applied to RMX(r,M) rather than to M. 96 Note that only the signer needs to generate randomness, the verifier 97 receives it with the message/signature. As said, off-line collision 98 search is useless against a signature scheme that uses RMX. Rather, 99 to break the signatures the attacker needs to solve a cryptanalytical 100 problem close to finding second preimages (which is a much harder 101 task than finding collisions, and it has to be done on a 102 per-signature basis rather than off-line). Importantly, to gain this 103 security advantage the value of r must be unpredictable to the 104 attacker until the full content of the message to be signed is 105 determined; we recommend that the length of r be at least 128 bits. 107 The use of RMX and its application to signatures do not depend on the 108 way the salt r is transmitted; therefore, different applications may 109 choose different ways to transport r. This is analogous to the use of 110 the IV in CBC encryption: the definition of CBC specifies how to use 111 a block cipher to encrypt any-length message given the value of an 112 IV, but leaves it up to the application to decide how to transmit the 113 IV. In Section 4 we report on some experimental implementations of 114 RMX (openssl, NSS/Firefox, and XML signatures), and discuss some 115 options for the transport of the salt in applications using RMX. In 116 particular, we suggest a mechanism that can be shared by applications 117 that use algorithm identifiers (as per X.509), namely, transporting 118 the salt as a parameter of the algorithm identifier. 120 It is important to note that the use of RMX in the context of digital 121 signatures does not require changes in signature standards such as 122 PKCS#1 (RSA) or FIPS 186 (DSS). Furthermore, an important conclusion 123 of initial implementation experience with RMX is that the complexity 124 of implementing and deploying RMX in the context of digital 125 signatures is comparable to the effort needed to upgrade existing 126 systems to use a new deterministic hash function, such as SHA256. 127 Moreover, once the mechanisms are in place to deal with such upgrade 128 (cf. [BR05]), supporting RMX becomes a relatively simple matter (see 129 Section 4 and the references there). 131 We stress that our proposal is not intended as an alternative to the 132 search for new, stronger hash functions to replace SHA-1 and MD5, but 133 it is rather intended to complement this effort by providing a 134 "safety net" for digital signatures in case a hash function in use is 135 later found to be weaker than believed initially. Given our limited 136 understanding of the best ways to build collision resistant hash 137 functions, prudent engineering principles call for building 138 cryptographic primitives that rely as little as possible on the 139 strength of hash functions. Our work addresses this principle in the 140 context of digital signatures and as such it resembles the effect of 141 the HMAC design in the message authentication area. 143 We refer the reader to the paper by these authors [HK06] for a more 144 extensive description and rationale of the design of RMX, as well as 145 an analysis of the cryptographic strength of the scheme (in that 146 paper the scheme specified here, namely, applying RMX to the message 147 before inputting it to the hash function, is referred to as the 148 "eTCR construction"). 150 COMPATIBILITY WITH NIST's RANDOMIZED HASHING PUBLICATION [NIST]. 151 The present document is somewhat wider in scope than [NIST] which 152 defines the same randomized hashing transform but provides less 153 implementation guidance. Also, the specification here of the central 154 RMX transform is slightly more general than [NIST], in particular it 155 allows for some hash-specific optimizations (especially for 156 Merkle-Damgard and related hash functions). We anticipate that the 157 final specifications of RMX in both documents (here and [NIST]) will 158 be identical. 160 IETF SCOPE. This Internet Draft is offered to the IETF community 161 for consideration for standardization and adoption in protocols whose 162 security heavily relies on digital signatures. The need for 163 randomized hashing is especially acute in applications (e.g., PKIX, 164 S/Mime) where non-repudiation or third-party-verifiability are 165 crucial; however, it is recommended also as a general way of 166 strengthening signatures in other applications. In particular, 167 protocols that support hash agility (newer TLS versions, for example) 168 should make provisions for the future use of randomized hashing (see 169 Section 4 for some implementation guidance). 171 Visit http://www.ee.technion.ac.il/~hugo/rhash/ for more information 172 and updates on this work. 174 2 The Message Randomization Scheme RMX 176 The RMX message randomization procedure is the core of the randomized 177 hashing scheme and it is specified next. RMX takes as input a message 178 M (to be signed) and a random salt value r, and outputs M', the 179 transformed message that will be input into the hash-then-sign 180 signature module. 182 RMX should be seen as a mode of operation for hash functions, and as 183 such it may depend on some of the parameters of the underlying hash 184 function such as a block length or the hash function's padding 185 mechanism. Specifically, the RMX definition uses two parameters, 186 block_length and pad_length, that may depend on the underlying hash 187 function. 189 The first, block_length, is used by RMX to determine the expansion of 190 the input salt r into an internal salt value r'. RMX sets 191 block_length to the block length of the underlying hash function 192 (e.g., it will be 512 for SHA-256). However, if this hash function 193 does not define a block length (or if this length is less that 128 194 bits) then block_length is set to the length of the salt value r 195 input to RMX. (This provision for a non-blockwise hash function is 196 due to NIST's desire [NIST] to accommodate any, possibly 197 unconventional, hash function that may emerge in the future.) 199 The parameter pad_length is used by RMX to determine the number of 200 bits with which RMX pads the input message (RMX performs an internal 201 padding in addition to any padding that may be defined by the 202 underlying hash function). In all cases, pad_length is computed as a 203 function of the length of the input message M (we denote this length 204 by |M|) and possibly also as a function of block_length. 206 After the description of RMX below, we present two concrete 207 instantiations of pad_length: a generic function that does not assume 208 any structure on the underlying hash function (this is the same as 209 the RMX mechanism defined in [NIST]), and a different instantiation 210 that is optimized for Merkle-Damgard hash functions (where a block 211 length is well defined). We expect the latter instantiation to be 212 used with contemporary hash functions such as SHA-1 and SHA-2. 213 (See discussion in Section 5 regarding the security advantages of 214 using the second instantiation when the underlying hash function is a 215 Merkle-Damgard iterated hash function.) 217 Specification of the RMX transform. 219 Parameters: 221 block_length // Length of the internal salt value r' used in the 222 // algorithm 223 pad_length // A function to determine the number L of padding 224 // bits used internally by RMX (depends on |M|). 226 Input: 228 Message M, Salt r // r is random of size at least 128 bits 230 Output: 232 Randomized Message M' // input to hash function and signature 234 1. Let r' be r concatenated with itself as many times as needed 235 (last copy possibly truncated) to cover block_length bits 237 2. Let L = pad_length(|M|) 239 3. Define m to be a message obtained by concatenating the original 240 message M, followed by L zeros and by two bytes containing the 241 number L written in big-endian notation. That is: 243 m = M || 0^L || L 245 4. Define R to be the a string of the same length as m (i.e., 246 |M|+L+16 bits) composed by concatenating r' with itself as many 247 times as needed (with the last copy of r' possibly truncated) 249 R = (r' || r' || ... || r' || r') truncated to |M|+L+16 bits 251 5. Define m' to be the bitwise XOR of m and R. That is: 253 m' = m XOR R 255 6. Define M' to be the concatenation of r' followed by m'. That is: 257 M' = r' || m' 259 7. Output M' 260 NOTE: While the description of RMX above treats the input message M 261 as one unit, actual implementations of RMX do not need to buffer the 262 whole message but can rather (as in a streaming scenario) read and 263 process M block by block. The same is true for the output message M' 264 that can be output block by block. This is particularly convenient 265 when inputting M' into a hash function that reads its input 266 block-by-block; in this case the RMX and hash computation can be 267 pipelined. Also worth noting is that since the parameter (function) 268 pad_length depends on the length of M, its value will usually be 269 computed as part of the RMX procedure after the whole message is 270 received. 272 Next, we present two possible instantiations of the parameters pad 273 length and block_length. 275 GENERIC PARAMETERS. This definition can be used with any hash 276 function regardless of its structure or iteration. It corresponds to 277 the current randomized hashing definition in [NIST]. 279 Set block_length = |r| (i.e., r'=r). 280 pad_length is set to: 281 0 if |r'| <= 16+|M| 282 |r'|-(16+|M|) otherwise. 284 PARAMETERS FOR MERKLE-DAMGARD HASHING. This specification of the 285 parameters is intended for Merkle-Damgard hash functions (and related 286 iterated functions) and it provides the maximal benefits of RMX for 287 such functions (by maximizing the number of random bits XOR-ed to the 288 last padded block). The specification is optimized by setting r' to 289 be of the length of a hash block. We use b to denote this block 290 length and c to denote the number of padding bits added by the 291 underlying hash function (for the so-called MD-strengthening). 292 For example, b=512, c=64 in SHA-256 and b=1024, c=128 in SHA-512. 293 Specifically, in the Merkle-Damgard case we define: 295 Set block_length to b. 296 Let b' = |M| mod b and b''=b'+c+24. 297 pad_length is set to: 298 2b-b'' if b'' > b 299 b-b'' otherwise 301 (The first case corresponds to the cases where the hash function adds 302 a full new padding block and hence pad_length = (b-b')+(b-24-c); 303 in the other case pad_length = b-(b'+c+24)).) 305 IMPLEMENTATION. As we already said, the definition of RMX allows for 306 an implementation that acts as a simple front-end interface to the 307 iterated hash function, or it can be integrated with typical 308 implementations of digest functions that read the message block by 309 block and feed these successive blocks into the compression function. 310 We discuss more implementation issues in Section 4. 312 3 Building Signatures using RMX 314 The main purpose of randomized hashing, and specifically the RMX 315 transform, is for use with digital signatures where RMX may preserve 316 the security of the signatures even in the presence of off-line 317 collision attacks. 319 To compute a signature on a message M using the RMX transform with 320 hash function H (e.g., SHA1, SHA2) and signature algorithm SIG (e.g., 321 RSA or DSA) one proceeds as follows (we assume pad_length and 322 block_length are set by the hash function H): 324 1. Choose a random value r as the input salt for the RMX transform 325 (the length of r may be specified by an application or by the signer 326 itself; in all cases, it has to be in the range [128,block_length]). 328 2. Set M' = RMX(r,M) according to the RMX message randomization 329 scheme defined in Section 2. 331 3. Apply H to M' 333 4. Sign the value H(M') using algorithm SIG to obtain a signature s. 335 5. Transmit the salt r, message M and signature s to the receiving 336 side. 338 NOTE: For block-based iterative hash functions such as Merkle-Damgard 339 Steps 2 and 3 are block-wise computations and can be interleaved (or 340 pipelined). In these cases there is no need to wait for the full 341 message M' to be computed out of r and M before starting the H 342 computation. In a typical implementation one feeds each block of M 343 into the RMX computation and then feeds the resultant block of M' 344 into the hash function H. 346 The verification procedure is defined similarly to the above: it 347 receives the three elements r, M, s, computes M' = RMX(r,M) and 348 provides the (randomized) message M' and signature s to the 349 verification procedure (as before the RMX and hash computations can 350 be pipelined). 352 Note that the above procedure can be used with any signature scheme 353 that follows the hash-then-sign paradigm including the two major 354 standards: RSA (both deterministic and PSS encoding) [PKCS1] and 355 DSS [DSS]. 357 To support RMX-enabled signatures as above, an application needs to 358 satisfy two requirements: (1) the ability of the signer (not the 359 verifier) to generate the random salt r; and (2) the ability of the 360 application to accommodate the transmission of r. We expect most 361 applications to meet requirement (1), and even more so given the 362 increasing capabilities of computing devices. In particular, most 363 cryptographic applications already require the ability to generate 364 (pseudo) random bits for key generation, IV's, nonces, or 365 probabilistic signatures such as DSS. Moreover, note that it is only 366 the signer that needs to generate randomness, not the verifier (see 367 Section 5). As for (2), a great majority of applications can afford 368 the sending of a few extra bytes of salt in addition to a message and 369 signature. While different applications can accommodate the sending 370 of the salt in different ways, we discuss a general mechanism that 371 may work for many different application in Section 4. A few more 372 comments are in order here: 374 1. A receiver of a signature can only start to hash the message after 375 it knows the salt. Hence, in applications where buffering the entire 376 incoming message is impractical, it is necessary to send the salt 377 before the message (rather than with the signature itself that is 378 often transmitted after the message). 380 Also, we stress that an application using RMX must ensure that an 381 attacker cannot choose, or influence, the contents of the message to 382 be signed after seeing the salt. Hence the salt, even if sent before 383 the message, will be sent to the verifier only after the message to 384 be signed has been fully determined. 386 2. For extremely bandwidth-limited applications, one can sometime 387 save on bandwidth by including the salt in the signature (even if it 388 means sending the salt after the message). For example, with DSS 389 signatures one can re-use the random component r = g^k that already 390 exists in the signature as the hashing salt, thus preserving the 391 original data size. It should be noted, however, that this means that 392 the quantity r = g^k must be computed before computing the message 393 digest (and kept secret until the message with which r will be used 394 is fully determined). 396 In the case of RSA-PSS [PKCS1] an approach similar to DSS can be used 397 to save bandwidth (here the randomness used internally by the 398 signature can be recovered by the recipient of the signature via the 399 RSA-verification operation). The situation is more problematic with 400 the deterministic RSA encoding of PKCS#1 v1.5 [PKCS1]; here the only 401 way to preserve bandwidth is to include the salt r under the 402 signature itself. That is, instead of applying the RSA operation 403 solely to the result of the randomized hash operation one applies it 404 to the concatenation of this result and the salt r. In this way, the 405 recipient of the signature can recover the salt via the 406 RSAverification procedure. This, however, requires a change in the 407 message encoding of PKCS#1 v1.5, and hence less appealing as a 408 general solution. 410 3. Using an independent salt value has the additional advantage that 411 it allows for the pre-computation of the randomized hash value. That 412 is, one can choose r, compute d = H(RMX(r,M)) and store the triple 413 (r, M, d), such that upon a request for a signature on M one computes 414 the signature directly on the pre-computed d. Also, using an 415 independent salt value supports multi-level hashing which is 416 required, for example, in XML signatures [RMX]. 418 4. One cannot overstate the importance of not disclosing the value of 419 the salt r before a message to be signed is fully determined. 420 However, while it will be the general case that a new random string 421 is used for each signature, there is no impediment to reusing the 422 same r for several messages as long as r is not disclosed before all 423 these messages are fully determined (this may be appropriate for 424 applications, maybe a CA, that sign a batch of messages before 425 disclosing the signatures). 427 4 Implementation Notes 429 The fact that one can use RMX while leaving the hash-then-sign 430 module intact makes its adoption and implementation quite straight- 431 forward. Our implementation experience shows that adding support for 432 RMX to existing applications and software libraries entails the same 433 complexity as adding a new deterministic hash function (e.g. SHA256). 435 The one issue that requires attention is the transmission of the 436 salt r, which needs to be done at the application level. Several 437 experimental implementations of RMX deal with this issue. These 438 include works of Boneh and Shao [BS06] for the NSS Library and the 439 Firefox browser, by us [RMX] for the openssl library, and by McIntosh 440 for XML signatures [RMX]. All these projects implemented RMX-enabled 441 X.509 certificates, and in particular needed to specify how the salt 442 r is communicated from the signer to the verifier of the certificate. 443 The two alternatives that were considered are as follows: 445 THE SALT AS PART OF THE SIGNATURE. A natural solution for 446 transporting the salt with a signature is to append the salt to the 447 signature itself (i.e., in this case the salt becomes an additional 448 component of the signature string). As discussed in Section 3, this 449 approach may require the buffering of the whole message at the sender 450 or receiver, and hence it is less desirable as a general solution. In 451 the specific case of certificates this buffering may be practical, in 452 which case this transport solution is the one to require the smallest 453 change to the certificate-handling code. 455 THE SALT AS AN ALGORITHM PARAMETER. The projects mentioned above 456 chose to implement a more general, and slightly more involved, 457 option; i.e., to specify the salt as a parameter of the signature's 458 algorithm identifier. For example, the certificate structure as 459 defined in X.509 and RFC 3280 (PKIX) includes an AlgorithmIdentifier, 460 whose ASN.1 definition is as follows: 462 AlgorithmIdentifier ::= SEQUENCE { 463 algorithm OBJECT IDENTIFIER, 464 parameters ANY DEFINED BY algorithm OPTIONAL } 466 This structure has an (optional) parameter that can be used to carry 467 the value of the salt. One can define the signature algorithms that 468 use RMX (e.g., OBJ rmxsha1WithRSAEncryption) to have a parameter of 469 type OCTET STRING. The signing function would copy the salt that it 470 used for hashing into that parameter, and the verification code will 471 extract it from there. (See above references for more details.) 473 NOTE. A previous version of this document required to concatenate the 474 salt r to the result of the randomized hash operation before signing; 475 this resulted in the need to change encoding schemes for standards 476 such as PKCS1. The current specification simplifies the scheme (and 477 eases adoption) by dropping this requirement without jeopardizing 478 the security. 480 5 Security Considerations 482 This whole document is about security. Here we highlight some 483 important rules to observe, and comment on some of the analysis work 484 that backs up the security of the proposed mechanisms. 486 Any application that implements digital signatures using the 487 randomized hashing scheme described here must ensure that an attacker 488 cannot choose, or influence, the contents of a message to be signed 489 after seeing the random salt. In particular, the salt must be 490 unpredictable by the attacker before the message is determined. 491 Consequently, the input r to the RMX function must be generated by a 492 strong random number generator, or by a cryptographically-strong 493 pseudo-random generator, and should be of length at least 128 bits 494 but no more than the parameter block_length. Note that it is only the 495 signer who generates randomness; the verifier receives it as part of 496 the signature (or message). For example, in the important case of 497 certificates, the CA will generate randomness to sign a certificate 498 but verifiers of the certificate (which may be many and computatio- 499 nally restricted) do not need to generate randomness at all. 501 We note that while it would have been advantageous to specify the RMX 502 transform independently of any parameter of the hash function (such 503 as in the "default" specification of RMX discussed at the end of 504 Section 2), there are substantial advantages to synchronizing the RMX 505 parameters with those of the underlying hash function. Specifically, 506 for block-based iterative hash functions, such as Merkle-Damgard, it 507 is best to align the (extended) salt r' defined by RMX with a full 508 block of the hash function; this ensures that the r' value, that 509 occupies the first block of M', is hashed into a randomized IV before 510 starting the processing of the message m0 (this is not the case if r' 511 and the beginning of m0 occupy the same block). Another reason to 512 have the length of r' (i.e., block_length) be the same as a hash 513 block length is that it allows for a more efficient implementation of 514 RMX in the case of iterative hash functions (as noted in Section 2). 516 Another hash-dependent parameter is the amount of padding RMX appends 517 to message M, and which is determined by the function pad_length. 518 This is best exemplified (and motivated) using Merkle-Damgard (M-D) 519 hash functions. Recall that M-D functions specify a padding rule in 520 which a pad of the form 100...0 is added to the end of a message 521 followed by an encoding of the message length. When applied to a 522 message whose length is (close to) an integral number of blocks this 523 padding results in the addition of a full padding block by the M-D 524 processing. In the case of RMX, this padding block is added to M' 525 after the RMX procedure has finished, and hence this added block is 526 NOT randomized at all. Similarly, a message of length just slightly 527 over an integral number of blocks will be padded by a M-D function to 528 a full block, where only very few bits of that last block will be 529 randomized by RMX. In these cases, the attacker has a predictable 530 (i.e., little randomized) block to attack, thus reducing the level of 531 security offered by the randomization scheme. We take care of these 532 issues, i.e., maximizing the number of bits randomized by RMX in the 533 last block, via the function pad_length. Specifically, for the case 534 of M-D functions, this maximization is achieved using the 535 implementation of pad_length presented at the end of Section 2. 537 In general, it is best to consider the randomized hashing mechanism 538 specified in this document as a mode of operation of hash functions. 539 In this case, the dependency on specific parameters of the underlying 540 hash function is natural and appropriate (similarly to the case of 541 CBC mode where both the padding and the IV have lengths that depend 542 on the block length of the underlying block cipher). 544 ANALYSIS: The randomized hashing mechanism specified here is 545 presented and analyzed in [HK06] (in that paper this scheme is 546 referred to as the "eTCR construction"; the RMX scheme itself, 547 instantiated for M-D functions, is presented in the full web version 548 of the paper). We refer the reader to that document for the 549 mathematical analysis. In a nutshell, it is shown that finding 550 off-line collisions against the underlying hash function (as in 551 recent attacks) is insufficient to break RMX-based signatures. 552 Instead, an attacker against such signatures needs to solve a 553 cryptanalytical problem much harder than finding off-line collisions, 554 namely, one that is equivalent to a variant of second-preimage 555 finding (called e-SPR in [HK06]). Thus, RMX provides a "safety net" 556 for digital signatures in the case that the hash function in use 557 turns out to be vulnerable to collision attacks. (It may be worth 558 pointing out that if a hash function is collision resistant then the 559 same hash function used with RMX is also e-SPR; hence, RMX schemes 560 can only add security to a signature scheme, never decrease it.) 562 Acknowledgments. 564 We thank Michael McIntosh, Dan Boneh and Weidong Shao for their RMX 565 implementation work, and Mark Davis and Suresh Chari for their 566 assistance with our own implementation. We are also indebted to Quynh 567 Dang for documenting RMX for NIST and for many fruitful discussions 568 on the subject. 570 References 572 [BR05] Steven M. Bellovin and Eric K. Rescorla, "Deploying a New Hash 573 Algorithm", NDSS'06. 574 http://www.cs.columbia.edu/~smb/papers/new-hash.pdf 576 [BS06] Dan Boneh and Weidong Shao, "Randomized Hashing for Digital 577 Certificates: Halevi-Krawczyk Hash, An implementation in 578 Firefox". http://crypto.stanford.edu/firefox-rhash/ 580 [DSS] Digital Signature Standard (DSS), FIPS 186, May 1994. 582 [HK06] Shai Halevi and Hugo Krawczyk, "Strengthening Digital 583 Signatures via Randomized Hashing", Crypto'2006. 584 http://www.ee.technion.ac.il/~hugo/rhash/ 586 [RMX] Shai Halevi and Hugo Krawczyk, "The RMX Transform and Digital 587 Signatures". http://www.ee.technion.ac.il/~hugo/rhash/. 589 [NIST] "Randomized Hashing Digital Signatures", NIST Special 590 Publication SP 800-106, Draft, July 2007 592 [PKCS1] PKCS #1 v2.1: RSA Cryptography Standard, RSA Laboratories, 593 June 14, 2002 595 Full Copyright Statement 597 Copyright (C) The IETF Trust (2007). 599 This document is subject to the rights, licenses and restrictions 600 contained in BCP 78, and except as set forth therein, the authors 601 retain all their rights. 603 This document and the information contained herein are provided on an 604 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 605 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 606 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 607 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 608 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 609 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.