Re: [Gnu-arch-users] Re: MD5 is broken

[Jan Hudec]

On Thu, Mar 17, 2005 at 01:42:39 -0500, Adrian Irving-Beer wrote:
> On Wed, Mar 16, 2005 at 10:03:55PM +0100, Karel Gardas wrote:
> 
> > "One-way hash functions are supposed to have two properties.  One,
> > they're one way.  This means that it is easy to take a message and
> > compute the hash value, but it's impossible to take a hash value and
> > recreate the original message.  (By 'impossible' I mean 'can't be
> > done in any reasonable amount of time.')
> 
> Unless one knows the size of the hashed data, aren't there an infinite
> number of increasingly large combinations of bytes that resolve to any
> given hash?
> 
> Isn't being irreversable a function of any lossy algorithm?  Even MP3
> and JPEG files are one-way, although they try their hardest to create
> an *approximation* of the original.

The exact wording should probably have been:
Given the hash value, it's not possible to create a message that has
this hash value by any means that would be in average case faster than
trying random messages and checking whether their hash value is equal to
the specified. (If the hash has n bits, than the complexity is
O(2^(n-1)).)

> > Two, they're collision free.  This means that it is impossible to
> > find two messages that hash to the same hash value.
> 
> Hashes are a specific length.  Hashed data is not (although there are
> pragmatic limits).  So how can a finite set of bytes permute to a
> unique hash for every one of an infinite number of source values?
> 
> There will always be collisions.  The key, I would think, is that it's
> practically impossible to predict where collisions will occur.

Again, the exact definition would be:
It is not possible to find two messages with the same hash in any way
that is faster on average than generating random messages and comparing
their hash values with all the messages generated so far. (If the hash
has n bits, than the complexity is O(2^(n/2)) due to so called "birthday
paradox".)

> Further, as far as I can tell (I'm no expert), the original posting
> discusses the creation of two documents, *both* in their control, that
> could be made to have the same checksum.  Attacking arch's use of MD5
> requires that you come up with a document on your side that matches a
> specific hash of data outside your control.

Yes, it seems to do. And what more, the addition about attacking packaes
says, that something must decide based on the compressed form, but
there is no such things in Arch. So Arch is not broken... YET.

> That being said, I still advocate using more than one hash, and
> particularly signing the file size in addition to the hash.

I agree here. While the hash was not broken in a way that actually
allows attack on Arch, it is quite likely that such breach will appear
in not-so-distant future (a year or two). Thus I would advocate to add
the extra hash now too.

-------------------------------------------------------------------------------
                                                 Jan 'Bulb' Hudec 
<address@hidden>

signature.asc
Description: Digital signature