Slashdot Mirror
Brute-Force Password Cracking With GPUs
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!"
If we throw enough GPUs at it, if we could detect dupes on Slashdot?
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.
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.
More like, a GPU is a freight train moving at 15 MPH, a CPU is a Ferarri doing 120MPH, and you need to transport a warehouse of boxes across country.