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

From: "Gordon Mohr" <[email-masked]>
Date: Mon, 13 Jan 2003 15:47:38 -0800

David Wagner writes:
> Gordon Mohr wrote:
> >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?
> 
> 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?

Some speculative thoughts were...

- It could be beneficial for the hash of leaf segments to be a 
  common, unaltered original hash algorithm; this would allow cross-
  referencing of leaf segments with other applications which 
  use only that plain algorithm.

- It will avoid trivially predictable cross-algorithm collisions 
  between different inputs. 

  That is, with the "different salt for leaves and nodes" method, 
  you establish that for short input, tree(alg)( input ) == 
  alg( 0x00 || input ). If in fact some applications or the system 
  as a whole is using a mixture of tree(alg)() and alg(), some coders
  may assuming that collisions between hashes are as hard to find 
  as collisions within any one hash. There thus might be places 
  where a single lookup structure is keyed by multiple hashes, and 
  thus where confusion/collisions between related (but non-identical)
  inputs could occur.

  While due care and proper labelling of keys can avoid this
  problem, it also seems that using bit-rotation to create the
  separate hash function can avoid the problem. 

- Some future application might have use for a file (and
  verification tree) stitched together with mixed-size and
  arbitrarily-large leaves. For example, "assemble a file from the 
  segment with hash W, segment with hash X, segment with hash Y, 
  and segment with hash Z -- where each segment may be either
  a byte range of any length with that hash, or a composite of
  other segments with that treehash."

  Such a scenario would probably want to use an unsalted,
  standard, cross-referenceable algorithm for all bytes ranges 
  of any length, and would need a truly independent algorithm 
  for the node combinations -- and it seems like a bit-rotated
  version of the first algorithm could be sufficiently 
  independent, while any input-salted version unavoidably
  has collisions with the unsalted version.

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

In fact, Justin and I have pretty much settled on the approach
of prefixing leaf input with a 0x00 byte, and node concatenation
input with a 0x01 byte, as that seems the safe, well-worn approach.

However, I remain curious about the bit-rotation transformation as a 
potential remedy -- if not here and now, then perhaps in some other
future case where similar cross-hash issues become important. I don't 
see any obvious problems, but I don't trust my own analysis -- so I 
wanted to throw the idea out for wider consideration while the topic
remained fresh. 

Thanks,

- Gordon

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