9 ms·

Slightly off-topic, but I've been intrigued by one way functions for quite a while now. How does someone go about making a one way function like MD5 and SHA1? H

by rustc 13y ago

Slightly off-topic, but I've been intrigued by one way functions for quite a while now. How does someone go about making a one way function like MD5 and SHA1? How do you know it can't be reversed easily?

masklinn 13y ago
http://en.wikipedia.org/wiki/Cryptographic_hash http://en.wikipedia.org/wiki/Cryptographic_hash should be an OK start, with further links to more precise explanations of the crypto concepts. > How do you know it can't be reversed easily? Some you prove: http://en.wikipedia.org/wiki/Provably_secure_cryptographic_hash_function http://en.wikipedia.org/wiki/Provably_secure_cryptographic_h... But more commonly (because provably secure crypto functions are extremely hard to design) you think hard about them, then unleash fellow and opposing crypto specialists to try and break them[0], as was done by NIST[1] [0] http://en.wikipedia.org/wiki/Cryptanalysis http://en.wikipedia.org/wiki/Cryptanalysis [1] http://en.wikipedia.org/wiki/NIST_hash_function_competition http://en.wikipedia.org/wiki/NIST_hash_function_competition
- martinced 13y ago
  > How do you know it can't be reversed easily? It is impossible to reverse because information is lost. There's an infinite number of "plain text" leading to a same hash. If you could reverse, say, SHA-1, then you'd just have invented the best compression scheme ever and the world as we know it would be no more: the implication would be huger than anything we can imagine. You could compress a full movie in a SHA-1 hash. Not. Gonna. Happen. It is impossible. The problem is not reversing information: reversing is simply impossible. The problem is finding collisions and hence being able to create plain texts that shall lead to the same hash.
- bo1024 13y ago
  It should be noted that we still don't "know": even "provably" secure functions depend on an assumption that may or may not be true, such as that factoring integers is much harder than multiplying them. Of course, almost everyone thinks these problems are in fact hard (at least for classical computers), but there's no proof (such a proof would imply P != NP).
  - mjn 13y ago
    The assumption needed is even stronger than the complexity-class question: even if you proved integer factorization was not in P, that wouldn't be enough, since you need integer factorization to be almost always hard in every instance of the problem. Or at least you must have some way to identify and exclude the easy-to-solve instances. Example: SAT-solving is NP-complete, but nonetheless heuristic SAT solvers are very good in practice, which makes its hardness too weak for cryptographic use. That can be ameliorated by trying to identify a more specific subset of "actually hard to solve SAT" (some of the research on the SAT "phase transition" aims at this), but it's pretty difficult. A few problems like integer factorization seem to have just arrived with this apparent always-hard property, but attempts to engineer it have been less successful, hence to my knowledge no used-in-practice cryptosystem is based on taking an NP-hard problem and turning it into a cryptographically useful one-way function (even though Diffie & Hellman suggested that as a research agenda way back in 1976). I wrote an essay on that subject a few years ago, since the reverse question also comes up in AI discussions: http://www.kmjn.org/notes/nphard_not_always_hard.html http://www.kmjn.org/notes/nphard_not_always_hard.html
    - betterunix 13y ago
      "to my knowledge no used-in-practice cryptosystem is based on taking an NP-hard problem and turning it into a cryptographically useful one-way function" Not used in practice, but such a result was presented by Atjai and Dwork: https://dl.acm.org/citation.cfm?id=258604 https://dl.acm.org/citation.cfm?id=258604
    - eru 13y ago
      There were some attempts to make the knapsack problem into an encryption system. But the early attempts were broken, then patched up and re-broken etc, and nobody has invested enough time into breaking the latest efforts, so cryptographers don't trust it.
    - tgflynn 13y ago
      An interesting thing about this is that you can transform the integer factorization problem into SAT quite easily (I have code that does it). The resulting SAT problems seem to be hard to solve for heuristic SAT solvers once you get beyond a very small number of bits for the integer sizes.
jiggy2011 13y 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 13y 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 13y 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 13y 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.
CJefferson 13y ago
On the question of "can't be reversed easily", the only real way is to try getting lots of clever people to try to break it :) There are also standard attacking techniques, so you can check (and maybe prove) these techniques do not work, but that still does not show there is a trivial crack you have missed.
betterunix 13y ago
"How does someone go about making a one way function" It's hard -- cryptographers have yet to even prove that one way functions actually exist! We have lots of theoretical candidates -- discrete logarithms for certain groups, integer factorization, problems related to hidden linear codes, and so forth. Some day, we will either prove that OWFs do not exist, or that OWFs do exist (and hopefully one of the candidates is actually an OWF), or that the existence or non-existence of OWFs is independent of the mathematical systems we use right now (i.e. that it is an axiom). Having said that, you might be interested in the work of Atjai and Dwork on creating an OWF (a trapdoor OWF, actually, and a corresponding public key cryptosystem) from an NP-Hard problem: https://dl.acm.org/citation.cfm?id=258604 https://dl.acm.org/citation.cfm?id=258604

by rustc 13y ago

masklinn 13y ago

http://en.wikipedia.org/wiki/Cryptographic_hash http://en.wikipedia.org/wiki/Cryptographic_hash should be an OK start, with further links to more precise explanations of the crypto concepts. > How do you know it can't be reversed easily? Some you prove: http://en.wikipedia.org/wiki/Provably_secure_cryptographic_hash_function http://en.wikipedia.org/wiki/Provably_secure_cryptographic_h... But more commonly (because provably secure crypto functions are extremely hard to design) you think hard about them, then unleash fellow and opposing crypto specialists to try and break them[0], as was done by NIST[1] [0] http://en.wikipedia.org/wiki/Cryptanalysis http://en.wikipedia.org/wiki/Cryptanalysis [1] http://en.wikipedia.org/wiki/NIST_hash_function_competition http://en.wikipedia.org/wiki/NIST_hash_function_competition

martinced 13y ago
> How do you know it can't be reversed easily? It is impossible to reverse because information is lost. There's an infinite number of "plain text" leading to a same hash. If you could reverse, say, SHA-1, then you'd just have invented the best compression scheme ever and the world as we know it would be no more: the implication would be huger than anything we can imagine. You could compress a full movie in a SHA-1 hash. Not. Gonna. Happen. It is impossible. The problem is not reversing information: reversing is simply impossible. The problem is finding collisions and hence being able to create plain texts that shall lead to the same hash.
bo1024 13y ago
It should be noted that we still don't "know": even "provably" secure functions depend on an assumption that may or may not be true, such as that factoring integers is much harder than multiplying them. Of course, almost everyone thinks these problems are in fact hard (at least for classical computers), but there's no proof (such a proof would imply P != NP).
- mjn 13y ago
  The assumption needed is even stronger than the complexity-class question: even if you proved integer factorization was not in P, that wouldn't be enough, since you need integer factorization to be almost always hard in every instance of the problem. Or at least you must have some way to identify and exclude the easy-to-solve instances. Example: SAT-solving is NP-complete, but nonetheless heuristic SAT solvers are very good in practice, which makes its hardness too weak for cryptographic use. That can be ameliorated by trying to identify a more specific subset of "actually hard to solve SAT" (some of the research on the SAT "phase transition" aims at this), but it's pretty difficult. A few problems like integer factorization seem to have just arrived with this apparent always-hard property, but attempts to engineer it have been less successful, hence to my knowledge no used-in-practice cryptosystem is based on taking an NP-hard problem and turning it into a cryptographically useful one-way function (even though Diffie & Hellman suggested that as a research agenda way back in 1976). I wrote an essay on that subject a few years ago, since the reverse question also comes up in AI discussions: http://www.kmjn.org/notes/nphard_not_always_hard.html http://www.kmjn.org/notes/nphard_not_always_hard.html
  - betterunix 13y ago
    "to my knowledge no used-in-practice cryptosystem is based on taking an NP-hard problem and turning it into a cryptographically useful one-way function" Not used in practice, but such a result was presented by Atjai and Dwork: https://dl.acm.org/citation.cfm?id=258604 https://dl.acm.org/citation.cfm?id=258604
  - eru 13y ago
    There were some attempts to make the knapsack problem into an encryption system. But the early attempts were broken, then patched up and re-broken etc, and nobody has invested enough time into breaking the latest efforts, so cryptographers don't trust it.
  - tgflynn 13y ago
    An interesting thing about this is that you can transform the integer factorization problem into SAT quite easily (I have code that does it). The resulting SAT problems seem to be hard to solve for heuristic SAT solvers once you get beyond a very small number of bits for the integer sizes.

jiggy2011 13y 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 13y 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 13y 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 13y 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.

CJefferson 13y ago

On the question of "can't be reversed easily", the only real way is to try getting lots of clever people to try to break it :) There are also standard attacking techniques, so you can check (and maybe prove) these techniques do not work, but that still does not show there is a trivial crack you have missed.

betterunix 13y ago

"How does someone go about making a one way function" It's hard -- cryptographers have yet to even prove that one way functions actually exist! We have lots of theoretical candidates -- discrete logarithms for certain groups, integer factorization, problems related to hidden linear codes, and so forth. Some day, we will either prove that OWFs do not exist, or that OWFs do exist (and hopefully one of the candidates is actually an OWF), or that the existence or non-existence of OWFs is independent of the mathematical systems we use right now (i.e. that it is an axiom). Having said that, you might be interested in the work of Atjai and Dwork on creating an OWF (a trapdoor OWF, actually, and a corresponding public key cryptosystem) from an NP-Hard problem: https://dl.acm.org/citation.cfm?id=258604 https://dl.acm.org/citation.cfm?id=258604