[rb-general] transitive collision resistance [was: rb formalism]

[Arnout Engelen]

> > One can even construct a general proof:
> > Given a H where it is not possible to collide H(a) = H(b) with a ≠ b

I'm not sure what you mean by 'not possible to collide' here. Hashes
are typically smaller than the allowed inputs, which means there must
exist different input files that produce the same output hash. A
cryptographic hash just makes those collisions hard to find/create, it
cannot prevent them.

> Let us stop right here, having the same hash *DOES NOT* mean that the files are the same

Agreed, but I don't think anyone was claiming that.

> And then I would formally prove that the only way for hashes to all be true is if all bytes in the file are exactly identical.

As above, this is impossible to prove because it cannot be true. The
hashes will still be smaller than the allowed inputs, which means
there must exist inputs that have the same hash. They may just be hard
to find.

Example: say you have 2 independent 256-bit hash functions (so
functions that, given an input, produce a 256-bit hash), and you
combine them by just concatenating the bits, producing a 512-bit hash
function. This 512-bit hash function can produce at maximum 2^512
different outputs. Suppose we are hashing inputs of exactly 512 bits
long. Then there are 2^512 different possible inputs. Since there are
also 2^512 different possible outputs, the desirable property you
described above might still hold (if we are smart/lucky). As soon as
we also allow other inputs (with more or less bits than 512), however,
there are more possible inputs than there are possible outputs, so
there must be collisions.


Arnout