The power of graphics processing units may threaten the world’s password security system

Aug 09, 2010 by Rick Robinson

It’s been called revolutionary - technology that lends supercomputer-level power to any desktop. What’s more, this new capability comes in the form of a readily available piece of hardware, a graphics processing unit (GPU) costing only a few hundred dollars.

Georgia Tech researchers are investigating whether this new calculating power might change the security landscape worldwide. They’re concerned that these desktop marvels might soon compromise a critical part of the world’s cyber-security infrastructure - protection.

“We’ve been using a commonly available graphics processor to test the integrity of typical passwords of the kind in use here at Georgia Tech and many other places,” said Richard Boyd, a senior research scientist at the Georgia Tech Research Institute (GTRI). “Right now we can confidently say that a seven-character password is hopelessly inadequate - and as GPU power continues to go up every year, the threat will increase.”

Designed to handle the ever-growing demands of computer games, today’s top GPUs can process information at the rate of nearly two teraflops (a teraflop is a trillion floating-point operations per second). To put that in perspective, in the year 2000 the world’s fastest supercomputer, a cluster of linked machines costing $110 million, operated at slightly more than seven teraflops.

Graphics processing units are so fast because they’re designed as . In parallel computing, a given problem is divided among multiple processing units, called cores, and these multiple cores tackle different parts of the problem simultaneously.

Until recently, multi-core graphics processors - which are made by either Nvidia Corp. or by AMD’s ATI unit - were hard to use for anything except producing graphics for a monitor. To solve a non-graphics problem on a GPU, users had to couch their problems in graphical terms, a difficult task.

But that changed in February 2007, when Nvidia released an important new software-development kit. These new tools allow users to directly program a GPU using the popular C programming language.

“Once Nvidia did that, interest in GPUs really started taking off,” Boyd explained. “If you can write a C program, you can program a GPU now.”

This new capability puts power into many hands, he says. And it could threaten the world’s ubiquitous password-protection model because it enables a low-cost password-breaking technique that engineers call “brute forcing.”

In brute forcing, attackers use a fast GPU (or even a group of linked GPUs) - combined with the right software program - to break down passwords that are blocking them from a computer or a network. The intruders’ high-speed technique basically involves trying every possible password until they find the right one.

For many common passwords, that doesn’t take long, said Joshua L. Davis, a GTRI research scientist involved in this project. For one thing, attackers know that many people use passwords comprised of easy-to-remember lowercase letters. Code-breakers typically work on those combinations first.

“Length is a major factor in protecting against brute forcing a password,” Davis explained. “A computer keyboard contains 95 characters, and every time you add another character, your protection goes up exponentially, by 95 times.”

Complexity also adds security, he says. Adding numbers, symbols and uppercase characters significantly increases the time needed to decipher a password.

Davis believes the best password is an entire sentence, preferably one that includes numbers or symbols. That’s because a sentence is both long and complex, and yet easy to remember. He says any password shorter than 12 characters could be vulnerable - if not now, soon.

Would-be password crackers have other advantages, says Carl Mastrangelo, an undergraduate student in the Georgia Tech College of Computing who is working on the password research. A computer stores user passwords in an encrypted “hash” within the operating system. Attackers who locate a password hash can besiege it by building a rainbow table, which is essentially a database of all previous attempts to compromise that password hash.

“Generating a rainbow table takes a long time,” Mastrangelo explained. “But if an attacker wants to crack many passwords quickly, once he’s built a rainbow table it might then only take about 10 minutes per password rather than several days.”

Software programs designed to break passwords are freely available on the Internet, Boyd says. Such programs, combined with the availability of GPUs, mean it’s only a matter of time before the password threat will be immediate.

Boyd hopes his password work will increase awareness of the GPU’s potential for harm as well as benefit. One result of this research, he says, could be GPU-based workstations that would offer rapid assessments of a given password’s real-world security strength.

Explore further: Vatican's manuscripts digital archive now available online

Source: Georgia Institute of Technology

4.3 /5 (24 votes)

Related Stories

Are you any good at creating passwords?

Jan 30, 2010

There's an interesting little study that's been done by security firm Imperva, which analyzed some 32 million passwords posted online in December by some enterprising hacker.

So many passwords, so little memory

Apr 15, 2009

How many keys are on your keychain? I just looked at mine and counted nine keys. And that's not counting the bulky little remote control key fob that locks and unlocks my car. I've tried to consolidate my keys by making one ...

Software tool helps tap into the power of graphics processing

May 17, 2010

Today's computers rely on powerful graphics processing units (GPUs) to create the spectacular graphics in video games. In fact, these GPUs are now more powerful than the traditional central processing units (CPUs) - or brains ...

NVIDIA Introduces New Integrated GeForce 9400M GPU

Oct 15, 2008

Demand for better visual computing performance continues to grow as more and more applications tap the massively parallel processing power of the graphics processing unit (GPU) for more than just graphics. ...

Recommended for you

Kickstarter suspends privacy router campaign

Oct 20, 2014

Kickstarter has suspended an anonymizing router from its crowdfunding site. By Sunday, the page for "anonabox: A Tor hardware router" carried an extra word "(Suspended)" in parentheses with a banner below ...

User comments : 26

Adjust slider to filter visible comments by rank

Display comments: newest first

jplur
5 / 5 (4) Aug 09, 2010
Lets just hope websites don't allow billions of brute force log in attempts.
trekgeek1
5 / 5 (4) Aug 09, 2010
18 characters baby!!! Crack that!

I'm not a hacker so I don't see how it's done. The times I have messed up my passwords on a sight, the system locks you out after 5 or so misses. How can they try so many combinations? Even if they override this feature, you will be limited to the speed at which the host server can respond with either a "correct" or "incorrect" attempt. As parallel as your GPU may be, you are bottle necked by the connection and latency of the host. Anyone?
fmfbrestel
5 / 5 (5) Aug 09, 2010
Ok, i understand the basics here, but wouldn't any system that uses a 3 strike lockout login system be automatically immune to this?
fmfbrestel
3 / 5 (1) Aug 09, 2010
after more thought, the vulnerability would lie more in someone stealing your laptop, or a rouge employee trying to gain root access at the mainframe. there would not be latency problems and a smaller likelihood of a lockout system.
MatthiasF
not rated yet Aug 09, 2010
BrookGPU back in 2004 started the GPU revolution, not CUDA.

http://www.graphi...rookgpu/
http://en.wikiped...BrookGPU
Topperfalkon
5 / 5 (1) Aug 09, 2010
The main concern in regards to this is that it leaves more modern wireless encryption protocols susceptible to attack. WEP has already been useless for a while, but WPA takes a fair amount of time and WPA2 takes a hell of a lot more.

Also, given a good enough bandwidth, sending parallel password attempts has just as good a chance DoS-ing a server as it does of cracking the password, so that may be another use there?
ScottSalley
4 / 5 (4) Aug 09, 2010
A system that locks you out after 3 (or 5) attempts doesn't prevent this scheme from working. It is often possible to grab the encrypted password (as a regular user) or sniffing the network. Once you have that, you can take it back to your evil overlord lair and spend a few hours cracking the password before going back to the system to break in.
fmfbrestel
not rated yet Aug 09, 2010
Thanks Scott, that makes this significantly more relevant in my eyes then. Time to beef up my important passwords i guess.
plasticpower
5 / 5 (3) Aug 10, 2010
@trekgeek1, they pull out your hard drive and attack a particular encrypted file that your OS uses to remember passwords. I've seen it done in seconds by students.
andyarok
4.5 / 5 (2) Aug 10, 2010
Dont need to pull out hard drive, boot from a portable OS copy SAM and Hash Tables, sig u r done.... thats how we use to do... No trace...

Using special characters like Alt+no. would make it hard to break.
trekgeek1
not rated yet Aug 10, 2010
@trekgeek1, they pull out your hard drive and attack a particular encrypted file that your OS uses to remember passwords. I've seen it done in seconds by students.


Interesting, does it matter what kind of hard drive you use? I know that some use more encryption than others. Also, I was speaking more along the lines of over a network, they'd never get my actual hard disk, that's protected by me, not encryption.

ScottSalley made a good point about getting the encrypted version and cracking it later. Though without communicating with the authorization server, I don't see how you would know when you got it. Again, I'm not well versed in this.
CSharpner
5 / 5 (2) Aug 10, 2010
There are several types of systems people are talking here and not all are exposed to this threat. Those not exposed:

- Anything where you're communicating to another machine that's processing your login request. No amount of CPU (or GPU) power on YOUR end will improve your chances because the bottleneck is the machine on the OTHER end which will NOT and CAN NOT process requests as fast as your GPU can process them.
- Also, another protection for systems trying to be hacked remotely is simply that the server that's responding to the logins just delays say 1 second after every attempt on a given account and then locks out for a minute or two after 3 to 5 failed attempts.

This GPU attack can ONLY work IF:
- You have the hashed password file in your local possession.

This means, you have to have already gained extreme access to the machine (usually, direct, physical access). NOT an easy task.

trekgeek1, you got it spot on in your first comment.
CSharpner
not rated yet Aug 10, 2010
trekgeek1,

To answer your most recent question:
Though without communicating with the authorization server, I don't see how you would know when you got it. Again, I'm not well versed in this.


Here's how passwords are stored (if the programmer designed his app right, and MOST DON'T!):

- User creates account and gives password.
- system runs the password through a hash routine (mathamatical mumble jumble) that creates what appears to be a random string of a specific length (not related to pw length).
- THAT hash is the hash and THAT is what's stored in the database, NOT the actual password.
- Later, when user logs back in, they enter their password. The login routine does the same hash algorithm on it to produce a hash string. If the user typed in the same pw they did when they created their account, the algorithm produces the same hash.
- The login routine looks up that hash in the database to determine success or failure.

Hashes are irreversible (except for brute force).
CSharpner
5 / 5 (1) Aug 10, 2010
...continued...

If a hacker steals your notebook (or server, or server HD), they may not be able to log in. But, they can boot from another disk, access the files on your hard drive, specifically the password hash file, then take the first hash as their target and starts trying trillions of passwords, hashing each one, and comparing it to the stored hash. If it matches, they now know the password.

The problem is, the hacker has to know which kind of hash algorithm the app uses (or try all the common ones). Also, it's common for secure apps to add "salt" to the password before hashing it. Salt is a secret key added to the user's password before it's hashed. This essentially makes the user's pw longer. The hacker would have to brute force much more to figure this out. If the salt is very long (like a full sentence) and the length of the hash is decently long (say 10 characters or more), it's unlikely that current GPU technology could crack it.
DaveGee
5 / 5 (1) Aug 10, 2010
In today's world there's no reason a computer that is part of a corporation and/or educational institution should have ANY local accounts on it cept for a generic admin account. All authentication should be done over a directory server... Be it ldap or whatever it is that microsoft uses... Active Directory I think? Anyway all passwords shoul be sent via an encrypted connection to the directory server so nothing can be plucked out for offline unscrambling. Since the entire path between the user entering in a password to it getting sent to a auto server is all scrambled they'd first have to break the 128/256 DES conversation that's the same stuff used to protect you banking information and then find the encrypted password and then do their offline dictionary assault to finally get your password. If your company has machines with local passwords on each system then they are asking for trouble. The idea of using a sentence for a password is a great one. Ie: Hey!DidYouKnowIHaveNOT1but2pet
jimbo92107
not rated yet Aug 10, 2010
If a hacker gets his hands on the physical machine, it's game over. However, I don't see why engineers cannot block attempts to remotely sniff packets and obtain the encrypted password. As for brute force without packet sniffing, it's just a matter of allowing no more than three guesses, timing the guesses to be no more frequent than ten seconds per guess, and notifying an administrator when somebody attempts to guess more than that.
Skeptic_Heretic
not rated yet Aug 10, 2010
Dont need to pull out hard drive, boot from a portable OS copy SAM and Hash Tables, sig u r done.... thats how we use to do... No trace...

Using special characters like Alt+no. would make it hard to break.

Leaving the drive in the machine wouldn't bypass the TPM software encryption schemas like WAVE Eras and Safeboot, however, as soon as you pull the drive, the TPM is no longer in play.
CSharpner
not rated yet Aug 10, 2010
However, I don't see why engineers cannot block attempts to remotely sniff packets and obtain the encrypted password

They do... with packet encryption. Generally using public/private keys, just like your browser does with any https web site. A hacker can easily steal/copy packets, but they're encrypted and with 128 bit key encryption, it's unlikely to be broken any time soon... not even with modern GPUs.
CHollman82
1 / 5 (1) Aug 11, 2010
then take the first hash as their target and starts trying trillions of passwords, hashing each one, and comparing it to the stored hash. If it matches, they now know the password.


You can generally figure out the hashing algorithm with a relatively small number of specific conversions...

What I mean is, while brute forcing it may take trillions of tests, you may be able to mathematically determine the algorithm after running only a few thousand of strings through it and observing the results.

I know of software that uses machine learning algorithms, in the form of pattern recognition, to do just that.
mrlewish
1 / 5 (1) Aug 14, 2010
There is one problem with a strikeout or timeout system. A DOS attack on that user can be implemented without the hacker having real access.
gwrede
1 / 5 (1) Aug 14, 2010
Davis believes the best password is an entire sentence, preferably one that includes numbers or symbols.
Theoretically yes. But with this as company policy, people will make sentences like "My daddy had 95 sheep and 30 cattle." Now, this is even worse than a good password!

Password sentences made by amateurs tend to contain common words. A lower-class worker in London uses 300 words as his entire vocabulary in an average week, according to a study I read in the '70s. But let's make a sentence of 8 words from a vocabulary of 2000 words: 2.56e26 alternatives. A single 15-character word made of [a-z][A-Z][0-9] is 7.69e26, which is three times more.

I bet that within 10 years we'll have skipped passwords entirely. They will be replaced by some hardware thing (like a memory stick on your key chain, or an ID card with a chip) that has a biosensor. Identity theft will be back to needing physical access, which is a huge problem in cybercrime.
gwrede
1 / 5 (1) Aug 14, 2010
(Ctd.) The sentence figure above assumes one chooses at random from the set of 2000 words. In reality, people will choose sentences that make sense, which means they will follow (at least some) rules of grammar. That would drastically reduce then number of alternatives, making it orders of magnitude worse than the 15-character password!
_nigmatic10
not rated yet Aug 14, 2010
Best password in the world is the OFF button. Decrypt that!
KBK
1 / 5 (1) Aug 14, 2010
The most important part of any successful hacking has always surrounded the idea of hacking the people involved, and almost never any of the hardware.

Back in the day, when we had VAX systems and UNIX, the college admin for that system stated, "anyone who can hack this system is good enough to be a super user and will be allowed to be one".

Did I hear an invitation to the Dance? Yes I did.

So I watched his patterns.

And proceeded to make and install a fake login program on his favorite login terminal. One that looked and acted identical to the real one. One that put the logins (password and name) in a file for me when it shut itself down and opened his 'window', as per normal.

Simple enough. Old school... still the best, still the most successful -to this day.
DaveGee
5 / 5 (1) Aug 15, 2010
To those who say sentence styled passwords aren't as secure I have just one comment for you, you are predicating the ease of guessing someones password based on the supposition that said hacker somehow knows what style of password is in use.

And knowing the sad state of affairs most people currently use to pick a password no hacker is going to assume they are using a sentence of words and numbers.

Finally if the hacker somehow did know a sentence was being used all one needs to do to mix things up like take one word in the sentence and use caps for every other characte or spell a word backward or both.

Like so: I LiKe a chilled bottle of ados @ 4:00pm
CSharpner
5 / 5 (1) Aug 16, 2010
Like so: I LiKe a chilled bottle of ados @ 4:00pm


Exactly. And when you add in all the proper names, numbers, grammar, punctuation, human languages, and mispellings, a sentence is MUCH more difficult to hack. No one's saying sentences are unhackable. They're correctly stating that they're generally more difficult to hack.