How Hash Algorithms Work (2007) • Hacker News Board

Re: How Hash Algorithms Work (2007)

#31

Post by koolba » Fri, Jan 13, 2017, 3:17 PM UTC

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

Re: How Hash Algorithms Work (2007)

#32

Post by _coldfire » Fri, Jan 13, 2017, 3:30 PM UTC

seanwilson wrote: post #9

Curious42 wrote: post #8

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.

Re: How Hash Algorithms Work (2007)

#33

Post by Berobero » Fri, Jan 13, 2017, 3:49 PM UTC

koolba wrote: post #31

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

Surely no guide to hash algorithms is complete without mentioning the pigeonhole principle at least once.

Re: How Hash Algorithms Work (2007)

#34

Post by xyzzyz » Fri, Jan 13, 2017, 3:59 PM UTC

_coldfire wrote: post #32

seanwilson wrote: post #9

Earlier quoted context omitted.

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

Re: How Hash Algorithms Work (2007)

#35

Post by Zash » Fri, Jan 13, 2017, 4:03 PM UTC

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.

Re: How Hash Algorithms Work (2007)

#36

Post by jm0dotcodes » Fri, Jan 13, 2017, 4:07 PM UTC

jdwyah wrote: post #21

"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

Re: How Hash Algorithms Work (2007)

#37

Post by libruary » Fri, Jan 13, 2017, 4:41 PM UTC

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.

Re: How Hash Algorithms Work (2007)

#38

Post by Sholmesy » Fri, Jan 13, 2017, 4:43 PM UTC

jm0dotcodes wrote: post #36

jdwyah wrote: post #21

"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

Re: How Hash Algorithms Work (2007)

#39

Post by chris_va » Fri, Jan 13, 2017, 4:46 PM UTC

halomru wrote: post #26

winston1984 wrote: post #19

Earlier quoted context omitted.

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

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.

Re: How Hash Algorithms Work (2007)

#40

Post by Ar-Curunir » Fri, Jan 13, 2017, 5:21 PM UTC

stygiansonic wrote: post #29

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.