Differences Between Fast Hashes and Slow Hashes

Summary

This article is intended for new John users who have not had a lot of experience cracking different types of hashes. The goal is to explain the differences between fast hashes and slow hashes so that new users will have realistic expectations when using John to crack passwords. Note that the original essay was posted to the John Users mailing list.

Two Basic Hash Types

  1. Fast Hashes
  2. Slow Hashes

Fast hashes are typically cryptographic hashes. These hashes have several design requirements, one of which is that they must be easy to compute. In other words, they must be fast and efficient to calculate. Why would their designers want them to be fast?

The main reason for the efficiency requirement is that cryptographic hashes are used for such things as message authentication codes (MACs), digital signatures, and other authentication systems as well as for checksums to ensure data integrity during file transfers, etc. For these reasons (and several others) software and hardware that calculate these hashes must be able to do so very quickly with almost no noticeable latency to the end-users of these systems. The faster they are, the better. Some examples of fast hashes include (but are not limited to) MD4, MD5 and SHA-1. These hashes are used extensively by many software and hardware systems and are in general very common.

One advantage to fast hashes is that they are very portable and can be found in programming libraries for most every major programming language. Thus, developers using PHP, C++, Java, C, Ruby, etc. can easily use a fast hash such as MD5 to store user passwords. And, if the developers switch from one language to another, they can do so with the knowledge that MD5 is just a library call away.

Slow hashes, on the other hand, have different design goals. They are expected to be copied and subsequently attacked by crackers. Thus, they are designed to be inefficient and more difficult to calculate. Some examples of these slow hashes are bcrypt, PBKDF2 and scrypt. Also, slow hashes are not as widely available and not as simple to implement as fast hashes.

Both fast and slow hashes are in use today for password storage so you should expect to see both when auditing systems in heterogeneous environments. Microsoft's Active Directory Servers store user passwords as fast MD4 hashes while many Linux and BSD systems use slower bcrypt hashes. And, if you've never cracked a slow hash type, it may come as somewhat of a shock to you to see how many cracks per minute you get when attacking the slower brcrypt hashes. Here's an example that demonstrates the difference:

john-1.7.9-jumbo-6/run/john –test –format=nt2 Benchmarking: NT MD4 [128/128 SSE2 intrinsics 12x]… DONE Raw: 30302K c/s real, 30302K c/s virtual

john-1.7.9-jumbo-6/run/john –test –format=bf Benchmarking: OpenBSD Blowfish (x32) [32/64 X2]… (6xOMP) DONE Raw: 5724 c/s real, 947 c/s virtual

As you can see, the performance difference is huge. Even with OpenMP, the bcrypt hashes are still far more difficult to attack.

Other Password Cracking Software

Many of the new GPU based password crackers only work on the fast, easy hashes. They can crack hundreds of millions of these hashes each second. They are very impressive and exciting to watch as the cracked passwords scroll by on the console. If you are new to password cracking and you have only used one of these newer GPU based password crackers to audit simple, fast hashes, you may expect that all password hashes crack that easily. If you hold that expectation, you will be disappointed when you use John to crack OpenBSD Blowfish hashes. You may even think that John is not as good as those other password crackers, but if you do, you would be mistaken.

John works with the fast, easy hashes as well as the hard, slow hashes and adds new hashes each release. The developers of John don't back away from hard, slow hashes. In fact, they find it a challenge to crack them! They understand that in the real-world many security aware organizations implement systems that use slow, hard hashes and thus need the ability to audit their passwords too, and they should be able to do that.

Conclusion

I typically limit my password auditing sessions to 48 hours and I audit both the fast and the slow hashes and I would encourage you to do the same. It's been my experience that 48 hours is a reasonable time period in which to crack most of the weaker passwords. During this time, I may crack 50% or more of Active Directory hashes, but only 20% to 30% of bcrypt hashes. However, there are exceptions to this. On one occasion, I cracked close to 70% of the bcrypt hashes using John, but that was only because there was a very common, simple pattern used throughout most of the hashes. That's by far the most bcrypt hashes I've ever cracked while auditing. It was a shame to see such a good, strong hash wasted on such weak passwords.

In conclusion, now that you know what sort of performance to expect when cracking fast and slow hashes, you should be more effective when performing password auditing.

john/essays/fast-and-slow-hashes.txt · Last modified: 2012/07/07 13:52 by rbt
 
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate to DokuWiki Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki Powered by OpenVZ Powered by Openwall GNU/*/Linux Bookmark and Share