Are hashes truly One-Way functions?
So recently an interesting topic of discussion rose on one of our meetings here, what exactly are one way functions? After some debate we realized that we were dealing with 2 different areas that had 2 different meanings to the word. In the security world, an One Way Function is a hash function and in the Cryptanalysis world One Way Functions are the Holy Grail.
Let’s begin by clearing up what are Hash Functions, they are mathematical functions that map any input, no matter the size, to a fixed size output. For example, a simple hash function would be to sum the hex value of every character in a text and in the end output that sum in 32 bit form.
Now if you did the math, you can see a problem there, if you accept inputs of ANY size, and outputs only fixed size, there will eventually be two different inputs with the same output! This is a huge problem that is known as Hash collisions, and the simple hash i defined earlier is ridden with them. For example: both “aba” and “baa” will output the same value! And since hashes are usually used for generating unique values that would be reeeally bad! But as usual, technology advanced and now we actually have hashes that deal well with that problem and offer a quasi-uniform distribution of hashes to almost any input so that we have a function that if you give it any kind of input, it will output an unique value for that input! And since the output is (almost always) smaller than the input, it is very hard to discover the input given only the output of those functions! A good example of a secure (at least at the moment this article is being written) hash function is the SHA-256 that gives outputs with 256 bits of size.
But here’s where the confusion arose, if you have a function that can take any input, and output an unique value, and it is very hard to compute the input when you are given only that unique value then Hashes are obviously One-Way Functions! Except they are probably not… And here’s why.
Speaking from the world of Cryptanalysis and mathematics, One-Way Functions are basically functions that given the domain it is easy to compute the image, but given the image it is hard to compute the domain. “Well but aren’t hashes exactly that as you said earlier?” you might ask and well, no, we have a problem of scale and proof here. When i say “hard to compute the domain” what i mean is that if an attacker with every possible conceivable method of inverting this one way function F tries to compute the inverse of F(X) given only F(X), his probability of succeeding in polynomial time MUST be smaller than or equal to 2-N with N being the size of F(X) in binary. This means that no matter what the attacker has, his chance of actually finding some X’ that F(X’) = F(X) is negligible.
“Again, aren’t hashes exactly that?” well here’s the thing, nobody knows yet! One-Way functions are still an open conjecture, dare i say the biggest most important conjecture in crypto, which means that nobody was able to prove that an One-Way Function exists yet! Proving a function is One-Way is extremely difficult! You would have to prove that for every possible attack, the chance of inverting is still negligible, and that’s an insane task to do! Maybe impossible even!
But still, just because proving the existence of One-Way Functions is hard doesn’t mean nobody is trying to, after all think about it, if you have something that is irreversible unless you know some key you can create a perfect encryption system! And right now the biggest contender for that is the famous RSA! RSA bases its security in the mathematical problems of factoring large numbers and the RSA problem, which both are still not proven to be solved fast and a lot of people believes RSA might be an One-Way Function
Now the coolest thing about One-Way Functions is that if you actually manage to somehow prove one does exists, you prove that P != NP! And that… That is the mathematical holy grail right now, if you actually managed to prove that your name would be permanently written into every mathematical book for the rest of time! If you are un-familiarized with the “P = NP?” problem, i strongly recommend reading on it, it is the coolest mathematical possibility ever!
So, going back to hashes, the main point is that hashes may be One-Way Functions, but nobody was able to prove it yet! And nomenclature is confusing… Something might mean Y in this context but then it means X in other context… Its all very confusing, especially when you deal with even more common words like Trees and Architecture. But do not fret! Now you should be able to rub in your coworkers face that he’s actually wrong when saying Hashes are One-Way Functions! Except don’t… nobody likes you when you do that.
Author: Enris N. von Tein
Conviso Application Security
