Brute-Force Password Cracking With GPUs 128
An anonymous reader writes "We all know that brute-force attacks with a CPU are slow, but GPUs are another story. Tom's Hardware has an interesting article up on WinZip and WinRAR encryption strength, where they attempt to crack passwords with Nvidia and AMD graphic cards. Some of their results are really fast — in the billions of passwords per second — and that's only with two GTX 570s!"
Umm... (Score:1)
Didn't we hear about this a week or two ago?
Re: (Score:2)
Re: (Score:2)
Yes, it was the Tom's Hardware article... the link was marked as visited and I generally avoid TH....
Re: (Score:2)
It's been known for quite some time, but apparently the one who submitted it and the editor who greenlit it didn't get the memo.
Re: (Score:2)
It's been known for quite some time, but apparently the one who submitted it and the editor who greenlit it didn't get the memo.
Did they crack the memo?
Re: (Score:1)
Re: (Score:2)
Wow you really know nothing about encryption. Sigh.. Everyone is an expert. Zdnet looked at ighashgpu that's unsalted password decryption when you already have a precomputed hash table. TH looked at salted password decryption where you have to perform a SHA-1 transformation invocation thousands of times per every password attempt.
Experts -- What do they know?
Re: (Score:2)
> Experts -- What do they know?
Enough to tell you in excruciating detail why they were wrong! :-)
Re:Umm... (Score:4, Informative)
Even though it's a dupe, why are GPUs so much faster than CPUs at this? It doesn't seem like they have any more power, is the architecture that different from CPUs? Is it an issue where you can basically dedicate all resources (GPUs plus VRAM) to the one task?
Re: (Score:2)
Re: (Score:2)
Re: (Score:1)
Re: (Score:1)
Re: (Score:2)
And based on the replies you've gotten, maybe I read wrong?
Depends on what types of number crunching you're doing. If every step depends on the previous step then you won't be able to exploit the hundreds of cores that makes up even a cheap GPU these days by running them in parallel. If, on the other hand, your task consists of subtasks which can be easily done simultaneously like password hashing (just send a separate password to be hashed to all cores at once) or n-body calculations you will experience huge speedups. If you do a lot of matrix (vector) operations
Re: (Score:1, Insightful)
Does anyone else remember the days when slashdot readers were technical? This discussion is fucking painful.
Re: (Score:1)
Re: (Score:2)
>Been around since ~1997 too. Perhaps technical discussions went on here some time before that?
I have read comments to the same effect in other discussions (can't find one at the moment).
I'll admit I noticed a sort of dilution of the technical level of late, but it may be the price to pay for popularity. I followed some very interesting discussions here, and recently.
Besides, who could follow high level technical discussions about so many subjects? For instance, the posts below yours, that quickly explai
Re: (Score:2, Insightful)
Does anyone remember when you could come on this website and have a discussion on this website and learn about new concepts and ideas? Don't be so bitter, even you were a noob at some point in your life.
Re: (Score:2)
> Does anyone else remember the days when slashdot readers
> were technical? This discussion is fucking painful.
Well, in the enterprising tech spirit feel free to establish: :-)
"Slashfork.org - News for real Nerds, Stuff that used to matter!"
Re:Umm... (Score:5, Informative)
CPUs and GPUs have very different focuses. A CPU is designed to take a single piece of data, run an operation on it, then grab a different piece of data, and run another operation on it. (There's a whole bunch of optimizations for running the same operation on different bits of data, and different operations on the same bit of data, but those are largely optimizations, and only apply to relatively small scales). A GPU is designed to take a butt-load (technical term) of data, and perform the same operation on all that data, followed by another operation on that same butt-load of data.
When you are cracking passwords, you have a bunch of potential passwords you want to try. On a CPU, you are stuck with hashing between 1 and maybe a dozen simultaneously. On a GPU, you could potentially run a few million simultaneously. Each step on the GPU would be slower, but your total output of hashed passwords would be much higher.
Re: (Score:2)
Thanks. Would the GPU have a single, multi-stage pipeline (with apparently a lot more stages than a CPU), or does it actually have multple pipelines? Or maybe just a ton of small cores? I'm confused about where the parallelity (technical term) actually gets implemented in the hardware.
Re: (Score:1)
Recent GPUs have hundreds of relatively simple cores. As you can see here [nvidia.co.uk].
Re: (Score:2)
Of course, a GPU would fail spectacularly at a lot of things. They'd probably
Re: (Score:2)
a Radeon HD 6990 has, if my data is correct, 3072 cores running at 830mHz
That is re-goddamn-diculous. Thanks, I guess that answers my question.
Re: (Score:3, Informative)
GPUs are much more specialized than CPUs. CPUs can only do a few things in parallel depending on the number of cores available in the CPU chip (ie 4). GPUs have a magnitude more processing paths than CPUs, the GTX 570 mentioned has 480 cores. That's what's being leveraged here, it's not the resources or power, it's the number of parallel processing paths.
Slashdot has no credibility on this topic (Score:1)
Didn't we hear about this a week or two ago?
It was a slightly different entry in /.'s series on "passwords are dead! oh noes!", except it was on brute forcing hashed passwords. It makes the same fundamental mistake that comments on that post pointed out _repeatedly_.
This is on brute forcing data encrypted with a symmetric cipher whose key is derived from a password. Yes, if you naively translate the password into a key, you go from a 128 or 256-bit keyspace to about the size of the dictionary.
Crypto 101: if you're deriving a crypto key from a passwor
Re: (Score:2)
I wonder (Score:5, Funny)
Re: (Score:2)
Isn't that the point of the 'recent' tab? To identify dupes and vote them down?
Re: (Score:2)
More likely with enough GPU's they'll come up with perfect summaries.
Password hacking process could be used to create completely new content - even data like images. If you can make billions of attacks per second the amount of coherent information must eventually be high enough.
Re: (Score:1)
old news (Score:2, Insightful)
this has been known since 2009....
Irrelevant (Score:2)
Zip and RAR encryption has never been trustworthy. Let me know when they can crack GPG.
Re: (Score:2)
The quoted billion passwords per second was for ancient Zip 2.0 encryption.
The actual numbers for modern RAR encryption (from TFA) is 14605/sec.
That's an average of 4 years for a random 7 character alphanumeric password, or 200 years for a 8 character one.
Re: (Score:2)
Alphanumeric would be 62 different characters.
going from seconds to minutes to hours to days to years for a 7 character password....
62 ** 7 / 14605.0 / 60.0 / 60.0 / 24.0 / 365.0 results in 7.6459888127245952
So its actually around 7.7 years but thats with just one computer.
If you had 7.7 computers, it would take a year.
If you got a shitload of time on Amazon (which I hear has GPU rigs available for rent) you could shrink that time way down.
WinRar question... (Score:2)
I've been told before that WinRar's encryption wasn't much to crow about, but this article says it's 128-AES. So.. which is it? Is it fairly secure (provided it is used properly...) or does it still have a major weakness that makes it easy to get into?
Re: (Score:2)
Right, but that's not what I'm asking. I'll be more specific: Is using WinRar with a 8+ character password reasonably secure or does it have another vulnerability that weakens it? This article suggests that it's pretty darned secure. BUT... this is a benchmark article, not a strength of security exercise.
This is why you use encryption programs... (Score:4, Interesting)
WinZIP and WinRAR have effective encryption, but one needs to have an effective passphrase with it.
Ideally, the best way to encrypt stuff is with not just a passphrase, either with random keyfile for symmetric encryption, or use public key crypto (although PK crypto has its own caveats). This way, there is no brute-forcable passphrase to guess, so an attacker has to deal with the complete keyspace of an encryption algorithm, and not just what people type in.
Re: (Score:2)
Re: (Score:2)
There are multiple ways to brute force. One is just finding the known subset of the keyspace (what people can type in), and running scans through that. Another is using dictionaries (ye old Crack). Of course, using dictionaries, then scanning the keyspace is useful too.
Dictionaries are still useful even though people's passwords tend to more than just a word these days. A lot of people use two words and a character, so that is far more gussable than trying to just brute force every single option in a 10
Re: (Score:2)
Specifically: 10,000 * 10,000 * 90 - assuming that both words are in the set of 10,000 commonly used words. If you assume uncommon words are in use, you may have to look at 200-300k words for each position unless you know that they stuck to the sh
Re: (Score:3)
Typically bruteforcing refers to exhaustively searching a reduced dictionary... bruteforcing 62^8 (alphanumeric, mixed case, a reasonable metric for a 'decent' password) might be easier with a GPU investment, bruteforcing 256^32 (let's assume a 256bit keyspace) is not.
Re: (Score:2)
I think you meant 2^256 in your second example. Technically, bruteforcing that probably is easier with a GPU, kind of like how you can get to Alpha Centauri faster in a galleon than by walking.
Re: (Score:2)
256^32 == 2^256...
Re: (Score:1)
Brute force is synonymous with checking the keyspace against a dictionary.
Architecture allows for the GPU do to this much more quickly, with the correct software. It is, however, still checking against a dictionary. Parent mentions encrypting what has already been encrypted (note the use of the word symmetrical), so that you must crack the whole keyspace, as opposed to the area of the encrypted file that you know contains the reversible hash (or, as opposed to just getti
Re:This is why you use encryption programs... (Score:5, Informative)
I was under the impression that brute forcing did exactly that. They're not using a dictionary. They're taking advantage of the GPU processing power.
For this kind of encryption, the archive password is converted into a key. This is done because remembering a large key is hard, but remembering a password is not.
However, this kind of conversion is not remotely secure. With around 70 typable characters ("a-z", "A-Z", "0-9", a few symbols, etc.) the number of possible keys for keylength l is around 70^l . If we use a secure crypto algorithm, say, AES-256, then we would encrypt the archive with a 256-bit key. Something that uses a password for encryption does so by permuting the password into a key, typically through some combination of hashing, concatenation, and salting. This process deterministically maps the relatively-small ASCII password space to a 256-bit key space. So even though you're using a secure-sized 256-bit key, there are still only (at most) 70^l possible keys, since each key must be generated from a password.
Now, with AES-256, there are 2^256 possible keys. While brute-forcing the 256-bit keyspace is considered hard (that works out to about 1 * 10^77 possible keys), brute-forcing the possible plaintext passwords that could have generated the key is significantly easier (a 10-character password has only 2 * 10^18 possibilities).
So back to what the OP said, while the crypto and keysize of the underlying cryptography are secure (in this example, AES-256), the keyspace is inherently limited since it has to be derived from a much-smaller set of passwords. The OP is spot-on ... if you really want to encrypt something securely, you have to use a much larger keyspace, which, in this case, means generating a complete 256-bit key rather than deriving one from an ASCII password. This article shows that password-derived keys are not secure.
Re: (Score:2, Informative)
I find it strange that you discount using a longer passphrase without bothering to calculate how long it would need to be. Assuming 70 typeable characters, getting 2^256 possible keys only requires 256*ln(2)/ln(70) ~ 42 characters assuming an equal distribution. (english text actually has much less entropy than an ideal even distribution of characters, but we'll ignore that for the time being)
As an example, "This is a fourty two character passphrase!" is a fourty two character passphrase. It's not unreasona
Re: (Score:2)
Except that your passphrase is not 80^42 (8.5e79 or about 265 bits) possibles. It's more like (10,000^7) * 2 * 12 (2.4e29 or 97.6 bits) because all of the words are fairly common ones and probably exist in a shortened dictionary of the 10,000 most common words. They're also all
Re: (Score:2)
So even though you're using a secure-sized 256-bit key, there are still only (at most) 70^l possible keys, since each key must be generated from a password.
Maybe I'm just not thinking hard enough about this but it seems very trivial to me to create a password/passphrase hashing algorithm that wouldn't be limited as you defined. Yes, there may be about 70 possible characters that can be typed - but their placement in the password (1st, 4th or 17th character) can also used to increase the possible keyspace.
Additionally, the length of the key (256-bits) and the length of the passwords do not have to be identical - the password can be much longer and thus can ha
Re: (Score:3)
I don't know where your delusion of 70 "typable" keys comes from. Maybe from being egocentric, and thinking ASCII-only. PROTIP: http://www.neo-layout.org/ [neo-layout.org]
Good luck scanning through way more Unicode key combinations
Also: what stops a hacker from trying out passwords on the keyfile instead of the encrypted file?
It's an example to demonstrate how much more limited the typable keyspace is than an unconstrained binary keyspace, nothing more. I think you're quite out of line throwing words like "egocentric" around because an arbitrary example used QWERTY/ASCII.
However, say you did have 1024 typable characters. A random 10-character password with such a keyboard layout would yield only about (at most) 1024 ^ 10 = possible combinations, still well short of the example binary keyspace.
We're getting a bit off-topic, but
Re: (Score:2)
However, say you did have 1024 typable characters. A random 10-character password with such a keyboard layout would yield only about (at most) 1024 ^ 10 = possible combinations, still well short of the example binary keyspace.
And I fail at HTML... 1024 ^ 10 ~= 1 * 10^31.
Re: (Score:1)
Commonsense PW Acceptance Limits? (Score:1)
So why don't more systems lock you out after 3 tries for another 10 minutes or an hour?
That would deny brute force attacks.
Re: (Score:2)
Not much use if you have a password protected .zip or .doc file as you aren't using WinZip or MS Word to check the password.
Re: (Score:1)
The article (or even the summary) is not talking about repeatedly attempting to log in to a system. It's talking about encrypted files.
Re: (Score:2)
Re: (Score:2)
So why don't more systems lock you out after 3 tries for another 10 minutes or an hour?
That would deny brute force attacks.
Copy the file of passwords to your local machine, then hash against that file using software than intentionally does not implement such a delay.
Heck if you have access to backups, or vmware images, or backups of vmware images, just copy and NOP out the delay code...
Re: (Score:2)
How am I going to enforce that on an encrypted file possessed by someone who is trying to decrypt it against my wishes?
Why none of this matters! (Score:2)
For most intents and purposes this is not that news worthy. In order to get processing performance like this you need a system that can also answer billions of password guesses per second. So keeping it simple, you need to get said database, make it function on/in a system/environment that can handle and that will allow this much activity for all those guesses.
ergo, someone has to jack yo shit before they can start guessing your password which may be more difficult than just trying to guess that password
Re: (Score:1)
Re: (Score:1)
Bitcoin currently has no passwords. If you get their wallet.dat, it's all over.
Re: (Score:2)
Why are GPUs faster? (Score:2)
I gotta ask why GPUs are faster? And because they are faster, why aren't CPUs using methods and techniques similar to GPUs for getting certain things done? I remember the days of the "math coprocessor" that the math processor was used to help speed things up by performing math on-chip rather than by using subroutines in software.
I was always under the impression that GPU means graphics processor unit, not "Guessing Passwords Unit."
Re: (Score:2)
These days there are GPGPUs with GP standing for "General Purpose". They're not only used for displaying graphics anymore but for general-purpose vector calculations. GPUs are faster *for vector calculations* because most of the chip consists of arithmetic units. In return, GPUs are much, much worse at pretty much everything else, such as branching. Don't try to run if-statements on GPUs.
Re: (Score:1)
My naive interpretation of this: http://www.nvidia.com/object/GPU_Computing.html [nvidia.com]
In effect, having a good,recent GPU is the equivalent of having hundreds of CPUs all in one single chip. Since password guessing is a task that can be divided easily, the GPU is 100x faster than a regular CPU, and it is very efficient at number-crunching.
Re: (Score:3, Informative)
In layman terms: The CPU is like a truck, the GPU like a Ferrari
One goes faster, but can't run on all kinds of terrain (data)
Re:Why are GPUs faster? (Score:5, Insightful)
Re: (Score:2)
This analogy works (if you think the GPU is around 500MHz/1GHz and the CPU is at 3GHz)
But I prefer the other way because for example, GPUs would probably suck at SQL, or parsing XML, whereas the CPU can just 'deals with it'
Of course, analogies are never perfect
Re: (Score:2)
But the important thing. Did they crack the Wikileaks insurance file or not?
Re: (Score:2)
Since you don't know the plaintext, it's impossible, even by bruteforce
In the case of Zip, you know some metadata (like zip headers) and I guess it uses known data from file formats or checksums
One is AES->Zip->Data, wikileaks is AES->??
Re: (Score:2)
Since you don't know the plaintext, it's impossible, even by bruteforce
Not really. For example we might assume that the original file is a .txt file and that the document is in English. Based on this we could perform a sample decrypt followed by a quick (relatively speaking) analysis looking for characters in the ASCII printable range. If the key is wrong the result should appear random. At the same time we can check for non-varying bytes that occur at certain positions in word documents, or for image file format headers. Most file formats don't try to disguise themselves
Re: (Score:2)
Interesting, that's what I thought.
So the most secure thing to do would be having random bytes at the beginning of the AES file
Re: (Score:3)
Re: (Score:2)
Yes, yes... (Score:1)
"Omg, what am I going to do about my eight char password I use half across the Internets?"
Well...
One could print out a passwordcard [passwordcard.org].
Then one might start using passwordmaker [passwordmaker.org], to whatever phone/OS one fancy. By which time one (sh/c)ould check if ones passwords are long enough [lockdown.co.uk] and while this "one" is at it, have a look at these tricks [passwordmaker.org] from an almost "tl;dr-ish" list. Now, apply elbow grease and a bit of go figure. "Problem solved? Moving on?"
Oh, who am I kidding? Then all those (fear) mongering polemics would
Re: (Score:2)
A 15 char pass phrase is much more secure than an 8 char password. All it takes is a nonsensical pass-phrase and a light peppering of special chars and no one could break it without having a few dedicated power plants to supply electricity to their GPU cluster.
$5 wrench would work better.
Re: (Score:2)
Oh wow. Imagine what a Beowulf cluster of $5 wrenches could accomplish!
Real encryption (Score:2)
With the recent MTGox compromise, I've been looking at a better password system. It looks like one way to go is to use a program like password safe or keesafe to generate unique passwords per website. However, I'm curious as to how resistant these master files are to GPU attacks. GPUs basically sliced through the MTGox MD5 hashes like butter. How long would it take a higher-end distributed cluster to break a Password Safe master file? It's blowfish encrypted I believe.
7z (Score:1)
Which tool can crack 7zip passwords?
Relevance?! Which client/server can handle that?! (Score:2)
Where is the practical relevance?!
If done over a network I guess it would generate a kind of traffic no server could handle.
In forensics, yes. But where otherwise?!
Re: (Score:1)
Re: (Score:2)
When you design a security system that relies on passwords - you need to make the assumption that the attacker has either the password hash or the binary file that is being protected. In which case, they are not subject to any delays or lockouts and they can ramp up the brute-force rate to whatever they can afford. They may even have access to a 10k machine botnet, in which case their resources will far exceed your own. So you should also make the assumption that the
Re: (Score:1)
Using GPUs to crack passwords isn't going about it the same way that you are thinking. There are no network connections to a server as the GPUs wouldn't be any faster at that than a normal CPU. What they are doing is getting a copy of the encrypted passwords in some way. Either from a workstation with cached passwords or gaining some amount of access to system to get a hold of the encrypted passwords. Then they run the cracking software against that local file using the GPUs to do the heavy lifting.
Back
Password length matters (Score:4, Informative)
Things to remember - password difficulty is based on x^y, where x is the number of possible characters and y is the password length. Increasing password length is *always* going to be more effective than increasing the mix of characters (indeed the point of a dictionary attack is to reduce can be thought of as reducing 96^8 8 character passwords to a mere 250,000^1).
Each additional alphanumeric character increases the search space by a factor of 62 - a two word password is still only 250,000^2, a password of ten random lowercase characters is 26^10, a *much* larger number.
Moores law says processing power doubles ~18 months. Every new lowercase character extends life of your password almost 12 years before new hardware can decrypt it as quickly as today's hardware. 23 1/2 if you use upper and lowercase.
Don't panic.
Re: (Score:1)
Assuming an alphanumeric search space is naive. There's actually (26 *2) + (10 * 2) + (11*2) -> 94 characters that can be typed on a US PC keyboard, far more if you add all the composable characters (over 30k). For example the default settings for the (not-quite) standard mkpasswd utility generates a password with four lowercase characters, two uppercase characters, two numbers, and one typable symbol. That's not quite 94^9 -> 572,994,802,228,616,704 or 5.73E+17 permutations, not quite because you can
Re: (Score:2)
Yes but the point is that (barring quantum machines) adding length (y) increases the permutations (and thus the size of the search space) at a far greater speed than adding characters (x). It also happens to be much for a human being to do rather than pulling out esoteric unicode characters that may or may not be legal characters in a given system.
Pug
Re: (Score:2)
Most people tend to pick words that are familiar to them, that they probably use in everyday speech or hear regularly. Not many will crack open a random dictionary or book and pull a word out at random from the other 97% of the word list.
Now, identifying the 3% most commonly used words? That's a bit more of a guessing game.
In Soviet Russia (Score:1)
Re: (Score:2)
is there some sort of fundamental hardware/architecture difference that makes them better suited to this task?
This. GPUs have dozens of cores optimized for parallel computation.
Re: (Score:2)
...really? Some of us play games on the GPUs, too. Or *gasp* do actual work with them! And the more expensive ones are faster. Because that's how technology works. No, not everyone needs an F1 car. Most people would be fine with a Corolla. And the cheaper cards generally give you much more value for your money. But if you can't see where some people would be more concerned about absolute performance than pure economy, then you're stupid.
This is not a slashvertisement. This is simply tech journalism. Or is C
Re: (Score:2)