<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>