5 ms·

Well, a hash function cannot be one-to-one because of the pigeonhole principle.

tux3 5y ago
It doesn't have to be, in principle. There are hash functions that take fixed size input, and output no smaller (or arbitrarily long) hashes. Look at the hash construction in stream ciphers, for example. The keystream is very long, but the key is short. Or look at a perfect hash function, as used for hash tables.
didericis 5y ago
Theoretically couldn’t there be a hashing algorithm that’s one to one if it always spits out a hash as long or longer than the input message? I’ve never actually walked through the math behind hashing algorithms, but I’m assuming collisions come from truncation. I’m guessing you’re usually not able to know exactly where two inputs that collide for the first n bits end up diverging, so the only way to ensure most hash functions are one to one is if the outputs have infinite length. But, if you had outputs of infinite length for different inputs, eventually they’d have to diverge. Idk if that’s true of all hashing functions/maybe there’s a way to know after what point outputs for different inputs have to diverge for some.
- AlexSW 5y ago
  The output length/size of a hash function is fixed, whereas it takes an arbitrary-length/size input.
  - didericis 5y ago
    I know it's normally fixed, but I did a quick google and saw a stack overflow answer saying there are some algorithms that allow for variable length outputs: https://crypto.stackexchange.com/a/3564 https://crypto.stackexchange.com/a/3564 That doesn’t necessarily mean you can figure out what length output for a given input is needed to make it one to one. Not sure you could avoid collisions even if the length of the output was infinite, but I’m assuming different inputs have to have outputs that diverge at some point.
    - 7steps2much 5y ago
      You are correct, at least in theory. Assume you have two inputs, A and B. A may hash to: A38uT75kjGz B may hash to: A38uHso629t So yes, if you were to cut these off after the A38u then you would no longer be able to say for sure if you hashed A or B to arrive at your hash. Of course in practice this usually isn't a problem as long as you have "a long enough" output.
      - bitkrieg 5y ago
        Your example made me wonder, is there a known instance from a common hash algorithm where the input results in exactly the same string representation of the output hash? Eg. "AE485D" hashes to "AE485D". Is this even mathematically possible?
        charcircuit 5y ago
        The modulus function has this property.
        kevinventullo 5y ago
        Java’s built-in hash function for integers is the identity function.
        morelisp 5y ago
        The mathematical term for this is a "fixed point", where f(x) == x. Assuming a perfectly random uniform distribution, the usual desirable property of a cryptographic hash - the probability of a hash function not having a fixed point (that is, hashing at least one x to itself) is (1-1/n)**n, where n is the number of possible outputs. As n approaches infinity - which it does pretty rapidly in this case, since we're talking about 2**32 to 2**512 in practice - this approaches 1/e, or about 37%. So, not only is it possible, but most "good" hash functions (63% of them) will have them.
    - charcircuit 5y ago
      Those are XOFs (extendable output functions), not hash functions.
- mistercow 5y ago
  Not so theoretically. Perfect hash functions have exactly that property, although I've never heard of a perfect cryptographic hash function. That concept seems inherently contradictory.
- oconnor663 5y ago
  Most cryptographic hash functions in practice mix their input block-by-block into some "state" that's of a fixed size. This lets you implement them with a small, constant memory footprint, which is important. For older designs like MD5, SHA-1, and SHA-256, the final hash is literally that state, just serialized into bytes and returned to the caller. (This is what makes "length extension attacks" possible on these hashes, which is why we need constructions like HMAC.) For newer designs like SHA-3 and the BLAKE family, the output is some function of the state, which prevents length extension attacks. This also makes it easy for these functions to offer "extendable output" features, i.e. as many output bytes as you like. (SHA-3 isn't standardized with this feature, but the very closely related SHAKE functions will gladly give you outputs of any length.) However, one important thing to realize about these functions is that extended outputs do not increase security. This is counterintuitive, because we're used to distinctions like SHA-256 vs SHA-512, with the larger output providing more security in some sense. That's true, but it requires SHA-512 to keep a larger state in addition to producing a larger output. SHAKE128 and BLAKE3 always use the same state size, regardless of how many output bytes you ask for, and if you produce a collision in that state, all the output bytes will collide too. Another commenter mentioned perfect hash functions, and my understanding of those is that they typically require the input set to be of some fixed size. If the input set is "any possible string", which it pretty much is for cryptographic hashes, I think trying to design a perfect hash function starts to get weird? At the very least, the state you need to keep will be proportional to the longest message you want to hash.
  - didericis 5y ago
    This is very helpful, thank you. This whole thread is making me realize I should read up more on hash differences/implementations.
    - oconnor663 5y ago
      (shameless plug) If you want to start by doing your own implementation of SHA-256, you can take a look at one of my assignments :) https://github.com/oconnor663/applied_crypto_2021_fall/tree/main/sha256 https://github.com/oconnor663/applied_crypto_2021_fall/tree/...
- deleted 5y ago
  [deleted]
- 3np 5y ago
  Arguably per-definition a hash function takes arbitrary-size input and produces fixed-length output - change either of those and it's no longer a hash function. Don't and the pigeonhole principle guarantees infinite theoretical collisions.

tux3 5y ago

It doesn't have to be, in principle. There are hash functions that take fixed size input, and output no smaller (or arbitrarily long) hashes. Look at the hash construction in stream ciphers, for example. The keystream is very long, but the key is short. Or look at a perfect hash function, as used for hash tables.

didericis 5y ago

Theoretically couldn’t there be a hashing algorithm that’s one to one if it always spits out a hash as long or longer than the input message? I’ve never actually walked through the math behind hashing algorithms, but I’m assuming collisions come from truncation. I’m guessing you’re usually not able to know exactly where two inputs that collide for the first n bits end up diverging, so the only way to ensure most hash functions are one to one is if the outputs have infinite length. But, if you had outputs of infinite length for different inputs, eventually they’d have to diverge. Idk if that’s true of all hashing functions/maybe there’s a way to know after what point outputs for different inputs have to diverge for some.

AlexSW 5y ago
The output length/size of a hash function is fixed, whereas it takes an arbitrary-length/size input.
- didericis 5y ago
  I know it's normally fixed, but I did a quick google and saw a stack overflow answer saying there are some algorithms that allow for variable length outputs: https://crypto.stackexchange.com/a/3564 https://crypto.stackexchange.com/a/3564 That doesn’t necessarily mean you can figure out what length output for a given input is needed to make it one to one. Not sure you could avoid collisions even if the length of the output was infinite, but I’m assuming different inputs have to have outputs that diverge at some point.
  - 7steps2much 5y ago
    You are correct, at least in theory. Assume you have two inputs, A and B. A may hash to: A38uT75kjGz B may hash to: A38uHso629t So yes, if you were to cut these off after the A38u then you would no longer be able to say for sure if you hashed A or B to arrive at your hash. Of course in practice this usually isn't a problem as long as you have "a long enough" output.
    - bitkrieg 5y ago
      Your example made me wonder, is there a known instance from a common hash algorithm where the input results in exactly the same string representation of the output hash? Eg. "AE485D" hashes to "AE485D". Is this even mathematically possible?
      - charcircuit 5y ago
        The modulus function has this property.
      - kevinventullo 5y ago
        Java’s built-in hash function for integers is the identity function.
      - morelisp 5y ago
        The mathematical term for this is a "fixed point", where f(x) == x. Assuming a perfectly random uniform distribution, the usual desirable property of a cryptographic hash - the probability of a hash function not having a fixed point (that is, hashing at least one x to itself) is (1-1/n)**n, where n is the number of possible outputs. As n approaches infinity - which it does pretty rapidly in this case, since we're talking about 2**32 to 2**512 in practice - this approaches 1/e, or about 37%. So, not only is it possible, but most "good" hash functions (63% of them) will have them.
  - charcircuit 5y ago
    Those are XOFs (extendable output functions), not hash functions.
mistercow 5y ago
Not so theoretically. Perfect hash functions have exactly that property, although I've never heard of a perfect cryptographic hash function. That concept seems inherently contradictory.
oconnor663 5y ago
Most cryptographic hash functions in practice mix their input block-by-block into some "state" that's of a fixed size. This lets you implement them with a small, constant memory footprint, which is important. For older designs like MD5, SHA-1, and SHA-256, the final hash is literally that state, just serialized into bytes and returned to the caller. (This is what makes "length extension attacks" possible on these hashes, which is why we need constructions like HMAC.) For newer designs like SHA-3 and the BLAKE family, the output is some function of the state, which prevents length extension attacks. This also makes it easy for these functions to offer "extendable output" features, i.e. as many output bytes as you like. (SHA-3 isn't standardized with this feature, but the very closely related SHAKE functions will gladly give you outputs of any length.) However, one important thing to realize about these functions is that extended outputs do not increase security. This is counterintuitive, because we're used to distinctions like SHA-256 vs SHA-512, with the larger output providing more security in some sense. That's true, but it requires SHA-512 to keep a larger state in addition to producing a larger output. SHAKE128 and BLAKE3 always use the same state size, regardless of how many output bytes you ask for, and if you produce a collision in that state, all the output bytes will collide too. Another commenter mentioned perfect hash functions, and my understanding of those is that they typically require the input set to be of some fixed size. If the input set is "any possible string", which it pretty much is for cryptographic hashes, I think trying to design a perfect hash function starts to get weird? At the very least, the state you need to keep will be proportional to the longest message you want to hash.
- didericis 5y ago
  This is very helpful, thank you. This whole thread is making me realize I should read up more on hash differences/implementations.
  - oconnor663 5y ago
    (shameless plug) If you want to start by doing your own implementation of SHA-256, you can take a look at one of my assignments :) https://github.com/oconnor663/applied_crypto_2021_fall/tree/main/sha256 https://github.com/oconnor663/applied_crypto_2021_fall/tree/...
deleted 5y ago
[deleted]
3np 5y ago
Arguably per-definition a hash function takes arbitrary-size input and produces fixed-length output - change either of those and it's no longer a hash function. Don't and the pigeonhole principle guarantees infinite theoretical collisions.