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?
> How do you know it can't be reversed easily?
Some you prove: 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
[1] http://en.wikipedia.org/wiki/NIST_hash_function_competition
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).
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
Not used in practice, but such a result was presented by Atjai and Dwork:
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.
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.
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
[2] Though it can be useful if using checksums for security.
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.
There's no practical way. Mathematically you can "just" brute force it, end of the universe will probably inhibit the practical application of that.
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:
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.