Cracking Passwords In The Cloud: Amazon’s New EC2 GPU Instances

Update: Great article about this at Threatpost! This also got slashdotted, featured on Tech News Today and there's a ZDNet article about this.

Update: Because of the huge impact I have clarified some things here

As of today, Amazon EC2 is providing what they call "Cluster GPU Instances": An instance in the Amazon cloud that provides you with the power of two NVIDIA Tesla “Fermi” M2050 GPUs. The exact specifications look like this:
- 22 GB of memory
- 33.5 EC2 Compute Units (2 x Intel Xeon X5570, quad-core “Nehalem” architecture)
- 2 x NVIDIA Tesla “Fermi” M2050 GPUs
- 1690 GB of instance storage
- 64-bit platform
- I/O Performance: Very High (10 Gigabit Ethernet)
- API name: cg1.4xlarge
GPUs are known to be the best hardware accelerator for cracking passwords, so I decided to give it a try: How fast can this instance type be used to crack SHA1 hashes?

Using the CUDA-Multiforce, I was able to crack all hashes from this file with a password length from 1-6 in only 49 Minutes (1 hour costs 2.10$ by the way.):
1. Compute done: Reference time 2950.1 seconds
2. Stepping rate: 249.2M MD4/s
3. Search rate: 3488.4M NTLM/s
This just shows one more time that SHA1 for password hashing is deprecated - You really don't want to use it anymore! Instead, use something like scrypt or PBKDF2! Just imagine a whole cluster of this machines (Which is now easy to do for anybody thanks to Amazon) cracking passwords for you, pretty comfortable ;=) Large scaling password cracking for everybody!

Some more details:
◦ Multiforcer Output
◦ Hashes
◦ Charset
◦ Makefile
◦ cpuinfo
◦ meminfo
◦ nvsmi
If I find the time, I'll write a tool which uses the AWS-API to launch on-demand password-cracking instances with a preconfigured AMI. Stay tuned either via RSS or via Twitter.

Installation Instructions:
I used the "Cluster Instances HVM CentOS 5.5 (AMI Id: ami-aa30c7c3)" machine image as provided by Amazon (I choosed the image because it was the only one with CUDA support built in.) and selected "Cluster GPU (cg1.4xlarge, 22GB)" as the instance type. After launching the instance and SSHing into it, you can continue by installing the cracker:

I decided to install the "CUDA-Multiforcer" in version 0.7, as it's the latest version of which the source is available. To compile it, you first need to download the "GPU Computing SDK code samples":
#wget http://developer.download.nvidia.com/compute/cuda/3_2/sdk/gpucomputingsdk_3.2.12_linux.run
# chmod +x gpucomputingsdk_3.2.12_linux.run
# ./gpucomputingsdk_3.2.12_linux.run
(Just press enter when asked for the installation directory and the CUDA directory.)


Now we need to install the g++ compiler:
# yum install automake autoconf gcc-c++

The next step is compiling the libraries of the SDK samples:
# cd ~/NVIDIA_GPU_Computing_SDK/C/
# make lib/libcutil.so
# make shared/libshrutil.so

Now it's time to download and compile the CUDA-Multiforcer:
# cd ~/NVIDIA_GPU_Computing_SDK/C/
# wget http://www.cryptohaze.com/releases/CUDA-Multiforcer-src-0.7.tar.bz2 -O src/CUDA-Multiforcer.tar.bz2
# cd src/
# tar xjf CUDA-Multiforcer.tar.bz2
# cd CUDA-Multiforcer-Release/argtable2-9/
# ./configure && make && make install
# cd ../
As the Makefile of the CUDA-Multiforcer doesn't work out of the box, we need to open it up and find the line:
CCFILES := -largtable2 -lcuda
Replace CCFILES with LINKFLAGS so that the line looks like this:
LINKFLAGS := -largtable2 -lcuda
And type make. If everything worked out, you should have a file ~/NVIDIA_GPU_Computing_SDK/C/bin/linux/release/CUDA-Multiforcer right now. You can try the Multiforcer by doing something like this:
# export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH
# export LD_LIBRARY_PATH=/usr/local/cuda/lib64:$LD_LIBRARY_PATH
# cd ~/NVIDIA_GPU_Computing_SDK/C/src/CUDA-Multiforcer-Release/
# ../../bin/linux/release/CUDA-Multiforcer -h SHA1 -f test_hashes/Hashes-SHA1-Full.txt --min=1 --max=6 -c charsets/charset-upper-lower-numeric-symbol-95.chr

Congratulations, you now have a fully working, CUDA-based hash-cracker running on an Amazon EC2 instance.

COMMENTS:
Deryck H
November 17th, 2010 - 01:22Best thing I’ve read or heard about all day. I love this kind of stuff. You should run a distributed.net client on a few of these clusters

Wonder how long until things like RC4-128 SSL is completely deprecated. Something that many people put blind trust into through their web browsers.
hackajar
November 17th, 2010 - 01:27Very poor numbers for the Tesla EC2:

CUDA Device Information:
Device 1: “Tesla M2050″
Number of cores: 112
Clock rate: 1.15 GHz
Performance Number: 16058

[root@ip-10-17-130-104 CUDA-Multiforcer-Linux-0.72]# ./CUDA-Multiforcer -d 0 -l -h NTLM -f hash.txt –min=8 –max=8 -c charsets/charset-upper-lower-numeric-symbol-95.chr -o outhash.txt –threads 768 –blocks 60 -m 1024
Version 0.72, length 0-14
Hash type: NTLM
Hashes loaded (22 hashes)
Launching kernel for password length 8
Done: 0.00% Step rate: 1110.7M/s Search rate: 24435.0M/sec
Bitweasil
November 17th, 2010 - 03:08… Um.

It’s a 448 core unit, but clocked slower than the GTX470 (which is a 1.21ghz).

Those numbers look OK, but not great. Try a thread count of 512 or 1024. I may play with this soon.
Cyber Killer
November 17th, 2010 - 09:48Currently passwords are recommended to have 8+ characters. Finding hashes of any type (this is not reserved only to sha1) of 1-6 chars is not that hard even for a desktop machine. That’s why (good) services don’t store only the hashed passwords in the database. They (should) add a (sometimes) random additional string to the pass to make it even longer (try reversing a hash of a 128 char string), so finding the hashes is not trivial. It’s called “salting”.

Unless you can prove to find a collision for sha1, which hasn’t been done yet, even with countless thousands of hours of a BOINC project, your 49-minute statistic doesn’t prove anything except that Amazon clusters are fast .
sbo
November 17th, 2010 - 09:53Sha 1 is broken in a matter of collision. It has a theoretical break, from 2005, that lets the attacker find pairs of messages with same hash (collision) in lower computational complexity than it should provide.

BUT this has little to do with cracking passwords which is another property of hash functions , where also the “theoritical” protection is good but is “lowered” by other things (such as policy, no salting, weak passwords, attacks that compute “words” with char set instead of trying to find ALL the combinations,shortcut for cracking doesnt exist in a matter of flaw in sha-1 design in order to reduce the complexity).

The problem with the hash functions now (because of the NIST Competition) is their design. Before the competition (and the attacks on SHA1) everyone just took MD5 (for example) made some changes and announced a NEW hashing scheme. Now it is obvious that some serious works needs to be done…

The thing we should keep from this article is that A) we have to learn how (and where) to use hashes b) Nowadays computation power (ever for the average user) is not a dream. A combination of 6 char pass for example isn’t an obstacle of many “days” of computing/calculating or an hour in a super computer ( big coorporation, agencies, NSA ,CIA etc). Its there waitng for you and with the use of distributed computing the average user may soon be able to crack even strong 7-8 char password easily without waiting and waiting…

And as we have seen from this post, many people, don’t know even the basics of password protection and hashing. That’s what should alert the community.

Good work again for the author.
Cyber Killer
November 17th, 2010 - 10:02OK, I need to correct myself – as @sbo says, there are collisions in sha1. Anyway the rest of my previous comment stays the same .
blandyuk
November 17th, 2010 - 10:16I cracked 13/14 of those hashes in 15 seconds with my large dictionaries and hashcat nVidia GPUs are slower than ATI GPUs. See benckmarks below:

http://golubev.com/gpuest.htm
Jan Dittberner
November 17th, 2010 - 11:49Normal password hashing routines (i.e. glibc’s crypt function) use (pseudo)-random salt values that increase the complexity of such brute force attempts by orders of magnitude. Is there still any serious application or OS using non-salted passwords?
Thomas Roth
November 17th, 2010 - 11:58Actually yes, I see this a lot of times. I’m also shocked on how many new software projects still use MD5.
Benjamin
November 17th, 2010 - 14:31Adding salt to a password won’t increase the complexity of a brute-force attack. The salt is stored *with* the hash, after all. So instead of searching for “aaa”, “aab”, …, I search for “salt_aaa”, “salt_aab”. Salt is intended to prevent rainbow attacks, where someone makes a huge table of all N-character passwords and lets passwords be looked up by their hash. No brute force needed!
David Schwartz
November 17th, 2010 - 14:40This shows that short passwords are broken. It’s not any defect of the hashing algorithm (except perhaps that it lacks seasoning).
Carsten
November 17th, 2010 - 15:01Cool article, and great job Thomas! It would be awesome to see this cracking weak SSL/TLS ciphers.

6 chars is maybe not that impressive, and yes there are some caveats, like no salting of the hashes. But still the pure power and prowess of those that are cracking passwords/hashes seems to be creeping closer to the current password and cryptographic key length standards…
sha1 hash
November 17th, 2010 - 17:49Wow. Quite frightening. Wonder how it would perform for longer PW? Would be interesting to see how fast it could crack MD5.
David Barr
November 17th, 2010 - 22:02Benjamin: Salt would help if you have multiple hashes with a different salt for each. If this wasn’t done, an attacker would only have to compute the hash each of his guesses one time to compare against multiple stored hashes.
Anonymous Troll
November 18th, 2010 - 04:06SO OLD!

Please ppl stop reinventing the wheel…
news.electricalchemy.net/2009/10/cracking-passwords-in-cloud.html

¬¬
Thomas Roth
November 18th, 2010 - 08:27It’s not old. The GPU instances of Amazon launched 3 days ago.
Grugnog
November 18th, 2010 - 17:34Properly stretched passwords – which would include most linux passwd formats, and even several web applications (such as Drupal) that have adopted the phpass library would have effectively prevented this attack. Hashes are designed to be fast, as well as secure – and hence a single round of hashing is a very poor defence. Stretching applies many repeated rounds of salting and hashing, which make an attack that checks many passwords extremely slow (many years), but is still fast enough that a single password can be checked in a reasonable time interactively. Read http://www.openwall.com/articles/PHP-Users-Passwords for more details.
scriptkiddieloveslamers
November 18th, 2010 - 19:08What about SSHA, and what clown would use SHA-1 for passwords anyways?
淘知识
November 19th, 2010 - 02:00Very Cool.SHA-1 is over.
Platinum
November 19th, 2010 - 04:04shit, your password is too short, most of them can be searched by google

you can put all sha1 of 6byte password in a 30$ harddisk

and if you want guess a 8byte password in ec2, you need pay 36 ^ 2 * 2$

wtf, stupid article
sbo
November 19th, 2010 - 08:52SHA-1 was over long time ago, but for other reasons. i think that even other “new” and more “secure” hash algorithms would have about the same results, because we are talking about DISTRIBUTED brute force, which mean, “TRY TO CALCULATE MORE IN LESS TIME”. So The only thing we can talk about is the “CALCULATE” phase which has to do at most with a)How many ops has one hash application b)How many ops would the “cracker” be able o run.

About the sha-1 and collision, one project about the collision was already stoped, and most people say thats it is mainly a “theoritical break”, but a) Colliding pairs have been announced from 2005 b) the computational complexity of proposed method is really low (2^52 or 2^59 i think) , always in contrast to what is the theoritical boundary (2^80).

Salting has to do with Bruteforce also. a) it makes weak and small passwords stronger b)Salt hs to e secret b) You will have to compute the over all hash but have the knowledge of the salt and Pass part. c) Most crackers (i talk about the programms) bruteforce passwords and dont mess with salt (so i wont really help). d) There is a small possibility that you will break the password with Pass1.Salt1 , so you will go try pass1 as password, BUT what happens if the salt was SaltX? This means you have another password (passX). So hash(Pass1.salt1) != hash(pass1.saltX) != hash(pass2.SaltX).Complete failure and wast of time. (without hash, even we could find another pass it wouldnt be a problem , it would be a collision, but then you can go try your luck in a casino too…Or maybe you have exhausted it…)

Oh! and always remember that we are talking about complexity but also probalities…

Finally i have to mention that this article is good and i dont some people here, it presents a practical application, using GPUs ,potential of distributed computed, and ALL these with the help of amazon (no, you dont have to go to the “nearby” univ./research center, or hack into it and “run” your process, or you can just continue say that distributed computing and the use of GPUs is something you can do everyday for fun and profit with low cost, please send me an email, to inform me to i am jealous and i need it for work).
sbo
November 19th, 2010 - 09:04Also, many people said about the 6byte (i prefer the 6-char -beacause of the “charset used”) password, that are quite small and weak. I agree with that,as i mentioned before, but many people continue using these kind of passwords. Also the results where good,and can be applied to even bigger passwords (you may spend some days but not decades). Think of a completely distributed CPU/GPU cracked (with good and optimized implementation), the total computation time needed would be pretty much lower that ordinary bruteforcing, or even bruteforcing with the “help” of a single GPU. instead calculating for example 500mil hashes per sec you could calculate MANY more.

And if someone think that this methods are “junk”, it is better not to be interested in BRUTEFORCING, or in general exhaustive search in many problems.
sysiu
November 19th, 2010 - 10:33yes, i don’t see the point of salting too
Carlos
November 19th, 2010 - 10:38A benchmark with pyrit for hacking WPA/2 would be interessting…8 Tesla C1060 cards can try 88.000 PMK/s from a wordlist.. 2 Tesla C2050 maybe 25.000 keys/s? Is it possible to use pyrit with these cards in the amazon cloud?
sysiu_wtf
November 19th, 2010 - 16:45@sysiu- is this because your lacking in knowledge or braincells- or are you another monkey from uk?
sbo
November 19th, 2010 - 18:32It is not a matter of lacking knowledge. Its a matter of boredom…
Some people are bored to THINK, to read (other posts, articles books), to ask (someone else) and to search.

Thats the problem.

Salting. The idea behind salting is “extending” a password by a set of bytes (a word, some bits, some characters etc). In this way the PASSWORD becomes more complex. IF someone doesnt know the salt then he/she will have to crack it to, even worse if he doesnt know the existance of the salt he wont find a good combination. (look at my previous comment).

If the salt is known, then its a matter of bruteforcing the password only by “concating” the salt. (it may take some ops more because of computing the salt’s hash, by that i mean the “blocks” needed to somputed by the hash algo.)

And a very good answer about the salt, is that, IT WORKS. as simple as that, it just make it difficult to many people to crack a pass. May be it will send some scriptkiddies away. Maybe even some security analyst or hacker will prefer not spending his time on a pass with hash.

But again, read the post, read some comments, and search ,ask ,think, whatever . just DONT say something just to say it…
dfdt
November 20th, 2010 - 11:26This is pretty stupid. Something is considered “broken” in cryptography, if you find an attack that is faster than bruteforce. Bruteforce is always a valid option and there’s quite nothing one can do to prevent it. While SHA-1 has some other problems, this is definitively not one of it.
If you expect weak passwords, consider employing key strengthening. But this is not a problem of the hash algorithms but of the expected passwords.

I mean, wtf should this prove? Dont use SHA-3 either (when it’s official) because I can brute-force 1 char passwords on my mobile phone in seconds and some people still use 1 char passwords?

Also, what is the contribution of this article? You did not even facilitate the “cloud”, or did I miss this part? I’ve been able to ask my neighbor to use his GPU for 49 minutes since quite some time, do not need Amazon for this. You mean I can buy more instances and do it faster? Well, I doubt you’ll be able to speed up your silly 6-char experiment significantly because all instances will test the same passwords.
You are welcome to report back when you managed to synchronize GPU cracking for a larger amount of instances and crack some 8-12 byte passwords in negligible time.
Cloud Freak
November 20th, 2010 - 11:47I agree with sbo. I would always implent a minimum requirement of 12 characters for the password and by mixing it up with a specific Salt SHA-1 should Be still good to go.

Allthough I’m a big fan of the cloud, as it makes powerful ressources available, even for the small guy, but all the stuff you can do with it in the criminal perspective sounds scary.

In my opinion the access to those Services is way too easy. You can sign up in 1min and you are good to go. No Verification, nothing.. Maybe that is something to think about.
Thomas Roth
November 20th, 2010 - 12:12Hello, this is not stupid and I did not say that SHA1 is broken. I just say that you should not use SHA1 for passwordhashes, as there are much better ways to do it like PBKDF2.
And, as stated in the article, it was just a benchmark using one instance to do some calculations on how many nodes you’d have to utilize to break stronger passwords.
“Well, I doubt you’ll be able to speed up your silly 6-char experiment significantly because all instances will test the same passwords.” That’s wrong. It’s no problem to split the task of cracking passwords onto several instances. Especially cracking hashes is extremely easy to distribute. The experiment is not ‘silly’ if you would’ve understand what the article is about.
Thomas Roth
November 20th, 2010 - 15:32Read the article, understand it, and then rethink what you’ve written. I didn’t claim that I cracked SHA1 or anything. I just showed how fast one instance can be used to brute force SHA1 password hashes and that one can easily use a lot of nodes in the cloud to make password cracking faster. Maybe you should learn what a scriptkiddie actually is.
Gonggo Ballak
November 20th, 2010 - 18:10could you please change the font? this cursive font is not good to read, THANKS!
dfdt
November 20th, 2010 - 18:21“It’s no problem to split the task of cracking passwords onto several instances.” Yes, this aint no problem, obviously. But splitting the crack of max 6byte passwords is, because the workloads are so small you won’t benefit from distribution very much.

Also, PBKDF2 may employ SHA-1 — those are two different things your are talking about.

There are several benchmarks on GPU cracking already. CUDA-Multiforcer is far from new either. It has been run a thousand times already in a set-up similar to the one you have described. The only thing new is that you are now able to rent the set-up from Amazon.

On your “Benchmark”:
At a rate of 250M/sec for one node, 7chars would take 77hours in this set-up. 8chars would already require 307 days (worst-case, half the time in average for uniform distribution).
Consequently, if we’d use 307 instances (and suppose perfect linear scalability) to crack an 8-char hash in a single day, we’d have to spend 307*24*$2.10, that are $15472. Neat; but people who have that money to spend, probably buy their own clusters.
Oh, and guess what, a 10 character password already requires 7594 years. Or almost 140 Million US Dollar to rent time from Amazon to crack in a single day.

So what we learn from this is not “Don’t use SHA-1″, but rather “Dont use short passwords”.
Thomas Roth
November 20th, 2010 - 21:08“Also, PBKDF2 may employ SHA-1 — those are two different things your are talking about.” – Yes, it may employs SHA1, and the recommendation is that it does that at least 1000 times. What’s your point?

“There are several benchmarks on GPU cracking already. CUDA-Multiforcer is far from new either. It has been run a thousand times already in a set-up similar to the one you have described. The only thing new is that you are now able to rent the set-up from Amazon.” – I never stated anything else. I just gave it a try on the cloud instance. So what?

“At a rate of 250M/sec for one node, 7chars would take 77hours in this set-up. 8chars would already require 307 days (worst-case, half the time in average for uniform distribution).” – Yes, that’s right. (By the way I’m down to 25 minutes, using some tweaks from the author of the Multiforcer.

“Consequently, if we’d use 307 instances (and suppose perfect linear scalability) to crack an 8-char hash in a single day, we’d have to spend 307*24*$2.10, that are $15472. Neat; but people who have that money to spend, probably buy their own clusters.” – You’re missing that we’re talking about criminals who would want to use that. It’s no problem to get credit card data to buy a cluster of $15k. (Yes, it really is no problem.)

“So what we learn from this is not “Don’t use SHA-1″, but rather “Dont use short passwords”. – Right conclusion. Read the article at Threatpost, I told them exactly the same.
hardcore
November 22nd, 2010 - 07:18It is more important than just passwords.
courts also rely on MD5 and SHA checksums to ‘ensure’ that evidence is not tampered with.
Daniel
November 22nd, 2010 - 12:51Amazing job

=]
Name(required)
November 24th, 2010 - 14:58In the defense of Thomas Roth, I find his article fair and balanced, he never claimed to have invented a new hack of SHA and he posted the limitations in clear.

I found that a lot of comments left by angry trolls smell like “too bad I did not thought about that earlier”

For every argument they will be a counter argument, So what?
damaskino
November 25th, 2010 - 18:06I’m totally agreed with the last comment. Some people are just haters. Read the article, you not agree with it, post your point in a constructive way. WTF, stupid article etc… Are not constructive at all. I found this article pretty interesting on the importance of using long password instead of short. Some comments are interesting too. They complete well the article.
Troll took day off
November 27th, 2010 - 19:01This is awesome and simple. Thanks Tomas.
Anonym
November 28th, 2010 - 13:04Is there any possibility to do that with RAR files?
I have one RAR File I password protected 1 year ago. Inside there are sensitive financial data. But I forgot the password and I need some of them. Sphere: Related Content