New 25 GPU Monster Devours Passwords In Seconds
securityledger.com
securityledger.com
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...
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).
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.
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-...
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.
Depending on how widespread this behaviour is, while 90-95% of linkedin passwords were easily cracked, that might not generalise to all sites.
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.
This is not, strictly speaking, true. You are talking, I believe, about Lanadauer's principle [1]. This states that it is the destruction of entropy that costs energy. There are computational methods that can theoretically avoid these energy losses [2]. In fact, Lanadaer theorized about reversible computing in his original paper [3].
Bremmerman's limit, mentioned below, is more applicable.
1. http://en.wikipedia.org/wiki/Landauer%27s_principle 2. http://en.wikipedia.org/wiki/Reversible_computing 3. http://www.cc.gatech.edu/computing/nano/documents/Bennett%20...
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.
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).
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
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)
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.
> it makes no odds to me - I'm getting neither of them in a reasonable timeframe
There's nothing wrong with a passphrase as long as it can't be gotten in a reasonable timeframe, obviously! My point about generation stands, though - no password scheme stands in a vacuum, and if whatever you do catches on, you can guarantee software will be made to exploit the low entropy passwords on that scheme (for example, attacks can now include tricks like taking the website name - LinkedIn - and performing common mutations to generate passwords to attempt: L1nk3dIn1)
If it became really common, people would make rainbow tables for it too. All you'd need to do is create a reduction function that maps back into the set <passwords formed from concatenating common words> :)
This applies to all forms of password generation though: ultimately, entropy is important, and if you care about your security you should know whether the entropy levels of your passwords afford you the security you want or need.
Exactly. This is a weak password: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa" or "qwertyuiopqwertyuiop"
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.
So, for example, if you used a multi-word password on your ATM machine, and someone aimed an infrared camera at the machine after you left and retrieved the set of buttons that you pressed, the game would be over if your password were short--or at least much closer to being over if it were long.
Alternatively, an attacker could eavesdrop on your keyboard sounds and capture the timing of the clicks, thereby inferring candidate sets of letters. Or they could examine how much oil is on each key of your keyboard, or how much each key is worn, and adjust for the stats on the English language, etc.
Or, as in the ATM case, an agent could interrupt you right after you've entered your password on a false pretext ("Excuse me, I need help.") and surreptitiously take an in infrared photo of your keyboard. This is plausible in many semi-public scenarios (bank teller, etc.)
I think the saving grace here is that a sufficiently long password uses most letters in the English alphabet--but it is still prone to attack if you can at least get the relative ordering of some of the letters, or you know the password's length (by listening to the number of keyboard clicks, for example).
By the way, it's a bit easier to discuss bits of entropy rather than number of possibilities. Assuming each possibility is equal (which is NOT true if you pick the password yourself, rather than randomly) then the entropy would be the logarithm of the no. of possibilities. Generally people use base 2, so:
Random 12 digits alphanumeric: 71 bits of entropy Four common words: 30 bits of entropy Five words: 60 bits of entropy
The multi-GPU cracker on the frontpage today would take 500,000 years to crack the 5 word password if it was stored via bcrypt (according to the article, which sadly did not specify the work factor). The four common words one, however, would fall in just four hours!
P.S. It isn't actually hard to remember a complex password. Almost anybody can do it! The passphrase method is actually not dissimilar to the technique I use. Say the password started "OK53B3" (I just generated this in LastPass). OK, let's figure out a way to remember it. OK, I thought of a way to remember the first two letters ;) 53.. 54 cards in a deck with the jokers, so we've lost a joker. "OK, guys, we've lost a joker" "B3" sounds like someone with a few missing teeth saying "be free!" so I'm imagining a toddler throwing the joker out of the window going "be thfree!"
Very rapidly this will shortern as your memory of it strengthens with repetition (if you're entering this password every day - I recommend using a password manager so you have just one secure password you enter every day). After a few days it will be "OK missing joker be three" etc then just the password itself. After a bit longer it just becomes muscle memory - I couldn't actually recite it easily anymore, but I type it in seconds.
The important thing though from an entropy perspective is that whether you are making a story for your passphrase or for your password, the story comes second. Generate the password / passphrase and then create a story, this assures that each possibility is equal as I mentioned earlier (if they are unequal, there is less entropy).
Of course, I recognise that even with a good memorisation technique, passphrases still beat out f%8D( from a learning curve, ease of use, and accessibility standpoint. The reason I've stuck with the ugly and relatively short passwords is purely so I can type them in as fast as possible!
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
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'The error rate on a touchscreen keyboard is high enough to really become a problem at 20+ characters when you only see the last typed character (no password review).
It could also be keyed in via something like Swype or SlideIT in almost as fast as it could be keyed in on a computer keyboard.
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).
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.
It might be better now with faster JavaScript engines, but I wouldn't bet on it.
That said, I'd be curious to know how long it'd take a device like this to decrypt "secure" AES256 text.
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].
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.
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.
A retinal print?
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.
(Hi Jeremi, nice work!)
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)
I don't think there are any vanilla SHA asics on a modern production process.
Do they have better instructions/pipelines for the math needed? Why are these not useful/implemented in general CPUs?
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...
When is this not the case?
I would love to see research about the use of keys and passphrases. Especially, do people who have a key then chose a weaker master password?
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.
Possibly worse, 1Password used to have a mistake in their key generation algorithm that means you could verify a password without the time-consuming key stretching, effectively making it thousands of times faster to crack. JTR doesn't use that method though.
I don't know any computing provider who rent out AMD GPUs... (This would be a startup opportunity.)
No it doesn't. My passwords are 30-character randomly generated and look like this:
T7PN2m7Yju43IWtoBkwL6TLx18Rdyq
(26 + 26 + 10)^30 = 5.91 × 10^53 possible combinations
1.53 × 10^42 seconds
4.84 × 10^34 years
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.
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
This should be part of your risk assessment. For most people and most passwords the risk is not someone riffling through your wallet to find the card with your 30 character password. The risk is from criminal gangs hacking a system and downloading a huge database of usernames / password hashes, and then performing an offline attack on those hashes.
For most people writing a good password down and keeping the password safely is better than using a weak password.
That´s why I use a 'throwaway' password for most unimportant accounts. Sure, may be easy to break, but it isn't logging in to my gmail.
Don't forget also the risk of getting locked out of your account.
Just don't re-used passwords _anywhere_ - choose a password generation/storage solution that works across all your devices, and use it to generate unique strong passwords for everything. (1PassWord + DropBox works great for me across my MacOSX, iOS, Android, and Windows devices - I occasionally would like it on Linux too, but rarely enough that I'm satisfied to use my phone and re-type passwords in Linux)
My beef with 1PW is that it's a single point of failure, not to mention inconvenience/risks. For example, what if I need to check gmail in a trusted, but borrowed device.
The main issue I think is that using only one password for security is insufficient (but not necessarily go for a 2-factor auth)
(Though in the complete disaster scenario, I have stored in my wallet, as suggested by Bruce Schenier, the app-password my phones use and the list of backup verification codes - unlabelled so a casual thief _probably_ won't know what to do with them... I've also got irregular exports of everything and the 1Password passphrase and phone PIN printed out and stored in an envelope in the office safe. I _think_ I'm sufficiently paranoid about all that...)
> 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.
> 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.
Hashes don't tend to have side-channel attacks.
(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)
I use KeePass, with a copy (via dropbox) on my smartphone for when I'm not at my own computer.
Surely this is an embarrassingly parallel problem that practically balances itself?