A little more about passwords

By now, you've probably heard about ElcomSoft's patent application for a procedure used to crack passwords 25 times as fast using a GPU instead of a CPU. The parallelization that goes on in the modern GPU is to blame for this kind of accelerated password cracking -- what we call "hardware-assisted brute force password cracking" in the security biz.

Here's how brute force password cracking works in practice:

  1. A malicious security cracker gets his or her hands on the hash of your password or otherwise recreates a password test for your user account's password on a local system so he or she can try out passwords to see what works.
  2. He or she then writes or configures a program to generate combinations of characters from a character set -- and up to a reasonable length -- that allows for generating the entire set within a period of time he's willing to wait.
  3. The program then generates combinations of characters within those constraints and tries them against that password test until it finds one that works.
  4. The malicious security cracker uses the newfound password to access your account, assuming you haven't changed it in the meantime (perhaps after reading this article and realizing that uppercase and lowercase alphabetic characters limited to eight characters or less is a bad idea).

According to ElcomSoft's numbers, a dual-core CPU can generate about 10 million password attempts per second, assuming the CPU isn't doing much else (such as running Vista's Aero Glass user interface, for instance). As ElcomSoft correctly points out, that adds up to about two months (61 days) for cracking an eight-character alphabetic password. I'll demonstrate with a little arithmetic in irb (the interactive Ruby interpreter):

> irb

irb(main):001:0> eight_char_alphabetic = 52 ** 8

=> 53459728531456

irb(main):002:0> cpu = 10_000_000

=> 10000000

irb(main):003:0> seconds_per_day = 60 * 60 * 24

=> 86400

irb(main):004:0> max_seconds = eight_char_alphabetic / cpu

=> 5345972

irb(main):005:0> max_days = max_seconds / seconds_per_day

=> 61

As you can see, that's 61 days, give or take. According to ElcomSoft's numbers again, the GPU password-cracking system can generate about 200 million password attempts per second with the $150 graphics adapter used in tests. The numbers look something like this:

irb(main):006:0> gpu = 200_000_000

=> 200000000

irb(main):007:0> max_seconds = eight_char_alphabetic / gpu

=> 267298

irb(main):008:0> max_days = max_seconds / seconds_per_day

=> 3

I'm cheating a little for ElcomSoft here, because I'm using integer arithmetic instead of floating point math. The real numbers are more like 61.9 and 3.1. You get the idea, though.

Now, just for the heck of it, let's take a password that's probably about as strong as the one I happen to be using on the laptop on which I'm writing this. Let's assume the password looks something like this:

    One p^55w0rd

That's a capital letter O in "One," and a zero in "p^55w0rd," in case the font used in your browser doesn't differentiate sufficiently to make it obvious. That combination of characters means we're drawing from a character set of 73 possible characters -- 26 lowercase, 26 uppercase, 10 numbers, and 10 special characters from above the numbers using the [Shift] key, plus the space character. Now, let's figure out how long it would take the GPU method to crack that password at a rate of 200 million generated combinations per second:

irb(main):015:0> strong_p = 73 ** 'One p^55w0rd'.length

=> 22902048046490258711521

irb(main):016:0> max_seconds = strong_p / gpu

=> 114510240232451

irb(main):017:0> max_days = max_seconds / seconds_per_day

=> 1325350002

irb(main):018:0> max_years = max_days / 365

=> 3628610

Notice anything interesting? I do -- the fact that it could take a malicious security cracker using a GPU for hardware-assisted brute force password cracking 3.6 million years to crack that password. The median period for cracking a password of that length and character set would be about 1.8 million years then.

Okay, so a reasonably strong password pretty well armors you against this brute force technique using GPUs. That's not all though -- you're even safer than you think. This means of cracking passwords assumes the malicious security cracker can either download the necessary data to perform automated tests (including upper limits to the character set and password length used, as well as something against which to test passwords such as a hash of your password) or access to your machine such that he or she can run the tests in-place (since trying to do it over the Internet would slow things to such a crawl that "hardware-assisted" becomes a nonissue for brute force password cracking). If your authentication mechanisms don't make password lengths and password hashes (or equivalent) available to the security cracker, things get a lot more complicated for him or her.

So what's left?

Last week, I listed 10 security tips for use with computers running any of the major general-purpose OSes, and the very first item suggested that you use strong passwords. The opposite -- using weak passwords -- is really the biggest threat to your security when it comes to hardware-assisted brute force password cracking attempts.

Consider that a four-character password using nothing but lowercase letters can be cracked in less than a second using a single-core CPU. Even worse, you don't need to do a random brute force with many passwords because people have a tendency to use actual words for passwords. A simple dictionary attack -- comparing words in the dictionary up to a given length until the correct password is found -- suffices in many cases.

Don't expect that ElcomSoft's system means the end of effective password protection. Just don't be the one whose password is "password" and gets his computer owned by a malicious security cracker with minimal effort either.