Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How Hash Algorithms Work (2007)

metamorphosite.com

Post reply on HN
Print view View original

41–50 of 61 posts

Re: How Hash Algorithms Work (2007)

#41

Post by JohnStrange »

clishem wrote: post #22
rkda wrote: post #2

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

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

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.

Re: How Hash Algorithms Work (2007)

#42

Post by JohnStrange »

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?

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.

Re: How Hash Algorithms Work (2007)

#44

Post by curun1r »

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…

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

Re: How Hash Algorithms Work (2007)

#45

Post by fooza »

clishem wrote: post #22
rkda wrote: post #2

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

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

Only now I understand why people use (sic)

Re: How Hash Algorithms Work (2007)

#46

Post by bquinlan »

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…

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.

Re: How Hash Algorithms Work (2007)

#47

Post by koolba »

curun1r wrote: post #44
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…

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

> 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

Re: How Hash Algorithms Work (2007)

#49

Post by tannranger »

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

Re: How Hash Algorithms Work (2007)

#50

Post by lindig »

tannranger wrote: post #49

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.
Post reply on HN