XML Signature Enhancements to Support Randomized Hashing

Shai Halevi¹, Hugo Krawczyk², and Michael McIntosh³

IBM Research

IBM T.J. Watson Research Center

Yorktown Heights, New York, 10598

¹Email: shaih@alum.mit.edu

²Email: hugo@ee.technion.ac.il

³Email: mikemci@us.ibm.com

Prepared for

W3C Workshop on Next Steps for XML Signature and XML Encryption

25-26 September 2007

Abstract. We propose extensions to XML Signature to facilitate the use of Randomized Hashing, a technique that greatly enhances the security of digital signatures in the presence of collision attacks. Existing extensibility mechanisms provided by XML Signature allow the definition of the necessary signature elements and associated processing for implementation of Randomized Hashing. However, interoperability between implementations requires standardization.

Position Statement

Randomized Hashing [RH][SP 800-106] is a mode of operation for cryptographic hash functions intended for use with standard digital signatures without necessitating of any changes in the internals of the underlying hash function (e.g., the SHA family) or in the signature algorithms (e.g., RSA or DSA). The goal is to free practical digital signature schemes from their current reliance on strong collision resistance by basing the security of these schemes on significantly weaker properties of the underlying hash function, thus providing a safety net in case the (current or future) hash functions in use turn out to be less resilient to collision search than initially thought.

The XML Signature [XMLDSIG] provides extensibility points allowing the specification of new algorithms and is particularly well-suited for the implementation of randomized hashing. However, in order for a variety of implementations of any algorithm to be interoperable, they must extend the framework in the same way.

We propose the W3C specify an extension to XML Signature that would facilitate the interoperable use of Randomized Hashing.

Randomized Hashing

Randomized Hashing specifies a randomized mode of operation for hash functions. It can be used with any hash function by adding simple randomization to the input. The effect is increased security (cryptanalysts will have to work much harder to break the resultant signature schemes).

The implementation of Randomized Hashing does not necessitate of any changes to the underlying hash functions (such as SHA-1 or SHA2) or to signature algorithms (such as RSA and DSS) but require changes in signature schemes to allow the specification and processing of a salt value which is used to randomize the input message before feeding it into the message digest and signature algorithms. In some more detail:

Existing signature algorithms work as follows:

To sign a message x (e.g. via RSA)

Set h=H(x), s = RSA⁻¹( encode(h) ), return s as the sig on x

Application of Randomized Hashing to sign a message x works exactly as before except that the message x is first randomized using a random string (a “salt”) r chosen by the signer using a randomization scheme, called RMX, that we sketch next:

r is concatenated with itself as many times as needed to obtain a string r’ of the length of the message x; then x is bitwise XORed with r’ to obtain a string x’; finally, a string x’’ is formed by the concatenation of r and the string x’. The string x’’ is denoted as RMX(r,x).
The signature is the pair (r,s) where s is computed using the standard RSA procedure applied to x’’=RMX(r,x) instead of x, i.e.,

Set h=H(x’’), s = RSA⁻¹( encode(h) )

To break the the existing signature scheme the attacker must either compute RSA⁻¹ or find y≠x s.t. H(x)=H(y). When using randomized hashing, off-line collisions (such as a pair x,y as above) are useless, instead the attacker needs to solve an on-line problem, for each signature. In particular, it is shown in [RH] that this task is as hard as solving a variant of the much harder “second preimage” attack against the hash function.

Extending XML Signature to Support Randomized Hashing

In order to apply randomized hashing to XML signatures one needs to compute the RMX transform prior to the generation of the message digest. The obvious complication in the usage of RMX with XML Signatures is the fact that the signature algorithm is applied to the SignedInfo which is a collection of computed digest values. In this case, the RMX algorithm is also used when computing digest values for each Reference element within the SignedInfo.

The XML Signature standard is very extensible. The SignatureMethod, DigestMethod, Transform, and CanonicalizationMethod elements may all contain information as subelements to be used by the specified algorithm implementation. This provides us with several possibilities for where to place the salt value associated with Signature and MessageDigest generation. In our specific implementation, we have used the SignatureMethod element to provide parameters to the signature algorithm and the DigestMethod element to provide parameters to the digest algorithm. In both instances we use a Salt element to contain the salt value to be used with the RMX algorithm.

Example SignatureMethod:

<ds:SignatureMethod Algorithm="http http://www.w3.org/2000/09/xmldsig#rsa-sha1-rmx ">

<ds:Salt>

n7ebJNarKaZsFVQXea/cRWJCKzE=

</ds:Salt>

</ds:SignatureMethod>

Example DigestMethod:

<ds:DigestMethod Algorithm=" http://www.w3.org/2000/09/xmldsig#sha1-rmx”>

<ds:Salt>

QPps5aXD2G0Z1wOCTltRp0akcpE=

</ds:Salt>

</ds:DigestMethod>

Since Randomized Hashing can be used with any existing message digest or signature algorithm, we propose appending “-rmx” to the existing algorithm identifier.

For example: “http://www.w3.org/2000/09/xmldsig#sha1” becomes “http://www.w3.org/2000/09/xmldsig#sha1-rmx” and “http://www.w3.org/2000/09/xmldsig#rsa-sha1” becomes “http://www.w3.org/2000/09/xmldsig#rsa-sha1-rmx”.

In order to specify the salt value, we propose adding a “Salt” element to the schema as an optional child for both “DigestMethod” and “SignatureMethod”. For example:

</simpleType>

</sequence>

</complexType>

</sequence>

</complexType>

Conclusions

The changes necessary to implement Randomized Hashing with XML Signature are minimal and well worth the security benefits provided by such randomization. Standardization of the necessary algorithm identifiers and XML elements would be a tremendous benefit to implementers. We urge the W3C to specify extensions necessary for interoperable implementation of Randomized Hashing with XML Signatures.

References

[RH] Shai Halevi and Hugo Krawczyk, Strengthening Digital Signatures via Randomized Hashing, Advances in Cryptology, CRYPTO 2006 Proceedings.

[SP 800-106] Quynh Dang, NIST Special Publication 800-106 (Draft), Randomized Hashing Digital Signatures, July 2007

[XMLDSIG] W3C XML-Signature Syntax and Processing, W3C Recommendation, 12 February 2002