<div dir="ltr">On Fri, Oct 3, 2014 at 1:18 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">
<div bgcolor="#FFFFFF" text="#000000"><span class="">
<div>On 10/02/2014 06:50 PM, Jonathan Katz
wrote:<br>
</div>
<blockquote type="cite">
<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>
</div>
</div>
</div>
</div>
</blockquote>
<br></span>
But here you are not using counter values in the digest calculation.
Is there a way to determine any kind of homomorphism when no
collisions can be found in H()?<span class=""><br></span></div></blockquote><div><br></div><div>Yes, I was. By digest(., .), I meant to apply your scheme.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000"><span class="">
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><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>
</blockquote>
<br></span>
Interesting, thanks for pointing this out. If I interpret the
improvement of the GBA correctly, does that mean the time complexity
to find a collision is N^(L/2) / L vs. N^(L/2)?<br>
<br>
Thanks,<br>
<br>
Jason<br>
</div>
</blockquote></div><br></div></div>