<div dir="ltr">On Thu, Oct 2, 2014 at 6:53 PM, Jason Resch <span dir="ltr"><<a href="mailto:jresch@cleversafe.com" target="_blank">jresch@cleversafe.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Assuming there was a secure cryptographic function H() with an output of L bits, what attacks or weaknesses would exist in a protocol that did the following:<br>
<br>
<br>
Digest = H(B_0 || C_0) ^ H(B_1 || C_1) ^ H(B_2 || C_2) ^ ... ^ H(B_N || C_N) ^ H(N)<br>
<br>
<br>
Where B_0 through B_N are the blocks (of size L) constituting the message and C_0 through C_N are L-bit counters.<br>
<br>
One problem seems to be that if any collision can be found for a given H(X || C_i) and H(Y || C_i), it leads to an essentially infinite number of collisions (any message that contains X as a block can have that block replaced with Y), but what other vulnerabilities does this construction have that would make it unsuitable as a general purpose cryptographic hash function?<br>
<br>
Thanks for your expertise.<br></blockquote><div><br></div><div>There are several issues. Most obvious is that your hash is homomorphic, i.e.,<br></div><div>  digest(B_0, B_1) ^ digest(B'_0, B_1) ^ digest(B_0, B'_1) = digest(B'_0, B'_1)<br><br></div><div>Also, collisions in your hash function can be found in faster than square-root time using Wagner's generalized birthday attack.<br></div></div></div></div>