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

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

<p>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).</p>

<p>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?</p>

<p>The former is simply the birthday problem while the latter is:</p>

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

<p>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. </p>

<p>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.</p>

<p>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.</p>

<p>Finally, I don't know anything about X.509 whitespace.</p>

CC BY-SA 2.5
2011-01-18T03:26:14.793Z
2011-01-18T03:26:14.793Z
PulpSpy
<p>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.</p>

<p>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.</p>

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

<ol>
<li><p>Why isn't the length of <b>ONLY</b> the data being consumed added as a final block to the MD calculation?</p></li>
<li><p>In the case of X.509 - Why is the whitespace and comments being taken into account as part of the MD?</p></li>
</ol>

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

<ol>
<li>$MD(M + |M|) = xyz$</li>
<li>$MD(M + |M| + |M| * magicseed_0 +...+ |M| * magicseed_n) = xyz$</li>
</ol>

<p>where :</p>

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

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

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

<ol>
<li>It not only generates the same MD</li>
<li>But is also comprehensible/parsible/compliant</li>
<li>and is also the same size as the original message,</li>
</ol>

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

<p><b>Further Question</b>: 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 ?</p>

<p>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.</p>

<p>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?</p>

<p>Links:</p>

<ol>
<li>Postscript: <a href="http://www.schneier.com/blog/archives/2005/06/more_md5_collis.html" rel="nofollow noreferrer">http://www.schneier.com/blog/archives/2005/06/more_md5_collis.html</a></li>
<li>X.509: <a href="http://www.win.tue.nl/~bdeweger/CollidingCertificates/" rel="nofollow noreferrer">http://www.win.tue.nl/~bdeweger/CollidingCertificates/</a></li>
</ol>

<p>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: <a href="https://cstheory.stackexchange.com/questions/585/what-is-the-difference-between-a-second-preimage-attack-and-a-collision-attack">csse question</a>. Please DO NOT focus on answers that relate to generating messages of length different from the original message as any such solution is invalid.</p>

CC BY-SA 2.5
2011-01-16T08:09:32.230Z
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](http://th.informatik.uni-mannheim.de/People/lucks/HashCollisions/).
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-16T08:20:28.320Z
@Tsuyoshi: That is a nice example, good work!, however the technique they used was to generate the original message with a series of nulls in the area between the header and the first text block of the postscript file. Most if not all renderers do not render or even flag a parse error with such garbage, then subsequently by using tunneling they were able to generate the specific data required in-place of the nulls to allow for the modified file to have the same MD.
Dominar
CC BY-SA 2.5
2011-01-16T08:21:22.283Z
@Tsuyoshi: [Continued from above] Firstly this will never be the case in reality, and secondly the proposition in the question clearly states only the data that will be functional/rendered/used will be apart of the MD and accumulate |M|, hence this particular attack would not succeed.
Dominar
CC BY-SA 2.5
2011-01-16T08:25:18.523Z
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
CC BY-SA 2.5
2011-01-16T08:29:03.750Z
@Tsuyoshi: That is very true, however no cryptographic protocol relies entriely on one primitive alone. The idea is not to make the hash function secure, its too late for that, the proposition is what is the likelyhood of messages of the same length having a common MD that are also strictly compliant for a particular DFA. Assume messages such as images, sounds or executables that are very sensitive to change. All the attacks to date have been on formats that are very error tolerant or specification-less (html) or ignore areas that they don't recognize etc.
Dominar
CC BY-SA 2.5
2011-01-16T08:41:34.180Z
Note to all: Bizarrely, this poster has reposted this question, deleting his original. This question, as I see it, adds nothing new.
Noon Silk
CC BY-SA 2.5
2011-01-16T09:03:35.600Z
@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
CC BY-SA 2.5
2011-01-16T09:07:18.800Z
@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
CC BY-SA 2.5
2011-01-16T10:02:34.843Z
@Noon my hands are not capable :), but everyone gets a chance to understand the norms here.
Suresh Venkat
<cr.crypto-security><hash-function>
Collision Attacks, Message Digests and a Possible solution
Dominar
# Collision Attacks, Message Digests and a Possible solution

(Asked by: username_0 on 2011-01-16)

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|.
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](https://cstheory.stackexchange.com/questions/585/what-is-the-difference-between-a-second-preimage-attack-and-a-collision-attack). Please DO NOT focus on answers that relate to generating messages of length different from the original message as any such solution is invalid.

**Tags:** cr.crypto-security, hash-function

> **Comments:**
> **username_1**: 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](http://th.informatik.uni-mannheim.de/People/lucks/HashCollisions/).  
> **username_0**: @Tsuyoshi: That is a nice example, good work!, however the technique they used was to generate the original message with a series of nulls in the area between the header and the first text block of the postscript file. Most if not all renderers do not render or even flag a parse error with such garbage, then subsequently by using tunneling they were able to generate the specific data required in-place of the nulls to allow for the modified file to have the same MD.  
> **username_0**: @Tsuyoshi: [Continued from above] Firstly this will never be the case in reality, and secondly the proposition in the question clearly states only the data that will be functional/rendered/used will be apart of the MD and accumulate |M|, hence this particular attack would not succeed.  
> **username_1**: 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.  
> **username_0**: @Tsuyoshi: That is very true, however no cryptographic protocol relies entriely on one primitive alone. The idea is not to make the hash function secure, its too late for that, the proposition is what is the likelyhood of messages of the same length having a common MD that are also strictly compliant for a particular DFA. Assume messages such as images, sounds or executables that are very sensitive to change. All the attacks to date have been on formats that are very error tolerant or specification-less (html) or ignore areas that they don't recognize etc.  
> **username_2**: Note to all: Bizarrely, this poster has reposted this question, deleting his original. This question, as I see it, adds nothing new.  
> **username_3**: @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.  
> **username_2**: @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.  
> **username_3**: @Noon my hands are not capable :), but everyone gets a chance to understand the norms here.  

---

## 1 answers

### Answer by username_4 on 2011-01-18. Score: 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.


---

