How do one-way functions work in cryptography?

Question

Note: I wasn't sure of whether to ask this here, or on Security.se, but I am really looking for more of the mathematics side of it, so I decided to post it here

---

I am looking to write my own program, that encrypts passwords, and gives you a hash. What I am trying to figure out is how to do this mathematically. Is there any way in mathematics to do something to a number, so that you can't reverse it? For example, given the number 3482034, how can I change it in such a way, that even if the equation I used is known, there is no way to reverse engineer it to get the number 3482034 anymore? Is this even possible, or am I just mistaken about the way things are encrypted?

---

Edit: Basically what I am asking is, how do one-way-functions work, and how can I create my own?

---

Answer 1

#include <ritual warnings against ever using any cryptographic function you have designed yourself, to protect any real data>

There's precious little mathematics (in the sense of proofs) involved in the design of cryptographic hash functions. Generally new hash functions are created by a procedure resembling this

1. An algorithm is proposed, generally by designers who are sufficiently famous as cryptographers that the general impression is that it they possibly know what they are doing, such that their handiwork stands a decent chance of possibly being secure.

2. Other cryptographers attempt to break it, publishing their partial results, if any. (If the proposers are insufficiently famous, the proposal may not entice anyone to try to break it, in which case it dies a silent death).

3. If, after some time, nobody has managed to break the algorithm and tell the world about it, and there's evidence that a lot of really smart people have tried really hard to do so, and the general opinion of those smart people is that they feel they understand fairly well why it is hard to break (as opposed to just being so strange and weird that one cannot even get a handle on it), then a consensus in the cryptographic community may emerge that the proposal is probably close to being as strong as anything else we have (which can be computed with about the same effort).

There's a lot of mathematics involved in step 2 (attempts to break the algorithm), and this mathematics again informs the design in step 1, because the designer of a new algorithm will make sure that it cannot be broken by any of the methods he already knows about. But the final decision that the algorithm is likely to be secure is essentially not a mathematical one.

Some, but not all, recent hash function designs are built from smaller components (typically a block cipher) and come with an actual mathematical proof that the entire hash function is secure (in a technical sense) if one assumes that the underlying block cipher is secure (in a different technical sense). But that really just moves the problem around, because block ciphers themselves are designed by the non-mathematical procedure outlined above. And nobody has the first idea how one might conduct a mathematical proof from first principles that a block cipher is technically secure.

---

If you want to learn about how to construct hash functions (please not for securing your data, but possibly for satisfying your curiosity), a natural place to start is to study the design of existing hash functions. The definitions for MD5, SHA-1 and SHA-2 are available online in a fairly readable form. The NIST is currently conducting an open competition for the design of a next-generation hash function; the proposals there are also available on-line and show a somewhat larger diversity of design than the current MD5-SHA family exhibits.

The definition of SHA-2 is also where you would go if you just want to implement a hash function in a programming environment that doesn't already have one built in (such environments exist, though the mainstream programming languages are not among them). In that case, forget about inventing one yourself -- just implement what SHA-2 says, and be sure to test that you get the right bits out of the test cases listed at the back of the specs.

The mathematical prerequisites for understanding the specifications are generally modest, and limited to understanding basic bitwise and word-wise logical and artihmetic operations. Some schemes also depend on finite fields of order $2^n$, though. There are many introductions to that to find on the web, especially since these finite fields provide the theory behind constructing the S-boxes in AES.

Answer 2

From a mathematical point of view what you want is a function that is not inversable, ie. non-injective. Consider for example the function $f_1(x)=\lfloor x/10 \rfloor$ (where $\lfloor \cdot \rfloor$ means "round down"). This function will map the values $\{0,1,2,..,8,9\}$ to $0$. So if you only know that the output was $0$, it is impossible to know which input it was. Of course this is not a very good hashing function, as there are only 10 rather obvious possibilites, but it would qualify as being a "one way function" anyways.

In practice it is more important that it is very hard to invert the function rather than it really being non-invertible. If you restrict yourself to inputs of 16 characters or less a hash function like sha, md5 etc. might very well be invertible, but the only way to know would be to calculate every input-ouput pair. In the above example $f_1$ was easy to "invert" because it was such a simple function. To make in cryptografically more robust you would add a lot of complexity....

The most commonly used non-invertable map (as part of a much more complex algorithm) is the modulo operation. It is the rest of an integer devision eg. let $\%$ denote the modulo operator, then $1\%3=1$, $2\%3=2$, $3\%3=0$, $4\%3=1$ ... (this might be "hidden" in the form of an overflow in an addition etc. but is still present in most modern hash algorithms)

Use this modulo operator in a few places, and chances are, you already have an acceptable hash algorithm (assuming it does not have to stand against serious attacks). For example:

$ (a\cdot x^n) \% m $ for proper $a,n,m\in\mathbb{N}$. or:

$ h(n) = (m\cdot h(n-1) + a_n)\%p\quad\quad h(0)=q\quad\quad m,p,q\in\mathbb{N} $

where $a_n$ is the sequence of input bytes and $h(n)$ gives the hash of the first $n$ bytes. For more examples you can easily check the wikipedia.

Of course, the more security you want, the more constraints there are going to be on your algorithm. What should be the time constraint for a single hash? How many different hashes should there be? Of course every possible output should be roughtly equally likely... And should change as much as possible even if you only change one bit of the input..... The list goes on, so that modern hashes really are not that trivial anymore, trying to comply with as many such constraints as possible.