[Cryptography] Creating a Parallelizeable Cryptographic Hash Function

Bill Cox waywardgeek at gmail.com
Tue Oct 7 17:34:01 EDT 2014

On Tue, Oct 7, 2014 at 2:58 PM, Jerry Leichter <leichter at lrw.com> wrote:

> On Oct 7, 2014, at 7:02 AM, Bill Cox <waywardgeek at gmail.com> wrote:
> > Actually, this is one of my favorite processes for producing good
> ideas.  Continuing with this process, what's wrong with:
> >
> > Digest = H(1 || B1) * H(2 || B2) * ... * H(n | Bn) mod p
> 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
> Digest(M || Bn+1) = Digest(M) * H(n + 1 || Bn+1) mod p
> - taking the remainder mod p twice produces the same result as doing it
> only once.
> > 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?
> You've tossed around a powerful result without tying it to the security of
> what you wanted to secure!
>                                                         -- Jerr

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.

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.

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?

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141007/907489de/attachment.html>

More information about the cryptography mailing list