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

[Bernhard M. Wiedemann]

somewhat offtopic

On 20/12/2018 09.59, Daniel Shahaf wrote:
> Hash functions are usually defined in terms of collision resistance.
> The constructions above have not been proven to be collision resistant,
> and moreover, they might not *be* collision resistant — even if h() is.
> Therefore, we should assume they are not collision resistant.

https://en.wikipedia.org/wiki/Collision_resistance says:

> Collision resistance is a property of cryptographic hash functions: a hash function H is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H(a) = H(b), and a ≠ b.



While I agree that you can certainly find collisions when you do
crc16(H(a),H(b))
or
H(crc16(a),crc16(b))

I fail to see how that would be possible with cryptographic hash
functions like SHA-256, so
H(H(a),H(b))

especially since the hash functions internally usually work in rounds
and you have to complete a sufficient number of rounds to get resistance
and adding another full hash around it is like doubling the number of
rounds and the concatenation in the middle does not weaken that.


One can even construct a general proof:
Given a H where it is not possible to collide H(a) = H(b) with a ≠ b
Then it is also not possible to collide
H(H(a),H(a2)) = H(H(b),H(b2)) with a ≠ b  or  a2 ≠ b2

because of the premiss, we have
H(a) ≠ H(b)  or  H(a2) ≠ H(b2)
so that H(a),H(a2) ≠ H(b),H(b2) - assuming hash output of fixed length
and then the premiss applies again to the outer H
to prove the conclusion.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 261 bytes
Desc: OpenPGP digital signature
URL: <http://lists.reproducible-builds.org/pipermail/rb-general/attachments/20181221/a16bd5b0/attachment.sig>