Re: Re-secured Algorithm?

tomstdenis_at_gmail.com
Date: 08/28/05 

Date: 28 Aug 2005 05:19:20 -0700

Regis wrote:
> On 27 Aug 2005 19:12:53 -0700, tomstdenis@gmail.com wrote:
>
>
> >MD5 collisions are actually trivial to generate.
>
> Prove it.
> Generate some collisions for everyone to see.
> Seeing as how it's "trivial", I would expect to see something within
> the hour...or by tomorrow evening at the latest.

Um I guess you weren't around last year but the same people who broke
SHA-1 had real collisions in MD5. Google for around august of 2004.

Once you find two messages Q and Q' which collide you can append
anything you want [hint: stripwire].

> >You assume everyone is computationally bounded to a 16Mhz 386.
>
> No, I assume no such thing.

Well apparently because you assume people can't do things.

> >Point is computing power is very accessible. To think that people
> >won't exploit openings in MD5/SHA1 is naive.
>
> The desire to achieve something and the ability to achieve that thing
> are two very different things.

Say that to the RC5-64 team.

> >2^63 work is not out of reach.
>
> No, I never said it was out of reach.
> What I said -- and will say again -- is that it's impractical.
> Period...end of story.

First, I disagree [specially in the case of MD5]. 2^63 may be
impractical now but it won't be in a dozen years.

The point of cryptography is to seek efficient designs for which we can
understand but can't break.

I mean if "good enough" is your criteria you might as well stick with
64-bit symmetric keys. I mean right now that's not practical to break
[took a team of many thousands to achieve].

> >Sounds bad. Except if I was really keen on finding collisions I'd use
> >this thing called the net to cluster people.
>
> No...actually, you wouldn't...because that would require other people
> to join in. Lots and lots of other people. My personal bet is that
> you wouldn't be able to organize anything even remotely adequate in
> terms of collective processing power because nobody gives a rat's ass
> about you.

Oh, that's a sound argument. Personal attacks!

> When SETI sets up a distributed computing effort, there's no shortage
> of volunteers. But when Tom St. Denis tries to set up something to
> find collisions in SHA-1 or MD5, how many people do you really think
> would even bat an eyelash?

Personal attacks aside [you're just jealous anyways] I doubt many
people would join in ANYONES md5 search. It's boring and people know
the result. Why do you think there isn't much interest in RC5-72?

> >The point is to think OF THE FUTURE. Do I want to develop a new system
> >using SHA-1 if it means the life of the system will only be ten years?
>
> Nobody here is touting SHA-1 as being the hash-of-choice in ten years.
> Common sense tells us that.
> But common sense also tells us that as things stand today, there's
> virtually zero risk in using it because 2^63 is still a really really
> big number with a lot of zeroes attached to it.

Common sense then tells you too keep deploying systems using crypto you
know you can break?

> >The problem is you're not thinking of ten years from now. Some of us
> >have to develop systems that intend to be used for a long time.
>
> LOL
> I'm sure that you (being 23 and all) are developing systems that will
> be in use ten years from now.

Why the personal attack? What credence does that lend to your position
here? Just because you can't do anything of substance doesn't mean
others can't.

And besides you had better ask several dozen companies using my
software, the many thousands using it in OSS, etc, etc that same
question.

But you knew that, you're oh so much more mature and experienced.
[whatever, I know for a fact you're younger than 25, mature people are
like well groomed ladies, if you have to say you are you're not.]

> Although I suppose it's technically possible...but then
> again...developing system that only YOU will be using hardly counts..

Actually I rarely use my own crypto. I use OpenSSH religiously and
GnuPG often.

But I guess I could use Dropbear [SSH software using LibTomCrypt] or
... ;-) Next thing you know I'll be using GnuTLS software that ... oh
wait USES MY MATH LIBRARY.

More people use my software than I think you care to realize. You're
too busy thinking up, fidgiting with your brow furiously your next
insightful insulting reply.

> >The other thing is there is no reason to propose SHA-1 anymore. At the
> >very least use SHA-2 and there are others yet [WHIRLPOOL and Tiger/192
> >come to mind].
>
> SHA-1 is tried and tested and proven effective over the course of the
> last 10 years. It's been the most widely used hash (next to MD5), and
> the most scrutinized. The fact that we're just now discovering these
> "weaknesses" 10 years later which still require 2^63 work, tells us
> that there's nothing wrong with continuing to use it for the
> foreseeable future -- especially if you've already implemented it into
> a vast infrastructure.

SHA-1 never should have existed. But that aside ... There are smarter
ways to design a hash now. SHA-2 isn't it.

You know what, right now I wouldn't fear using SHA-1. What you are
missing is deployment. Why write new software that uses SHA-1 when all
that is going to happen is you'll have to change it in another couple
years...?

> WHIRLPOOL is way too new to be trusted. I like the fact that one of
> its creators is Rijmen (of Rijndael fame), but this one thing alone is
> not enough for me to put my trust into it.

It's also on solid academic standing too. It's a wide-trail design
using a well known synthetic approach.

> Tiger is not as new...which is good, but also not as
> scrutinized...which is bad.

Agreed.

Tom

Relevant Pages

  • Re: MD5s eulogy
    ... MD5 is Dead. ... A Close relative, SHA-1, is in the OR bleeding out on the table. ... slashdot article reference included below. ... >arbitrary collisions, just random collisions), it's folly to think it'll ...
    (news.software.readers)
  • Re: MD5 vs SHA-1
    ... > US government. ... Because MD5 is a 128-bit hash, collisions can start to occur ... For this reason, SHA-1 is safer. ... some potential weaknesses have been found in MD5. ...
    (sci.crypt)
  • Re: SHA-1 broken
    ... A Chinese research group now says that collisions can be found in the full ... SHA-1 in 2**69 hash operations, much less than the brute-force attack of ... 2**80 operations based on the hash length. ... MD5 was cracked. ...
    (Bugtraq)
  • Re: This Weeks Finds in Mathematical Physics (Week 226)
    ... Yeah, I said SHA-1 and MD5 are different, and I said they were both vulnerable ... Attacking hash functions by poisoned ... where Ldenotes the length of the axiom system A, ...
    (sci.physics.research)
  • Re: When will md5crk complete?
    ... and in that case birthday attack ... > His core message is correct however: you shouldn't be using MD5. ... Collisions DO exist for every hash algorithm... ...
    (sci.crypt)