New 25 GPU Monster Devours Passwords In Seconds

http://securityledger.com/new-25-gpu-monster-devours-passwords-in-seconds/

by _ikke_ • 14 years ago

111 90 14 years ago

Exciting to see the technology behind this field progressing so quickly but troubling considering the passwords my users likely use. Though to be completely realistic their password hashes are very likely already known.

Sam_Odio• 14 years ago

It looks like - contrary to the article - the presenters are discussing hash functions, not encryption[1]. There is a difference[2].

That said, I'd be curious to know how long it'd take a device like this to decrypt "secure" AES256 text.

1. https://hashcat.net/p12/js-sha1exp_169.pdf

2. http://stackoverflow.com/a/4948393

_ikke_2• 14 years ago

Passwords shouldn't be encrypted anyway. Chances are hackers will be able to obtain the key too, and then passwords are really easy to fetch.

Passwords should be hashed non-reversible (ideally using a slow hash). The original password is to no use of the application.

And sending plain-text passwords to users is even more bad[1].

[1] http://plaintextoffenders.com/

archgoon• 14 years ago

>That said, I'd be curious to know how long it'd take a device like this to decrypt "secure" AES256 text.

Well, according to the article it tops out at about 340 Gigahashes/second. Let's for the sake of simplicity assume it can do about 1 teraflop (10^12 operations per second, or about 2^40 operations per second). The best known attack for the full 14 round AES encryption reduces it's complexity to 2^96 instructions. So you finish this in 2^56 seconds, or about 2 billion years. I recommend you either wait for an advancement in cryptanalysis or just 30 more doublings of parallel processing power.

akulbe• 14 years ago

I wonder what algorithm 1Password uses, and how it would fare, compared to the other options.

mileswu2• 14 years ago

It encrypts all your passwords using AES with a 128 bit key derived from your master password (PBKDF2) [1].

This is very different to what the article is talking about, since it encrypts your passwords, but the article talks about hashing which is one-way.

[1] http://help.agilebits.com/1Password3/agile_keychain_design.h...

xorgar831• 14 years ago

The problem with PBKDF2 however is that if you pick a weak password it's useless. It would be better if they included an option for a key as well like other password safes do.

nwh4• 14 years ago

If you are genuinely interested in testing your 1Password keychain, the Jumbo builds of JTR include support for the agilekeychain, and some branches (Magnum Jumbo for example) offer OpenCL support for even faster attacks.

I tried it against mine, and was significantly disappointed in how quickly even my laptop could attack it. I promptly increased the complexity of my master password.

newman314• 14 years ago

What was it before (key length)? And what is it now?

mileswu2• 14 years ago

“I was extremely disappointed that setting up a clustered VMware instance wouldn’t allow me to create a VM that spanned all the hosts in the cluster. E.g. if i had five VMware ESX hosts with 8 processor cores, I wanted to be able to create a single vm with 40 cores and use all nodes in the cluster,” he wrote.

Not sure why he would have thought this would be possible. This would be an extremely hard problem given the latency involved between different nodes.

Then he came across VCL, or Virtual Open Cluster... “It did just what I wanted, not with an entire OS per se, but with an entire OpenCL application. and that’s good enough for me.”

A similar (but far older) system is MPI[1], which enables parallel computation across many compute nodes for your code by providing message passing. It's kind of a pain to use in my limited experience since you have to adapt your code (it seems like VCL is transparent for OpenCL programs), but it does work. No need for OpenCL, tho of course you could always use OpenCL + MPI. A common thing I see is MPI+OpenMP (for parallel cpu computation).

[1] https://en.wikipedia.org/wiki/Message_Passing_Interface

peteretep• 14 years ago

The numbers are ... misleading ... and choosing NTLM hashes seems like bordering on misinformation.

Taking SHA-1 (which YOU MUST NOT USE for password hashing blah), it manages 63 billion a second. To try all the passwords for that in the alphanumeric space:

- 10 chars: 35 weeks

- 11 chars: 44 years

- 12 chars: 2,800 years

- 16 chars: 11 times the age of the sun

10 chars for bcrypt: 600,000 years...

http://www.wolframalpha.com/input/?i=%2865**16+%2F+63+billio...

ErrantX• 14 years ago

Absolutely; NTLM has been attackable for ages. Running on a Quad core machine it can be cracked in a reasonable amount of time.

The cost/time trade-off for such cracking makes this rig pointless for such cracking, unless you absolutely must have it in 6 minutes.

I don't see any other major use for this; it's simply not powerful enough to attack anything new (Edit: even with 128, rather than 25, GPU's).

mrb3• 14 years ago

I don't think this is misinformation. You would be surprised at the number of IT people who have no clue how fast NTLM hashes can be brute-forced. Spreading this knowledge is good.

Ranting about NTLM, I am also shocked at how many people are unaware of the pass-the-hash vulnerability enabled by the mere possession of hashes, without having to brute-force them: http://www.youtube.com/watch?v=DkbBCR_vfRQ (disclaimer: I made this video and was a developer for Metasploit/Nexpose).

DanBC4• 14 years ago

> I don't think this is misinformation. You would be surprised at the number of IT people who have no clue how fast NTLM hashes can be brute-forced. Spreading this knowledge is good.

That's just depressing, considering how long this has been a problem.

Advice has been, for many years, to avoid using passwords 14 chars or less to force use of NTLMv2.

Here's a Microsoft document from 2004: (http://www.windowsecurity.com/articles/Protect-Weak-Authenti...)

> You would be surprised at the number of IT people who have no clue [...]

No, you're right. It's widespread lack of knowledge, and letting people know that some stuff is not secure, and other stuff is more secure if you have a complex passphrase, is important.

michaelt2• 14 years ago

LinkedIn used unsalted SHA-1, had their passwords leaked, and within a month 90-95% of leaked passwords were cracked[1].

Admittedly LinkedIn isn't a critical application calling for people's most secure passwords - but it's evident that only 5-10% of users use passwords that take more than 1 month to crack when hashed with SHA-1.

[1] http://securitynirvana.blogspot.co.uk/2012/06/final-word-on-...

rmc2• 14 years ago

Admittedly LinkedIn isn't a critical application calling for people's most secure passwords

People re-use passwords. Often it's not access to the LinkedIn account that's the problem, but that that same password will give you access to their email account, after that, you have everything.

chubs• 14 years ago

Glad to hear bcrypt is still safe; that's what i use for my apps.

Keyframe3• 14 years ago

I'm kind of rusty on algorithmic information theory (I'm an artist, heh)! Is there such a thing as (formalized) upper limit of what we could do as far as computing combinations go? I know of Kolmogorov complexity (vaguely), but what are the hard limits and challenges of just prodding through (faster and faster as tech goes forward) combinations until success? I plan on developing a story around that and make a movie out of it - so any help would be appreciated (you guys can contact me via email if you want).

itry• 14 years ago

"what are the hard limits and challenges of just prodding through (faster and faster as tech goes forward) combinations until success?"

According to current theory of physics, every computation needs at least a certain amount of energy. So if you want to do many computations today, you will have to use a certain amount of energy today. Now lets say, you have a machine that turns any matter into energy without any loss. You put in m mass and you get out e=mc^2 energy. Problem is: You cannot get more matter into that machine today then is around you in a radius of 24 light hours.

So that would be a hard limit.

But quantum computers have proven to break that limit. One theory is that using a quantum computer means using computers in an unlimited number of parallel universes. So there is no limit to the number of calculations you can do. (See David Deutsch and his theories about parallel universes)

I think there are theories about the limits of what a quantum computer can calculate. But I dont know them. Would be interesting to read about it if there is something published.

Then again, what might look like a "hard limit" today will probably not do so tomorrow. Some time ago the "lower limit on energy per calculation" sounded like a hard limit. Then quantum computers came along and blasted through it.

marshray2• 14 years ago

I read a reference someone posted somewhere once (sorry to not be more specific) that sounded pretty convincing.

Apparently it takes a minimum amount of energy to flip one bit in a conventional (non quantum) computer.

In order to brute force a 128 bit key, you'd need some sort of 128 bit register. Multiply the amount of energy needed per bit flip and the result implies there are never likley to be enough power plants on Earth to iterate through all the combinations (let alone perform the computations required to test the candidate key).

Hope this helps, perhaps this is enough for you to find the original reference.

Edit: perhaps it was http://en.wikipedia.org/wiki/Landauer%27s_principle as mentioned below.

joshmaker• 14 years ago

However, the length of the average password is probably closer to 8 chars (http://www.codelord.net/2011/06/18/statistics-of-62k-passwor...) at which point the time to crack a password drops to 84 minutes for SHA-1 and 30 minutes for MD5. Also if users aren't required to use uppercase or special characters, they probably won't (http://research.microsoft.com/pubs/74164/www2007.pdf), at which case things look a lot worse.

Daniel_Newby• 14 years ago

> VCL makes load balancing across the cluster – once an arduous task that required months of custom scripting – a trivial matter.

Surely this is an embarrassingly parallel problem that practically balances itself?

alexkus2• 14 years ago

For an embarrassingly parallel task like this why does there need to be any blazingly fast communication between the nodes at all?

My guess is that they've taken HashCat and not made any changes to it at all and just ran it on this virtual cluster so that it assumes that it's talking directly to each GPU/node.

For brute forcing things there's no need for fast communication between the nodes, you just split the work up into units of n seconds each and then have them poll for work from a central host. Sure it's a bit more work/complex as you're effectively running individual copies of HashCat on each node but that's just a bit of scripting and saves you the cost of Infiniband!

The Virtual Open Cluster and Infiniband solution would be much better for tasks that require lots of intercommunication between the nodes (e.g. block Lanczos of large sparse matrices) but brute forcing passwords/hashes isn't a great example.

dave1010uk• 14 years ago

I guess the parallelism is why botnets are so good at it. I wonder if anyone's tried getting JavaScript web workers (or possibly, somehow WebGL) to poll a central server to do cracking. A site with just a few thousand visitors a day should be able to crack passwords faster than this machine.

nwh4• 14 years ago

I have attempted this, and I believe others on the wider Internet have as well. Essentially it ended up being slower than if the central servers CPU was used to attack the hashes instead. With only JavaScript available to do the hashing, the maximum per client was disappointingly slow, around 2000 hash/second each if I remember correctly.

It might be better now with faster JavaScript engines, but I wouldn't bet on it.

rorrr3• 14 years ago

> That renders even the most secure password vulnerable to compute-intensive brute force

No it doesn't. My passwords are 30-character randomly generated and look like this:

    T7PN2m7Yju43IWtoBkwL6TLx18Rdyq

Do you want to guess how long it will take to bruteforce with that "monster"?

    (26 + 26 + 10)^30 = 5.91 × 10^53 possible combinations

At 348 billion guesses per second it will take

    1.53 × 10^42 seconds

    4.84 × 10^34 years

That's quite a bit longer than the age of the universe.

alexkus2• 14 years ago

True, but in reality you're probably sending that password over something less secure (like an SSL connection) that doesn't require quite as long (but still a very long time) to crack.

Anything is only as secure as the weakest link in the chain.

If (I'm sure you don't) you allow your browser to save that password so that you don't have to enter it every time then you just need one cleverly designed trojan to be run on your machine (probably easier to do than waiting 4.84E34 years to crack a password) to grab the saved passwords cache from your browser and it's no longer secret.

raverbashing3• 14 years ago

There you go

30 chars password don't matter. Sure, it's not low hanging fruit, but it's not troublesome if you're the target

Why?

Weakness 1: Because it's written down somewhere. Weakness 2..n: weaker links in the chain

rorrr3• 14 years ago

> The National Institute of Standards and Technology (NIST) has issued a statement that says SSL certificates with a key length of 1,024 bits or fewer will be insufficient for security after December 31, 2010

> It is recommended that the algorithms and key sizes in the "Through 2030" row (e.g., 2048-bit RSA) should be used to provide the cryptographic protection

http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-P...

1024 bit is impossible to bruteforce. Simply incrementing an integer 2^1024 times will take more energy than our whole universe has.

Heck, even 128 bit would take 3.1×10^19 years to bruteforce with that GPU setup. My citibank.com uses a 256-bit connection.

SSL is not "less secure" than my 30-character password (correction: 128-bit one is a bit less secure, but 256-bit one is much more secure).

If it were, all the banks would be freaking out and would shut down their web interfaces.

DanBC4• 14 years ago

Yes, there might be other attacks on the password, but rorr is responding directly to part of the article which claims

> Gosney’s system elevates password cracking to the next level, and effectively renders even the strongest passwords* protected with weaker encryption algorithms, like Microsoft’s LM and NTLM, obsolete.

Reply

nemo1618• 14 years ago

Such passwords are certainly secure, but it's a pain to have to carry Keepass/other programs around when using other computers. I think I've found a happy medium by memorizing a simple password-generation function in my scripting language of choice. It produces sufficiently strong passwords, and if you're stranded without Keepass you can still generate them using a local interpreter or a site like codepad.org.

Reply

wcoenen• 14 years ago

This doesn't work because there are conflicting rules out there about what a password should look like. Less than X chars, more than X chars, must contain certain chars, must'n contain certain chars...

I use KeePass, with a copy (via dropbox) on my smartphone for when I'm not at my own computer.

Reply

bigiain5• 14 years ago

If you can sync your password safe aoftware to your phone, that pretty much solves that problem, at least for me.

(I also rely on having one of my phones or my iPad with me anytime I need secure access to any account of mine, 'cause I use two factor auth using TOTP tokens for places that support it like Google, Amazon, and Dropbox)

Reply

rb2k_• 14 years ago

Seeing as what kind of GPU farms people ran/run for mining Bitcoin, this is somewhat "in the middle" rather than being a "monster"

Reply

mrb3• 14 years ago

As a matter of fact, I sold 16 GPUs to Jeremi, the security research in question, and yes it was just a fraction of my Bitcoin mining farm. Your statement is true :-)

(Hi Jeremi, nice work!)

Reply

nakedrobot2• 14 years ago

I haven't seen the discussion that I think is really necessary - when are we going to move beyond passwords, which are obviously growing more and more obsolete? What are we going to use instead of passwords in the future?

Reply

ars2• 14 years ago

There are 3 types:

What you know.

What you have.

What you are.

And of the 3 What you know (i.e. password) is the most secure when used properly. It's impossible to steal without your knowledge, and it's impossible to misplace.

What you have (eg. physical key) can be stolen from you - or even borrowed, used, and returned without you ever knowing. It can also be copied, and it can be lost - sometimes without being aware of it for a long time.

What you are (eg. fingerprint, iris) is the worst, and the least secure. It's trivial to copy - even from a distance, and it's impossible to change. The entropy available is also low.

So in the future we are still going to use passwords.

Reply

Karunamon2• 14 years ago

What you are.. trivial to copy - even from a distance..

A retinal print?

Reply

_b8r02• 14 years ago

The problem with all of this is that security specialists (of which I am one, guilty as charged) have historically campaigned for more complex passwords. This worked well for conventional (non-clustered, non-accelerated) password cracking mechanisms.

Sadly, this starts to fall apart with accelerated and/or distributed cracking. On average I crack a few hundred passwords a week, and more often than not organisations have what I call seed words (e.g. the password reset word or common words used throughout the organisation) and the majority of passwords are variants of them.

My own ability to crack passwords for most algorithms (within a reasonable timeframe) tends to cap at dictionary words with number and letter substitution and somewhere around the 8-10 character mark. Using a phrase means that as an attacker you have to account for other people using more complex but shorter passwords. I'd still suggest getting capitalisation, punctuation or at least a number in your phrase but the bulk of the keyspace comes from the length rather than complexity plus the fact that the people carrying out these attacks are normally cracking more than one password at a time.

For a few years now (since around the time of Oeschlin's paper[1]) I've been advising customers to use longer passwords made of phrases and things they can remember for passwords they regularly use[2] and randomly generated passwords of some length stored in a password safe[3] for things they might forget. The goal of this advice is to make it harder for people to crack passwords and to reduce the volume of passwords people have to remember.

[1] http://lasec.epfl.ch/pub/lasec/doc/oech03.pdf

[2] http://xkcd.com/936/

[3] http://keepass.info/ - one of many options available

Reply

sspiff3• 14 years ago

Since reading that xkcd, I use phrases as passwords, using a simple Ruby script to generate them:

  w = File.readlines('/usr/share/dict/words').map { |w| w.chomp }.reject { |w| w !~ /^[A-Za-z]+$/ }; 3.times { print w[rand * w.size] }; puts

I generally get an easy to remember password after about 3 tries. The biggest issue I have with this is typing in passwords on mobile devices.

Reply

_ikke_2• 14 years ago

Aren't phrases easier to type on mobile devices than letter / number combinations? I always find it annoying to have to switch to different keyboard modes (text / numbers), or having to hold the letter / number key for a few seconds.

Reply

trebor• 14 years ago

A slight refactoring for Ruby 1.9.3 users, uses Array#sample to grab 3 random words, etc.

    ruby -e 'w = File.readlines("/usr/share/dict/words").map { |w| w.chomp }.reject { |w| w !~ /^[A-Za-z]+$/ }; puts w.sample(3).join(" ").downcase'

Reply

CodesInChaos• 14 years ago

Is `rand` a secure random number in ruby? In many programming languages/implementations the default PRNG is only seeded with the current time, which leads to quite low entropy.

Reply

ZoFreX3• 14 years ago

It's worth pointing out that length is not important, only entropy is important. If you create a really long phrase by forming a sentence from very common English words, the entropy is actually really low, and if everyone started doing this you can bet your boots the password crackers would catch up.

However you create your password you should take a stab at calculating the entropy (and incidentally a 10 character truly random password with alphanumeric+specials will be very hard to crack - it's the fact that the passwords are mutations of a seed word that makes them weak, and not their short length)

Reply

rmc2• 14 years ago

It's worth pointing out that length is not important, only entropy is important

Exactly. This is a weak password: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa" or "qwertyuiopqwertyuiop"

Reply

vonuebelgarten• 14 years ago

> It's worth pointing out that length is not important, only entropy is important.

Entropy is important, but multi-word passwords stills being efficient since their alphabet is quite large when compared with common alpha-symbolic-numeric passwords.

For example, a completely random password with 12 digits and upper/lower case letters have (26+26+10)^12 = 3.226e21 possibilities. Quite good unless you need to memorize this thing. I use such nonsense things for password stored in my password safe.

A password with four very common words (among the 1000 most common words in the user's native language, which I assume the attacker know) have 1e9 possibilities -- very bad. Relevant XKCD for explaining how bizarre is an English text with such restricted vocabulary: https://xkcd.com/1133/

A password with five words selected among the most 4000 words of the user's native language have 1.024e+18 possibilities. Put some uncommon/random/made-up word in the mix is enough to make a direct attack on the password non-viable and force the attacker to search for more elaborated methods. Plus side: is easy to memorize.

Reply

_b8r02• 14 years ago

> It's worth pointing out that length is not important, only entropy is important.

Theoretically yes, as long as you assume the equivalent of a spherical cow in a vacuum.

We've (the security community) become very good at enforcing password schemes that are hard for users to remember and easier for computers to crack. While you could correctly assert that a 30 character long lower case letter only phrase has less entropy than a 15 character sequence of randomly generated numbers, letters of mixed case and punctuation, it makes no odds to me - I'm getting neither of them in a reasonable timeframe.

The reason for this is that if you look at the way web site passwords and company passwords are compromised it's not a single account that's hacked. It's going to be the domain or the database of password hashes. Because you're running all of these through a cracker at once you can't (as an attacker) generally afford to waste the time going through combinations of dictionary words with permutations, especially if you know that if you crack a big enough percentage of passwords you've got the access you need and can move on.

Cracking one 10 character random password with alphanumeric and special characters is a problem of scale with the password generaton algorithm. Depending on the algorithm used you can wait for appropriate rainbow tables to appear to increase your chances, for a cryptographic flaw in the algorithm or for moore's law to catch up. Trying to exhaust the same keyspace for a 30 character password (bearing in mind that the attacker is unlikely to know whether or not your password is high or low entropy, especially if other cracked passwords imply a high entropy policy is in place) is going to be much harder, and will only likely take place if no results of value have been found earlier on.

Reply

RenierZA• 14 years ago

Can someone please explain why GPUs are so much better at brute force than CPUs?

Do they have better instructions/pipelines for the math needed? Why are these not useful/implemented in general CPUs?

Reply

Fixnum• 14 years ago

Roughly speaking, CPUs are highly optimized for sequential execution, with long pipelines, high power consumption, and complex implementations of arithmetic/logic instructions (I'm not an expert, but I _believe_ these are much _better_ than on GPUs, except possibly for certain graphics-related GPU primitives), but relatively few threads. GPUs are optimized for parallel execution, and run many more threads than CPUs, each with higher latency, but nonetheless with higher overall throughput.

Reply

skriticos2• 14 years ago

Cute. Following Bitcoin hash generation process, this looks like a toy. FPGA and ASIC hashing would be news on par with contemporary hash generation on smaller scale. This is just a better room heater. (i.e. hashing/W ratio is bad).

Reply

himlion• 14 years ago

On the other hand hashing/$ invested is pretty good compared to fpga.

I don't think there are any vanilla SHA asics on a modern production process.

Reply

ck2• 14 years ago

Also makes me think we should be using AES256 at a minimum with SSL and not AES128 anymore.

With AESNI acceleration available on most servers, there is little penalty to upgrade.

They say AES128 is safe until about 2030 but who knows if that took into account super-GPU clusters.

(insert imagine a Beowulf cluster of these... comment here)

Reply

pkorzeniewski• 14 years ago

Recently I was thinking about alternative ways of implementing authorization security and I had, maybe a silly, idea - wouldn't it be more secure to always log user in and when given a wrong password, "simulate" (generate) account data? In my opinion it would be much harder to write an algorithm detecting if account data is real or not, and isn't the point of cracking to get access to user data?

Reply

shocks• 14 years ago

I wonder how much heat this this generates? How does it stay cool? I have two GTX 670s in SLI and they can get to about 60 degrees with a gap between them... This many cards sandwiched so close must get really really hot. I don't see any water cooling...

Reply

lallysingh• 14 years ago

Can I rent something equivalent from Amazon by the hour? I wonder how much that would cost.

Reply

mrb3• 14 years ago

No. Amazon only has Nvidia hardware in their EC2 GPU clusters. Nvidia is not equivalent as it is significantly slower than AMD/ATI hardware for password cracking. Eg. a top-of-the line AMD GPU brute-forces MD5 hashes about 5x faster than a top-of-the-line Nvidia GPU, see: http://golubev.com/gpuest.htm

I don't know any computing provider who rent out AMD GPUs... (This would be a startup opportunity.)

Reply

dj_sa• 14 years ago

My password is 24 chracters long, and fully random. I don't memorise it. I use Aladdin to type it for me. http://igg.me/aladdin-key

Aladdin is trying to improve the current situation of people using simple or identical passwords everywhere by removing the need to memorise passwords. Aladdin works with Windows, Mac, Linux as well as Android and iPad.

Aladdin is a USB key(board). No software needed.

Reply

New 25 GPU Monster Devours Passwords In Seconds

Related Stories