[lug] MD5 strength?

[D. Stimits]

rm at fabula.de wrote:
> On Fri, Aug 30, 2002 at 06:48:40PM -0600, D. Stimits wrote:
> 
>>I am curious, for the MD5 password hash, is this currently considered 
>>strong, or is it easily broken by normal hardware? I have people telling 
>>me that password hash is useless and broken quite easily, and if this is 
>>about old style passwords, I agree...but with MD5, I do not believe that 
>>any real weakness, other than perhaps theoretical, has been found. If 
>>someone uses a buffer overflow attack to email the shadow file, and if 
>>the shadow file is MD5, what kind of difficulty would the attacker have 
>>at cracking non-common passwords (passwords not from a common words, 
>>where it must actually be broken instead of guessed)?
> 
> 
> Humpf? As the name 'hash' allready implies: there is no way to "break"
> an MD5 password--the original password can't be recovered from the
> crypted version (the crypted version is a _M_essage _D_igest). Now, for

This is true only if it is not practical to generate all/most possible 
combinations/permutations of characters. I believe generating a 
dictionary of hashes from known words is trivial in any one-way hash, 
but due to seed/salt and other size difficulties, this is not 
necessarily true on *some* algorithms, where computing power and storage 
space is limited. The context of the question is not general encryption, 
it is about finding the password...having a dictionary of all 
combinations/permutations of permitted characters counts. However, there 
is a further stipulation in the original question...that the password 
being used is not a stupid common word, that the chosen password is 
random. In the case of single DES, it would be trivial to create a 
dictionary of all possible hashes of all 8 character or less password 
phrases, even if completely made up of random characters.

So far it looks like most answers tend to say that MD5 is a fair hash if 
the password chosen is good. I suppose this is why a number of package 
management utilities still use MD5 for checks against tampering, rather 
than moving to something "better" (like SHA-1).

> login etc. you don't _need_ the original version, you only need a word
> that will hash to the same value, and that's where the concerns you mention
> start: given enough hardware it's possible to find words that hash to
> the same value. So, for really strong security you might want to pick
> another digest method (SHA seems to be safe).

I don't disagree at all, but I am interested in MD5 because there seems 
to be some mistaken assumption still out there in the world that if 
someone manages to read a shadow password file that all of your 
passwords are useless even though encrypted. I think that this is due to 
the original crypt function using only DES. The glibc version offers MD5 
in addition to single DES, which is why I am interested in it. Using MD5 
only requires glibc be present, whereas SHA-1 and most newer "strong" 
algos require OpenSSL [with a different license, which has caused some 
people to argue...nobody argues about whether they can link dynamically 
to glibc and call the crypt function for passwords].

D. Stimits, stimits AT attbi.com

> 
>   Ralf Mattes
> 
> 
>>D. Stimits, stimits AT attbi.com
>>
>>_______________________________________________
>>Web Page:  http://lug.boulder.co.us
>>Mailing List: http://lists.lug.boulder.co.us/mailman/listinfo/lug
>>Join us on IRC: lug.boulder.co.us port=6667 channel=#colug
> 
> _______________________________________________
> Web Page:  http://lug.boulder.co.us
> Mailing List: http://lists.lug.boulder.co.us/mailman/listinfo/lug
> Join us on IRC: lug.boulder.co.us port=6667 channel=#colug
>