Re: Can anyone break MD5 scheme?

[John Daniele <johnd () tsintel com>]

Hello,

> As for MD5, to the best of my knowledge, brute force is the only way to
> 'crack' it... however I have heard rumors that some implementations are
> weaker then others.

Brute force is the least efficient attack against MD5, the next best thing
is a 'birthday attack' which is based on the idea that in a group of 23
random people there's a probability of 50% that 2 share the same birthday.
Therefore, if x represents given inputs to MD5 and y represents its
possible outputs there are x(x-1)/2 pairs of inputs. For each pair there's
a probability of 1/y. There's a 50% probability that a matching pair will
be found in y/2 pairs. There's a good chance of this occuring if n is
greater than the root of y. However, this would still take thousands of
years of computer time in a practical attack! Next best thing after that
is a differential cryptanalytic attack. But that's only been proven
effective against 1 round of MD5.

_________________________________________
John Daniele
Technical Security & Intelligence Inc.
Toronto, ON
Voice:  (416) 684-3627
E-mail: johnd () tsintel com
Web:    http://www.tsintel.com

On Sat, 30 Nov 2002, flur wrote:

> Perhaps a less controversial solution to get your linux box online would be
> to designate an older machine running MS Windows as a router... There is
> lots of software that will do this for you (ie Sygate, WinRoute, etc). With
> few access list rules you can make the router quite transparent, and it can
> serve as your first line of defense.
>
> As for MD5, to the best of my knowledge, brute force is the only way to
> 'crack' it... however I have heard rumors that some implementations are
> weaker then others.
>
> At 06:03 AM 11/28/2002 +0800, you wrote:
> > I paid a high monthly fee for my PPPOE connection. The damned ISP offered
> > only the client for M$ Windows. According to the packet dump, they use
> > CHAP for authorization and the CHAP challenge  said it used MD5. But when
> > rp-pppoe MD5s the string of Identifier+Secret+Challenge Value, the
> > concentrator said the response is wrong.
> >
> > Apparently the ISP-offered client is not going with the RFC 1994 standard
> > for CHAP and obviously I cannot get their source code by social engineering.
> >
> > /Is there a way to break the MD5? Or anyway around ? /I  need to know my
> > ISP's digest scheme to get my Linux box online. I lived in a
> > higly-sensored country and who knows what the offered client will do
> > behind my back? Thanks in advance for my safety (not privay).
> >
> > __________________________________________________
> > Do You Yahoo!?
> > Everything you'll ever need on one web page
> > from News and Sport to Email and Music Charts
> > http://uk.my.yahoo.com
>
>
> ____________________ __ _
> ~FluRDoInG                        flur () flurnet org
>                              http://www.flurnet.org
> KEY ID 0x8C2C37C4 (pgp.mit.edu) RSA-CAST 2048/2048
> 1876 B762 F909 91EB 0C02  C06B 83FF E6C5 8C2C 37C4