Cracking passwords with 25 GPUs

Security Ledger reports on a breakthrough in password-cracking, using 25 graphics cards in parallel to churn through astounding quantities of password possibilities in unheard-of timescales. It's the truly the end of the line for passwords protected by older hashing algorithms and illustrates neatly how yesterday's "password that would take millions of years to break" is this year's "password broken in an afternoon," and has profound implications for the sort of password hash-dumps we've seen in the past two years.

A presentation at the Passwords^12 Conference in Oslo, Norway (slides available here), has moved the goalposts, again. Speaking on Monday, researcher Jeremi Gosney (a.k.a epixoip) demonstrated a rig that leveraged the Open Computing Language (OpenCL) framework and a technology known as Virtual Open Cluster (VCL) to run the HashCat password cracking  program across a cluster of five, 4U servers equipped with 25 AMD Radeon GPUs and communicating at  10 Gbps and 20 Gbps over  Infiniband switched fabric.

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.

In a test, the researcher’s system was able to churn through 348 billion NTLM password hashes per second. That renders even the most secure password vulnerable to compute-intensive brute force and wordlist (or dictionary) attacks. A 14 character Windows XP password hashed using NTLM (NT Lan Manager), for example, would fall in just six minutes, said Per Thorsheim, organizer of the Passwords^12 Conference.

New 25 GPU Monster Devours Passwords In Seconds [Security Ledger] (via /.)


      1.  Oh, I see. In that case “The end of the line for passwords” and not mentioning that you need a whole database seems very poor journalism.

        1.  Oh, database was my word. I just wanted to imply a large file of encrypted passwords locally stored. I guess this is a white hat technology demonstration to prove that the password era is doomed, I didn’t read the whole article.

    1. This is for brute-forcing the hashes of passwords; it assumes that you’ve obtained the hash. Not difficult to do for the password to get into your computer, but it would require breaking into a website to dump their hashes if you were to try and break into, say, someone’s email account. 
      But there have been a lot of high-profile hash dumps in the past little while, and this shows that those passwords aren’t secure. If someone *does* happen to break into and dump the hashes of a website, and those hashes were made using an older algorithm, then it won’t be difficult to crack all of them.

  1. As mentioned on another site, this works fine when the system is internal. However this is not the same thing as cracking over a network not to mention the internet. If they already physically have your encrypted data in the first place you might be in a bit of trouble however.

  2. Ahh, and I was wondering what to get my Chinese and Russian hacker friends for Christmas! Perfect, does it come in red?

  3. This rig is designed for cracking password hashes that you’re in possession of – encrypted passwords stored for the server to compare incoming passwords against.
    A rainbow table for a (strict) 14 character NTLM password hash set where the password uses a-z,A-Z,0-9 has a key space size of ~1.24e+25, which is very, very, very, very large (beyond, beyond, beyond petabyte), and thus infeasible for rainbow tabling (storage space insufficient).

    The upshot of this story is that commercially-available, off-the-shelf, inexpensive hardware is available that will allow a moderately determined attacker to reverse-engineer your original password, from a stolen database of encrypted passwords (hashes), inside of minutes – meaning, if someone stole (let’s say) a 1000-person corporation’s NTLM hash database off a hard drive that was not properly wiped by a tech, they could have all their 14-character-length policy-enforced “strong”, random-noise-generated passwords inside 6 hours 4 days a significantly short amount of time.
    Edit- they updated the article; the 6-minute figure is for LM hashes (as in, exhausting the entire hash keyspace), while an 8-character NTLM hash keyspacewould take 5.5 hours at most, for 100% of a 1000-password corporation’s hash database.

    1. Thanks. I’ve worked with a couple of companies that do security, what is interesting to me is not the brute force methods but all the other methods that use lying, tricking, and stealing to get passwords. (I don’t want to use the phrase “social engineering” because that makes it sound too clever. As with the “pretexting” which is what the called it when people lied to the phone company about the owning of their cell phone to get the password of their voice mail, or in the case of the News of World paper owned by Murdoch where they paid employees of the phone company and their DMV to get info)

    2. This only works against LM passwords because their 14 character passwords are uppercased and then split into two 7-character strings which are hashed separately.  That’s why they can do the 14-character LM passwords in 6 minutes: because they’re really just doing 2 7 character hashes.

      If we use 14 character passwords drawn evenly from the whole 94 character easy-to-type-on-a-standard-keyboard set, and then assume that they were hashed using NTLM (no upcasing and splitting and it’s the quickest password hash they tested against), it would take them 94^14/3.84e11 = 1.2e16 seconds.  There’s roughly 3e7 seconds per year, so about 4e8 years, which is to say 400 million years.  Even a 14 character password drawn from only lowercase letters would be 26^14/3.84e11 = 1.85e8 seconds = about 6 years.

      So, realistically, long random passwords: still perfectly safe unless they do something really dumb in the hash which effectively reduces the length (as LM does).

      1.  Unfortunately, users don’t tend to select passwords that are long and random. It’s pretty amazing how easy it is to crack passwords based on dictionaries and a few common mangling patterns.

        1.  That’s certainly true.  I’m not arguing that passwords are secure, in general, but rather taking issue with the tone which suggests that even if you did choose a long, random password (using something like PasswordMaker or a random password generator) that your password is still in danger of being compromised.  Long, random passwords are secure and are likely to continue being secure for decades, and hooking 25 GPUs together doesn’t make a significant dent in that.

          1. I get what you’re saying. Now how do we convince people to actually do it? The problem with password security is really that it’s only as strong as the user, and their (in)tolerance for inconvenience in the name of security.

      2. The authors state the virtualization package can support up to 128 GPU – a ~5-fold increase in tooling that can be thrown at a task, for just this one cluster. The coordination server needs a large amount of memory, but that’s not out of the reach of a large corporation or a state (or a criminal enterprise). If there’s a way to split the key space being searched so that individual clusters sweep discrete areas of keyspace, that also significantly divides the realtime.

        Anyone with a significant budget, could assemble enough of these systems to begin to search for gaps in the armour of a target.

        1. A five fold increase would mean that the random 14-character password’s search time would shrink from 400 million years to 80 million years.  I think that with those sort of numbers, you’ll get the job done faster if you sit on your hands until processors get faster before starting.

  4. “A 14 character Windows XP password hashed using NTLM (NT Lan Manager), for example, would fall in just six minutes”
    The source article’s been updated to correct this – that’s for LM, not NTLM.

  5. Given all the repeated cases of GPUs doing amazingly powerful non-graphical things, I start to wonder why we aren’t just using GPUs in place of CPUs.

    1. Because a CPU and GPU are two different things.

      The CPU is general-purpose. It handles all your general arithmetic and logic, and the instructions in memory and then executes them. And it handles your IO.

      While the GPU is narrowly focused. The GPU is designed to handle the small parallel instruction sets useful for various parts of graphics processing, video decoding, etc…

      A GPU is actually generally not more powerful than a CPU. If you gave a CPU and a GPU the same set of instructions to run though once on a single set of data. The CPU would likely beat the GPU, and in some cases it wouldn’t even be possible for the GPU to do what you ask.

      The power of the GPU comes from it’s ability to take a single set of instructions, and run those same set of instructions on hundreds of pieces of data at the exact same time. While the CPU would have to run those instructions in a loop one after each other in sequence.

      That’s why GPUs are more powerful than CPUs for tasks like graphics processing where you are applying the same instructions on large numbers of pixles, vertexies, etc… And in this case, password hashes. Because the GPU gets to solve hundreds of hash operations at the same time while the CPU gets to solve one.

  6. What’s worrying about this isn’t the immediate possibilities of this particular rig so much as the exponential upwards curve in password-cracking speed that this extra data point suggests.

    1. Indeed! There’s also the worrying capability of any given state’s cryptanalysis apparatus to buy and assemble (or manufacture) hundreds of these kinds of rigs, and turn them against the encrypted disk images copied from your computer as you pass through customs.

  7. A few months ago I was given the entire database of hashes for my work, without any user identification, to test for password strength and whatnot. Within 15 minutes of starting I had over 30,000 passwords. Using an 8 node general use CPUs, I cracked 97,000 out of approximately 127,000 passwords over a 2 day period. If I had configured the test to use the GPUs, which I had intended to, I may have had even more.

    I’m rather inclined to agree with the assessment of the value of passwords being fairly low these days. We’ve started using multiple rounds of SHA-512 where possible, which really slows down the hash throughput rate.

  8. I was on about this previously, with Cory, but never replied to his reply to clarify why I was saying that leading people to believe encryption is secure is not a good idea. 

    I was actually paraphrasing some leading cryptologists, and former people from the NSA.  They had varioiusly been describing the advanced state of modern crypto-analysis based in supercomputing, as well as brute force password guessing as in the current article by Cory.

    The bottom line is that anything can be cracked, and it is just a matter of time and money.  That is why Zimmerman called his PGP encryption software “Pretty Good Privacy” instead of “Complete Privacy”. 

    People should consider encryption a good way to keep things private from those who are not looking,

    1. I agree up to a point – but as was pointed out above by KeithIrwin, choosing LM as the ‘proof’ that GPU-array haxxors will totally pwn yr TrueCrypt volume is like saying that someone with quick fingers can break yr home deadlock because they can unlock one of those 3-barrel “0-9” bike locks.

      I’m stil comfortable that a decently thought-out AES/Serpent/Twofish cascade (with keyfiles) will be safe until roughly the heat-death of the universe, or the bankruptcy of whatever organisation is trying to brute-force it, whichever comes first.

      von Neumann-Landauer limit FTW, in other words.

      If this story tells us anything, it tells us that Microsoft’s security implementations are, like everything they produce, a half-assed second-rate compromise that still manages to require 5x the LoC of a decent alternative.

      That’s sort of like saying that Dick Cheney is a bit of a dick. It’s not news.

  9. (sorry, intended to reply to Gordon Stark above)

    The goal is not to make information inaccessible. It’s to make it cost more to get access than the information is worth.

    For personal banking details, you want it to be too expensive for the average criminal (or small criminal enterprise) to gain access, so blowfish with a short password is good enough.

    If it’s human-rights/insurgency related in the Middle East and lives are at stake, you’ll want to use something much stronger.

Comments are closed.