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!"
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: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:Umm... (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.
Re:Why are GPUs faster? (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: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.
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:This is why you use encryption programs... (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 unreasonable to blind-type something like that into a password field for someone with a reasonable amount of typing skill.
The main trouble is that people get the idea that passwords should be as compact as possible. This is partially due to using the term "password" instead of "passphrase", and partly due to stupid, stupid systems which impose a maximum length limit on passwords.