Collision Attacks, Message Digests and a Possible solution

Question

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?

Links:

1. Postscript: http://www.schneier.com/blog/archives/2005/06/more_md5_collis.html
2. X.509: http://www.win.tue.nl/~bdeweger/CollidingCertificates/

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.

Answer 1

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.