<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Oct 8, 2014 at 10:33 AM, 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:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><span></span>In the case you propose, there's another issue:  Digest(X) == 0 if and only if one of the constituent hashes is 0.  That breaks one of the basic requirements for a secure hash function:  Given H(X), it's difficult to find a Y != X such that H(Y) == H(X).  When H(X) == 0, it's trivial to find as many examples as you like.<br><div><span><blockquote type="cite"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div></div></div></div></div></blockquote></span></div></div></blockquote>I challenge you to find x such that H(x) == 0.  Assuming we have a good hash primitive, you can't.  So, this is not really a problem.  However, we can't use just any hash function.  H has to be secure.<br><div><span></span> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div><br></div><div>Note that the cost of computing your digest is at least double that of simply doing a hash over the original data (as you run the hash on twice as much data - not to mention the cost of all those modular multiplications). You'd need to justify that cost.<span><br></span></div></div></blockquote><div><br></div><div>Not true for block sizes of B where B is large.  Anything over 1MiB should be  fine.  However, if the block size is just a KiB or so, then the modular multiplications will dominate.  There needs to be a significant need for constant time update in this case.<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div><br></div>I also see no obvious advantage to your scheme over simply adding the constituent hashes together (effectively mod 2^n) - a much, much cheaper operation which doesn't have problems with 0.  (You can make it even cheaper by considering each H() value as a vector of 32- or 64-bit values and adding them as vectors.)  Can you describe an attack on the cheaper approach that fails for yours?<span><font color="#888888"><div><div>                                                        -- Jerry</div></div><div><br></div></font></span></div></blockquote></div><br></div><div class="gmail_extra">That is much cheaper, but David Wagner broke such systems in his paper on Generalized Birthday attacks:<br><br><a href="http://www.di.ens.fr/~fouque/ens-rennes/gbp.eps">www.di.ens.fr/~fouque/ens-rennes/gbp.eps</a><br><br></div><div class="gmail_extra">He explores security using various operators and goes into some depth about possible attacks on multiplication modulo primes.  However, his explored directions also directly apply to attacks on discrete logs.<br><br></div><div class="gmail_extra">I'm afraid I know of no secure shortcut that avoids 2048-bit arithmetic.  That this can be done securely at all is new information, SFAIK.<br><br></div><div class="gmail_extra">Thanks for taking a crack at it.<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">Bill<br></div></div>