Page 1 of 2 12 LastLast
Results 1 to 10 of 15

Thread: Irreversible hashing algorithms

  1. #1
    Banned
    Join Date
    Aug 2001
    Location
    Yes
    Posts
    4,424

    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?

  2. #2
    Senior Member nihil's Avatar
    Join Date
    Jul 2003
    Location
    United Kingdom: Bridlington
    Posts
    17,188
    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.

    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?

  3. #3
    Banned
    Join Date
    Aug 2001
    Location
    Yes
    Posts
    4,424
    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...

  4. #4
    Senior Member
    Join Date
    Mar 2004
    Posts
    557
    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
    Last edited by sec_ware; November 29th, 2007 at 09: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)

  5. #5
    Senior Member nihil's Avatar
    Join Date
    Jul 2003
    Location
    United Kingdom: Bridlington
    Posts
    17,188
    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.

  6. #6
    Banned
    Join Date
    Aug 2001
    Location
    Yes
    Posts
    4,424
    Thanks for the explanation, sec_ware - that's exactly what I was looking for!

    Thanks for the input, too, nihil!

  7. #7
    Right turn Clyde Nokia's Avatar
    Join Date
    Aug 2003
    Location
    Button Moon
    Posts
    1,696
    My head hurts after reading this thread...

  8. #8
    Senior Member
    Join Date
    Oct 2003
    Location
    MA
    Posts
    1,052
    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/

  9. #9
    Junior Member
    Join Date
    Dec 2007
    Posts
    12
    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.

  10. #10
    Senior Member
    Join Date
    Oct 2003
    Location
    MA
    Posts
    1,052
    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 09:26 PM.

Similar Threads

  1. ZWinCrypt - Simple C++ Library for Hashing, Encryption and Compression
    By encipher in forum Cryptography, Steganography, etc.
    Replies: 0
    Last Post: April 11th, 2007, 02:25 AM
  2. Possible flaw in RSA and other modulus based encryption algorithms.
    By Overlord_77520 in forum Cryptography, Steganography, etc.
    Replies: 2
    Last Post: September 2nd, 2005, 11:59 PM
  3. Encryptions Algorithms
    By BUDsmoker in forum Cryptography, Steganography, etc.
    Replies: 4
    Last Post: May 8th, 2005, 07:52 PM
  4. Encryption Algorithms - Basics
    By kruptos in forum The Security Tutorials Forum
    Replies: 0
    Last Post: January 29th, 2005, 01:01 AM
  5. Introduction about cryptography
    By nirvanainheaven in forum AntiOnline's General Chit Chat
    Replies: 1
    Last Post: March 24th, 2003, 04:51 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •