GPGPU: Why Passwords Need To Be Long

[Remington]

This might not be news to some, but it's something I picked up while doing research for my security course, and I figure it might be something worth looking at.

General-Purpose Graphics Processing Unit (GPGPU) programs are a new type of program that specialize in using a computer's graphics card to assist the CPU in computing resource-heavy tasks. The power of GPUs lies in their ability to perform parallel processing: whereas a CPU can only handle a few threads of logic (general rule of thumb is number of cores x2), GPUs can handle hundreds of logic threads simultaneously (how many exactly depends on the graphics cards in question). Current applications of the theory lean towards math-heavy work like protein folding or physics simulations, but some more practical applications have recently been developed, namely password crackers.
http://gpgpu.org/



Summary: By using both CPU and GPU, password cracking utitlies can increase their bruteforce password guess rate astronomically. An example would be the ighashgpu cracker.
http://mytechencounters.wordpress.com/2011/04/03/gpu-password-cracking-crack-a-windows-password-using-a-graphic-card/

I'm going to use the NTLM hash here. If you are wondering what NTLM is, your Windows (NT and above) logon passwords are not stored as plain text but encrypted as LM and NTLM hashes. They are not reversible and hence supposed to be secure. LM hashes can easily be broken using Rainbow Tables but NTLM hashes are relatively stronger. But that's not stopping us from cracking them.

For comparison, I'm going to use another popular and free security tool – Cain & Abel. This is an excellent tool for breaking different passwords, using the CPU.

To crack a password, you need to have the NTLM hash of that password. Fortunately, Cain & Abel has a hash calculator. So let's do some password cracking.



A password with 5 characters

Using Cain, I generate a random password "fjR8n" whose NTLM hash is "AA8251D1BB587ABFAE6403194216041F" without quotes of course.

As you see, Cain has taken about 24 seconds to crack the password at the rate of 9.8 million passwords/sec.


Let's see what ighashgpu has to offer.


The password is found in less than one second. Secondly look at how many passwords the GPU has churned out per second. Dude, it's 3.334 billion passwords.




A password with 6 characters

Let's now take "pYDbL6" as the 6 character password. The NTLM hash for that password is CB898E9CA230D14413756875DD8BF71D.

Now that Cain reports it would take approximately 1 hour and 30 minutes to crack our password. Note that this is the maximum time Cain would take to crack the password. It could even be less than that, depending on the password.

What about ighashgpu?

Ighashgpu finds the password in staggering 4 seconds. Also note that the maximum time it would take to crack a 6 character alphanumeric password is about 17 seconds. See the difference between GPU and CPU computing?

3.33 billion passwords/sec against Windows password hashes is scary. Period. 8-12 character passwords, everyone.

[Freeky]

Fuck.

[Lenin McCarthy]

http://xkcd.com/936/

[Golden Applesauce]

If you have access to the hashed password, doesn't that also mean you already have access to the filesystem?

[Remington]

If you have access to the hashed password, doesn't that also mean you already have access to the filesystem?

Yeah, that's true.

[Precious Moments Zalgo]

If you have access to the hashed password, doesn't that also mean you already have access to the filesystem?

The author addressed a similar question in the comments section of the article.  He didn't go into any details, but said if the machine has a working dvd drive or usb port, then it's possible to get the hashed passwords.  I'm not sure, maybe he meant if the bios isn't locked down and/or is set up to boot from dvd/usb.

[Faust]

If you have access to the hashed password, doesn't that also mean you already have access to the filesystem?

The author addressed a similar question in the comments section of the article.  He didn't go into any details, but said if the machine has a working dvd drive or usb port, then it's possible to get the hashed passwords.  I'm not sure, maybe he meant if the bios isn't locked down and/or is set up to boot from dvd/usb.

Yeah he would have meant boot from CD usb. I needed access to my interns pc after he finished so I just put in the ubuntu disc and made myself a root account.

[Cramulus]

http://xkcd.com/936/

is that true?? a long password trumps a short complex one?

[Disco Pickle]

is that true?? a long password trumps a short complex one?

If I'm not mistaken, that's due to the power of the exponential power.

And that they're using brute force.

[Elder Iptuous]

the forum thread for that particular comic is pretty lengthy...
i guess the argument against it is that an attack that limits to concatenated dictionary attacks will rejoice at the choice...

[Disco Pickle]

the forum thread for that particular comic is pretty lengthy...
i guess the argument against it is that an attack that limits to concatenated dictionary attacks will rejoice at the choice...

yeah, but even with that, ones that long, getting not just the words in the correct order, but all of the letters to spell the words.

that's some serious clock time.

[Triple Zero]

If you have access to the hashed password, doesn't that also mean you already have access to the filesystem?

The author addressed a similar question in the comments section of the article.  He didn't go into any details, but said if the machine has a working dvd drive or usb port, then it's possible to get the hashed passwords.  I'm not sure, maybe he meant if the bios isn't locked down and/or is set up to boot from dvd/usb.

Yeah he would have meant boot from CD usb. I needed access to my interns pc after he finished so I just put in the ubuntu disc and made myself a root account.

There's various things about hash cracking:

theoretically, in security it is assumed that as soon as an attacker gains physical access to your machine, it's no longer your machine. there's just too many ways they can mess with it or plant back doors.

this GPGPU thing is just yet another way to make it even easier

it is possible that someone's document files are encrypted, unless you're logged in (this is actually a simple checkbox "HD encryption, yes/no?" during Ubuntu installation, you're lucky your intern did not enable it,  Faust ).

so in that case, as soon as you get physical access to the machine, you can boot from USB or CD, and the only thing you can get at is either a harddisk full of encrypted noise or the hashed passwords of the login accounts (these need to be available, otherwise the login program cannot check the one-way-hash of what you typed in with the one-way-hash of the correct password to determine whether to let you in or not).

so in that case, you grab the hashes, crack them and pwn the box w00t mad h4xx0r sk1llz etc etc




another much more widespread scenario--well I'm not sure if it actually happens more than the above scenario (since hacking attacks with physical access are by their nature often kind of secretive), but the following scenario just affects much more people, in general (and even you!) :

When hackers gain access to some big website or server, one that has many, often 100,000s, user accounts. Big forums, social websites, that sort of stuff. Now if they coded their shit properly, they will never save their passwords in plaintext in the database, specifically because of the possibility of this particular event happening, instead, they will save a salted one-way-hash of the passwords.

Now the hackers got this huge database dump of one-way-hash salted passwords, and the thing about one-way-hashes is that it is supposedly very hard to go the other way (i.e. get the password from the salted hash).

This happens really really quite often, with rather big websites and forums (Gawker, to name one). This is why it is so important to never ever re-use a password on different websites, that's the only was you the user can protect yourself, instead of relying on the big corporate websites implementing their security properly (which they won't).

And the GPGPU thing makes this many, many times faster and easier for the attacker.

That's why this is kinda a big deal.

But not really. Because the sad thing is, implementing a correct password hashing scheme is really really hard and 99% of most people are doin it wrong. In fact, the very SMF software running this forum is doing it wrong.

For example you could already do this without GPGPU program because you can just rent a couple of boxes worth of computing from Amazon S3 until they're doing it fast enough.

Or you wait a few years, and computers get 10x as fast


Here's my advice for if any of you [coders] ever happens to think to need to implement a correct password safekeeping hashing scheme. THIS is THE ONLY RIGHT WAY TO DO IT:

USE BCRYPT

Why BCrypt? Because it's SLOW AS HELL, as opposed to MD5 or SHA256, which are designed for speed. BCrypt is in fact designed for SLOW. Afaik it has a variable setting so you can tell it how slow you want it to be. Just in case the computers get unexpectedly faster in the near future, you can just crank up your BCrypt slowness all the fucking way up to 11

yes this can make you safe from GPGPU attacks as well.



Oh and to answer Cram

is that true?? a long password trumps a short complex one?

Yes. This is absolutely true.

Think about it like this.

With digits, how many numbers can you make with four digits chosen from 0-9?
The answer is: 10⁴ = 10,000. This is the short complex password.

How many numbers can you make with twelve digits chosen from just 0-3?
The answer is 4¹² = 16,777,216. This is the long (three times longer) password chosen from a much simpler alphabet.

Does that clear it up?

There's been a lot of discussion about that particular XKCD cartoon. It's not always as simple as that. Some sites do not allow long passwords (which is stupid and retarded, yes, but as we are very aware, that only seems to make it more likely for people to do it that way). In fact, there even are websites that silently truncate your password and only look at the first 8 characters of it. You need to check that, by deliberately misspelling the last letter of your long password and see if it errors on you.
In all fairness, I made a programming error once on a website for myself that did exactly this. It took me weeks before I wondered why I never seemed to mistype my rather long passphrase.

Also if you want to use different passwords for different sites, using many words long passwords, is also not going to make them very memorable.

(Solution: Just write them down on a piece of paper in your wallet) (if you can keep your creditcard secure, you can also keep the piece of paper secure)

Finally, there's one solution that's strictly better than using long passwords, and that is to use a proper password manager such as KeePass.

Basically this allows you to do both things, because it will generate completely random (very complex) long passwords for you. That's about as secure as you can get.

Then it stores them encrypted under a single passphrase (which you will need to remember, but it's just one).

You can carry around KeePass on a USB stick or put the password file on your DropBox account, so you can use it anywhere.

No, I don't do this either. But it's the best solution.

My personal strategy is to practice and try to be good at memorizing complex passwords

[Triple Zero]

the forum thread for that particular comic is pretty lengthy...
i guess the argument against it is that an attack that limits to concatenated dictionary attacks will rejoice at the choice...

No. If you read the comic, you'll see that he takes that into account:

he only counts 11 bits of entropy for each word in the long password:

11 bits has 2¹¹ = 2048 combinations.

So he is assuming that the dictionary from which he picks the random words only has 2048 words in it

that's a pretty fucking tiny dictionary.

most password dictionaries are in the 100,000s.

except he uses four words, so the amount of combinations is 2048 * 2048 * 2048 * 2048 = 2⁴⁴ = 17,592,186,044,416

that's how long you'll be guessing IF you take the optimal approach of only guessing "four concatenated dictionary words" GIVEN that you know exactly from which 2048 words they were taken.

if you don't know that, you'll be guessing even much much longer


it's a pretty good approach. the downsides are only of a practical manner, the theory is absolutely sound.

[Elder Iptuous]

i see.
and the practical downside being how you mentioned that you would have to should have different, very long passwords for each website, thus negating the 'easy to remember' part?

[Precious Moments Zalgo]

If you use something like Diceware to generate your words, then you are choosing from a dictionary of 7776 words.  Each word will add 12.9 bits of entropy.  A totally random password of any printable ASCII character has 6.5 bits of entropy per letter.  A four word Diceware password and a password of eight random printable ASCII characters will be approximately equally difficult to crack (51.6 vs 52 bits of entropy).