Subject: [Cfrg] Bit-rotation to create alternative secure hash? (was re: Merkle Hash Tree Weakness - Request for Advice)

From: "Gordon Mohr" <[email-masked]>
Date: Fri, 3 Jan 2003 01:09:11 -0800

In the context of designing a tree hash over a file, for the
purpose of incremental subrange verification, and ensuring 
that there are no trivial collisions as will occur when the
exact same function is applied to leaves and concatenated 
internal nodes...

Justin Chapweske wrote:
> The quote from Dr. Wagner follows:
> 
> "
> The standard fix is to do one or the other of the following.
>    (1) Include a depth, i.e., we compute the hash value at a
>        node of depth d as Hash(d,l,r) where l represents the
>        hash value at the left child and r the right child's hash.
>    (2) Use a different hash function at the leaves than at
>        internal nodes.  In other words, we compute the hash value
>        at a leaf node as Hash("leaf",x) where x is the data
>        associated at that leaf; we compute the hash value at
>        an internal node as Hash("internal",l,r) where l,r are
>        as above.
> If I recall correctly, both of these can be proven secure if
> the underlying hash is modelled as a random oracle.  However,
> I haven't checked this, so I could be wrong.
> "

Consider the secure hash created by taking an existing secure
hash, and applying a final 1-bit-left-rotation step to its output, 
with wraparound.

In approach (2) above, would it be reasonable to use a standard
secure hash as the "leaf" function , and the shifted version of 
the same secure hash as the "internal" function?

- Gordon 
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Russ Housley <[email-masked]>
Date: Fri, 03 Jan 2003 08:54:34 -0500

Gordon:

It would be much more efficient to rotate by a byte, rather than a bit.  Is 
there any reason you chose a bit rotation?

Russ

---

From: "Gordon Mohr" <[email-masked]>
Date: Fri, 3 Jan 2003 11:52:15 -0800

Good point. 

I only highlighted the 1-bit approach as a sort of "minimal 
representation" of the technique... if a 1-bit shift is OK, 
then just about any other n-bit shift (n < hash width)
should be OK too.

- Gordon

---

From: [email-masked] (David Wagner)
Date: 12 Jan 2003 22:19:27 GMT

>the same secure hash as the "internal" function?

I don't know, but I'm a bit confused why you're asking.  What advantages
does bit-rotation have over the input separation method I described in
my email?

This is not intended to be a hostile question.  I just want to
understand why you are asking.  We know that the input separation method
I described works.  The bit-rotation method might work, or it might not,
it would require some thought and analysis to decide which is the case.
Before I put in the time to do that kind of analysis, I want to understand
what the motivation might be.  In general, when we have a well-analyzed
method that is known to work, I'm reluctant to invent new methods,
if the standard method works acceptable well.

I'll note that performance can't be the answer.  Both the bit-rotation
and input separation methods should have comparable performance
characteristics.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg