From: Roger Bryner <bryner@atlas.chem.utah.edu>
Date: Tue, 5 Jul 94 17:27:16 PDT
Subject: Re: MD5 is 1=>1?
In-Reply-To: <9407042142.AA28845@toxicwaste.media.mit.edu>
Message-ID: <Pine.3.89.9407051714.A13153-0100000@atlas.chem.utah.edu>
MIME-Version: 1.0
Content-Type: text/plain


On Mon, 4 Jul 1994, Derek Atkins wrote:
> MD5, like all hash functions, are many-to-one functions.  This means
> that theoretically there are an infinite number of messages that will
> hash to the same value.  This also means that reverting from the hash
> back to your original message is nigh impossible.  The security of MD5
> is based upon the fact that *finding* two messages that hash to the
> same value is as difficult as a brute-force attack, which requires
> 2^128 trials (maybe it's 2^127, but I don't think that really
> matters).
Hmm, I read this as reverting is imossible, as it genrealy is when you 
start with 1MB and hash it to 128 bits(or compression would be neat!), 
then that finding two messages that hash to the same value is as 
difficult as brute force, which is not really true, if taken literally.

Perhaps my original question about cycles and entropy loss is beter in 
the context of a broken system such as MD4.  Are there 128 bit messages 
in MD4 which hash to the same value, and if so, what insight into the 
cycle leingth vs string leingth would it give us.

lets say each dot is a 128 bit number, a string could feed a cycle, such 
as shown below.  When this occurs, you loose entropy, as it ceases to 
be sequentially dependent on a 128 bit number, and instead a subset of 
the cycle.
==>
.......................
                  .   .
                  .....


Here is an example hash function, for two 64 bit words, a, b;

hash(a,b)=a+b,a-b;
now hash^2(a,b)=2a,2b.

so here you have lost 1 bit of information when  you start to itterate 
the hash function, and will be left with exactly 1  option after 128 
iterations of this function in every case.

This is why I won't use securedrive with the 1024 option, as I view it as 
a SERIOUS NEGITIVE THREAT TO SECURITY OF THE SYSTEM.  Changeing this to 
encrypting 1024 times with idea and a key generated by a PRNG has no such 
security hole possible, and is what I would view as a proper "buisy work 
function[TM]" althought nothing has been said about its ireducibility.

I would recomend replacing that option or discarding it, that is unless 
hash functions never throw away bits in sizes smaller than their output size.
(again, that was my question)

Roger.