How Hash Algorithms Work (2007) | Hacker News Reader

How Hash Algorithms Work (2007)

metamorphosite.com

175 pointsjjoachim358 comments

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

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.

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

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.

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.

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:

     A really long string that goes on for [truncated] ...

and

     Some other really long string goes on for [truncated] ...

I can create a hash function that looks at the first character at gives either a 0 or 1 depending on whether it's an "A". For that known data set it'll perfectly hash the two strings into two buckets.

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.

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.

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.

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

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.

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

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

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

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

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

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

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.

Though 2^n could be much larger than the number of items in the observable universe fairly quickly.

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

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.

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.

"A Comprehensive and fundamentally innacurate guide"

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 -n 'test' | sha1

will give you the same output as the article by removing the new line.

    a94a8fe5ccb19ba61c4c0873d391e987982fbbd3

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.

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

Surely you mean factoring numbers into primes as primes cannot be factored.

Right :X

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.

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

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

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

As explained in your link, rainbow tables make salts important. Imposing arbitrary requirements on users is misguided.

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)

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.

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?

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

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?

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.

Reply on news.ycombinator.com