<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/03/2014 12:25 PM, Jonathan Katz
wrote:<br>
</div>
<blockquote
cite="mid:CAC7JQK0S3CdxsiEWew7g3j+eZJTfqcBD-2h1-_LZsUSb4Vhu1w@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<div dir="ltr">On Fri, Oct 3, 2014 at 1:18 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">
<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
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>
</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>
</div>
</blockquote>
<br>
Okay I see how that works now. That is an interesting property, but
can it be used to undermine the security of any typical applications
of hash functions?<br>
<br>
Thanks,<br>
<br>
Jason<br>
<br>
<blockquote
cite="mid:CAC7JQK0S3CdxsiEWew7g3j+eZJTfqcBD-2h1-_LZsUSb4Vhu1w@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<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>
</blockquote>
<br>
</body>
</html>