3 ms·

In the case of MD5 and SHA1 the length (of the output) is fixed to something like 160 bits. So the length of the output will always be the same regardless of in

by jiggy2011 14y ago

In the case of MD5 and SHA1 the length (of the output) is fixed to something like 160 bits. So the length of the output will always be the same regardless of input length. There's no way you could take the complete works of shakespeare , pass it through SHA1 and then take the output and somehow reverse it (the 160bits) to get the complete works of shakespeare back out because too much information has been destroyed. It's effectively an extreme form of lossy compression. What a good hash function should do though is ensure that small changes in the source guarantee a completely different output hash.

ajanuary 14y ago
> What a good hash function should do though is ensure that small changes in the source guarantee a completely different output hash. Not always true. For example, see locality sensitive hashing [1] which relies on similar inputs being hashed to similar outputs to quickly look up similar items. That's where I think the really interesting aspect of hashing algorithms comes from - what the different characteristics are and what applications that has (speed for checksums, slow for passwords, similar inputs giving similar outputs for similarity searching) [Edit] The key characteristic of all hashing functions is it produces a fixed size output. The fact this makes a one way function is incidental; though crucial for many applications like password storage, it's not really that important for things like checksums [2] or hash tables. [1] http://en.wikipedia.org/wiki/Locality_sensitive_hashing http://en.wikipedia.org/wiki/Locality_sensitive_hashing [2] Though it can be useful if using checksums for security.
- eru 14y ago
  About your edit: That's not actually a good key characteristic. E.g. in the context of purely functional data structure, the key property is that hash functions are fast to compute and provide keys that are easy to look up, but may have collisions.
  - ajanuary 14y ago
    Apologies, I phrased that poorly. I meant the characteristic that makes it a hash function is producing a fixed size output. It may not be that important for some contexts, but without that characteristic it's not a hashing function. Conversely, I can have a function that isn't one way, but produces a fixed size output. Granted, it's not going to be that useful, but it's still a hashing function. If I have a one-way function that doesn't produce a fixed size output, it's not a hashing function.
alex-g 14y ago
This is misleading. With a one-way function, we are interested in making it hard to find any preimage, not just the one you originally thought of. There are lots of functions whose range is small, but where it's easy to find a preimage (eg: take the first 160 bits of input; XOR all 160-bit chunks together; always return 0). The avalanche effect (referred to in the last sentence) is important as a heuristic. Among other things, it makes it harder to go from an "approximate" preimage to an exact one. If we had f(x) = y, where y is similar to our target y', we shouldn't be able to find x' with f(x') = y' just by looking at the neighborhood of x. But this doesn't rule out more "clever" ways of tweaking x, and it doesn't obviously stop an attacker from deducing some property of x'. So for one-way functions, what we really want to assert is the nonexistence of an algorithm for finding (properties of) preimages, that is any better than just trying lots of new values of x.
pbhjpbhj 14y ago
>There's no way you could take the complete works of shakespeare , pass it through SHA1 // There's no practical way. Mathematically you can "just" brute force it, end of the universe will probably inhibit the practical application of that.
- jiggy2011 14y ago
  Well, you can brute force something that will hash to that, but it won't necessarily be the original text.
  - pbhjpbhj 14y ago
    How likely is a collision on two works that match the description "the complete works of shakespeare"? [this question left as an exercise for the reader]
    - jiggy2011 14y ago
      I mean, if all you have is the output hash and you have no idea what the input text was.

ajanuary 14y ago

> What a good hash function should do though is ensure that small changes in the source guarantee a completely different output hash. Not always true. For example, see locality sensitive hashing [1] which relies on similar inputs being hashed to similar outputs to quickly look up similar items. That's where I think the really interesting aspect of hashing algorithms comes from - what the different characteristics are and what applications that has (speed for checksums, slow for passwords, similar inputs giving similar outputs for similarity searching) [Edit] The key characteristic of all hashing functions is it produces a fixed size output. The fact this makes a one way function is incidental; though crucial for many applications like password storage, it's not really that important for things like checksums [2] or hash tables. [1] http://en.wikipedia.org/wiki/Locality_sensitive_hashing http://en.wikipedia.org/wiki/Locality_sensitive_hashing [2] Though it can be useful if using checksums for security.

eru 14y ago
About your edit: That's not actually a good key characteristic. E.g. in the context of purely functional data structure, the key property is that hash functions are fast to compute and provide keys that are easy to look up, but may have collisions.
- ajanuary 14y ago
  Apologies, I phrased that poorly. I meant the characteristic that makes it a hash function is producing a fixed size output. It may not be that important for some contexts, but without that characteristic it's not a hashing function. Conversely, I can have a function that isn't one way, but produces a fixed size output. Granted, it's not going to be that useful, but it's still a hashing function. If I have a one-way function that doesn't produce a fixed size output, it's not a hashing function.

alex-g 14y ago

This is misleading. With a one-way function, we are interested in making it hard to find any preimage, not just the one you originally thought of. There are lots of functions whose range is small, but where it's easy to find a preimage (eg: take the first 160 bits of input; XOR all 160-bit chunks together; always return 0). The avalanche effect (referred to in the last sentence) is important as a heuristic. Among other things, it makes it harder to go from an "approximate" preimage to an exact one. If we had f(x) = y, where y is similar to our target y', we shouldn't be able to find x' with f(x') = y' just by looking at the neighborhood of x. But this doesn't rule out more "clever" ways of tweaking x, and it doesn't obviously stop an attacker from deducing some property of x'. So for one-way functions, what we really want to assert is the nonexistence of an algorithm for finding (properties of) preimages, that is any better than just trying lots of new values of x.

pbhjpbhj 14y ago

>There's no way you could take the complete works of shakespeare , pass it through SHA1 // There's no practical way. Mathematically you can "just" brute force it, end of the universe will probably inhibit the practical application of that.

jiggy2011 14y ago
Well, you can brute force something that will hash to that, but it won't necessarily be the original text.
- pbhjpbhj 14y ago
  How likely is a collision on two works that match the description "the complete works of shakespeare"? [this question left as an exercise for the reader]
  - jiggy2011 14y ago
    I mean, if all you have is the output hash and you have no idea what the input text was.