Subject: [Cfrg] Weakness in rotation to create alternative secure hash?

From: Amir Herzberg <[email-masked]>
Date: Sun, 05 Jan 2003 08:55:14 +0200

I think David Wagner's second suggestion requires the two hash functions to 
be `independant` (and only known proof is in the random oracle model):

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

Considering Gordon's suggestion/question re a using two highly related hash 
functions, namely the leaf function being identical to the internal 
function except for rotation... this specific proposal seems very weak, in 
fact insecure for any specific hash function (i.e. even in the `random 
oracle model`). This is most trivial if you consider rotation of size n, 
where n is the length of the output of the hash (e.g. 160 bits); in this 
case we just permutated the order of the blocks to the internal hash 
function... In fact, this seems to work also for any rotation e.g. one bit 
(or one byte). Or did I get it wrong (I admit I haven't checked all 
details...)?

Best, Amir Herzberg

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

---

From: "Gordon Mohr" <[email-masked]>
Date: Sat, 4 Jan 2003 23:22:11 -0800

> (or one byte). Or did I get it wrong (I admit I haven't checked all 

Clearly the case where the rotation r = the output hash length n, you've
got a null transformation, and the derived hash is not usefully different.

I'm conjecturing that for any r < n, the derived (rotated) hash is just 
as secure -- with regard to the base (unrotated) hash -- as a completely 
independent hash algorithm would be. 

At least in the case of avoiding collisions at the end of a tree-hash
process, I haven't yet found a problematic situation. But I could easily
be missing something.

- Gordon

---

From: Amir Herzberg <[email-masked]>
Date: Sun, 05 Jan 2003 13:09:47 +0200

Gordon and all: Reading before I somehow missed and thought you apply the 
rotation to the inputs... sorry! Of course you apply it to the outputs... 
This design seem secure if the hash function is collision resistant as well 
as resistant to rotated collision, i.e. to finding x, y s.t. h(x)=r(h(y)) 
where r() is the rotation function. Both properties hold under the `random 
oracle analysis`. However, I think for any real application it is desirable 
to minimize the assumptions and requirements from the hash function; I'm 
therefore not sure if there's sufficient motivation for using this 
construction. It is easy to demonstrate an artificial (impractical) example 
of a collision resistant hash where finding `rotated collisions` is easy.

Best, Amir