Sign in with
Sign up | Sign in

Password Cracking: GPGPU-Style

Harden Up: Can We Break Your Password With Our GPUs?
By

Password Cracking: i5-2500K

The goal of a brute-force attack is to try multiple passwords in rapid succession. But modern CPUs aren't particularly well-optimized for this. While my Sandy Bridge-based workstation can process about 28 million passwords per second, it still isn't using all of its available CPU cycles. Remember that you're only guessing and checking. The above CPU utilization screenshot shows that, while clock rate is of course going to help, this application is able to take advantage of parallelism, suggesting that even more cores would help accelerate the process. 

Well, as we know, when it comes to parallelized tasks, what a CPU can sometimes do well, the ALUs on a graphics card can often do better. AMD and Nvidia had the video transcoding community convinced of this up until Intel proved a little dedicated logic on its Sandy Bridge architecture could vastly outperform a massively parallel graphics processor. But now it looks like we have another potential application for the general-purpose computing capabilities of today's GPUs.

In the past, GPGPU-based password cracking was limited to academia, where graduate students slaved away over custom code that never saw commercial implementation. That's no longer the case. Now there are two GPGPU tools available to anyone with a credit card: Parallel Password Recovery and Accent Password Recovery.

Parallel Password Recovery is solely optimized for Nvidia's CUDA parallel computing architecture. That's not to say CUDA is better than AMD's Stream initiative. However, Nvidia should be given its due credit. Nvidia's foray into general-purpose GPU computing is a much older one, and the company has given developers access to a plethora of the low-level libraries needed to explore the technology. The response from AMD has been much slower. In fact, we still see issues with getting Stream acceleration enabled in popular transcoding apps. This partially explains why the other solution, Accent Password Recovery, still seems to favor Nvidia's design. Though it recognizes CUDA and Stream, only Nvidia hardware is optimized to attack Zip 2.0 encryption.

Cracking With A GeForce GTX 460
Brute-Force Attack in Passwords Per Second
Parallel Password Recovery Accent Password Recovery
Compression: Zip
Encryption: Zip 2.0
24 111 280
516 096 000
 Compression: Zip
Encryption: AES-128
185 072
166 800
Compression: Zip
Encryption: AES-256
185 177
156 138
Compression: RAR Normal
Encryption: AES-128
34934231


And boy is there a boost in Zip 2.0 encryption! With a GeForce GTX 460, we're already pushing over 500 million passwords per second. To give you an idea of what that means, we can now crunch every possible combination of ASCII characters from a password length between one and seven characters in less than 48 hours. Moving up to an eight-character password takes about 168 days.

GeForce GTX 460
Brute-Force Attack
All ASCI Characters
Total Time for Search
Password Length Between 1 and 6 Characters Password Length Between 1 and 8 Characters
If You Push 180 000 Passwords Per Second...50 days, 20 hours
1284 years, 79 days
If You Push 24 Million Passwords Per Second...9 hours, 9 minutes
9 years, 230 days
If You Push 500 Million Passwords Per Second...26 minutes, 21 seconds
168 days, 17 hours


Of course, Zip 2.0 is rather outdated. WinZip only maintains this scheme for compatibility reasons. AES is the new "it-girl" everyone is fawning over. This scheme is much harder to parallelize, though software developers are certainly trying.

Performance is absolutely hammered once we start trying to recover a password encrypted using the AES cipher. Literally, the mouse cursor on our test system stutters along. Brute-force attacks on AES are clearly slow. To try every possible combination of ASCII characters from a password length of 1 to 7 would take over 13 years.

2 x GeForce GTX 570 SLI
Brute-Force Attack in Passwords Per Second
Parallel Password Recovery Accent Password Recovery
Compression: Zip
Encryption: Zip 2.0
45 412 290
1 492 279 088
 Compression: Zip
Encryption: AES-128
495 133
513 936
Compression: Zip
Encryption: AES-256
496 244
513 880
Compression: RAR Normal
Encryption: AES-128
13 90414 605


General-purpose GPU computing is all about parallelism, so if one card's 480 CUDA cores are good, the combined 960 cores from two cards must be better, right?

When we slap two GeForce GTX 570s together and enable SLI, Zip 2.0 encryption starts to look like Play-Doh. Thanks to optimized code, we can push 1.5 billion passwords per second. This is a bit insane. Now we've cut the search time for a one- to eight-character password using all ASCII characters down to almost two months.

Meanwhile, AES security still looks pretty good. If the password is beyond seven characters long, we'll have to spend nearly five years crunching numbers at 500 000 passwords per second.

Ask a Category Expert

Create a new thread in the Reviews comments forum about this subject

Example: Notebook, Android, SSD hard drive

Display all 92 comments.
This thread is closed for comments
Top Comments
  • 10 Hide
    ryandsouza , June 20, 2011 5:51 AM
    "Think of this as generating every single combination of numbers that can be used to solve that same Sodoku puzzle, starting from an all zeros all the way through all nines. "

    Sudoku puzzles have numbers from 1 through 9!
Other Comments
  • 1 Hide
    jeff77789 , June 20, 2011 4:33 AM
    "While it would take a longer time to find a password made up of nine or 10 passwords, it's definitely doable between a few gaming buddies. "


    9 or 10 characters?
  • 2 Hide
    jj463rd , June 20, 2011 5:04 AM
    How about adding some extended ASCII codes to a password.
  • 10 Hide
    ryandsouza , June 20, 2011 5:51 AM
    "Think of this as generating every single combination of numbers that can be used to solve that same Sodoku puzzle, starting from an all zeros all the way through all nines. "

    Sudoku puzzles have numbers from 1 through 9!
  • 3 Hide
    rpmrush , June 20, 2011 5:59 AM
    This reminds me of Bitcoin GPU crunching. 6990s are favored right now. I wonder how many were sold specifically to Bitcoin miners? I tried it with my dual 6850s but the heat was rediculous. I didn't like the stress on my hardware so I gave up mining. I'm sure it's the same with password software. Maxing out your GPUs. Great for Winter, not Summer!
  • -7 Hide
    mediv42 , June 20, 2011 6:01 AM
    I've always wondered about this: why don't they just code a delay into the decryption program, so you can't check a billion passwords a second?
  • 2 Hide
    joshyboy82 , June 20, 2011 6:03 AM
    I like the scale, but in your small example (a,b,c) you were right and wrong at the same time. Based on your configuration 6 possibilities are correct, but because you tell someone that they can use A or B or C in the password doesn't stop them from choosing aaa, therefor the combination is 9, not 6. Otherwise, interesting article.
  • 4 Hide
    acku , June 20, 2011 6:07 AM
    Quote:
    "Think of this as generating every single combination of numbers that can be used to solve that same Sodoku puzzle, starting from an all zeros all the way through all nines. "

    Sudoku puzzles have numbers from 1 through 9!


    Fixed! Sorry. I usually play Sudoku variants. :) 


    Quote:
    I like the scale, but in your small example (a,b,c) you were right and wrong at the same time. Based on your configuration 6 possibilities are correct, but because you tell someone that they can use A or B or C in the password doesn't stop them from choosing aaa, therefor the combination is 9, not 6. Otherwise, interesting article.


    I could understand that, but I left out that since I was trying to show a simple example of how permutations differ from combinations. As you pointed out, repetitions are allowed in passwords. I actually mention that in the sentence that follows in the next paragraph.
  • 1 Hide
    webdev511 , June 20, 2011 6:12 AM
    Password Haystacks Yes Steve Gibson has already covered something like this. Passphrases with upper lower number and speical are the way to go. Yes, please avoid shortcuts.
  • 5 Hide
    acku , June 20, 2011 6:15 AM
    Quote:
    I've always wondered about this: why don't they just code a delay into the decryption program, so you can't check a billion passwords a second?


    It wouldn't be easy from a design standpoint, cause now you're talking about fiddling with the design of the program.

    The easiest way to slow down the verification portion of the password authentication process is increasing the number of transformation invocations for key generation. The problem is that this slows down the performance of your machine, even if you have the correct password.

    jj463rdHow about adding some extended ASCII codes to a password.


    That assumes WinZip and WinRAR supports them. To be honest, I haven't looked into that. Though, I'm inclined to believe that neither program supports them.
  • 4 Hide
    shin0bi272 , June 20, 2011 6:59 AM
    the tables in this review are horrible... they go from lengths of time to number of passwords and theres no discernible notation when they do.
  • 8 Hide
    Mark Heath , June 20, 2011 7:26 AM
    Cracking a password? There's an app for that.

    Saw something on this elsewhere recently (http://www.zdnet.com/blog/hardware/cheap-gpus-are-rendering-strong-passwords-useless/13125)

    I've changed the password for important (tangible value) passwords such as that for my steam account to a password that now uses a few special characters, and some mixed up numbers, lower and upper case letters, totalling 18 characters. (lol)

    Now I have a few different tiers of passwords, a now replaced 8 string of letters and numbers for unimportant things a couple of years ago, a now replaced string of 15 characters for semi-important things a couple years ago (have real world information or usefulness for a potential bad guy), their 8 and 15 respectively replacements and my new 18 character string for things that have definite tangible real world value to potential nasties.

    And being only 15 I think I'm on the right track :) 

    The only thing that *really* worries me are the choice of security questions sometimes. If you're not allowed to pick your own, the answer would be easy to find on my Facebook page or similar (if I had one ;) ) Mother's maiden name? There's a Facebook page for that.
  • 3 Hide
    acku , June 20, 2011 7:37 AM
    Mark HeathCracking a password? There's an app for that.Saw something on this elsewhere recently (http://www.zdnet.com/blog/hardware/cheap-gpus-are-rendering-strong-passwords-useless/13125)I've changed the password for important (tangible value) passwords such as that for my steam account to a password that now uses a few special characters, and some mixed up numbers, lower and upper case letters, totalling 18 characters. (lol)Now I have a few different tiers of passwords, a now replaced 8 string of letters and numbers for unimportant things a couple of years ago, a now replaced string of 15 characters for semi-important things a couple years ago (have real world information or usefulness for a potential bad guy), their 8 and 15 respectively replacements and my new 18 character string for things that have definite tangible real world value to potential nasties.And being only 15 I think I'm on the right track The only thing that *really* worries me are the choice of security questions sometimes. If you're not allowed to pick your own, the answer would be easy to find on my Facebook page or similar (if I had one ) Mother's maiden name? There's a Facebook page for that.


    Actually, AccentZIP and AccentRAR are real world derivatives of the ighashgpu program that Zdnet wrote about. Ivan Golubev actually wrote the code for all three programs and we had the pleasure of working with him to write this article. The difference is that with ighashgpu, you're mainly looking at hash cracking.
  • 2 Hide
    aaron88_7 , June 20, 2011 7:40 AM
    You could buy multiple GPU's for a hefty price, or you could just use Amazon's cloud computing to do it for you....

  • 2 Hide
    aaron88_7 , June 20, 2011 7:41 AM
    Oops, link didn't show up, here it is:

    Linky Linky
  • 2 Hide
    acku , June 20, 2011 7:54 AM
    Quote:
    Oops, link didn't show up, here it is:

    Linky Linky


    Interesting. According to the article, it seems that the password recovery speed is limited by the internet connection.

    I seem to recall seeing someone mention that a pair of 590s was faster than 30000 passwords per second with Elcomsoft's GPGPU document cracker.

    Heck, assuming only 2002 SHA-1 transformations, a single GTX 460 would be faster.
  • 1 Hide
    compton , June 20, 2011 8:16 AM
    How much of a jem is this article? This is way better than trying to save 3 cents a year on your power bill. I for one would like to see the process expanded into a benchmark if possible. For one thing, it could be an excellent for CPUs where it seems like it's more optimized -- GPUs are basically limited to nVidia's CUDA, but I still think the brain trust at Toms could find a way to make an informative benchmark out password cracking.
  • 2 Hide
    kkiddu , June 20, 2011 8:51 AM
    What if you have TRANSLTR?
  • 2 Hide
    Hupiscratch , June 20, 2011 9:07 AM
    A next good article would be a search for the best decryption software. Let the decryption roundup begins!
  • 1 Hide
    Anonymous , June 20, 2011 9:32 AM
    Interesting article. I personally use a fairly simple way to use one different password for each website / service following an easy to remember pattern. The method is described here:

    http://passwordadvisor.com/TipsUsers.aspx

    Would also be interesting to see if Sandy Bridge AES instructions helps on brute force.
  • -3 Hide
    srgess , June 20, 2011 10:06 AM
    Im surprise they haven't tested Elcom solution, they are faster for recovery password with any competition with some process. You can put make a network resource. So lets say you have a lots of money and put 10-20 4 SLI GTX 590 computer or Tesla computer available resource to get a super computer , password cracking will pass from days to second. Imagine Top supercomputer in the world and its just a beginning. Soon we gonna have to have password with 20 + alpha numeric and special character. Or data crash after 10 attempt.
Display more comments