November 29th, 2007, 04:54 PM
Irreversible hashing algorithms
Hashing algorithms are based on those algorithms being impossible to be reversed (that is, given the hash and the algorithm, it is impossible to calculate the reverse function of that algorithm, and thus it is impossible to run the hash through the reversed algorithm in order to obtain the original string).
My question: how "impossible" is the "impossible" in my previous statement? Is this impossibility based on the computational infeasibility of calculating the reverse algorithm, meaning that today's math geniuses - with the help of their computers - cannot come up with a way to figure out how to reverse the algorithm, or is this an actual impossibility? Are there algorithms that have been mathematically proven to be irreversible? If so (and I hope not, because I can't wrap my brain around that concept), how? If not, can there ever be an algorithm that is absolutely irreversible?
November 29th, 2007, 06:50 PM
Maybe I am being pedantic here, but I would say that the algorithm and the hash are reversible or the messages would be undecipherable, and the whole process would be useless.
I would say "virtually impossible" which basically means computationally impractical. By that, I do not mean that it cannot be done, only that it would not be worth the effort.
If you have the hash and the algorithm you can decipher the message just as with old fashioned code books. To make this difficult for an unauthorised person you use "salts" and "nonces" for example, to obfuscate the raw hash.
I do not believe that there can. My argument is that they are intended to be reversed, but only by authorised recipients.
If not, can there ever be an algorithm that is absolutely irreversible?
Like any other non-destructive form of security, all you are buying is time.
Did you know that in English slang a "nonce" is a sexual pervert?
November 29th, 2007, 07:15 PM
I'm talking about one-way hashing algorithms, though (MD5, SHA...); algorithms that base their strength on the fact that the algorithm cannot be reversed (not even by an authorized user). Hashes produced by such algorithms are not supposed to be reversible or intended to be reversed...
November 29th, 2007, 07:57 PM
Those one-way hashing algorithms are indeed "irreversible" in the meaning
that they are not invertible. Even with infinite computer power you won't
be able to deduce the input unambiguous.
Example - "mod": 5 mod 2 = 1. 3 mod 2 = 1. 7 mod 2 = 1. So, you know the
output is "1" - what's the input?
-> Applying a hash function, you actually loose information. In order to
have a hash function with a certain usability, the output "space" however should
be somewhat large, otherwise you could easily modify a message without
being detected (that's the whole purpose of a hash function).
Furthermore, there are so-called "collisions": these are input values with the
same output (in the above example: 3, 5 and 7). The larger the output space
and "better" the hashing function, the less likely it is to get a collision. With
an algorithm like MD5, SHA..., take a 650MB image of a cd, calculate the hash,
change 1 byte, take again the hash: the output is completely different. That's a good algorithm.
Strength as a "Weakness": If you know that the input text is of a certain
length (like an email), you now the alphabet used (a-z, A-Z, 0-9, !, ?, ...)
and the language, then you may be able to produce a few readable texts
with the known hashing output (assuming really huge computer ressources...).
But this is (usually and today) an academic weakness. We say we "restrict
the input space" based on reasonable assumptions. And thus may be able
to filter out the correct answer. In the above example: we know for some reason,
our integer number has to be >=4 and <=6. If we get a hashing output "1"
we know it must be 5.
Hope this helps,
Last edited by sec_ware; November 29th, 2007 at 08:01 PM.
If the only tool you have is a hammer, you tend to see every problem as a nail.
(Abraham Maslow, Psychologist, 1908-70)
November 29th, 2007, 08:30 PM
Ah! I see, we are talking about message digests
I agree with sec_ware that they are not mathematically "reversible" in the true sense of the word. This is because the hash is of a fixed length whist the data that it is generated from is variable.
The way to crack it is to use brute force or rainbow tables. That is not a "reversal" but a "reconstruction" technique.
November 29th, 2007, 09:19 PM
Thanks for the explanation, sec_ware - that's exactly what I was looking for!
Thanks for the input, too, nihil!
November 30th, 2007, 12:09 PM
My head hurts after reading this thread...
December 1st, 2007, 04:23 AM
I agree with everything said. I looked into md5 collisions about a year ago and there are a few places you can read about it but this site has an example and everything check it out: http://www.mscs.dal.ca/~selinger/md5collision/
December 1st, 2007, 06:42 PM
md5 is rumoured to have been broken by chinese mathematicians, pure speculation i assume, but it is one of those things i would try to keep under wraps if i was the chinese government.
I have seen a ps3 cell processor churn out 1.4 billion hashes a second, so if you are still going to use md5, at least salt your data.
and there you have it, 2 good reasons to use sha-256, although with massive concurrent cpu's on the horizon, MIT has a processor capable of over 64 threads of execution, we may need to re think some things.
December 1st, 2007, 08:19 PM
Ive heard the same thing ildjarn but i think that was just a rumor i dont think it was confirmed. As far as Md5 it is a great algo but since rainbow tables were introduced it is not as secure. Same with any hash really rainbow tables can be made which can make the stored password useless if the hash is obtained.
Edit: I looked into that chinese thing and I think all they found is a way to produce md5 collisions which is not really a big deal any irreversible algo has collisions afaik..
Last edited by oofki; December 1st, 2007 at 08:26 PM.
By encipher in forum Cryptography, Steganography, etc.
Last Post: April 11th, 2007, 02:25 AM
By Overlord_77520 in forum Cryptography, Steganography, etc.
Last Post: September 2nd, 2005, 11:59 PM
By BUDsmoker in forum Cryptography, Steganography, etc.
Last Post: May 8th, 2005, 07:52 PM
By kruptos in forum The Security Tutorials Forum
Last Post: January 29th, 2005, 12:01 AM
By nirvanainheaven in forum AntiOnline's General Chit Chat
Last Post: March 24th, 2003, 03:51 AM