<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Oct 7, 2014 at 2:58 PM, Jerry Leichter <span dir="ltr"><<a href="mailto:leichter@lrw.com" target="_blank">leichter@lrw.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span>On Oct 7, 2014, at 7:02 AM, Bill Cox <<a href="mailto:waywardgeek@gmail.com" target="_blank">waywardgeek@gmail.com</a>> wrote:<br>
> Actually, this is one of my favorite processes for producing good ideas.  Continuing with this process, what's wrong with:<br>
><br>
> Digest = H(1 || B1) * H(2 || B2) * ... * H(n | Bn) mod p<br>
</span>This falls immediately to a prefix attack:  If I know Digest(M) and length(M) (assume for simplicity that length(M) is a multiple of the block size) then<br>
<br>
Digest(M || Bn+1) = Digest(M) * H(n + 1 || Bn+1) mod p<br>
<br>
- taking the remainder mod p twice produces the same result as doing it only once.<br>
<span><br>
> I think I've shown this is secure based on the difficulty of the discrete log problem.  If true, isn't this exactly what you say is unlikely to happen?<br>
</span>You've tossed around a powerful result without tying it to the security of what you wanted to secure!<br>
<span><font color="#888888">                                                        -- Jerr

</font></span></blockquote><div><br></div><div>Hi, Jerr.  Thanks for taking a look at this.  However, I am confused.  Why do I care that an attacker can in constant time compute the correct hash of a different set of data?  By multiplying in H(n+1 || Bn+1), the data is different, and so is the hash.  That seems to be the way we want this function to work.  In constant time any new block can be added or subtracted from the hash.  That is the goal, I believe.<br><br></div><div>It seems to me that the security model is that if we have D = H(B1, B2, ... , Bn), then an attacker should not be able to find find D = H(C1, C2, ... , Cm), unless n == m and Bi == Ci for all i in 1 .. n.  By appending H(n+1 || Bn+1), you've changed the message, and derived the correct hash of it, in constant time.  Isn't that useful?  You can also prepend, or even replaced any Bi you want in constant time.<br></div><div><br></div><div>I agree that this should certainly not be used for anything for now, but I would like to talk about it more.  Do you agree with my assertion that it is secure for the purpose of verifying data integrity of a large data set, while allowing constant time update, including appending new data blocks or replacing old ones?<br></div><div><br></div><div>Bill<br></div></div></div></div>