It has been ages that software systems have been saving hashed passwords in various forms, e.g. MD5, SHA1, salted hash, etc. Like a lot of other ways of storing user passwords, theoretically the hashed passwords are vulnerable to brute-force attacks. But people were not too worried about it, especially for longer passwords, because the sheer volume of computation had made such attacks nearly impossible. For example, to perform a brute-force attack on a 6-character password which consists of letters and numbers, the hacker’s brute-force attack program needs to traverse 62^6 = 56.8 billion hashes. “Who would be able to perform such an attack in a reasonable amount of time? Only the people who possess a supercomputer. Maybe someday in 30 years when PCs are as powerful as supercomputers, we will consider the risk then…”
Unfortunately that “someday” has already arrived – TODAY!
How did it happen? Let’s start with the Graphic Cards development. Inspired by enthusiastic and demanding computer game fans, graphic card manufacturers have been producing faster and faster graphic cards with their own processing unit, or GPU. GPUs bring a massively parallel computing capability to PCs with hundreds of processing cores in a single chip. In addition, the on-board RAM of graphic cards are very fast: up to 70GB/sec. To unleash the computing power of graphic cards, major graphic card manufacturers such as nVidia and AMD have introduced a new concept of General-Purpose computing on Graphics Processing Units (GPGPU), to perform computation in applications traditionally handled by the CPU (http://en.wikipedia.org/wiki/GPGPU). The following chart illustrates the difference in the number of processing cores between GPU and CPU.
In other words, by simply installing a computer game fan-level graphic card in your PC (together with GPGPU-aware software), you can easily turn your PC into a teraflop “Personal Supercomputer”, with a dirt-cheap price. This concept is now triggering a major revolution in scientific computing, video processing, cryptography, etc. Smart hackers have noticed the great processing power of GPUs and have started to leverage it in brute-force attacks on hashed passwords.
Geared by the powerful yet easily accessible personal supercomputers, brute-forcers can now traverse hashes at an unprecedented speed. For example, ATI HD5870 can generate 795 million SHA-1 hashes per second – 46 times faster than Intel i7 920 – one of the fastest CPUs at the moment (*measured in my test setup). A lot of gaming fans would setup two graphic cards to boost the performance (so-called “CrossFire setup”), as a result, a good gaming PC nowadays can generate 1.59 billion SHA-1 hashes per second! The following table shows the average time needed to crack salted SHA-1 passwords of various length with the help of a personal supercomputer (ATI HD5870 with CrossFire setup):
Avg. Time Required to Crack w/ 1 PC*
Avg. No. of PCs required to crack the password within 90 days
*The passwords are composed of alphabetic and numeric characters only.
As you can easily see, it is a piece of cake for personal hackers to crack a 9-charater (or shorter) passwords within the password expiration time (say 90 days). It is not too difficult for a well-funded hacker organization to crack a 10-character password within 90 days. With specially built Personal Supercomputers, such as the ones listed in http://www.nvidia.com/object/personal_supercomputing.html, cracking passwords can be even faster.
On the other hand, a recent study reveals that the average password length is 8 characters, and only 6% of them contain both alpha-numeric and special characters. This means that a gamer’s computer can crack most users’ passwords within a single day!
1. With the easily accessible and cheap personal supercomputers, the threat is real! System administrators should now seriously consider enforcing a minimum password length policy and set it to 11 at least.
2. Software vendors should start looking at countermeasures to significantly reduce the risk. One of the straightforward ways is to implement PKCS#5 recommendation (http://www.faqs.org/rfcs/rfc2898.html): to hash the salted password for 1000 times before storing it. Such an operation would not likely to be a burden for the normal authentication process, but will slow down the brute-force attack significantly.