Discussion:
Reversible hashing
f***@gmail.com
2007-11-04 02:18:48 UTC
Hi,
I would like to know if make sense the statement "Reversible hashing".
I mean is possible to develop a hash algorithm, or better a digest
algorithm, (variable input lenght, fixed output lenght) that do not
respect the rule to be one-way. I don't want to compare with other
hash algo such SHAx, MDx ecc... but, it can be done?
Just for curiosity; I think this question can be some kind of
interesting discussion, I am wrong?

Oh, sorry for my bad english ;-).

Cheers,
Federico.
Robert Kochem
2007-11-04 13:05:07 UTC
Post by f***@gmail.com
I would like to know if make sense the statement "Reversible hashing".
I mean is possible to develop a hash algorithm, or better a digest
algorithm, (variable input lenght, fixed output lenght) that do not
respect the rule to be one-way. I don't want to compare with other
hash algo such SHAx, MDx ecc... but, it can be done?
What you are searching is a compression algorithm that can compress data of
any length into a fixed length output. In the result that would mean that
this algorithm must be able to compress every existing bit of information
into the fixed length output. That would be the computer science version
of a "perpetual motion".

Robert
Federico
2007-11-04 14:51:46 UTC

dobbertin's "The firs two rounds of MD4 are not one-way"

In this articles the autor explain that a reduced version of md4
compression function can be reversed. I'm wrong?

cheers,
Federico.
Robert Kochem
2007-11-13 12:46:06 UTC
Post by Federico
dobbertin's "The firs two rounds of MD4 are not one-way"
In this articles the autor explain that a reduced version of md4
compression function can be reversed. I'm wrong?
You can break the one-wayness of every digest algorithm by brute force
searching - depending on the used digest algorithm that can take seconds to
million years or more. Please note that you will get wore than one possible
input value that produces the same output hash and you will not know which
one is the correct/original input you are searching for.

Robert
giorgio.tani
2007-11-13 16:56:22 UTC
Hi, the problem of non reversibility on hash functions is that while
the input is arbitrarily sized, the digest is fixed sized.
You have for instance a digest of n bit, which can have 2^n distinct
values, but you can have far more than 2^n possible inputs, in facts
there is no defined limit about the distinct input you can pass to the
hash function.
So, you will have infinite possible input mapped to 2^n possible
output, and you will not have the possibility to map 1:1 output to
input which is required to invert the function; you could not store in
the digest enough information to cover the space of possible inputs so
the relation between input and output is lossy.

The "invertibility" in the source you cite means that under some
circumstances weak or incomplete hashing processes could be correlated
in a computationally feasible way to more probable input, but it's not
extensible for the hashing process itself which is inherently lossy.
Ertugrul Soeylemez
2007-11-20 13:01:19 UTC
Post by Federico
dobbertin's "The firs two rounds of MD4 are not one-way"
In this articles the autor explain that a reduced version of md4
compression function can be reversed. I'm wrong?
It's easy to create a hash function, which is not preimage-safe. You
should be more precise about what you're looking for. Either you're
looking for a compression function with fixed size output (which is not
reversible uniquely), or you're looking for encryption.

Maybe you're looking for a preimage-resistant hash function, which is
not collision-resistant? Like a function F, for which you can generate
as many X with F(X) =3D Y as you like, as long as you know a single X,
which fits.

Regards,
Ertugrul S=C3=B6ylemez.

--=20
Security is the one concept, which makes things in your life stay as
they are. Otto is a man, who is afraid of changes in his life; so
naturally he does not employ security.

Kristian GjXsteen
2007-11-04 19:20:03 UTC
Post by f***@gmail.com
I would like to know if make sense the statement "Reversible hashing".
I mean is possible to develop a hash algorithm, or better a digest
algorithm, (variable input lenght, fixed output lenght) that do not
respect the rule to be one-way.
Ok, a family of hash functions { h_k : {0,1}* -> {0,1}^n } that is not
one-way, that is, there exists some algorithm that breaks preimage or
second-preimage resistance.

Apart from the trivial examples (CRCs etc.), does Note 9.20 in the
Handbook of Applied Cryptography provide an example of what you had
in mind?

--
Kristian Gj<F8>steen
Federico
2007-11-13 12:46:30 UTC
Kristian, let me read the article for a good response, but thanks for
your help and patience; I will say something soon :)

Federico.

Ps: Robert, I can't find any kind of parallelism with reversible one-
wayness with perpetual motion! Bah...
Federico
2007-11-13 16:55:50 UTC
Post by Kristian GjXsteen
Post by f***@gmail.com
I would like to know if make sense the statement "Reversible hashing".
I mean is possible to develop a hash algorithm, or better a digest
algorithm, (variable input lenght, fixed output lenght) that do not
respect the rule to be one-way.
Ok, a family of hash functions { h_k : {0,1}* -> {0,1}^n } that is not
one-way, that is, there exists some algorithm that breaks preimage or
second-preimage resistance.
Apart from the trivial examples (CRCs etc.), does Note 9.20 in the
Handbook of Applied Cryptography provide an example of what you had
in mind?
--
Kristian Gj<F8>steen
YES, but I also mean that a algorithm can be modified (truncate third
round of MD4 for example) for make easy to find preimages and so on...
I ,also, would like to say that my research is for educational purpose
only and if ,for shorten computation time, in addition with the hash
hostile environment that is another thing that the real world) for
example the size and some (about 5%) of original data.

This can help?

Again THX!

Federico.
Peter Pearson
2007-11-13 12:45:42 UTC
Post by f***@gmail.com
I would like to know if make sense the statement "Reversible hashing".
I mean is possible to develop a hash algorithm, or better a digest
algorithm, (variable input lenght, fixed output lenght) that do not
respect the rule to be one-way. I don't want to compare with other
hash algo such SHAx, MDx ecc... but, it can be done?
There are many algorithms that map variable-length inputs
onto fixed-length outputs; checksum algorithms, for example.
Cryptologists add the requirement of one-wayness (or, more
powerfully, collision resistance) to get algorithms that are
useful in information-security systems, but you seem to want
to waive that requirement. If you don't insert some other
requirement in its place, then checksums meet your need.

--
To email me, substitute nowhere->spamcop, invalid->net.