Things that are still secure

A possible attack exists for signing applications. The scenario of abuse assumes that the attacker wants to get something signed by another party, who uses a colliding hash. For example, a statement that the signer owes him a sum of money. If the attacker can generate two such statements with different amounts, he will have the lower value signed and the higher value used as 'proof' of what he should receive. The signature can be moved from the statement with the lower amount to the statement with the higher amount if the hash in the signature collides on the statements.

It is important in the scenario that the signer is a different party from the party generating the content to be signed. If all the signed data is generated by the signing party, or if the signer has no freedom in the data that he delivers, then there is still no problem. Also, signatures made before the attacker could know of this attack can be considered reliable.

There is one more scenario that can stop an attacker from abusing a colliding hash. This is when enough of the information being hashed is both under the control of the signer, and unpredictable to the attacker. For example, by prefixing and/or postfixing 160 bits of random information around the hash, the attacker doesn't stand a chance of prefabricating two documents with the same hash value. The signer is back in control.

Implementations using current technology

The data being signed often includes parts that can hold arbitrary data or a surprise, such as the notation data in PGP, non-critical certificate extensions in X.509 and perhaps references in XML signing. These fields can be filled with surprise data that is unpredictable to the attacker, for example a series of random octets. Normal signatures also include the signing time, but this is a debatable source of unpredictability.

These solutions are specific for a technology, but they are not hard to implement now because they need no new technology, just a place to plug additional bits. The only concerns is to keep the random generator safe from influence by the attacker.

Generic solution

A more general solution, ranging over both hash algorithms and signing technologies, is to define generic hash-strengthening parameters that can be incorporated as algorithm parameters into the hash algorithm being used. We considered two types for that purpose:

prefixSurprise

Arbitrary-length OCTET STRING that is used before any other hashing takes place. This is a way to scramble the initial vector of the hash algorithm before hashing starts. There does not seem to be a use for prefixSurprise wiht lengths in excess of the hash result length.

postfixSurprise

Arbitrary-length OCTET STRING that is used after all other hashing has taken place. This is a way to scramble the hash result up to that point. Since the remaining padding is not under influence of the attacker, it is likely that his damage (namely, getting the same hash outcome) will have been done before the padding. In other words, postfixSurprise would not help solving this.

Pleasant about prefixSurprise is that it upsets the hash before it starts processing inputs, so any scheme that would converge the data is far less likely to succeed. Since prefixSurprise seems the most influential and difficult to bypass, this is what we propose as a standard extension that could be applied in retrospect to current hash algorithms. The advised size of the prefixSurprise would be the size of the hash value.

The result of this extension to hashes would be that collisions stop to be threats to the security of digital signatures.

ASN.1 specifics

The parameter of current hash algorithms is set to NULL, which is an ASN.1 notation that DER-encodes to:

05 00

To uniquely identify the prefixSurprise parameter, OpenFortress has allocated OID 1.3.6.1.4.1.10471.6.4.3 for an OCTET STRING of any length holding hash prefix surprise. This OID translates to the following ASN.1 octets:

06 0a 2b 06 01 04 01 d1 67 06 04 03

The complete extension replacing the NULL value is a SEQUENCE of this OID and the parameters (the OCTET STRING) defined by it. So, assuming the prefixSurprise to be:

d4 1d 8c d9 8f 00 b2 04 e9 80 09 98 ec f8 42 7e

The following would replace the NULL value with this new parameter:

30 1e
   06 0a 2b 06 01 04 01 d1 67 06 04 03
   04 10
      d4 1d 8c d9 8f 00 b2 04 e9 80 09 98 ec f8 42 7e

Note that the last line can be replaced by any random surprise of the same length. The remainder of the ASN.1 encoding will not change because of that. An example that would match the 160 bit length of SHA1 algorithms is:

30 22
   06 0a 2b 06 01 04 01 d1 67 06 04 03
   04 14
      0f e4 44 43 c7 cc 99 d2 e0 78 73 95 c9 a1 9a cc c3 74 33 f1

Note how this does influence the length fragments (second octet on the two-octet lines) but how it uses the same OID.

The size of this extension is modest -- a mere 36 octets in the last case, so 34 octets more than in the original signature encoding. The result remains straightforward to put into the much larger data block available under public key algorithms.

Status and Interoperability

This document is here as a proposal -- it has no formal status until used in a standard. We merely hope it is useful, and appreciate a reference to OpenFortress Digital signatures if it is used in related work.

Specifically, we have not investigated the suitability of adding surprises for any specific hash algorithm and/or any specific signing technology.

Note that current signature-validating applications will fail if they receive the generic surprises. Either because they do not recognise the algorithm identifier due to its parameters, or if they are too sloppy to notice, because the hash values will be different due to the prefix.

The implementation that puts surprises in niches opened by current technology however, should not cause any problems with any of today's standards-compliant implementations. It is probably the best solution for the short term, leaving the generic surprise solution as an add-on to be phased in over a longer period of time.