Passwords passé?

We enter 2011 with a few developments that have a significant impact on the efficacy of passwords.  Advances in Computer Unified Device Architecture (CUDA),  optimized rainbow tables, solid-state drives (SSD), and infrastructure-as-a-service (IaaS) have come together to provide password crackers with a very powerful set of tools.  How these come together to crack strong passwords can be a technically exhausting conversation, so I will oversimplify a bit in the interest of getting you through this with only a slight headache.

One way to crack any password is to simply try every possible password until you find the one that works, a brute-force attack.  The limiting factor with this method is time.  The basic concept here is that the longer the password and greater the character set (lower-case, upper-case, numbers, special characters), the longer it will take to try every combination.  So the goal of the password cracker is to reduce that time.  Each of the technologies covered here reduces that time in a different way.  Using them together cuts that time by several orders of magnitude.  This has yielded results of 300 billion password guesses per second.  In practical terms, tests have shown that a 14-character password, including special characters, can be cracked in 5.3 seconds, on average.

Let's have a quick look at each of the technologies.  CUDA cuts time by providing very high-speed processing.  It is NVIDIA's parallel computing architecture that enables dramatic increases in computing performance by harnessing the power of general-purpose graphics processing units to perform computation in applications traditionally handled by the CPU.

Rainbow tables are basically lists of password hashes and their equivalent plaintext passwords.  A password hash, is what is actually stored, so that when you enter a password, its hash is compared to the stored hash.  While you can derive the hash from the password, the process cannot be reversed.  For you purists in the crowd, it is more accurate to say that it is computationally infeasible to derive the password from its hash.  The rainbow table is created by finding the password hashes ahead of time and then storing the results in the table.  So when attempting to crack a password, you can do a look-up in the table and see if the hash and its plaintext password is already there.  If so, the work has already been done for you.  The problem with rainbow tables is that they take up a lot of memory space.  Optimized rainbows allow for the fasted look-up, while minimizing the memory space required.  Keep in mind that the word "minimizing" is relative.  The test that cracked the 14-character passwords in 5.3 seconds used an 80GB rainbow table.

So, how do you get through an 80GB table quickly?  Enter SSD.  Compared to a mechanical hard disk drive, accessing data on a solid-state drive is about 100 times faster (give or take an order of magnitude).  Of course, they cost more as well, but at less than $2/GB, still very affordable.

Even as affordable as it is to build or buy a high-speed password-cracking computer, it can be done for even less.  With IaaS making serious processing power available by the hour at minimal cost, anyone with a credit card can get pretty much whatever they need. Amazon's EC2 service provides Cluster GPU Instances that will fit the bill quite well.  It's already been done at the cost of a mere $2.10/hr.

2011 looks like a good year to consider authentication methods beyond simple username/password.  The market has been responding with a wide variety of multifactor authentication mechanisms.  Check out Two-factor authentication is cool again! for some examples.  Regardless of which you choose, it is essential to protect against the increasing risk presented by simple username/password authentication.