1

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?

Kshitiz Sharma
  • 223
  • 1
  • 3
  • 8
  • 5
    Collision != first pre-image. For password cracking you need to find first pre-images, not collisions. – CodesInChaos Jan 05 '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?](http://security.stackexchange.com/questions/19906/is-md5-considered-insecure) – CodesInChaos Jan 05 '13 at 14:29

2 Answers2

6

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.

Thomas Pornin
  • 322,884
  • 58
  • 787
  • 955
4

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.

Community
  • 1
speakr
  • 141
  • 3