How Hash Algorithms Work (2007)(metamorphosite.com)
metamorphosite.com
How Hash Algorithms Work (2007)
http://www.metamorphosite.com/one-way-hash-encryption-sha1-data-software
60 comments
When I read that sentence, I assumed that the author meant that the computed hash for an input must be deterministic.
But she doubles-down on the uniqueness claim later:
Each hash is unique but always repeatable The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing.
This is such a large misunderstanding of hashing (as well as being obviously impossible) that it is hard to trust the rest of the article.
But she doubles-down on the uniqueness claim later:
Each hash is unique but always repeatable The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing.
This is such a large misunderstanding of hashing (as well as being obviously impossible) that it is hard to trust the rest of the article.
This is why I love HN; I either discover a great resource, or know what to avoid and why, and I almost always learn something in the process.
Surely no guide to hash algorithms is complete without mentioning the pigeonhole principle at least once.
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.
> 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.
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.
> 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
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
But then you have to cache the input strings, I don't see how the hash could work any other way independently of the input lengths. And thats rather called an index list compared to the common use of the word, which the GPs might have thought of differently, too..
> But then you have to cache the input strings, I don't see how the hash could work any other way independently of the input lengths. And thats rather called an index list compared to the common use of the word, which the GPs might have thought of differently, too..
It's definitely possible. Here's a simplistic example. Say I have two strings:
It's a very simplistic example but the same concept can be used to identify the minimum components of the inputs that would need to be looked at to create a unique hash function. It won't be a general hash function though; it's specific to that data set.
Note that this isn't useless either. It's common to have a fixed/known lists of strings that you want to do lookups upon.
It's definitely possible. Here's a simplistic example. Say I have two strings:
A really long string that goes on for [truncated] ...
Some other really long string goes on for [truncated] ...
It's a very simplistic example but the same concept can be used to identify the minimum components of the inputs that would need to be looked at to create a unique hash function. It won't be a general hash function though; it's specific to that data set.
Note that this isn't useless either. It's common to have a fixed/known lists of strings that you want to do lookups upon.
It's the arbitrary length that causes you to have more pigeons than pigeonholes.
> It's the arbitrary length that causes you to have more pigeons than pigeonholes.
No you can have a fixed length and arbitrary text. Say the input could be 32 hex characters representing a UUID. The key distinction is whether there is a finite / known list of the possible inputs. If so, then it's possible to create a hash function the perfectly hashes them.
No you can have a fixed length and arbitrary text. Say the input could be 32 hex characters representing a UUID. The key distinction is whether there is a finite / known list of the possible inputs. If so, then it's possible to create a hash function the perfectly hashes them.
Um, a fixed set of inputs cannot be of arbitrary length, since you by definition know the size of the longest possible input string.
The point is that a function cannot bijectively compress arbitrary input into fixed output. Of course if you make the function itself depend on the input itself, then you can pull all sorts of tricks, but normally we do not call a simple lookup table a 'hash function', because they are very different things.
The point is that a function cannot bijectively compress arbitrary input into fixed output. Of course if you make the function itself depend on the input itself, then you can pull all sorts of tricks, but normally we do not call a simple lookup table a 'hash function', because they are very different things.
>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?
Don't hashing functions have collisions?
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.
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.
> 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).
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).
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...
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...
> 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.
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.
> 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.
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.
>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
>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.
This is wrong. There is something called a 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.
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.
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.
Though 2^n could be much larger than the number of items in the observable universe fairly quickly.
More precisely, collisions should be as unpredictable as hashes themselves, so the only way to find collisions is brute force.
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 '...'
> Also, it should be computationally infeasible to find any other word which also hashes to '...'
> 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.
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.
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.
Only now I understand why people use (sic)
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.
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.
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.
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.
"A Comprehensive and fundamentally innacurate guide"
Saying they're unique is just very very wrong.
Saying they're unique is just very very wrong.
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
$ echo 'test' | sha1
4e1243bd22c66e76c2ba9eddc1f91394e57f9f83
:-P
echo -n 'test' | sha1
a94a8fe5ccb19ba61c4c0873d391e987982fbbd3The 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.
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.
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.
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.
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).
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).
As someone extremely new to this; can this procedure be worked backwards to retrieve the original text? If no, why not?
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).
>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.
?
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.
> 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.
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.
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).
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.
Of course this is assuming that the hash algorithm doesn't have any weaknesses you could exploit.
> Of course you could work backwards to find out which inputs could lead to a particular result
AKA rainbow tables, which explains why it is important not to use just a single word from the dictionary as a password.
https://en.wikipedia.org/wiki/Rainbow_table
AKA rainbow tables, which explains why it is important not to use just a single word from the dictionary as a password.
https://en.wikipedia.org/wiki/Rainbow_table
As explained in your link, rainbow tables make salts important. Imposing arbitrary requirements on users is misguided.
[deleted]
No, one important property of hashes in security applications is irreversibility (except for brute force, i.e. try and error).
For example, user passwords on a server should only be stored in hashed form (ideally with salt[1]). If an attacker gets access to that database, they will not be able to restore the original passwords without enormous computation costs.
The "why not" is harder two answer and I don't know all the details either. But the general idea is that the hashing algorithm contains irreversible operations where multiple (intermediate) inputs would result in the same (intermediate) output, so you cannot derive a unique input from the output.
A simple example for this is the modulo function: 9 mod 7 = 2, but also 16 mod 7 = 2. If you now see the result 2, the original number could have been 2, 9, 16, 23 or anything else of the form n*7 + 2.
[1]: https://en.wikipedia.org/wiki/Salt_(cryptography)
For example, user passwords on a server should only be stored in hashed form (ideally with salt[1]). If an attacker gets access to that database, they will not be able to restore the original passwords without enormous computation costs.
The "why not" is harder two answer and I don't know all the details either. But the general idea is that the hashing algorithm contains irreversible operations where multiple (intermediate) inputs would result in the same (intermediate) output, so you cannot derive a unique input from the output.
A simple example for this is the modulo function: 9 mod 7 = 2, but also 16 mod 7 = 2. If you now see the result 2, the original number could have been 2, 9, 16, 23 or anything else of the form n*7 + 2.
[1]: https://en.wikipedia.org/wiki/Salt_(cryptography)
This type of crypto hash is like hamburgers and cows (as a rather crude analogy): it's fairly easy to make a hamburger from the meat of the dead cow, almost impossible to make a cow from the hamburger meat.
In theory yes. In practice no, because cryptographic hashes are designed to make this as hard as possible. AFAIK you cannot prove that they are secure, so it might be possible that known hashes can be broken entirely by using some breakthrough techniques of cryptanalysis.
There is currently not much reason to believe such techniques exist, except perhaps for persistent rumors that the NSA is running some computationally very extensive operations (maybe with custom-built chips) that might be put to use for direct attacks on some weaker cryptographic algorithms like 2DES, RC4, SHA1, or 1024 bit RSA. That's pure speculation, though.
There is currently not much reason to believe such techniques exist, except perhaps for persistent rumors that the NSA is running some computationally very extensive operations (maybe with custom-built chips) that might be put to use for direct attacks on some weaker cryptographic algorithms like 2DES, RC4, SHA1, or 1024 bit RSA. That's pure speculation, though.
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?
Is "Step 5: Add '1' to the end"
Is this a delimiter for beginning of the padding or does it server some other purpose?
>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.
add a "rainbow tables" caveat to that.
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?
Can anyone recommand resources about the actual design of (cryptographic) hash algorithms?
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.
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.
49 + 399 = 448
448 mod 512 = 448, because 512 goes into 448 zero times with a remainder of 448.
Thanks! Notice the error in their second example?
What is the name of the hashing algorithm broken down in the article?
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.
> 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".