Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

There are a lot of research papers available online that discuss vulnerabilities of MD4 algorithm, but I couldn't find any implementation of these.

Uptill now I have used tools like John the Ripper or MDCrack and tried to bruteforce the hash. But bruteforcing seems like a waste of CPU power when collision attacks can be done much more efficiently. (In few seconds I've read).

Are there any available tools for generating collisions for MD4 hashing algorithms? (Preferably open source and preferably in Python, Ruby, Perl or Java because I know these better than C)

share|improve this question
2  
Collision != first pre-image. For password cracking you need to find first pre-images, not collisions. –  CodesInChaos Jan 5 '13 at 10:46
1  
This question might be interesting. It's about MD5, but the kinds of weaknesses MD4 has are similar to those of MD5: Is MD5 considered insecure? –  CodesInChaos Jan 5 '13 at 14:29
add comment

2 Answers

up vote 3 down vote accepted

Some googling pointed me to this source code file which, when compiled, should generate MD4 collisions using Wang's method (published in 2005). This is not the fastest collision attack for MD4, but it is enough to produce thousands of them.

However, tools like John the Ripper are for finding passwords from their hash; collisions are no help at all for such a task. Finding a collision is about computing two distinct strings m and m' which, when both hashed, yield the same value. For collisions, we do not care which hash value we actually obtain, as long as we get the same for both messages. For cracking password, you work over a fixed hash value which you cannot choose (you found it in a database or a similar source), and you try to find a string p which hashes to that specific value (and none other): this is a preimage attack.

MD4 is also academically broken with regards to preimages; an attack was found by Leurent in 2008. Mind the "academically" term, though: the attack has cost 2102 evaluations of the hash function. This is millions of times faster than the robustness expected from a hash function with a 128-bit output (which should resist up to cost 2128); however, this attack is still way beyond that which is technologically doable right now (a very big organization with lots of computers and money, like Google, might dedicate its vast wealth to the problem and perform about one billionth of the work within a few years, but no more).

For cracking passwords which were hashed with MD4, the best known method is still a "dictionary attack", also known as "brute force": try potential passwords until a match is found. If the hashing process did not include a per-password random element (a "salt") then the brute force effort can be shared through the use of precomputed tables (e.g. rainbow tables) but the tables still have to be built at least once.

share|improve this answer
    
Thanks for clarifying the difference between collision and preimage attack. I was mixing them up. Personally I've found rainbow tables to be pretty useless for passwords longer than 7 characters. A 8 char alphanumeric+basic symbols table is 18TB in size. So I'm searching for something a little more mathematical/efficient than bruteforce or RTs. –  Kshitiz Sharma Jan 5 '13 at 15:45
add comment

It seems that you are mixing up collision attacks and first preimage attacks (as already mentioned here). In the following I will describe both shortly, a more detailed explanation can be found here.

In a collision attack you are searching for two (different) messages which produce the same hash – the contents of the messages don't matter.

However, in a first preimage attack you have a pre-defined (fixed) hash and you are searching for a message which has exactly the same hash.

Therefore, if you want to find the passwords for any given password hashes, you actually have to apply a first preimage attack and no collision search. For preimage attacks on MD4 that are faster than just bruteforcing consider this paper and related work.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.