Re: Hashes,File protection,etc

["Roland Postle" <mail () blazde co uk>]

Hmm, you took the quote and made it look like I said it. I agree with
what you say but I'll attempt to defend the original author anyway, for
the hell of it.

a) You should assume there are some individuals/organisations who know
shortcuts which can reduce the keyspace they need to bruteforce.

b) Your 10K trials/second might an underestimate, tho I'm not qualified
to say what the most optimized algorithms can handle these days, it
wouldn't surprise me if it were close to 100K/sec even without above
assumed shortcuts.

c) 17K texts is just one application of MD5. To assume 17K texts, and
then say "MD5 is secure enough" is misleading. Password hashing springs
to mind. And if you want a random collision I'd guess you shouldn't
have to hash more than around 16 bytes (128 bits) of plaintext / trial,
since this is the keylength.

All of which means, with a big enough budget, you might be able to
prove something like 

On Tue, 15 Oct 2002 15:39:50 BST, Roland Postle <mail () blazde co uk> 
said: 
> hId-32=q1+f,d`0A

but never

On Tue, 15 Oct 2002 15:39:50 BST, Roland Postle <mail () blazde co uk> 
said:
>    MD5 has an output of 128 bits, which I think is too small for
>  good security.  A collision can be found by brute force in 2**64
>  operations.

:P

- Blazde

On Tue, 15 Oct 2002 12:27:39 -0400, Valdis.Kletnieks () vt edu wrote:

> On Tue, 15 Oct 2002 15:39:50 BST, Roland Postle <mail () blazde co uk>  said:
>
> >    MD5 has an output of 128 bits, which I think is too small for
> >  good security.  A collision can be found by brute force in 2**64
> >  operations.
>
> Assuming 10,000 trials a second, this will take 58,494,242 cpu *years*.
> (an 'md5sum' of a 17M file on my laptop takes 0.110 seconds on a 1.6G Pentium4,
> so 10K/sec trials of 17K texts is "in the ballpark" - even assuming a processor
> that's 10x faster gets you down only to 5M cpu-years).
>
> And notice that this is "a collision".  At that point, you have 2 essentially
> random plaintexts that happen to have the same MD5 hash, and said hash is
> unrelated to anything else.  Most likely, neither one resembles *in the
> slightest* something "reasonable" (for instance, if you're expecting a 1.8M
> source tarball, it should be in tar format and somewhere near 1.8M in size).
> Forcing a collision to *a specific known hash* is a lot harder - and at that
> point you'll probably still have an essentially random file.  And unlike
> beating a CRC-32, there's probably no efficient way to take a *given* file, and
> find a way to *modify* that file and still maintain the SAME md5sum.
>
> And remember that 58 million CPU years is *per collision*.  Are there *any*
> targets who's threat model *really* includes this?  Probably not for private
> individuals - there's cheaper ways to do it (Marcus Ranum's "rubber hose
> cryptography" and related methods).  Inter-bank encryption codes?  If they
> change them once per year, you'll need a 50 million CPU machine for it to
> do you any good.  I suspect even nuclear launch codes can be obtained with
> less investment of resources....
>
> So - do *YOU* have anything secured by an md5sum that's worth 58 million
> cpu-years to break?  If you don't, then md5 is 'secure enough'.  If you do,
> I hope you have all the physical security issues and personnel security
> issues dealt with... :)
> -- 
>                               Valdis Kletnieks
>                               Computer Systems Senior Engineer
>                               Virginia Tech