Hardware Assisted Brute Force Attacks: Still For Dummies

October 24, 2007

Evidently hardware assisted brute force password cracking has arrived:

A technique for cracking computer passwords using inexpensive off-the-shelf computer graphics hardware is causing a stir in the computer security community.

Elcomsoft, a software company based in Moscow, Russia, has filed a US patent for the technique. It takes advantage of the "massively parallel processing" capabilities of a graphics processing unit (GPU) - the processor normally used to produce realistic graphics for video games.

Using an $800 graphics card from nVidia called the GeForce 8800 Ultra, Elcomsoft increased the speed of its password cracking by a factor of 25, according to the company's CEO, Vladimir Katalov. The toughest passwords, including those used to log in to a Windows Vista computer, would normally take months of continuous computer processing time to crack using a computer's central processing unit (CPU). By harnessing a $150 GPU - less powerful than the nVidia 8800 card - Elcomsoft says they can be cracked in just three to five days. Less complex passwords can be retrieved in minutes, rather than hours or days.

GPUs, with their massive built-in paralellism, were built to do things like this. I'm encouraged that we're finally able to harness all that video silicon to do useful things beyond rendering Doom at 60 frames per second with anti-aliasing and anisotropic filtering.

There's a bit more detail on the elecom approach in their one-page PDF. They provide actual numbers there.

Using the "brute force" technique of recovering passwords, it was possible, though time-consuming, to recover passwords from popular applications. For example, the logon password for Windows Vista might be an eight-character string composed of uppercase and lowercase alphabetic characters. There would about 55 trillion (52 to the eighth power) possible passwords. Windows Vista uses NTLM hashing by default, so using a modern dual-core PC you could test up to 10,000,000 passwords per second, and perform a complete analysis in about two months. With ElcomSoft's new technology, the process would take only three to five days, depending upon the CPU and GPU.

Preliminary tests using Elcomsoft Distributed Password Recovery show that the [brute force password cracking] speed has increased by a factor of twenty, simply by hooking up with a $150 video card's onboard GPU. ElcomSoft expects to find similar results as this new technology is incorporated into their password recovery products for Microsoft Office, PGP, and dozens of other popular applications.

It's fun, and it makes for a shocking "Password Cracking Supercomputers On Every Desktop Make Passwords Irrelevant" headline, but password cracking supercomputers on every desktop doesn't mean the end of password-protected civilization as we know it. Let's do the math.

How many passwords can we attempt per second?

How many password combinations do we have to try?

52⁸ = 53,459,728,531,456

That's a lot of potential passwords. Let's stop playing Quake Wars for a few days and get cracking:

53,459,728,531,456 /  10,000,000 pps / 60 / 60 / 24 = 61.9 days
53,459,728,531,456 / 200,000,000 pps / 60 / 60 / 24 =  3.1 days

As promised by elecom, that works out to a little over three days at the GPU crack rate, and two months at the CPU crack rate. Oooh. Scary. Worried yet? If so, you shouldn't be. Watch what happens when I add four additional characters to the password:

5212 / 200,000,000 pps / 60 / 60 / 24 =  22,620,197 days

For those of you keeping score at home, with a 12 character password this hardware assisted brute-force attack would take 61,973 years. Even if we increased the brute force attack rate by a factor of a thousand, it would still take 62 years.

Elecom's idea of an 8 character password is awfully convenient, too. Only lowercase and uppercase letters, a total of 52 possible choices per character. Who has passwords without at least one number? Even MySpace users are smarter than that. If you include a number in your 8 character password, or a non-alphanumeric character like "%", attack times increase substantially. Not enough to mitigate the potential attack completely, mind you, but you'd definitely put a serious dent in any brute forcing effort by switching out a character or two.

628 / 200,000,000 pps / 60 / 60 / 24 =  13 days
728 / 200,000,000 pps / 60 / 60 / 24 =  42 days

Personally, I think it's easier to go with a pass phrase than a bunch of random, difficult to remember gibberish characters as a password. Even if your pass phrase is in all lower-case-- a mere 26 possible characters -- that exponent is incredibly potent.

2610 / 200,000,000 pps / 60 / 60 / 24 =  8 days
2612 / 200,000,000 pps / 60 / 60 / 24 =  15 years
2614 / 200,000,000 pps / 60 / 60 / 24 =  10,228 years

By the time you get to a mere 14 characters-- even if they're all lowercase letters-- you can pretty much forget about anyone brute forcing your password. Ever.

So what have we learned?

Brute force attacks, even fancy hardware-assisted brute force attacks, are still for dummies. If this is the best your attackers can do, they're too stupid to be dangerous. Brute forcing is almost always a waste of time, when vastly more effective social vectors and superior technical approaches are readily available.

Hardware-assisted brute force attacks will never be a credible threat. But short, simple passwords are still dangerous. If your password is only 8 alphabet characters, and if it's exposed in a way that allows brute force hardware assisted attack, you could be in trouble. All you need to do to sleep soundly at night (well, at least as far as brute force attacks are concerned) is choose a slightly longer password. It's much safer to think of your security in terms of passphrases instead of passwords. And unlike "secure" 8 character passwords, passphrases are easy to remember, too. Have you considered helping me evangelize passphrases?