8 ms·

How Hash Algorithms Work (2007)

175 points by jjoachim3 10y ago

rkda 10y ago
>The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing. Don't hashing functions have collisions?
- bhaak 10y ago
  Yes. This is trivially obvious by reasoning that a hash is a function that maps arbitrary data to data of a fixed size. There must be collisions otherwise it couldn't hash any possible string. Usually you want a hash that maps similar strings to completely different output hashes (and I guess that's what the author actually wanted to describe). But that is not a necessity of a hash function, just a usual property.
- marklgr 10y ago
  > Also, it should be computationally infeasible to find any other word which also hashes to [...] He knows there are collisions, he just chose to start with the simplest explanation and add the useful details as he moves on. It's fine by me, even though engineers tend not to like that (they prefer accuracy from the word go).
- jasode 10y ago
  You're right but I'm guessing the writer is thinking of the limited list of English "words". 1.46 x 10^48 = sha1 possible outputs ~7.5 x 10^5 = total English words [1] If you computed all ~750,000 hashes for all known English words, none of the sha1 hashes will match sha1("cat"). I'm guessing that you still wouldn't get a collision if you include all words from all world languages. For "words" to generate a collision, you'd have to increase the input domain by allowing "words" to mean any sequence of bytes (e.g. bytes of jpg image or audio file). [1] https://en.oxforddictionaries.com/explore/how-many-words-are-there-in-the-english-language https://en.oxforddictionaries.com/explore/how-many-words-are...
  - comicjk 10y ago
    > For "words" to generate a collision, you'd have to increase the input domain by allowing "words" to mean any sequence of bytes (e.g. bytes of jpg image or audio file). That is way overkill - the input domain could just be strings of words. Each word of a typical English text adds about one byte of entropy (2^8 states). We get a probable collision by having a number of text states around the square root of the number of hash states (because of the birthday paradox). So, sqrt(10^48) = 10^24 = (10^3)^8 which is about (2^10)^8. So the space of ordinary 10-word strings is big enough to give a sha-1 collision, without invoking inputs like binary files.
- hannob 10y ago
  > Don't hashing functions have collisions? They do. The text is somewhat misleading and not properly explaining that. All hash functions have collisions. But from a cryptographically secure hash function we expect that nobody is able to find such a collision. They exist, but the computational power to find one is not available to humans.
  - blauditore 10y ago
    More precisely, collisions should be as unpredictable as hashes themselves, so the only way to find collisions is brute force.
  - isolli 10y ago
    To be fair, it is better explained later in the text. But definitely misleading. > Also, it should be computationally infeasible to find any other word which also hashes to '...'
  - winston1984 10y ago
    >They do. >All hash functions have collisions. This is wrong. There is something called a perfect hash function: https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function >a perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions. In mathematical terms, it is a total injective function. They are very handy for hash tables with constant worst-case lookup time.
    - halomru 10y ago
      While very useful, you can only construct a collision-free hash function if you know all possible inputs. Otherwise perfect hash functions can only give guarantees over the frequency of collisions. In the more general case, for a hash function with n bits output, the pigeon hole principle demands that we have a collision at least every 2^n inputs.
      - chris_va 10y ago
- clishem 10y ago
  > If you are given the value of what 'cat' hashes too but you didn't know what made it, you would never be able to find out that 'cat' was the original word. This is false or inaccurate at best too. More correct would be that it should be computationally infeasible for any one entity to have any reasonable chance to obtaining the inverse of a hash, in the foreseeable future. With all hashing functions in existence, it's always theoretically possible to find the inverse, and that should be pointed out.
  - JohnStrange 10y ago
    Not only that it's also false from a practical perspective because you can easily find out that 'cat' was the original word by going through a list of hashes of all English words (>rainbow table attacks). That's why you use salts.
  - fooza 10y ago
    Only now I understand why people use (sic)
Curious42 10y ago
As someone extremely new to this; can this procedure be worked backwards to retrieve the original text? If no, why not?
- seanwilson 10y ago
  You can't retrieve the original text because information is lost in the process and many inputs hash to the same value. However, if the range of inputs is relatively limited, you can try hashing inputs until you find the right hash (see rainbow tables for discovering user passwords from the hash value).
  - _coldfire 10y ago
    >many inputs hash to the same value ? The chances of a sha256 collision is essentially zero barring a vulnerability being found in sha2. Far more likely for a comet to wipe out earth in your lifetime.
    - xyzzyz 10y ago
      Chances of practically finding a collision are indeed really small, though as you can easily calculate, there exists a sha256 hash value such that there are at least 2^256 different 512-bit long bit strings that map to it (and actually most of them should have this property).
    - seanwilson 10y ago
      > The chances of a sha256 collision is essentially zero barring a vulnerability being found in sha2. Yes, but to answer the question if you can find the input from the hash, the answer is no because it's impossible to be 100% certain as many input can hash to the same value.
- contravariant 10y ago
  Not all operations are reversible, which makes it difficult to work out a simple inverse. Of course you could work backwards to find out which inputs could lead to a particular result, but this set of possible inputs would grow rapidly as you work your way back through the algorithm, making it nigh impossible to work out the original message, even if you have some idea what it's supposed to look like. Of course this is assuming that the hash algorithm doesn't have any weaknesses you could exploit.
mbel 10y ago
The title probably should be 'Cryptographic Hash Algorithms'. The definitions from the post are approximately true for cryptographic hashes but not really for hash functions in general.
- js8 10y ago
  I agree, it's definitely not a "comprehensive" guide. If it was comprehensive, it would include different algorithms, trade offs, talk about things like perfect hashing, hashes that preserve ordering, etc.
- bogomipz 10y ago
  Does anyone have a "more" comprehensive guide they can recommend? There were parts of this I really liked but some of the "why" left me confused.
zebra1832 10y ago
Title is very misleading. Only one hash function is presented. Afaict the presented hashing function is not even named. Is it SHA1? No motivation is given, just (pseudo)code.
jdwyah 10y ago
"A Comprehensive and fundamentally innacurate guide" Saying they're unique is just very very wrong.
- jm0dotcodes 10y ago
  I can subscribe to this statement. I found that i don't get the same SHA-1 hash of 'test' as he did. $ echo 'test' | sha1 4e1243bd22c66e76c2ba9eddc1f91394e57f9f83 :-P
  - Sholmesy 10y ago
    echo -n 'test' | sha1 will give you the same output as the article by removing the new line. a94a8fe5ccb19ba61c4c0873d391e987982fbbd3
tomlx 10y ago
Title is missleading. From the title I expected something about how to design a hash algorithm, but the article is just a walk through the specific operations SHA-1 performs w/o further explanation. Can anyone recommand resources about the actual design of (cryptographic) hash algorithms?
DanBC 10y ago
It's a nice article, although they probably need to say that they're talking about cryptographic hashes earlier on, at least mention that some hashes are very easy to find collisions with.
glidek 10y ago
What is the name of the hashing algorithm broken down in the article?
stygiansonic 10y ago
This is really a walk through of the SHA-1 algorithm. It's also worthwhile to note that the statement that a hash takes a string and reduces it to a fixed length string is a little misleading. They really work at the binary level and this is seen in the example where the input is converted to binary assuming ASCII and the output hex encoded.
- A_Crazy_Idea 10y ago
  This is really a test of ycombinator users.
- Ar-Curunir 10y ago
  you could easily define hash functions that work over A..Z if you wanted; there's nothing special about that. The misleading part is about the reduction to a unique fixed length string; that's not possible unless the input domain is equal to (or smaller than) the output domain (and even then it's not necessary). Any other function is guaranteed to have collisions.
koolba 10y ago
The first section is wrong (emphasis mine): > A hash function is simply an algorithm that takes a string of any length and reduces it to a unique fixed length string. Hash functions strive for uniqueness but unless it's precalculated to ensure that it's true (by hashing every combination or deriving the parameters of the hash function accordingly), it's not guaranteed. A cryptographic hash function gives a high probability of uniqueness but again it's not guaranteed. > The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing. Say I have a (terrible) hash function H(X) => 1. Now "cat" will hash to the same value as the string "I don't understand hash functions".
- Berobero 10y ago
  Surely no guide to hash algorithms is complete without mentioning the pigeonhole principle at least once.
  - ReverseCold 10y ago
    Just learned about this => simply states that if you have x objects and y containers, where x>y, one container must have more than one object.
- curun1r 10y ago
  > Hash functions strive for uniqueness No hash function strives for uniqueness. As long as the digest length is shorter than the input length, you can logically guarantee that there will be collisions. And since all general purpose hash functions allow arbitrary length input data, this is always the case. But what cryptographic hash functions strive for is the difficulty in finding a collision. It's mathematically guaranteed to be there, but finding it should cost a prohibitively large amount of time and computing resources. There are also non-cryptographic hashes that only strive for the unlikelihood of accidentally getting a collision and don't protect against heavily contrived input data.
  - koolba 10y ago
    > No hash function strives for uniqueness. As long as the digest length is shorter than the input length, you can logically guarantee that there will be collisions. Nope! For a known set of N inputs of length K, I can devise a hash function that maps then to a log2(N) bit result with zero collisions regardless of K. > And since all general purpose hash functions allow arbitrary length input data, this is always the case. It's not the arbitrary length data that breaks the uniqueness guarantee. It's that you can have 2^X + 1 entries where you only have X bits of hash result: https://en.wikipedia.org/wiki/Pigeonhole_principle https://en.wikipedia.org/wiki/Pigeonhole_principle
Zash 10y ago
A hash function takes variable length input and returns a fixed length output, that's all. Then there are sub-categories optimized for things like use in hash tables or building blocks in crypto, all with varying emphasis on uniqueness, output size and speed.
libruary 10y ago
Would someone be able to ELI5 step 6 for me? I don't understand the math needed in order to determine that 399 zeros needed to be added.
- nolepointer 10y ago
  49 + 399 = 448 448 mod 512 = 448, because 512 goes into 448 zero times with a remainder of 448.
  - libruary 10y ago
    Thanks! Notice the error in their second example?
bogomipz 10y ago
I have a question about Step 5 in the post, it states: Is "Step 5: Add '1' to the end" Is this a delimiter for beginning of the padding or does it server some other purpose?
tannranger 10y ago
So there's a lot of talk about how encryption algorithms relying on the difficulty of factoring primes could be weakened by quantum computers in the near future. Are there any technological advances or scenarios where the security of hash algorithms could be weakened (other than computers just getting fasters via ~Moore's Law).
- lindig 10y ago
  Surely you mean factoring numbers into primes as primes cannot be factored.
  - tannranger 10y ago
    Right :X
natch 10y ago
>Finally, if I were to give you only 'a94a8fe5ccb19ba61c4c0873d391e987982fbbd3' and tell you that it came from the SHA-1, you should have absolutely no way to figure out what was put into the function to create that. add a "rainbow tables" caveat to that.

175 points by jjoachim3 10y ago

rkda 10y ago

>The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing. Don't hashing functions have collisions?

bhaak 10y ago
Yes. This is trivially obvious by reasoning that a hash is a function that maps arbitrary data to data of a fixed size. There must be collisions otherwise it couldn't hash any possible string. Usually you want a hash that maps similar strings to completely different output hashes (and I guess that's what the author actually wanted to describe). But that is not a necessity of a hash function, just a usual property.
marklgr 10y ago
> Also, it should be computationally infeasible to find any other word which also hashes to [...] He knows there are collisions, he just chose to start with the simplest explanation and add the useful details as he moves on. It's fine by me, even though engineers tend not to like that (they prefer accuracy from the word go).
jasode 10y ago
You're right but I'm guessing the writer is thinking of the limited list of English "words". 1.46 x 10^48 = sha1 possible outputs ~7.5 x 10^5 = total English words [1] If you computed all ~750,000 hashes for all known English words, none of the sha1 hashes will match sha1("cat"). I'm guessing that you still wouldn't get a collision if you include all words from all world languages. For "words" to generate a collision, you'd have to increase the input domain by allowing "words" to mean any sequence of bytes (e.g. bytes of jpg image or audio file). [1] https://en.oxforddictionaries.com/explore/how-many-words-are-there-in-the-english-language https://en.oxforddictionaries.com/explore/how-many-words-are...
- comicjk 10y ago
  > For "words" to generate a collision, you'd have to increase the input domain by allowing "words" to mean any sequence of bytes (e.g. bytes of jpg image or audio file). That is way overkill - the input domain could just be strings of words. Each word of a typical English text adds about one byte of entropy (2^8 states). We get a probable collision by having a number of text states around the square root of the number of hash states (because of the birthday paradox). So, sqrt(10^48) = 10^24 = (10^3)^8 which is about (2^10)^8. So the space of ordinary 10-word strings is big enough to give a sha-1 collision, without invoking inputs like binary files.
hannob 10y ago
> Don't hashing functions have collisions? They do. The text is somewhat misleading and not properly explaining that. All hash functions have collisions. But from a cryptographically secure hash function we expect that nobody is able to find such a collision. They exist, but the computational power to find one is not available to humans.
- blauditore 10y ago
  More precisely, collisions should be as unpredictable as hashes themselves, so the only way to find collisions is brute force.
- isolli 10y ago
  To be fair, it is better explained later in the text. But definitely misleading. > Also, it should be computationally infeasible to find any other word which also hashes to '...'
- winston1984 10y ago
  >They do. >All hash functions have collisions. This is wrong. There is something called a perfect hash function: https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function >a perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions. In mathematical terms, it is a total injective function. They are very handy for hash tables with constant worst-case lookup time.
  - halomru 10y ago
    While very useful, you can only construct a collision-free hash function if you know all possible inputs. Otherwise perfect hash functions can only give guarantees over the frequency of collisions. In the more general case, for a hash function with n bits output, the pigeon hole principle demands that we have a collision at least every 2^n inputs.
    - chris_va 10y ago
clishem 10y ago
> If you are given the value of what 'cat' hashes too but you didn't know what made it, you would never be able to find out that 'cat' was the original word. This is false or inaccurate at best too. More correct would be that it should be computationally infeasible for any one entity to have any reasonable chance to obtaining the inverse of a hash, in the foreseeable future. With all hashing functions in existence, it's always theoretically possible to find the inverse, and that should be pointed out.
- JohnStrange 10y ago
  Not only that it's also false from a practical perspective because you can easily find out that 'cat' was the original word by going through a list of hashes of all English words (>rainbow table attacks). That's why you use salts.
- fooza 10y ago
  Only now I understand why people use (sic)

Curious42 10y ago

As someone extremely new to this; can this procedure be worked backwards to retrieve the original text? If no, why not?

seanwilson 10y ago
You can't retrieve the original text because information is lost in the process and many inputs hash to the same value. However, if the range of inputs is relatively limited, you can try hashing inputs until you find the right hash (see rainbow tables for discovering user passwords from the hash value).
- _coldfire 10y ago
  >many inputs hash to the same value ? The chances of a sha256 collision is essentially zero barring a vulnerability being found in sha2. Far more likely for a comet to wipe out earth in your lifetime.
  - xyzzyz 10y ago
    Chances of practically finding a collision are indeed really small, though as you can easily calculate, there exists a sha256 hash value such that there are at least 2^256 different 512-bit long bit strings that map to it (and actually most of them should have this property).
  - seanwilson 10y ago
    > The chances of a sha256 collision is essentially zero barring a vulnerability being found in sha2. Yes, but to answer the question if you can find the input from the hash, the answer is no because it's impossible to be 100% certain as many input can hash to the same value.
contravariant 10y ago
Not all operations are reversible, which makes it difficult to work out a simple inverse. Of course you could work backwards to find out which inputs could lead to a particular result, but this set of possible inputs would grow rapidly as you work your way back through the algorithm, making it nigh impossible to work out the original message, even if you have some idea what it's supposed to look like. Of course this is assuming that the hash algorithm doesn't have any weaknesses you could exploit.

mbel 10y ago

The title probably should be 'Cryptographic Hash Algorithms'. The definitions from the post are approximately true for cryptographic hashes but not really for hash functions in general.

js8 10y ago
I agree, it's definitely not a "comprehensive" guide. If it was comprehensive, it would include different algorithms, trade offs, talk about things like perfect hashing, hashes that preserve ordering, etc.
bogomipz 10y ago
Does anyone have a "more" comprehensive guide they can recommend? There were parts of this I really liked but some of the "why" left me confused.

zebra1832 10y ago

Title is very misleading. Only one hash function is presented. Afaict the presented hashing function is not even named. Is it SHA1? No motivation is given, just (pseudo)code.

jdwyah 10y ago

"A Comprehensive and fundamentally innacurate guide" Saying they're unique is just very very wrong.

jm0dotcodes 10y ago
I can subscribe to this statement. I found that i don't get the same SHA-1 hash of 'test' as he did. $ echo 'test' | sha1 4e1243bd22c66e76c2ba9eddc1f91394e57f9f83 :-P
- Sholmesy 10y ago
  echo -n 'test' | sha1 will give you the same output as the article by removing the new line. a94a8fe5ccb19ba61c4c0873d391e987982fbbd3

tomlx 10y ago

Title is missleading. From the title I expected something about how to design a hash algorithm, but the article is just a walk through the specific operations SHA-1 performs w/o further explanation. Can anyone recommand resources about the actual design of (cryptographic) hash algorithms?

DanBC 10y ago

It's a nice article, although they probably need to say that they're talking about cryptographic hashes earlier on, at least mention that some hashes are very easy to find collisions with.

glidek 10y ago

What is the name of the hashing algorithm broken down in the article?

stygiansonic 10y ago

This is really a walk through of the SHA-1 algorithm. It's also worthwhile to note that the statement that a hash takes a string and reduces it to a fixed length string is a little misleading. They really work at the binary level and this is seen in the example where the input is converted to binary assuming ASCII and the output hex encoded.

A_Crazy_Idea 10y ago
This is really a test of ycombinator users.
Ar-Curunir 10y ago
you could easily define hash functions that work over A..Z if you wanted; there's nothing special about that. The misleading part is about the reduction to a unique fixed length string; that's not possible unless the input domain is equal to (or smaller than) the output domain (and even then it's not necessary). Any other function is guaranteed to have collisions.

koolba 10y ago

The first section is wrong (emphasis mine): > A hash function is simply an algorithm that takes a string of any length and reduces it to a unique fixed length string. Hash functions strive for uniqueness but unless it's precalculated to ensure that it's true (by hashing every combination or deriving the parameters of the hash function accordingly), it's not guaranteed. A cryptographic hash function gives a high probability of uniqueness but again it's not guaranteed. > The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing. Say I have a (terrible) hash function H(X) => 1. Now "cat" will hash to the same value as the string "I don't understand hash functions".

Berobero 10y ago
Surely no guide to hash algorithms is complete without mentioning the pigeonhole principle at least once.
- ReverseCold 10y ago
  Just learned about this => simply states that if you have x objects and y containers, where x>y, one container must have more than one object.
curun1r 10y ago
> Hash functions strive for uniqueness No hash function strives for uniqueness. As long as the digest length is shorter than the input length, you can logically guarantee that there will be collisions. And since all general purpose hash functions allow arbitrary length input data, this is always the case. But what cryptographic hash functions strive for is the difficulty in finding a collision. It's mathematically guaranteed to be there, but finding it should cost a prohibitively large amount of time and computing resources. There are also non-cryptographic hashes that only strive for the unlikelihood of accidentally getting a collision and don't protect against heavily contrived input data.
- koolba 10y ago
  > No hash function strives for uniqueness. As long as the digest length is shorter than the input length, you can logically guarantee that there will be collisions. Nope! For a known set of N inputs of length K, I can devise a hash function that maps then to a log2(N) bit result with zero collisions regardless of K. > And since all general purpose hash functions allow arbitrary length input data, this is always the case. It's not the arbitrary length data that breaks the uniqueness guarantee. It's that you can have 2^X + 1 entries where you only have X bits of hash result: https://en.wikipedia.org/wiki/Pigeonhole_principle https://en.wikipedia.org/wiki/Pigeonhole_principle

Zash 10y ago

A hash function takes variable length input and returns a fixed length output, that's all. Then there are sub-categories optimized for things like use in hash tables or building blocks in crypto, all with varying emphasis on uniqueness, output size and speed.

libruary 10y ago

Would someone be able to ELI5 step 6 for me? I don't understand the math needed in order to determine that 399 zeros needed to be added.

nolepointer 10y ago
49 + 399 = 448 448 mod 512 = 448, because 512 goes into 448 zero times with a remainder of 448.
- libruary 10y ago
  Thanks! Notice the error in their second example?

bogomipz 10y ago

I have a question about Step 5 in the post, it states: Is "Step 5: Add '1' to the end" Is this a delimiter for beginning of the padding or does it server some other purpose?

tannranger 10y ago

So there's a lot of talk about how encryption algorithms relying on the difficulty of factoring primes could be weakened by quantum computers in the near future. Are there any technological advances or scenarios where the security of hash algorithms could be weakened (other than computers just getting fasters via ~Moore's Law).

lindig 10y ago
Surely you mean factoring numbers into primes as primes cannot be factored.
- tannranger 10y ago
  Right :X

natch 10y ago

>Finally, if I were to give you only 'a94a8fe5ccb19ba61c4c0873d391e987982fbbd3' and tell you that it came from the SHA-1, you should have absolutely no way to figure out what was put into the function to create that. add a "rainbow tables" caveat to that.