Skip to Content

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.

 

GPU vs. 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):

 

 Password Length

Avg. Time Required to Crack w/ 1 PC*

 Avg. No. of PCs required to crack the password within 90 days

 5  0.3 sec  1
 6  18 sec  1
 7  19 min  1
 8  19 hrs  1
 9  49 days  1
 10  8.4 yrs  34

*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!

 

Conclusion

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.

To report this post you need to login first.

7 Comments

You must be Logged on to comment or reply to a post.

  1. Ethan Jewett
    This is a good explanation of a big issue, which is a manifestation of an even bigger issue: security code is very hard to get right. The solution is for vendors and implementors to use only expert-designed, publicly-reviewed implementations whenever possible. The password problem in the specific form outlined here has been solved for decades (long salts, slow hashes), but there are thousands of ways to make a little mistake and get it wrong.
    (0) 
    1. Dong Pan Post author
      Hi Ethan,

      Thanks for your great comments! Completely agree that software vendors should use expert-designed, publicly-reviewed security standards. I just want to point out that long salts is probably not going to help too much in this particular case.

      Long salts, such as the 64-bit salt recommended by PKCS#5, help reduce the risks of pre-calculated hash (i.e. the Rainbow Table problem, http://en.wikipedia.org/wiki/Rainbow_table) and Birthday Paradox issue (http://en.wikipedia.org/wiki/Birthday_paradox), but they don’t help too much to fight against brute-force attacks. The reason is that the processing time of a lot of popular hash algorithms are not very sensitive to the length of hash input (see the hash performance here: http://www.javamex.com/tutorials/cryptography/hash_functions_algorithms.shtml).

      (0) 
      1. Ethan Jewett
        Hi Dong,

        Yup, that’s why you need a long salt *and* a slow hash function. 😉 You got at that with the PKCS pointer, but there’s more to it than just recursively applying the hash algorithm. You also need to choose an algorithm that you know can’t be significantly optimized. 

        There’s a good, but ranty, blog on the full topic here: http://chargen.matasano.com/chargen/2007/9/7/enough-with-the-rainbow-tables-what-you-need-to-know-about-s.html  Definitely worthwhile reading. His point is very similar to yours.

        Thanks for the blog!

        Ethan

        (0) 
        1. Dong Pan Post author
          Hi Ethan,

          That’s indeed a very insightful article. Thanks!

          As I mentioned in the blog, repeated hashing is just *one* of the ways to slow down the brute-force attack. Here are the potential ways to achieve it (that I can think of now):

          1. Repeated hashing using fast hash algorithms such as SHA1 and MD5 – a CPU-intensive approach
          Pros: Hash algorithms such as SHA1 and MD5 are already widely used as password hashing mechanisms (usually with a salt) in existing systems. Therefore implementation of such a code change is very simple – just add the loop.
          Cons: To achieve the required results (esp. for shorter passwords), a large number of iterations may be necessary, thereby increasing the CPU load for normal user authentication process (remember, CPUs are not so good at mass hashing as GPUs are).

          2. Adaptive hashing algorithms like BCrypt – a CPU-intensive approach
          Pros: Adaptive hash algorithms provide adjustable hashing strengths according to the need (hopefully for the next 10-20 years).
          Cons: Same as above. In addition, it does not provide the same granularity as repeated hashing does when tweaking the hashing strength.

          3. Memory-intensive hash algorithms such as scrypt (http://www.tarsnap.com/scrypt/scrypt-slides.pdf)
          Pros: 1) High memory consumption of such hashing algorithms makes Parallel Computing (which GPGPU and FPGA devices are good at) very difficult to conduct, as the shared RAM on those devices are usually limited; while the memory consumption of regular authentication process stay at an acceptable level 2) Relatively low CPU consumption for regular authentication process
          Cons: To be found.

          I like the third approach best, but it will probably take some time to mature.

          Thanks for the very meaningful discussion on the new decade’s eve.:) I am pretty sure we will witness the change of password hashing mechanism in the new decade.

          Dong

          (0) 
  2. Sergio Ferrari
    Hi Dong,
      thanks for this interesting blog.
      To avoid brute-force-attack it should be enough to set a max number of failed attempts after which the user is locked and since this is a normal practice in SAP landscape I am curious to know if we have in any case to be worried?

    Sergio

    (0) 
    1. Dong Pan Post author
      Hi Sergio,

      Thank you for your comments.

      What this blog discusses is the so-called “offline attack”, i.e. suppose a malicious user has got the hash value of the victim’s password somehow, and tries to run brute-force attack against the hash. This is a common type of attack which is not vendor-specific. Translating that into SAP terminology, this means the malicious user has got the hash by accessing the SAP system’s database somehow. Locking users after failed logon attempts is an effective countermeasure to fight against “online attack”, which is not the focus of this blog.

      So how possible is it for a malicious user to gain access to the database of a system? Well, it depends. However be aware that nowadays more than half*(you can goolge it) of security breaches come from inside.

      Dong

      (0) 

Leave a Reply