Why unhashing is not possible?

Why unhashing is not possible?
Secure Home | Search | About
Login Password
Register Now! Lost Password?
 General Computer Security    Post an article   get this group's latest topics as an RSS feed add this group's latest topics to your My MSN content add this group's latest topics to your My Yahoo content add this group's latest topics to your Google content
Subject Author Date
Why unhashing is not possible? Randell_D 12-25-2007
Posted by Volker Birk on December 29, 2007, 4:02 am
If you were  Registered and logged in, you could reply and use other advanced thread options
> How could the hash possibly be guaranteed to be unique?

It can't, or it will not be a hash function any more.

Yours,
VB.
--
The file name of an indirect node file is the string "iNode" immediately
followed by the link reference converted to decimal text, with no leading
zeroes. For example, an indirect node file with link reference 123 would
have the name "iNode123". - HFS Plus Volume Format, MacOS X

Posted by Unruh on December 25, 2007, 6:35 pm
If you were  Registered and logged in, you could reply and use other advanced thread options

>I've always led the belief that if something can be created/built,
>then it can be "uncreated/unbuilt". In technology this is sometimes
>referred to as reverse-engineering. I understand too how hashing can
>be used within programs and fast database lookups but I failed
>miserably discussing the subject of hashes with someone who could not
>understand when I told them that you cannot reverse the process... I
>know you can crudely hack it (using John the Ripper for example) but
>you cannot "uncompress it" so to speak.

>So... my question here to you good people is... why can't a hash be...
>well... unhashed?

>Surely if the hash is unique, we know the process that got us the hash
>we have only to reverse the process... we can't... so... but why not?

No, a hash is NOT unique. Many many many many inputs give the same hash.
That is the essense of a hash.
And at each step in the hash, information is thrown away. Ie, in running
the hash in reverse one would have to keep guessing at the thrown away
material.

Secondly to find even one of those may be very difficult. Yes, If I try
2^128 inputs there is good possiblity I will find the one giving me the
hash I have, but 2^128 is a very large number and I cannot try that many.

For an encryption, which is one to one, there are 2^60 or 2^128 ( depending
on the key length) by which that output could have been generated from the
input ( the process depends on the key). Thus I do NOT know how the output
was generated and thus cannot reverse it.


Posted by Walter Roberson on December 25, 2007, 7:22 pm
If you were  Registered and logged in, you could reply and use other advanced thread options

>No, a hash is NOT unique. Many many many many inputs give the same hash.
>That is the essense of a hash.

http://en.wikipedia.org/wiki/Hash_function

A hash function [1] is a reproducible method of turning some kind
of data into a (relatively) small number that may serve as a
digital "fingerprint" of the data.


There is no requirement there that the output cannot be unique
if the input is limited.

For example, if you were to write a compiler or interpreter for
a language with a fixed set of keywords, then the strings that
were the keywords could be hashed to produce a table offset
used for dealing with that particular keyword -- instead of doing
a string search or B-Tree or 2-3 Tree traversal to determine
the entry.

Posted by Sebastian G. on December 25, 2007, 8:35 pm
If you were  Registered and logged in, you could reply and use other advanced thread options
Unruh wrote:


> And at each step in the hash, information is thrown away.


Unless you reach its maxixum output length (which is typically very short in
comparison to the input), any good cryptographic hash does its best in
preserving as much information as possible.

> Secondly to find even one of those may be very difficult. Yes, If I try
> 2^128 inputs there is good possiblity I will find the one giving me the
> hash I have, but 2^128 is a very large number and I cannot try that many.


Are you implying a cryptographic hash here? The OP didn't. Sometimes we just
want hashes that are only good at not randomly leading to collision, and CRC
is a perfect hash in this sense - yet is cryptographically insecure.

> For an encryption, which is one to one, there are 2^60 or 2^128 ( depending
> on the key length) by which that output could have been generated from the
> input ( the process depends on the key). Thus I do NOT know how the output
> was generated and thus cannot reverse it.

Nonsense again. You just have to know the key and for a small set of inputs
you can perfectly reverse it.

Posted by Unruh on December 25, 2007, 9:32 pm
If you were  Registered and logged in, you could reply and use other advanced thread options

>Unruh wrote:


>> And at each step in the hash, information is thrown away.


>Unless you reach its maxixum output length (which is typically very short in
>comparison to the input), any good cryptographic hash does its best in
>preserving as much information as possible.

No, it does its best at not preserving any information as possible if it is
a cryptographic hash. You want it to a reproducible mapping from stings to
finite length random numbers.

>> Secondly to find even one of those may be very difficult. Yes, If I try
>> 2^128 inputs there is good possiblity I will find the one giving me the
>> hash I have, but 2^128 is a very large number and I cannot try that many.


>Are you implying a cryptographic hash here? The OP didn't. Sometimes we just

Yes, he did. He implied that he was talking about a situation in which is
was very hard or impossible to reverse the hash. Or did you not happen to
read the OP post.

>want hashes that are only good at not randomly leading to collision, and CRC
>is a perfect hash in this sense - yet is cryptographically insecure.

>> For an encryption, which is one to one, there are 2^60 or 2^128 ( depending
>> on the key length) by which that output could have been generated from the
>> input ( the process depends on the key). Thus I do NOT know how the output
>> was generated and thus cannot reverse it.

>Nonsense again. You just have to know the key and for a small set of inputs
>you can perfectly reverse it.

??? Where did I say you know the key? You do not know the key if you are an
attacker, which is what the OP implied. Also, he was clearly discussing
with his friend the case of cryptographic hash functions which are not
easily reversed (ie it is not easy to find the preimage).



The site map in XML format XML site map

Contact Us | Privacy Policy