Cracking passwords

Recently, Robert Graham, CEO of Errata Security, posted a blog in which he stated that “today’s CPUs can ‘crack’ passwords eight times fast than they can ‘check’ the passwords.” And we’re not even talking about dual-core machines, just your plain vanilla PC desktop. Graham, who last summer hacked someone’s Gmail account before a live Black Hat audience, is used to making provocative statements. And, as with the Gmail hack, Graham’s not afraid to back these statements up with data.

Passwords
When you type in a password, the computer converts whatever you type into a hash. A hash is a unique algorithmic value that is then stored on your computer (or Web server). “Computers have been designed this way for the last 20 years,” said Graham, “so that when hackers break into your computers they can not just easily steal your passwords. All they can steal is that cryptographic information.” Typically, passwords are stored in MD4 hash, says Graham.

“My post was that when hashes are used typically, when they’re used normally, they’re only used for one file or one hash, or one object that’s being hashed, When the hacker can use a hash, though, they’re trying to crack it; they’re trying to use all different sorts of combinations . And computers today are massively parallel, so a hacker can check up to 10 different hashes simultaneously. Whereas the normal user of a hash is only checking one at a time. So that implied that hashes are a few bits weaker than you would expect, since hackers can use so much more parallel architecture on the computer to crack them.”

Dependencies
“They way that computers work is they can carry out multiple independent tasks at the same time. But cryptographic algorithms are fairly dependent. First you add something, then you XOR on the previous result, then you put the bit on the next stage, and so on, and so forth, so every stage is acting on the previous stage of the algorithm. So they’re one long dependent chain. So there’s not a lot of opportunity to do more than one hash at a time.”

“The Core II processor has three execution units which means it can calculate three hashes in the same amount of time it would take to calculate a single hash, because each execution unit basically takes an instruction. And while it’s executing, it goes off and fetches the next instruction. Now if that next instruction doesn’t depend on the results of the previous instruction, it sends that next instruction to the next execution unit.”

SIMD
Now we take Single Instruction, Multiple Data (SIMD) into account. “An SIMD instruction operates on four different values at the same time. So it’s one instruction and four values, rather than one instruction on a single value. These processors don’t actually have three SIMD units, they only have two SIMD units, so what that effectively means is that we can in the same amount of time it takes to use a single instruction we can execute two SIMD instructions and one non-SIMD instruction, all at the same time. So that’s a total of nine different values.”

One immediate impact is that John the Ripper, a popular open-source password-cracking program, a couple of years ago started using the SIMD units. “If you look at some of the code that was added just this last summer, it exploits both of the multiple execution units and the SIMD units all at the same time in order to crack Windows passwords. Although I found that John the Ripper is still too slow,” said Graham. Adding parallel processing speed up the hash process “to a great extent that other parts of John the Ripper are slowing it down. It takes too long for John the Ripper to decide what the next password is to check. Even if I can check 100 passwords at the same time, it wouldn’t be dramatically faster because the rest of the program is too slow.”

Threat to users?
Graham admits that this isn’t a huge threat to end-users. “This is a small increase in performance. That criminals are taking advantage of parallel processing “is not a big deal knowing that there’s a lot of bits–there’s 128 bits or 160bits in a hash, so that means it is removing a few bits on the end of the hash. So instead of being 160 bits of effectiveness, there is only 157 bits of effectiveness,” said Graham.

Graham points out that password cracking in and of itself remains a serious threat. The trick is not to use weak or poor passwords. Here’s some password recommendations from Carnegie-Mellon. And here are some common password myths. You may not be able to prevent someone from cracking your password, but you can seriously slow them down with a really strong password.