# Collision Attacks, Message Digests and a Possible solution

I've been doing some preliminary research in the area of message digests. Specifically collision attacks of cryptographic hash functions such as MD5 and SHA-1, such as the Postscript example and X.509 certificate duplicate.

From what I can tell in the case of the postscript attack, specific data was generated and embedded within the header of the postscript (which is ignored during rendering) which brought about the internal state of the md5 to a state such that the modified wording of the document would lead to a final MD equivalent to the original. The X.509 took a similar approach where by data was injected within the comment/whitespace of the certificate.

Ok so here is my question, and I can't seem to find anyone asking this question:

1. Why isn't the length of ONLY the data being consumed added as a final block to the MD calculation?

2. In the case of X.509 - Why is the whitespace and comments being taken into account as part of the MD?

Wouldn't a simple processes such as one of the following be enough to resolve the proposed collision attacks:

1. $MD(M + |M|) = xyz$
2. $MD(M + |M| + |M| * magicseed_0 +...+ |M| * magicseed_n) = xyz$

where :

1. M : is the message
2. |M| : size of the message in bits
3. MD : is the message digest function (eg: md5, sha, whirlpool etc)
4. xyz : is the pairing of the acutal message digest value for the message M and |M|. <M,|M|>
5. $magicseed_{i}$: Is a set of random values generated with seed based on the internal-state prior to the size being added.
6. '+' : is a concatentation operation A+B+C = ABC

This technqiue should work, as to date all such collision attacks rely on adding more data to the original message.

In short, the level of difficulty involved in generating a collision message such that:

1. It not only generates the same MD
2. But is also comprehensible/parsible/compliant
3. and is also the same size as the original message,

is immensely difficult if not near impossible. Has this approach ever been discussed? Any links to papers etc would be nice.

Further Question: What is the lower bound for collisions of messages of common length for a hash function H chosen randomly from U, where U is the set of universal hash functions ?

Is it $1/N$ (where N is $2^{|M|}$) or is it greater? If it is greater, that implies there is more than 1 message of length |M| that will map to the same MD value for a given H.

If that is the case, how practical is it to find these other messages? bruteforce would be of $O(2^N)$, is there a method of time complexity less than bruteforce?

Note: This question is NOT as easy as it seems. Please read it very carefully and make sure you have understood exactly what is being asked. The answer will require understanding of martingales and distribution ensembles. If you are unsure what these are or how they apply to this particular problem then please do not post answers. Prior knowledge of this class of attack is required, please access the links above and the following: csse question. Please DO NOT focus on answers that relate to generating messages of length different from the original message as any such solution is invalid.

• Finding hash collisions is not the same as finding a document with the same hash value as a given document. And in the case of MD5 hash collisions, two Postscript files with the same length (2,029 bytes) and the same MD5 hash value are already found by Daum and Lucks. – Tsuyoshi Ito Jan 16 '11 at 8:09
• I am no expert of cryptography, but my understanding is that while adding a layer of preprocessing can make a demonstration more difficult, it does not make the hashing algorithms really securer. – Tsuyoshi Ito Jan 16 '11 at 8:25
• Note to all: Bizarrely, this poster has reposted this question, deleting his original. This question, as I see it, adds nothing new. – Noon Silk Jan 16 '11 at 8:41
• @Noon, the poster requested that the previous post be deleted, so they could start over again with a more constructive discussion. I see no problem with this. – Suresh Venkat Jan 16 '11 at 9:03
• @Suresh: I see. I'm not sure I agree (it seemed to me the poster didn't understand the original comments to him, and I would guess he will get similar responses with a similar responding attitude), but I leave it in your capable hands. – Noon Silk Jan 16 '11 at 9:07

I will attempt an answer, which hopefully interpretes the question correctly and if not, will at least lead to some clarification.

Let's say the hash has an output of size $2^{N}$ and we are hashing messages only of length exactly $2^{M}$.

The last question is the best place to start: what is the probability of a collision with a randomly selected hash? A common analogy used when talking about collisions is balls and bins. The question addresses the scenario where we randomly throw (definition of the hash) $2^{M}$ balls (message space) into $2^{N}$ bins (output space).

I am not clear on the exact question: is it, what is the probability of at least one bin having more than one ball? Or is it, what is the probability that given I just threw a ball into a particular bin that another ball is thrown into the same bin?

The former is simply the birthday problem while the latter is:

$p=1-(1-\frac{1}{2^{N}})^{2^{M}-1}$

Now as the ratio $N/M$ increases, $p$ decreases. We cannot change $2^N$. Any method that lowers $2^M$ will have an effect. This includes restricting messages from any M-bit string to only M-bit strings from a language. Say there are $2^{L}$ admissible strings, $L \leq M$, then just substitute in ${L}$ for $M$ in the equation.

As for the first question of adding the length of the message as a suffix, one can still find a collision of a different length as long as the new collision ends with a suffix equivalent to it's (new) length. This makes finding collisions moderately harder but does not "solve" the collision problem by any means. It is not effective at enforcing the length remains the same, without some outside knowledge of what the length should be.

If the length is known, then this adding the length as a suffix adds redundant information and does not increase $M$ in the above equation.

Finally, I don't know anything about X.509 whitespace.