Cracking Passwords In The Cloud: Amazon’s New EC2 GPU Instances
stacksmashing.net
stacksmashing.net
This is an incredibly disruptive thing for Amazon to do. They've just brought near-government grade crypto-breaking capabilities to the mass market.
No, they really haven't. Near-government grade KDF-cracking capabilities will be when Amazon announces FPGA Compute instances.
In an interesting twist, The Register claims that Achronix's decision to use Intel was driven in part by national security considerations. We've reported extensively on the idea that chips fabbed overseas in insecure facilities could contain hidden kill switches or backdoors that would let an opponent cripple the US military, and Achronix allegedly wants to be able to sweeten its pitch to military customers by offering a home-grown solution.
[1] http://arstechnica.com/business/news/2010/11/intel-shifts-st...
Cool stuff, and all the more intriguing considering that Intel's getting involved.
Bang-for-buck is pretty much the name of the game in brute-force cracking. You're right that NSA probably doesn't have any budget constraints, but they'd still be interested in getting the most hashes/second possible out of $10 million.
For every instance you an go out and get they probably have a football field sized room full of stuff twice as fast.
The major powers have particularly good access to kit and people. There's a significant number of countries for whom this is actually more than they have (in fact I know of two or possibly three countries where the full capabilities definitely supercede existing ministry of interior type capabilities).
Basically, if your WPA network is vulnerable now, it already was vulnerable. A decent password and non-default ssid will still slow people down.
Are there legitimate uses for password cracking or is this about getting access to other people's accounts?
We sometimes crack passwords to do a password strength audit. Sometimes dictionaries aren't really enough (as someone might have chosen an obvious word in another language) so it's easier to just crack the passwords, automate analysis of the obvious and then scan through anything left behind.
WPA-PSK cracking is particularly useful in the UK Local Government sector, where local government in most cases needs to have an annual penetration test, often including their wireless networks. A lot choose WPA-PSK because it doesn't mean spending money on a full-blown wifi network.
The other thing we use password cracking for is when we do incident response work. Sometimes people encrypt things like documents or use PGP containers. This isn't quite making PGP cracking feasible, but certainly the majority of encrypted word documents should be doable with this.
EF8420D70DD7676E04BEA55F405FA39B022A90C8 "Password!"
5BAA61E4C9B93F3F0682250B6CF8331B7EE68FD8 "password"
A9993E364706816ABA3E25717850C26C9CD0D89D "abc"
1902E3D6FC4E78A0BCC50BA12B882769AFBF4A8C "bad"
8F2005004F8BAA7A1090A9BF3B03C48D38E78157 "P4s$"
CD3724AC40034097A3D27865D710E4F791B6AEDB "Bwah"
7110EDA4D09E062AA5E4A390B0A572AC0D2C0220 "1234"
http://stacksmashing.net/blogfiles/2010_11_15/sha1_hashes.tx...
The article says 1 to 6 character passwords. With 12 cores, I can enumerate the full printable ASCII character set in about 30 hours, but I would not try to do that. I would use patterns and word lists first. After 6 to 7 characters, brains begin beating the hell out of brute speed.
DA39A3EE5E6B4B0D3255BFEF95601890AFD80709 "" no_pass
0D824508182A1AA0EEF9A0B6EE52F8A32AF06F0A "GoOd!" brute_5
A94B95A7A4D432DE056B0030DA879AF841376069 "GPGPU" brute_5
BFE06C47BE2390ACA934AB6A128C141DCEB4072F "G0o|)" brute_5
My point still stands. These should have been better/stronger hashes. I did all of that in less than an hour on a CPU using full enumeration (aka brute force).
This just shows ignorance about hashing functions, especially fast ones. If they had used SHA-512, or say SHA-65536, it wouldn't be any more secure against brute-forcing / dictionary attacks. Barring SHA1 being cracked - ie, finding an efficient way to find SHA1 collisions - ie, "reversing" SHA1, it's no more deprecated than any other non-cracked hashing function.
About your only option is s/bcrypt, or something similar, which are intentionally slow / hard, to defeat brute-force attacks like this.
If computing power doubles every 2 years, then every two years we should bump up the required password length to match. If each character is randomly chosen from amongst 2^6=64 possibilities, then every 6 years we add 1 to the number of characters required.
For instance, if today we require 12 character passwords, which are clearly uncrackable even with Amazon's fancy new GPU instances, then in 2016 we require everyone update their password to a minimum of 13 characters. Every six years we bump it up again.
I think people vastly underestimate their ability to memorize passwords (just think how many phone numbers you probably had memorized back in the day). You could probably memorize passwords thousands of characters long if you bothered, and the only problem is that it would take too long to type them in.
You only need one long password, and all others can be stored in an encrypted file. This is not much to ask.
Bcrypt and scrypt look great, but not fundamentally any better than longer passwords.
Scrypt is better than longer passwords because it's actually possible to implement in practice.
So just drop IE6 support - those people will soon wake up. But that has its own problems. If 10% of my users use IE6, and I drop support for it, that could have a significant effect on conversion rates and the like. Those people are going to do something else, maybe even go to a competitor.
The same applies to passwords. If, say, tumblr suddenly required 12 character passwords, then it would be quite a hit to their signup rates. This is simply not going to fly when there exists far less drastic measures (i.e. scrypt).
You merely require them to use longer passwords, and require them to change them every year. My university does this. They require a minimum of 8 characters, and they require that we change our password every 3 months or we can't log in.
[1] Meaning: anyone who wishes to use the service but isn't willing to come up with an unending stream of genuinely different passwords for it.
Overly onerous password requirements reach a point where they no longer increase security, they just shift vulnerability to a new area. They also piss off users.
Section 8.5.10 Passwords must be at least 7 characters long.
Section 8.5.11 Passwords must contain numeric and alphabetic characters.
A technical-only solution is infinitely better than one where you try to change user behavior. You think memorizing a long password is easy because it's easy for you. Try telling that to someone who's 72 and just started using the Internet.
The reality is that anything that reduces friction to adoption is almost always a positive choice for any given company. There are exceptions, like banking, but for the most part, this is true.
This all ignores the fact that longer-length passwords are almost completely pointless, anyway, for a ton of reasons:
(1) The data you store on behalf of the user is probably not important enough to warrant the (very strong) inconvenience.
(2) Proper password storage ((b|s)crypt) can already mitigate a lot of these risks. If tuned properly, even a 4-character bcrypt password can become more computationally difficult to "reverse".
(3) Short passwords can be bruteforced over the wire? Well, you can prevent people from doing this. You control the environment and can make brute-forcing attacks against your login mechanisms unfeasible.
(4) For this to matter at all, some attacker has to steal the entire authentication table with all of the hashes. If that happens, the number of ways you're fucked is much larger than just your users having to change their passwords where re-used elsewhere.
Fundamentally, for most use cases, it should be a user's choice to opt to use a longer password that would be more difficult to crack, or use a shorter password for convenience.
Google already does this by showing a password strength bar when choosing a password. Unless you store very sensitive data, who are you to make that decision on their behalf?
Some UNIX geek once wrote a tutorial saying that good passwords have a random collection of uppercase, lowercase, and punctuation marks. It's too hard, so people just use "Pa$$worD".
These are all general purpose hash functions, designed to calculate a digest of huge amounts of data in as short a time as possible."
See the rest here: http://codahale.com/how-to-safely-store-a-password/
That's a weakness, not a strength. If you can only calculate 100 hashes per second, it will take a lot longer to crack a password than if you can calculate 100 000 hashes per second.
Ideally, use http://www.tarsnap.com/scrypt.html (made to be computationally annoying to brute force).
I think the word "annoying" here wins you the understatement-of-the-day award.
That said, you need to do more and move beyond SHA1 since you can now reverse a SHA1 into plaintext with the computing power EC2 gives you.
Can you know it was the same plaintext that went in? No, but as far as the SHA1 output is concerned, it's a suitable input and a suitable reverse.
For the application we're discussing, the fact that collisions can be engineered is sufficient to generate a reverse of the hash. At no point do you need to generate the original input in order to reverse it for this application.
best analogy for a hash is smashing a plate. you may be able to glue it back together but it is not the same plate
btw I wonder how long before somebody calcs and loads a rainbow table onto AWS and charges for lookups. so tempted...
Runs a WPA cracker against your provided pcap files for $17- $40, depending on how fast and how extensive a word list you want to use. (Yes, I realize they aren't using rainbow tables, but WPA uses the SSID as salt, so that wouldn't be as usefu.)
> you can now reverse a SHA1 into plaintext
So "foo" could hash to 1 and "bar" could hash to 1 also. It doesn't mean 1 means foo, but it means if your password is foo, bar works too when hashed and compared against a stored hash.
But this only works for small numbers of characters. You cannot inverse-hash a book length document. You also still can't inverse-hash a 16 character or probably even 12 character password.
This fast hashing stuff is only a problem because people use ridiculously short passwords. The examples in the article are a lazy, pathetic 6 characters. I think people vastly underestimate their ability to memorize passwords. For instance, I am able to memorize a 16 character password by just writing it down a few times and then testing myself. And since I can remember many such passwords, I could easily memorize 32 character passwords, which are probably impossible to crack for the next 50 years or so. And you really only need to remember one such password, because all your other passwords can be put in an encrypted file.
Edit: Wrote up this comment before the one about scrypt. It also looks nice, but it looks like there's no or only primitive language bindings available.
Second, store passwords as a salted hmac, not just a shaXsum. It is still usually a singel command, and WAY more secure than simple shaX or mdX, as it eliminates the risk of prefix/postfix attacks. Adding the salt makes dictionaries pretty irrelevant (as long as each install has a unique salt).
I mean GEEZ; even php does it now: http://us2.php.net/manual/en/function.hash-hmac.php
Also, a salted hash is not a particularly good storage mechanism, ranking only above cleartext and naively-hashed storage. Once someone discovers the salt, then it's fairly easy to attack the password database in the same way that you'd attack an unsalted hash -- make a list of all possible passwords, hash them, and see what matches. Machines like the one mentioned in the article can make trillions of these in a second. The problem with hashes for protecting passwords is that they can be calculated very quickly; good for ensuring that every packet on your VPN arrived without errors, bad for ensuring that a bad guy can't make a list of passwords, hash them, and check the hashes against your database.
The best password storage mechanism is via the use of a "slow" hash function like bcrypt or scrypt. You set these up so that it takes a full second of CPU time to generate the hash from the message. Then instead of trying trillions of passwords a second, the attacker can only try one!
If you're using Perl, use Authen::Passphrase. It's a module that lets you easily use bcrypt for new passwords but your old method for older passwords. With an API like that, there's no excuse for endangering your users by using salted hashes!
Nonce-per-password is used in BCrypt and while I don't know much about security, that's the vibe I'm getting from the folks who do.
Listen to 'jrockway.
Also, one of the teams used Amazon servers during the 2010 Defcon Crack Me If You Can contest. Here is their write-up: http://contest.korelogic.com/team_CrackHeads.html
The same with passwords, they imply a word. A much better solution is a pass phrase. As far as the system is concerned, functionally identical. But to the human mind, a completely different animal. A word is a word, but a phrase is limitless. With proper punctuation and capitalization, it has everything that makes a good password good: A-z, symbols, length. Except, being a phrase, it has an edge to a long complex password: you can remember it. A phrase has a beginning, middle, and an end.
That said, for the most part people who chose weak passwords do so for ease of memory, not because they're so stupid that they think they are only allowed words.
http://dev.myunv.com/articles/secure-passwords-with-phpass/ http://www.openwall.com/phpass/
You can use PBKDF2 as a password hash (even though it too is designed mostly to turn passphrases into keys), because PBKDF2 is iterated to slow down brute force attacks.
http://www.webtvwire.com/linking-law-expert-dr-stephan-ott-t...
IANAL but I suspect the OP feels the same laws could be applied here.
http://www.securityfocus.com/brief/567 http://www.schneier.com/blog/archives/2007/08/new_german_hac...
This has had a chilling effect already
for instance
http://en.wikipedia.org/wiki/Hydra_%28software%29
On September 2007, to comply with new German laws regarding distribution of hacking tools to the public, THC stopped making the program available.