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?

Hi Neg~,

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.

Quote:

---

If not, can there ever be an algorithm that is absolutely irreversible?

---

I do not believe that there can. My argument is that they are intended to be reversed, but only by authorised recipients.

Like any other non-destructive form of security, all you are buying is time.

//off-topic

Did you know that in English slang a "nonce" is a sexual pervert? :D

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...

Hi

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,
Cheers

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.

Thanks for the explanation, sec_ware - that's exactly what I was looking for!

Thanks for the input, too, nihil!

My head hurts after reading this thread... :(

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/

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.

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..

Quote:

---

Originally Posted by oofki

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..

---

Any hashing function that returns a fixed size string, will of course have collisions, finite amount of output, infinate amounts of input. It is the strength of the function that will make it difficult to find these collisions and to limit the number the best it can, however when you can start to predict these collisions it is safe to say the hash has been broken, go look at linux distro download sites, what do they use to validate a valid iso? md5, now that we can predict collisions we can theortically create 2 isos with the same hash, but very different data, lets say a logging method attached to the pam modules? It is also not just isos many applications use md5 to ensure the validity of their binaries, and what of tripwire, can we trust it anymore? While im sure a preimage attack is a long way off, as i said in my previous post, seeing a cell processor churn out 1.8 billion hashes a second, md5 is as good as broken(well in mine and many other security experts eyes).

Hi

Good contribution, ildjarn. I haven't seen before that you mentioned
preimage attacks, but excellent that you did so now! Salting is a simple
and effective method to render rainbow tables useless - Rainbow tables
have no style anyway (except the storage method!) :)


Quite a while ago, we did discuss the compromise of MD5[1,2] and
SHA-1[3,4,5] on this site. There are references to the original articles,
and to papers of some PoC-like studies. It is all dated, of course.

I have to admit that I have not looked into it since a year, but:
Although the research papers are genuine and should to be taken
seriously, nothing spectacular happened the last 3 years (well, we
may ask the chinese or american government :) ) as far as I know.
I am happy to be corrected.

Cheers

P.s. As a side note: the references to antionline-articles in the
posts below are not usable anymore (since Jupitermedia changed
the 'layout' of this site a while ago).

[1] http://antionline.com/showthread.php?t=269146
[2] http://antionline.com/showthread.php?t=261884
[3] http://antionline.com/showthread.php?t=263481
[4] http://antionline.com/showthread.php?t=267248
[5] http://antionline.com/showthread.php?t=273285




Cheers

Quote:

---

P.s. As a side note: the references to antionline-articles in the
posts below are not usable anymore (since Jupitermedia changed
the 'layout' of this site a while ago).

---

Old cross-references don't work, external links have vanished and attachments disappeared. Also, polls don't attach to their original threads.

This was a problem of updating to a newer version of vBulletin from a very old bastardised version. The natural progression of updates had been broken and the new version uses a different indexing system.

It has absolutely nothing to do with the layout, just the underlying software.

;)

Quote:

---

Originally Posted by sec_ware

Hi

Good contribution, ildjarn. I haven't seen before that you mentioned
preimage attacks, but excellent that you did so now! Salting is a simple
and effective method to render rainbow tables useless - Rainbow tables
have no style anyway (except the storage method!) :)

---

Eh some friends of mine put alot of effort into writing a super fast rainbow table some of the code in there was pretty fancy massive list of hashes, and amazing return speeds, but thats neither here or there.
As you and i both mentioned before salting helps greatly especially if you use per user salts rather than program/site wide salts, but still not 100%.

Quote:

---

Originally Posted by sec_ware

Quite a while ago, we did discuss the compromise of MD5[1,2] and
SHA-1[3,4,5] on this site. There are references to the original articles,
and to papers of some PoC-like studies. It is all dated, of course.

I have to admit that I have not looked into it since a year, but:
Although the research papers are genuine and should to be taken
seriously, nothing spectacular happened the last 3 years (well, we
may ask the chinese or american government :) ) as far as I know.
I am happy to be corrected.

Cheers

P.s. As a side note: the references to antionline-articles in the
posts below are not usable anymore (since Jupitermedia changed
the 'layout' of this site a while ago).

[1] http://antionline.com/showthread.php?t=269146
[2] http://antionline.com/showthread.php?t=261884
[3] http://antionline.com/showthread.php?t=263481
[4] http://antionline.com/showthread.php?t=267248
[5] http://antionline.com/showthread.php?t=273285




Cheers

---

Heh was going to link you to an article on sha-1 and when i opened my browser to grab the url i noticed this on the slashdot rss which is an article on what i was talking about before, using a new method that the same group researched on the origional prof. collision research.

http://www.win.tue.nl/hashclash/SoftIntCodeSign/

That article links to another article on sha-1 that is an interesting read, eh with the decressing costs of both processing power and storage, i honestly cant see why we cant step up to something like sha-256(i know the US government requires it for some applications dealing with sensitive data) microsoft is also pushing it for its use

http://www.eweek.com/article2/0,1759,1859751,00.asp

Despite a preimage attack on any of the above mentioned hashes. For digital signatures of binary, with the ability to generate collisions for md5, and with enough time(the amount of time is dropping) the same for sha-1. The nails are fairly secure in the coffin for these hashes.

if the cell cpus on a ps3 can put out 1.8 billion hashes a second how is that relative to say a 3 ghz dualcore?