Another reason not to use MD5

[Digital Parasite]

It looks like there is yet another reason not to use MD5. A group of people have pre-computed all MD5 hashes of 8 characters or less that use lowercase letters and numbers. They even provide a new web interface to do the lookup for you:

http://passcracking.com/

[dawithers]

bahahaha i was just thinking about that.....

yet another reason to switch my journalness back to sha1 from md5. Although they mentioned they plan on starting a sha1 table too.

if frickin 1and1's php supported sha1........its not supported in their version of php :(

[jlcooke]

Originally posted by dawithers
bahahaha i was just thinking about that.....

yet another reason to switch my journalness back to sha1 from md5. Although they mentioned they plan on starting a sha1 table too.


The problem with dictionary attacks is:
- salt
- computation time for a single hash

You can fix both of these by replacing:
digest = HASH( data )
with:
digest = HASH^65536( salt , data )
where HASH^65536(x) = HASH( HASH( HASH( ... HASH( x ) ... )))
where salt is 32bits long
store salt and digest together.

This will make computing a distionary like the one above useless since there are 2^32 (4,294,967,296) as many dictionaries to compute. And each dictionary is now 65536 (2^16) times harder to compute. All this while keeping the run-time computation very managable.


Originally posted by dawithers

if frickin 1and1's php supported sha1........its not supported in their version of php :(

Have you tried "mhash" ? As I recall it does work.

[Mystwalker]

Originally posted by Digital Parasite
It looks like there is yet another reason not to use MD5. A group of people have pre-computed all MD5 hashes of 8 characters or less that use lowercase letters and numbers. They even provide a new web interface to do the lookup for you:

http://passcracking.com/

I read those pages and Philippe Oechslin's "faster time-memory trade-off technique" paper. What I don't get:
Isn't it easier to just put all (Hash, password) tuples into a database system, set 2 indexes et voilà - fini!
When entering a hash (SELECT * FROM table WHERE hash=enteredHash), the result should be there in no time (hey, we have point queries of indexed data here!) with 100% coverage.
Do I oversee something?


Originally posted by jlcooke
[B]The problem with dictionary attacks is:
- salt
- computation time for a single hash

You can fix both of these by replacing:
digest = HASH( data )
with:
digest = HASH^65536( salt , data )
where HASH^65536(x) = HASH( HASH( HASH( ... HASH( x ) ... )))
where salt is 32bits long
store salt and digest together.

When I used the MD5 hash of a password as the key for a Triple-DES en/decryption, I simple added 'xxx' to the front and the start - so it's basically a very primitive version of this. :D
Of course, this won't protect much better - but I had no big background knowledge of MD5 then and the application was just an example for a lecture. So no sophisticated, unbreakable algorithms were neede. ;)
When I need it in "real life", though, I guess I will take your salt idea. Thanks! :thumbs:

[jlcooke]

Originally posted by Mystwalker
I Do I oversee something?

Yes - size.

8 charactor passwords using 0-9, a-z, A-Z is (10+26+26)^8 = 2.1834E+14 possible passwords.

DB size = 2.1834E+14 * (8bytes + 16bytes) 16bytes = 128bit.
or about 4.7 PetaBytes (1,048,576 GigaBytes)

And "index" into this data base would be very large indeed. Simply using the MD5CRK MD5 cores to *search* this space is 1,000,000 times faster then any hard drive based DB could be.

Use the approach I mentioned above and you'll be safe for sure.

[Matt]

Originally posted by jlcooke
DB size = 2.1834E+14 * (8bytes + 16bytes) 16bytes = 128bit.
or about 4.7 PetaBytes (1,048,576 GigaBytes)



I wouldn't mind a hard disk cabable of holding that much data ;)

It's nice to see that the people in charge of the project really know what they're talking about (from what I can see/understand) and have really got their head around the whole issue. It makes me feel much more confident in the project.

[Mystwalker]

Originally posted by jlcooke
Yes - size.

8 charactor passwords using 0-9, a-z, A-Z is (10+26+26)^8 = 2.1834E+14 possible passwords.

DB size = 2.1834E+14 * (8bytes + 16bytes) 16bytes = 128bit.
or about 4.7 PetaBytes (1,048,576 GigaBytes)

Hm, I optimized my idea:

- only 0-9;a-z like the ppl mentioned above
- as every password is there, there's no need to put it into a tupel - just sort the hashes according to a certain schema of the password
- indexes aren't needed, either - just jump to the right position (16 bytes * position#)

This would take (10+26+1)^8 = 3,512,479,453,921 hashes, thus 56.2 TBytes of data. Ok, HDDs for this size would still cost ~20K €...

Of course, it is not suited for bigger amounts of hashes...:blush: