Hacker News Reader

Comment by adrian_b | Hacker News Reader

No, it is what you say that is false. Please examine the inner structure of any widespread secure hash algorithm.

It is not possible to construct a complex-enough hash function with predictable properties (like being surjective and having equiprobable output values) from simpler non-invertible functions.

All good hash functions are made from a combination of invertible functions, over which some trick is used to make the resulting hash function non-invertible.

For instance, a non-invertible hash function (for a fixed input length) can be obtained as the sum of two invertible functions. For simplicity, one of the two invertible functions may be the identity function, as it is done in SHA-1, SHA-2 and a very large number of other frequently used hash functions.

Using such a hash function with fixed input length, there are many methods to extend it to work with a variable input length.

View on HN

Talk about goal post moving.

You went from hash functions are invertible to hash functions contain subroutines that are invertible. Which is true of pretty much everything.

> For instance, a non-invertible hash function can be obtained as the sum of two invertible functions. For simplicity, one of the two invertible functions may be the identity function, as it is done in SHA-1, SHA-2 and a very large number of other frequently used hash functions.

I dont understand what you are trying to reference here? Are you trying to claim that the compression function in a Merkle–Damgård hash function is invertible? Because it isn't (or at the very least usually designed in such a way that we do not know how to)

> You went from hash functions are invertible to hash functions contain subroutines that are invertible.

No. You misunderstood from the start because you apparently didn't recognize that SHA256 is built from an invertible block cipher named Davies–Meyer, and have probably googled the structure afterwards and then double-downed on the Merkle–Damgård compression function.

SHA256 is built up from an invertible block cipher for a reason. Invertibility has many important properties, one of which is the maximization of entropy while mixing the 256-bits of state into 256-bits of new-state.

Anyone who knows the internal structure of modern hashes knows what I'm talking about. Modern encryption is hugely built from one-to-one and onto functions. Its just the easiest way to prove various features.

Yes, even hash functions.

---------

BTW: Please pay attention to usernames as well. You're yelling at a fellow poster who is... erm... not me.

I have already written how most compression functions used in a Merkle–Damgård hash function are made to be non-invertible, by taking an invertible function and summing the input with the output (using the input means using the identity function of the input, which is the simplest invertible function).

Only with such methods it is possible to guarantee adequate mathematical properties for the compression function. Otherwise, if non-invertible functions are composed, the properties of the compound function are unpredictable, especially after the very large number of rounds (i.e. of function compositions) that are used in a practical hash function.

For anyone who might want to design a custom hash function it is critical to understand the importance of invertible functions, which is based on the fact that if you compose two invertible functions you get a function that is also invertible. Only this property allows predictions about the statistical characteristics of the result that is obtained after tens or hundreds of function compositions.

You can take the compression function of e.g. SHA-256, remove the final step that converts the invertible function into a non-invertible function, and you get a decent (invertible) block cipher function.

This is an awful lot of math. It’s funny juxtaposed to your other comment disregarding the need for mathematics background in encryption.

Reply on news.ycombinator.com