From: fnerd@smds.com (FutureNerd Steve Witham)
Date: Fri, 27 May 94 10:27:34 PDT
To: cypherpunks@toad.com
Subject: Re: well
Message-ID: <9405271720.AA27475@smds.com>
MIME-Version: 1.0
Content-Type: text/plain


i wrote-

> ps.  MD5 of a file with a random string appended to the *end*
>      *can* be computed after having discarded the file.

Matt Thomlinson asked-

> hmmm. why is this? can you find a smaller file that will hash to the same
> number if you get to play with the pad bits appended before the 4 logic
> applications? it would seem reaonably strong either way..
>
> (I know I'm wrong on this, I'm just wondering what I'm missing.)

MD5 and similar hash functions work from the beginning of a file to the
end, in blocks.  For each block, you take the output of the
calculation on the previous block (or initiation constants, if it's
the first block), combine it with the current block, and get the output
for this block.

So, you can calculate the output of the second-to-the-last block,
and store that and the last block, and throw away the rest of the
file.  Then you can append anything you want to the last block (doing
it right, see next paragraph) and calculate the MD5 of the whole file
plus the appendage, even though you don't have the whole file any more.
This trick doesn't work for adding stuff at the beginning.  (*This*
trick doesn't...)

(About appending "right"--MD5 and sisters append some special stuff
at the end of the last block, including the total file length.
You'd have to insert at the right point and adjust.)

But the shortcut for appended-to files wasn't obvious to me at first
either.

I agree with Perry that MD5 isn't necessarily the one to use, and
certainly won't always be.

A couple people agree that my trick *sounds* safe.
Somebody (sorry!) suggested some other methods:
 - Hash of ( file xor'd with repetitions of the same random string)
   --sounds a little safer to me.
 - Xor of specific bits in the file.  Sounds okay if you do a 128-
   bit-wide xor.  Except it doesn't test for bit-decay in the bits
   you didn't ask about.  A hash of the whole file does.

Anyway, I get the feeling cryptographers haven't studied this problem
long and hard.  Meanwhile a method that's about as cheap to compute
and as simple to explain, but seems less likely to be weak is:
 - hash( IDEA( file, random password ) )

-fnerd

- - - - - - - - - - - - - - -
To auditors without the code, calls seem
indistinguishable from noise.  --George Gilder
-----BEGIN PGP SIGNATURE-----
Version: 2.3a

aKxB8nktcBAeQHabQP/d7yhWgpGZBIoIqII8cY9nG55HYHgvt3niQCVAgUBLMs3K
ui6XaCZmKH68fOWYYySKAzPkXyfYKnOlzsIjp2tPEot1Q5A3/n54PBKrUDN9tHVz
3Ch466q9EKUuDulTU6OLsilzmRvQJn0EJhzd4pht6hSnC1R3seYNhUYhoJViCcCG
sRjLQs4iVVM=
=9wqs
-----END PGP SIGNATURE-----