undefined | Better HN

0 pointsbawolff2y ago0 comments

> Hashing (and cryptographic hashes) need to be inverted because of the pigeon-hole principle. If we have a space of 1000 numbers, we want 1000 unique hashes to 'maximize the space'.

This is non-sensical and false.

Hash functions are not invertible. They are not injective functions. The domain is much larger than their range. You can hash multi gb files and get a small fixed size result. Furthermore, the entire point of a hash function is to not be invertible

To be clear invertibility (and especially trap door invertibility) is quite important in crypto. After all - it is mostly the study of secret messages - no point to that if you cant unscramble the message.

However understanding the goal is not the same as understanding how it works and how it fails. There is a long journey going from invertible functions are cool to wtf is an eliptic curve. The point of a course in cryptography isn't to teach people just what a cipher does as a black box, but to teach them how it works under the hood.

> Its not like Galois Fiels are randomly used you know, mathematicians liked the properties of Galois Fields... and how easy it is to invert those operations.

If you mean in the context of aes s-boxes, Other block ciphers do not do that. The important aspect was their non linearity not invertibility. Any valid sbox is going to be invertible.

> Once you realize that invertibility is the key to all of these algorithms, then its very straightforward.

I'd be curious how you connect this to zero knowledge proofs

0 comments

4 comments · 1 top-level

adrian_b2y ago· 3 in thread

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.

bawolffOP2y ago

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)

dragontamer2y ago

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

adrian_b2y ago

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.

1 more reply

j / k navigate · click thread line to collapse