Author Topic: Password Cracking Made Easy Thanks to the GPU (Read 22549 times)

Josh · « **on:** October 25, 2007, 10:51 AM »

A technique for cracking computer passwords using inexpensive off-the-shelf computer graphics hardware is causing a stir in the computer security community.

Elcomsoft, a software company based in Moscow, Russia, has filed a US patent for the technique. It takes advantage of the "massively parallel processing" capabilities of a graphics processing unit (GPU) - the processor normally used to produce realistic graphics for video games.

Using an $800 graphics card from nVidia called the GeForce 8800 Ultra, Elcomsoft increased the speed of its password cracking by a factor of 25, according to the company's CEO, Vladimir Katalov.

The toughest passwords, including those used to log in to a Windows Vista computer, would normally take months of continuous computer processing time to crack using a computer's central processing unit (CPU). By harnessing a $150 GPU - less powerful than the nVidia 8800 card - Elcomsoft says they can cracked in just three to five days. Less complex passwords can be retrieved in minutes, rather than hours or days.
-News Scientist

Source

Armando · « **Reply #1 on:** October 25, 2007, 10:54 AM »

tinjaw · « **Reply #2 on:** October 25, 2007, 11:10 AM »

-Armando (October 25, 2007, 10:54 AM)

Did you read the article? Sorry, but this leaves the impression, for those who will only see your comment and not read the article, that this is a bad thing. As the article points out, this is meaningless. This only allows hackers to crack very small and very simple passwords - ones like 'EatMeat' - your basic letter only 8 character passwords. If you do the math, they would need to make this whole thing work 1,000 faster just to make it crack a password in a human's lifetime. Any reasonable password cannot be cracked in any reasonable amount of time. And it is very easy just to change your password today and turn it into a passphrase, making it almost impossible within your lifetime, to be cracked. For example, change your password from 'jE84%kd^' to "*IfYouAren'tFiredWithEnthusiasm,$YouWillBeFiredWithEnthusiasm." This is a random quote I grabbed and salted it with a '*' and a '$'. This is, to all intents and purposes, uncrackable via brute force.

Ralf Maximus · « **Reply #3 on:** October 25, 2007, 11:14 AM »

What I'm curious about is why the Russians would go to the trouble to patenting the technique. Is password cracking such a lucrative market niche that they worry about trade secrets?

Or is there application beyond password cracking?

tinjaw · « **Reply #4 on:** October 25, 2007, 11:26 AM »

What I'm curious about is why the Russians would go to the trouble to patenting the technique. Is password cracking such a lucrative market niche that they worry about trade secrets?

Or is there application beyond password cracking?
-Ralf Maximus (October 25, 2007, 11:14 AM)

1) It is good marketing that gets them more publicity.
2) There may or may not be application beyond password cracking and by patenting it, anything created that uses the same basic technique would most likely have to pay licensing fee to them for using the patented technology. So it is just good business sense to do so. (blah, blah, blah, patents are evil. blah blah blah ad nauseum)
3) It makes them more attractive as a buyout target. Companies are more likely to buy other companies if they have tangible assets that can not be lost as easily as say, developers who don't want to stay with the company after it is bought out.

Armando · « **Reply #5 on:** October 25, 2007, 11:40 AM »

-Armando (October 25, 2007, 10:54 AM)
Did you read the article? Sorry, but this leaves the impression, for those who will only see your comment and not read the article, that this is a bad thing. As the article points out, this is meaningless.
-tinjaw (October 25, 2007, 11:10 AM)

Sorry tinjaw.
Yes I read the article, and although I don't have the time to reread it now and you seem very competent and I might not have the qualifications to comment (

) cryptography/encryption, how and where does it say that it's "meaningless"?

tinjaw · « **Reply #6 on:** October 25, 2007, 11:47 AM »

Doh!

It appears that even *I* haven't read the article Josh quoted.

I had just finished reading Jeff Atwood's blog and was checking for new postings on DC and *assumed* (yes, I know) that Josh was linking to Jeff's blog. Sooooo....................

Jeff Atwood points out why this is meaningless.

Armando · « **Reply #7 on:** October 25, 2007, 11:50 AM »

oh! Thanks tinjaw -- I just reread the article Josh submitted and was starting to question my ability to understand English...

I'll check out the Jeff Atwood one.

Deozaan · « **Reply #8 on:** October 25, 2007, 12:07 PM »

-Armando (October 25, 2007, 10:54 AM)
Did you read the article? Sorry, but this leaves the impression, for those who will only see your comment and not read the article, that this is a bad thing. As the article points out, this is meaningless. This only allows hackers to crack very small and very simple passwords - ones like 'EatMeat' - your basic letter only 8 character passwords. If you do the math, they would need to make this whole thing work 1,000 faster just to make it crack a password in a human's lifetime. Any reasonable password cannot be cracked in any reasonable amount of time. And it is very easy just to change your password today and turn it into a passphrase, making it almost impossible within your lifetime, to be cracked. For example, change your password from 'jE84%kd^' to "*IfYouAren'tFiredWithEnthusiasm,$YouWillBeFiredWithEnthusiasm." This is a random quote I grabbed and salted it with a '*' and a '$'. This is, to all intents and purposes, uncrackable via brute force.
-tinjaw (October 25, 2007, 11:10 AM)

Okay, so I read the source article linked in Josh's post and I didn't get any of what you're saying. It left the impression to me that cracking passwords is a lot faster due to parallel processing.

It even says, in Josh's post:

The toughest passwords, including those used to log in to a Windows Vista computer, would normally take months of continuous computer processing time to crack using a computer's central processing unit (CPU). By harnessing a $150 GPU - [...] - Elcomsoft says they can cracked in just three to five days. Less complex passwords can be retrieved in minutes, rather than hours or days.

And the only hint I see about it taking a lifetime to crack a password is this:

Password cracking can be used to unlock data on a computer, but will not usually work on a banking or commercial website. This is because is takes too long to run through multiple passwords, and because a site will normally block a user after several failed attempts.

And the only reason it would take so long is because the banks and places would lock you out after a few attempts, and possibly flag the account for watch.

So I'm not sure where you're getting your info on a "reasonable" password taking an unreasonable amount of time to crack. Then again, I suppose that means I should ask your definition of a "reasonable" password.

Is "*IfYouAren'tFiredWithEnthusiasm,$YouWillBeFiredWithEnthusiasm." reasonable to you? Do you really want to type that in every time?

I'm probably slightly above average when it comes to passwords, thinking a mix of letters and numbers is reasonable. Strange characters would be good, and long strings of jumbled nonsense would be the best, but not from a usability standpoint.

EDIT: I typed this up while the previous comments were made. I'll read Jeff's blog now.

Ralf Maximus · « **Reply #9 on:** October 25, 2007, 12:25 PM »

2) There may or may not be application beyond password cracking and by patenting it, anything created that uses the same basic technique would most likely have to pay licensing fee to them for using the patented technology. So it is just good business sense to do so. (blah, blah, blah, patents are evil. blah blah blah ad nauseum)

So, if I develop (say) a DNA sequencer that runs partially in the GPU, I might have to prove it's not derived from their technology?

Does this imply these guys are just setting up a patent-troll scheme?

tinjaw · « **Reply #10 on:** October 25, 2007, 02:11 PM »

So, if I develop (say) a DNA sequencer that runs partially in the GPU, I might have to prove it's not derived from their technology?

Does this imply these guys are just setting up a patent-troll scheme?
-Ralf Maximus (October 25, 2007, 12:25 PM)

I haven't read the patent, but I doubt even the patent office is so stupid as to grant a patent for using a GPU for anything other than graphics. So no. But creating an application to open password encrypted ZIP files and uses the GPU to crack the password, would be an example. But then you enter the wonderful world of idea versus implementation. Using the GPU to crack passwords as a *concept* cannot be patented, but a particular way of doing it can. And I can go on an on about this and I ain't even a lawyer. Get a lawyer and they will slice this even thinner. However, I was just trying to provide some generic explanation of why they would want to get a patent.

Armando · « **Reply #11 on:** October 25, 2007, 02:19 PM »

Jeff Atwood's article was interesting. Thanks tinjaw.

f0dder · « **Reply #12 on:** October 25, 2007, 06:25 PM »

There's still plenty of 8-char passwords out there, and some revisions of the NT password system are flawed and limit the effective size of your passphrase even if you have a very long one - so there's plenty of situations where this can be useful for badguys.

It's mostly interesting because it shows how powerful GPUs have become these days, though, since anybody doing password cracking would be utilizing rainbow tables instead, which are much much much much faster than bruteforce attacks.

edit: nice to see that Jeff Atwood talks some sense, this could way too easily be overhyped into a big scare. 12-character passwords are reasonable, imho.

Lashiec · « **Reply #13 on:** October 25, 2007, 07:27 PM »

Actually, commercial applications to crack ZIP passwords do exist. And they work pretty fast...

More or less, Jeff Atwood's post is pretty good, except for this line:

Who has passwords without at least one number? Even MySpace users are smarter than that

LOL. He's thinking too high of users. A ongoing discussion we're having in another forum about the recent imposition of better passwords is showing that most people there is dumb and don't care about their security. In fact, they're complaining about his freedom to use a simple password (and the same one from every site they visit) if they want. Sheesh.

Good point about passphrases, though. That blog post by Mr. Hensing is brilliant, what a way to preserve your passwords from prying eyes without needing a password manager everywhere you go.

f0dder · « **Reply #14 on:** October 25, 2007, 07:36 PM »

Actually, commercial applications to crack ZIP passwords do exist. And they work pretty fast...
-Lashiec (October 25, 2007, 07:27 PM)

Afaik the original zip password algorithm was retarded, and there's other attack avenues as well - but it does show that you aren't just at the mercy of your passphrase length, but also the system it's used in.

mwb1100 · « **Reply #15 on:** October 26, 2007, 10:39 AM »

LOL. He's thinking too high of users. A ongoing discussion we're having in another forum about the recent imposition of better passwords is showing that most people there is dumb and don't care about their security.
-Lashiec (October 25, 2007, 07:27 PM)

But then again, the password you use for a forum probably isn't particularly sensitive. While I wouldn't particularly want anyone to know my DC password, I'm not losing any sleep worrying about it, even though DC has the credits which have something to do with money - with most forums all a password gets you is the ability to post. I haven't looked at the code for any forum software, but I'd be willing to bet that in most cases the password is stored in some recoverable fashion (probably even in plaintext) in the database - potentially a much bigger security risk than allowing weak passwords.

In my quick sample of 3 forums I have accounts on, I found that when I log on:

one sends my password in plaintext
one sends an MD5 hash of my password. More secure, but a rainbow table dictionary lookup will have no problem getting pretty much any password less than14 characters long
one sent a SHA1 hash of the password combined with the userID and sessionID. That's not too bad.

Am I worried? No.

On the other hand, my passwords for work and banking are something I take a bit more seriously. And when I access them over the Internet, I ensure that SSL is used.

f0dder · « **Reply #16 on:** October 26, 2007, 10:42 AM »

If something sends a hash of passphrase+whatever, it means your passphrase is stored in plaintext (or at least automatically recoverable) form somewhere server-side... If just a hash is sent, it could be that just the hash is stored serverside, but then of course the hash is just as good as your passphrase.

mrainey · « **Reply #17 on:** October 26, 2007, 12:16 PM »

I know next to nothing about this subject and have a question. How secure would a well-designed twelve-character password be if it had to be used in combination with a specific user name?

tinjaw · « **Reply #18 on:** October 26, 2007, 02:49 PM »

I know next to nothing about this subject and have a question. How secure would a well-designed twelve-character password be if it had to be used in combination with a specific user name?
-mrainey (October 26, 2007, 12:16 PM)

Could you provide an example? There are several ways to interpret your question.

mrainey · « **Reply #19 on:** October 26, 2007, 04:28 PM »

I guess I was thinking of a situation where a dialog requested a user name and a password as separate entries. This is the way I protect certain pages of my website (using .htaccess and .htpasswd files).

As you can readily see, I don't have much of a handle on how all this works.

mwb1100 · « **Reply #20 on:** October 26, 2007, 05:04 PM »

Generally, from a security standpoint user ID's are not considered secret. So, even though user ID's are often sensitive information, they are not typically factored into determining how secure an authentication system is.

If your userID's really are secret, then I suppose they could count to the length of the password (ie., it's the same as having a universal user with different passwords for the resources).

On the other hand, userID's usually often have a much more restricted set of characters and/or they follow a standard format (like an email address). So the characters in the userID would not add to the strength of the overall password nearly as much as the characters in the password portion (which presumably can contain any characters).

So, I'm not sure I'd feel comfortable suggesting that someone factor in the userID as part of the password strength.

How successful might someone be if they guessed the userID on some of those protected pages was 'mrainey'?

mrainey · « **Reply #21 on:** October 26, 2007, 05:31 PM »

How successful might someone be if they guessed the userID on some of those protected pages was 'mrainey'?

Fortunately, not very successful.

Renegade · « **Reply #22 on:** October 26, 2007, 08:36 PM »

Ralf asked and then answered the real question - "Where is this important?" It's not for password cracking. It's for non-parallel and distributed computing for things like he mentioned, DNA sequencing, etc.

For example, it would be very useful for all the gamer Star Trek fans that donate CPU to SETI to find aliens.

If SETI is on course to find ET inside of 100 years, this could cut it down to 4~10 years. Now wouldn't you rather be invaded within your lifetime?

Ergo, the answer is that this new technology is best suited, and perhaps even designed to help intergalactic slavers invade planet Earth and sell humans into either slavery on distant planets, or to setup new restaurants that charge exhorbitant prices with humans as a special delicacy on the menu.

See how easy that was?

mwb1100 · « **Reply #23 on:** October 26, 2007, 09:17 PM »

I don't know how the Elcomsoft patent affects (or is affected by) the fact that general purpose computing has been going on on GPUs for some time.

http://www.gpgpu.org/
http://en.wikipedia.org/wiki/GPGPU

Lashiec · « **Reply #24 on:** October 27, 2007, 09:34 AM »

Yeah, and hardware makers had been providing solutions for some time now. ATI and nVidia flavors.

Going back to the forum thing, my example was extensible to all services requiring a password, I was only using the forum as an example. Most probably those people are using weak passwords to access their email, bank accounts, etc. Some of them even said that they were using the same password for everything on the Internet so... Besides, stealing your forum password can be more troublesome than you think. One of the reasons this enforcement was made it's that some accounts were stolen in recent times, and one of them belonged to a guy who just won a valuable item. It's just like the different contests DC made in the past. Imagine what could happen if someone stole the accounts of C++ Builder contest winners.

AFAIK, forums use several different methods for storing users' passwords. Most use hashes, or as they sometimes put it "one way cryptographic algorithms" (to give a false sense of security?)