<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 10/02/2014 06:50 PM, Jonathan Katz
wrote:<br>
</div>
<blockquote
cite="mid:CAC7JQK2pLEwPquUScf3Ddb+XHUW+=TNCotBrFFpmJFR6=HnWrQ@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<div dir="ltr">On Thu, Oct 2, 2014 at 6:53 PM, Jason Resch <span
dir="ltr"><<a moz-do-not-send="true"
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>
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()?<br>
<br>
<blockquote
cite="mid:CAC7JQK2pLEwPquUScf3Ddb+XHUW+=TNCotBrFFpmJFR6=HnWrQ@mail.gmail.com"
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>
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>
</body>
</html>