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

Page 3 - Seeking answers? Join the Tom's Hardware community: where nearly two million members share solutions and discuss the latest tech.
Status
Not open for further replies.
[citation][nom]gti88[/nom]clonazepam, AFAIC, there's no tool for 7z password recovery. Thus, if you use 7z, your info is very secure.[/citation]

Yeah that's what my research has suggested. It's only a matter of time now and probably sooner than later.
 
G

Guest

Guest
So... What if we put this through the new japanese 8-petaflop computer? Are we looking at a 4-million-fold decrease in the amount of time it takes? Or what if the NSA has 100000 GPUs churning away at your password? Wouldn't that take just 48 seconds to crack your 8-character password?
 

alidan

Splendid
Aug 5, 2009
5,303
0
25,780
i have a question, why does password cracking slow down?
i mean my computer can theoretically handle hundreds of millions of passwords a second (i use brute force in other applications)

so, why does it slow down, shouldnt i be able to check the passwords as fast as i create them?

and i have reason for this, i have and archive thats passworded that i need cracked.
 

acku

Distinguished
Sep 6, 2010
559
0
18,980
[citation][nom]alidan[/nom]i have a question, why does password cracking slow down? i mean my computer can theoretically handle hundreds of millions of passwords a second (i use brute force in other applications) so, why does it slow down, shouldnt i be able to check the passwords as fast as i create them? and i have reason for this, i have and archive thats passworded that i need cracked.[/citation]

Did you read page 8?
 

nmathew

Distinguished
Dec 9, 2002
27
0
18,530
[citation][nom]acku[/nom]Yes but that's the same as having an alphabet with 300k letters and a password with only two characters. It's not the length of the password that matters, it's password strength. That's why it's easy to defeat a dictionary-based password. A word is essentially treated as a letter. "PasswordPasswordPassword" takes the same amount of time to check as "123". It's not the checking that's slow, it's the SHA-1 transformations. For example, "tobeornottobe" is made up of 6 words. The SHA-1 transformations (for WinZip AES-256) take the same amount of time to generate a decryption key made up of 6 letters such as "123456." Each entry in the master dictionary ("to" "be" "or" "not" "to" "be") that you're checking passwords from is a static variable. So when you're dealing with words, the computer treats them the same as letters.[/citation]

Sure, if the attacker knows we're limited to dictionary type words, it can be hacked via a dictionary attack, but the gross number of possible words makes for a decent search space. If my math is correct, lets assume that I have a pass phrase like your example. That's 6 "characters," but how many possible "characters" are there? If our words are limited to a list of the 100 most common words, and assume the attacker knows this, I get a possible number of passphrases as 100^6, which is 1 trillion. That's between a 8 and 9 character long all lowercase password in difficulty to brute force. Increase the rarity of the words to the 300 most common, and that number scales to only 729 trillion, but it's easy to remember, and better than a lower case and upper case 8 character password. Use rarer words or the much mocked l33t conversion to increase to 600 possible "words" and we're looking at ~46.5 quadtrillion, which is better than a truly random 9 character lower case + upper case + number password.

Plus, it's trivial to spoil such a passphrase to make dictionary attacks unhelpful. That, as I understand it, is the value of passphrases. They are long, easy to remember, and pretty easy to make immune to non brute attack methods. "22Tob3ornot2be?" doesn't have the greatest entropy, but it has enough. It's not nearly has entropic as a truly random 15 character string, but it can be remembered. Good luck breaking/guessing it. If we get slightly clever, and construct something containing a shot but nonsense string(traditional 4 character password), it becomes unassailable and something I'd be comfortable using for everything short of nuclear launch keys. I like beer, could become "I likIlb!e b33r!"
 

acku

Distinguished
Sep 6, 2010
559
0
18,980
[citation][nom]nmathew[/nom]Sure, if the attacker knows we're limited to dictionary type words, it can be hacked via a dictionary attack, but the gross number of possible words makes for a decent search space. If my math is correct, lets assume that I have a pass phrase like your example. That's 6 "characters," but how many possible "characters" are there? If our words are limited to a list of the 100 most common words, and assume the attacker knows this, I get a possible number of passphrases as 100^6, which is 1 trillion. That's between a 8 and 9 character long all lowercase password in difficulty to brute force. Increase the rarity of the words to the 300 most common, and that number scales to only 729 trillion, but it's easy to remember, and better than a lower case and upper case 8 character password. Use rarer words or the much mocked l33t conversion to increase to 600 possible "words" and we're looking at ~46.5 quadtrillion, which is better than a truly random 9 character lower case + upper case + number password. Plus, it's trivial to spoil such a passphrase to make dictionary attacks unhelpful. That, as I understand it, is the value of passphrases. They are long, easy to remember, and pretty easy to make immune to non brute attack methods. "22Tob3ornot2be?" doesn't have the greatest entropy, but it has enough. It's not nearly has entropic as a truly random 15 character string, but it can be remembered. Good luck breaking/guessing it. If we get slightly clever, and construct something containing a shot but nonsense string(traditional 4 character password), it becomes unassailable and something I'd be comfortable using for everything short of nuclear launch keys. I like beer, could become "I likIlb!e b33r!"[/citation]

Very true. Most people don't put that much thought into passwords, though.

The number of common words in the english language is far less than 100 million (300 million already includes many obscure words). If you include pseudowords like pa55word, then you're still looking at far fewer variations. Conversational english includes less than 10,000 unique words (what you use on a day to day basis). In the end, it's not just the password space that matters, it's also about the speed, which is what we're trying to show here. 3 billion passwords per second is nothing to scoff at.
 

mediv42

Distinguished
Jul 25, 2008
69
0
18,630
[citation][nom]acku[/nom]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.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.[/citation]
I mean winzip programmers could add a delay, not the user. winzip programmers (seems to me) could have a "read password, wait one second, check password" call in winzip - but someone else clarified later that the cracking programs are not actually checking the password by entering it.
 

nmathew

Distinguished
Dec 9, 2002
27
0
18,530
[citation][nom]acku[/nom]Very true. Most people don't put that much thought into passwords, though. The number of common words in the english language is far less than 100 million (300 million already includes many obscure words). If you include pseudowords like pa55word, then you're still looking at far fewer variations. Conversational english includes less than 10,000 unique words (what you use on a day to day basis). In the end, it's not just the password space that matters, it's also about the speed, which is what we're trying to show here. 3 billion passwords per second is nothing to scoff at.[/citation]


I had misread your post as suggesting that using a straight passphrase was inherently very weak, and I decided to run some numbers. I was surprised athow wel it started, and dissapointed in how the search space grew with more allowed words. Sadly, people didn't start using things like, "I hate22 folding laundry." as their passwords, and now we're stuck with most people having very weak, and rainbow tabletastic passwords.
 
G

Guest

Guest
Using a long but easy to remember password is the best way to avoid weakness due to brute force cracking without having to remember crazy combinations of random characters. 69BiteMyShinyMetalPassword.com01 IfYouCanReadThisI'mInTrouble001 etc...

 

kanaida

Distinguished
Mar 29, 2010
61
0
18,630
Passwords should not be generated by humans, and you can't protect your information when it's digital. If you can see it, hear it, or interact with it on your pc in any way shape or form, you can steal it.

Think of what a "program" is. It's something that was programmed. it can read, write, and be read. It's in memory. Hardware with encoded values you say?, well guess what has to "read" that key. a PROGRAM, that you can CHANGE, intercept, modify, emulate. You can make a program pretend it's a hardware key, or to read a key's value and pretend to be the key.

The only way to keep things safe, is for them to not be designed by a human. Only let humans use them, and not let them program in any way. In the real world, this isn't possible.

So next time you want to keep something safe. Follow these rules:
1) Keep it in your mind or physically safe if it's important, or don't use the internet.
2) If you do use the internet, Don't ever put even a hint of real information when joining any site. Never use the same password in more than a single site. Always assume that resource that you read, write, access can be known by anyone along with it's history most of the time.

 
G

Guest

Guest
Interesting article, goes to show that if people simply used common sense they could secure their data much better. Encryption is really the only way to do this effectively, along with using a long password. It's amazing how many people think that simply having a password on their computer for windows will keep their data secure.

I had a friend who used to store his bank statements in an unencrypted folder on his windows machine thinking that his 13 character windows password was keeping it safe. To convince him to start using TrueCrypt I booted up linux from a live CD and copied his bank folder to a flash drive then opened it on my computer completely bypassing his password. People are clueless.
 

acku

Distinguished
Sep 6, 2010
559
0
18,980


I want to thank @jeffunit for pointing this out earlier, and I suggest that you read his post. In a nutshell, you're still talking about something different. You're examining unsalted performance. I understand that everyone is interested in commenting on security, but I think it's important that we put information into context.

[strike]The results on your website are limited in scope to precomputed hash tables.[/strike] That's very different from what we're looking at in this article. For every brute-force variation from "0" to "asdklfjalsdfjlka;dfjl*(&*%^&$^&%" we have to perform thousands of SHA-1 transformation invocations per each attempt in order to generate a key (see page 8 of the article).

Your results are more of an abstract look at performance. We're looking at an applied concept of performance. Think about pure vs. applied math. Just because the 5770 does 3.3 billion passwords per second, that doesn't mean it actually does 3.3 billion passwords per second. In the real-world, you're trying to decrypt salted passwords.

ighashgpu was created by Ivan Golubev, who runs a great blog on security. We had the pleasure of working with Ivan on this article because he also wrote the code for Accent Zip and Accent RAR. He's a great guy and a great source of knowledge. I suggest that if you have more questions on how hash, rainbow tables, transformation invocations, etc.. all work together, you head over to his blog. He's always open to answering questions.

FYI: I didn't mention this in the article, because we would be diving way too deep into engineering, but architecture matters. Even if you take into account the 1:1 ratio of core clock and shader clocks on AMD, it's not an easy comparison to make with Nvidia cards. I had a long discussion with Ivan on why this is. Frankly, the 6xxx ATIs aren't that impressive as 5xxx were compared to 4xxx. They changed architecture to VLIW4 from VLIW5 but ALU count and frequency aren't that differs making 6990 only 15-20% faster than 5970 while eating (the same) 15-20% more power.
 

acku

Distinguished
Sep 6, 2010
559
0
18,980
I'm going to say only one thing: QuickSync can't compare to x264 quality. And x264 is aiming at accelerating some things with CUDA/OpenCL.

Please try to stay on topic. QuickSync can compare to x264 and we've had long discussions with the codec benchmarkers in Russia on this subject as well as MainConcept and others, but we've already covered this in length in our GPGPU video transcoding article. The purpose of this discussion is encryption.
 

acku

Distinguished
Sep 6, 2010
559
0
18,980
[citation][nom]fir_ser[/nom]Good review, but I hoped to see a test to professional GPGPUs such as Nvidia’s Tesla cards.[/citation]

According to Ivan Golubev (see my other posts in this thread if you don't know who he is)

"Tesla cards will be slower than even GTX570/580, estimations available here: http://golubev.com/gpuest.htm

In a nutshell, Teslas were designed for complex scientific calculations, main features are fast double precision floating point (1/2 of single precision while desktop GeForce having 1/8), ECC support, 3/6Gb onboard RAM. None of these features needed for AES/MD5/SHA-1/etc. To provide 24/7 stability NVIDIA down clocking Tesla GPUs, thus they are slower than desktop GeForces."
 

dvijaydev46

Distinguished
Jun 12, 2008
19
0
18,510
[citation][nom]acku[/nom]The results on your website are limited in scope to precomputed hash tables. That's very different from what we're looking at in this article. For every brute-force variation from "0" to "asdklfjalsdfjlka;dfjl*(&*%^&$^&%" we have to perform thousands of SHA-1 transformation invocations per each attempt in order to generate a key (see page 8 of the article).[/citation]
Well, I was not talking about precomputed tables in my post, but that's purely on bruteforcing. Yes I was talking about unsalted performance but most of us are still using Windows and the OS is protected by NTLM and not salted hashes, which is the reason why I took NTLM to show how fast GPUs are fast for password cracking.

[citation][nom]acku[/nom]Just because the 5770 does 3.3 billion passwords per second, that doesn't mean it actually does 3.3 billion passwords per second. In the real-world, you're trying to decrypt salted passwords.[/citation]
Sorry I don't get what you say. Do you mean that a GPU isn't searching 3.3 billion passwords per second?
 

acku

Distinguished
Sep 6, 2010
559
0
18,980


You're right, I didn't read your full blog post. However, you're still looking at limited scope of GPGPU performance, and it's not a realistic performance benchmark. Consider that transformation invocations account for 99% the overhead in brute-force attacks. That's why NTLM is insufficient to show the practical speed of GPU brute-force attacks. Performance is overstated.

If you really want to dive into Windows security, you should know that don't even need to crack the hash. You can implement a "PTH" attack, but if you're a security nut, you already know this. (If you have to ask what PTH means, you might need to read up more on NTLM and LM.) Hell, no one serious would use an unsalted hash to protect data. The idea that Windows passwords are "secure" is almost laughable. You just need to plug the hard drive into another computer. It's really as simple as that if you need to retrieve information. Provided the user isn't relying on server side authentication, you could just login as another user or a guest.

Basic point, unsalted performance is interesting, but salted performance is a better indicator of real-world GPU brute-force capabilities.
 

Mr_Man

Distinguished
Feb 17, 2008
202
0
18,680
I'm suddenly very proud of my 17- to 22-character passwords.
Great article, Tom's! Very enjoyable and informative to read.
 

misiu_mp

Distinguished
Dec 12, 2006
147
0
18,680
Nvidias are strong at double-precision floating point computations at the expense of fewer cores.
Radeons have many more cores but they are weaker at floating point per core. This is the kind of computations many scientific applications use, but hash cracking is all fixed-point. Now fixed-point performance is more comparable between geforces and radeons per core, so radeons with many more cores are much faster at it.
In games most used are single-precision floating point computations, which was what cards from both manufacturers has been most optimised for so far. Nvidias Tesla changes that somewhat with its enhanced double-precision floating point capability.
Still, since Radeons are so much faster at hashing, I find the lack of radeon tests in this article peculiar.
 
Status
Not open for further replies.