Thursday, October 29, 2009

Cracking Passwords in the Cloud: Insights on Password Policies

Previous Post: Breaking PGP on EC2 with EDPR


UPDATE 15 Nov 2010: Amazon announces "Cluster GPU Instances", again radically changing the economics of using EC2 for password cracking.  

We've had some questions about whether or not we are going to re-run our analysis using the EC2 GPU Instances.  We may do so, but in the meantime have a look at stacksmashing.net. The have already got some numbers posted for cracking SHA1 on EC2/GPU.


UPDATE 21 Dec 2009: Amazon announces "spot instances", radically changing the economics of using EC2 for password cracking.  

For years we have been preaching the virtues of long, complex passwords.  Putting dictionary attacks aside for a moment, one of the most interesting revelations of this project was the high cost of brute forcing simple passwords.

By simple here we mean a password only containing lowercase letters a through z.  And by optimistic cost to brute force we mean the EC2 usage charges we would incur to cover 50% of the keyspace.  If we're unlucky, we double the optimistic cost to calculate our "max cost" to exhaust the keyspace.

Clearly each additional character of password length adds a significant amount of cost to the brute forcing effort.  One might speculate that an average corporate adversary could quite easily come up with ~$50K USD to brute an 11 character simple password, but struggle to find the $1.5M USD to brute a 12 character simple password.

Next let's look at the case of a slightly more complex password, containing upper and lowercase a-z, plus the numerals 0-9:



In this case the hypothetical threshold between doable and not worth it falls at the 11 character password boundary.

Finally let's examine the cost to crack a truly complex password, consisting of upper and lowercase a-z, plus the numerals 0-9, the space character, as well as 32 special characters (think !@#$%^&*() etc):

In this case the "not worth it" threshold is at 9 character passwords.

So, looking at this data simultaneously, it's easy to make some recommendations about password length.  Assuming we are dealing with an adversary who is unwilling to spend more than $1M USD to brute your password, where are the length versus complexity sweet spots?


Referring to the chart above, we decide that simple passwords (a-z) are OK, provided they are at least 12 characters long.  Add numbers to your simple password, and again you're OK at 12 characters.  Introduce uppercase and special characters into the mix and 10 character passwords are acceptable.

Now let's consider a slightly different scenario.  Let's look at an 8 character password of variable complexity.  The complexity will start at 26 [a-z] and rise to 95 [a-zA-z0-9@#$ etc.].

Here we see that the cost to crack the 8 character password increases steadily with complexity, and that even fiercely complex 8 character passwords are still fair game for our adversary with <$1M to spend on a brute force attack.

Now let's look at fixing the complexity at a low value of just [a-z] and looking at the effect of increasing the length of the password on the cost to brute force.


Here we see that the cost to crack the simple password consisting of a variable number of just lowercase alpha characters jumps dramatically between 13 and 14 characters.

Remember, dictionary attacks are different than brute force attacks.  So if your 12 character simple password is composed of dictionary words, all bets are off.  Finally, remember that while a determined attacker may not have $10M USD to spend on EC2 cycles to crack your 10 character super complex password, a simple client side exploit may make that a moot point.

60 comments:

  1. what bothers me is that when you tell your accountants to have their passwords 12 chars long then maybe the "hacker" won't have to crack them... there is a big probability that with pass this long our accountant will just write his password down.... and u know what happens when someone writes his password on a sheet of paper...

    ReplyDelete
  2. Writing down a password is not as foolish as might appear. See the discussion here:

    http://www.schneier.com/blog/archives/2005/06/write_down_your.html

    Counter intuitive? Absolutely! Insecure? Not so much.

    So thanks to this article we now know how hard the password in your wallet needs to be.

    ReplyDelete
  3. Extremelly useful analysis, thanks for your work and openness on this topic. That will help many to define acceptable complexity and password size.

    ReplyDelete
  4. I think xkcd can with some perspective here:

    http://xkcd.com/538/

    Anything more than an 8 character simple password, you're going to get a "wrench attack" if anyone cares enough about your data.

    ReplyDelete
  5. You are totally ignoring CUDA (high end NVidia graphics cards) when giving your password recommendations.

    CUDA can crack passwords about 10 to 100 times faster than CPUs can, and costs less.

    ReplyDelete
  6. Regarding the scenario that is written down next to the computer: if physical security is compromised, you got bigger issues than the specifics of cryptography.

    ReplyDelete
  7. > and u know what happens when someone writes his password on a sheet of paper...

    A hacker will turn on his victims webcam and read it from the paper? He will resort to physical breakin because he can see that the password was 12 character a-z long and know he will probably find it somewhere on the victims desk?
    I know written down passwords are evil, but I also know that they are terribly more secure in a whole lot of cases than the alternatives. Unless one suddenly finds a cure for the common "most humans are not good in remembering literal complex strings and can certainly not be bothered to try"-problem :-)

    ReplyDelete
  8. One problem with that analysis, which is interesting for sure. Botnets are free. People hacking passwords are very likely to have access to botnets. So I wouldn't base my password length just on assumed cost. Why do that, when I can add few more chars above 12 chars, and make it inviable to be hacked with all the computer power on the planet for the foreseeable future.

    ReplyDelete
  9. Great write up, thanks for the effort!

    ReplyDelete
  10. ... some IT guy comes by and whinges? Yes, that's the worst. I'm a big fan of pass-phrases - some obscure but easy to remember set of words with spaces and punctuation.

    ReplyDelete
  11. Great analysis. Thanks. I have always added special characters to my personal passwords, now I will quit that and just make the looong.

    ReplyDelete
  12. Writing passwords down is not the act of stupidity sone people like to make it. Now, putting your password on a postit on your monitor or in an unlocked drawer - that's grounds for a whipping.

    ReplyDelete
  13. ... god kills a kitten?

    ReplyDelete
  14. So it's good to use a passphrase that you can easily memorise. Such as "use amazon cloud to crack this password, asshole" then you don't need to write it down, it's infeasible to crack and you should be pretty safe.

    I think the issue is though, there are far better ways of getting the data you want. Keyloggers, tempest, virii that grab a decrypted version from RAM, torture and bribery.

    ReplyDelete
  15. Off hand, many feel that writing your complex password down makes good sense. People are inherently better at physical security:

    http://www.schneier.com/blog/archives/2005/06/write_down_your.html

    In many cases this is the only approach to prevent password reuse, or pattern reuse, which can pose significantly more risk.

    ReplyDelete
  16. Awesome article, ingenious approach. Thanks for the figures, they will be very useful in future security work I do.

    ReplyDelete
  17. @arvind

    Writing passwords down is OK as long as they are kept in a well protected place (like a wallet).

    ReplyDelete
  18. Excellent article, really enjoyed it.

    ReplyDelete
  19. It's really outside of the scope of this document to discuss people's willingness to write down their passwords to remember them. I don't see how your comment was relevant or helpful in anyway.

    ReplyDelete
  20. @Arvind - yeah we know what happens: you have to break into someone's house and find that slip of paper. A bit riskier than spending a few K on breaking a weak password, no?

    ReplyDelete
  21. I have to (partially) disagree with Arvind. The key point is to make it easy to use the longer passwords. My personal experience is that even the most comples passwords can be memorized in a surprisingly short time. For me, at least, the lesson is that your accountant needs an easily taught process to generate 12 letter passwords that are easy to recover *if you know the process*. For example, I frequently generate passwords using the first or last letters of the words of a paragraph from a recent magazine, which gets recycled once I've memorized the password.

    ReplyDelete
  22. Thats why I always advise that they DO right them down. But, leave part of it out, a part they will always remember, like a mini password inserted somewhere within the passphrase (i.e. password = x2wr5ty$.37tu and write that down! Then the real password would contain the year i was born would replace the "$" or the ".".)

    ReplyDelete
  23. There is something wrong with some of your charts.

    On chart #3( [a-zA-Z0-9[:punct:]] )
    the cost for bruteforcing 9 characters is $10 million.

    But on chart #4 the $10 million is attributed to a 10 character length password.

    ReplyDelete
  24. What worries me is the very low cost of cracking normal 8-9 characters passwords. Just few bucks! That is something that governments can afford in massive scales.

    ReplyDelete
  25. I find one parameter missing: What about countermeasures like hashing a password repeatedly a few million times or, e.g., for 100ms? These are used in some products at least. How much effort does PGP/GnuPG spend on this?

    ReplyDelete
  26. @Arvind

    Writing a complex password down on a piece of paper ensures that nobody without physical access to the paper can crack your password. This can be desirable!

    http://www.schneier.com/blog/archives/2005/06/write_down_your.html

    ReplyDelete
  27. Interesting password length discussion, but why aren't you taking into account Moore's Law? It also depends on how long someone is counting on using a password to secure their data for. A 12-character password now might be very expensive to crack, but give it 5 years and it's a lot easier. It's like all those people who have 512-bit PGP keys from the early-to-mid-1990s who are still using them - they seemed impossible to crack at the time, but now anyone can crack them on a desktop PC in a month.

    ReplyDelete
  28. Long passwords are easy to remember, if you help your employees out with this: Use a sentence.

    "I love my dog."
    "My niece is cute."
    "This job sucks goat balls."
    "Log me in, please."

    Even if you assume the period at the end, you still have to brute force everything else.

    ReplyDelete
  29. There's nothing inherently wrong with writing a password down until you are familiar enough with it, it's the practice of leaving said written password lying around as though it's not important that creates a problem.

    http://www.schneier.com/blog/archives/2005/06/write_down_your.html

    Provided the paper password is treated with security consideration, it's a useful way to give you enough time to remember it, or if its for a site not often suited, stored in a safe place for retrieval should you forget it.

    Alternative is that people will use the same password for all websites, since that's the only way they can remember it.

    ReplyDelete
  30. True, but its basic security that your users are your weakest link. Long passwords mean they'll probably write them down, but the length of the password won't help at all when someone's threatening a users life for their password.
    Better to make it a combination of things with a way of subtly signalling coercion, generally a special keyword in place of a password. But really that's only doable for authentication.

    ReplyDelete
  31. Arvind: A good password is never a replacement for an idiot employee.

    ReplyDelete
  32. Bruce Schneir has argued, that as long as you keep your password note with your credit card, and take equal care, it is o.k. And that means it is perfectly reasonable to require long passwords. I also suggest that an organization needs a clear policy how users must create passwords. For example "based on initials of a phrase that is in your long term memory", like the PGP manual suggests. It amazes me, that almost no organization has this kind of positive policy guidance. Mostly they just warn of bad passwords, without telling how to create a good one.

    ReplyDelete
  33. One phrase:

    Pass-sentence.

    I may forget, or write down: ih4v3Ar3a11yL0ngP4ss.

    However, I'd likely be able to remember, and therefore *not* write down:
    My first car was a 1976 Chevy, that I bought 03-21-86.
    This has, numbers, symbols, case and would also be nightmarishly expensive to crack per the article, no?

    ReplyDelete
  34. Ok, please make those graphs use a log scale on the vertical. It makess them tons more usefull, as you're tracking an exponential expansion, etc, etc.

    ReplyDelete
  35. So the moral to the story - don't use passwords.. use other means like two-factor with simple pins/keyphrases and a constantly cycling variable piece.

    Passwords were always the worst solution.. we can train people to remember ATM pins most of the time.. and they have cards.. so two-factor is a skill they already have.

    Now if only there were really effective inexpensive two-factor providers out there.

    ReplyDelete
  36. What I figured a while ago is that a "password" is hard to remember and not all that secure, while a "pass phrase" is easy to remember and very secure. The big problem is getting people to type it in each time, but eliminating a lot of the special character requirements is probably worth it to the average user, especially if they don't have to retype it too often.

    ReplyDelete
  37. Well, the article is clearly focused on one aspect of security. Security in general is a complex issue and should always be approached holistically.

    For example, an important financial factor to consider is the cost of hiring thugs on the local market. If the cost of cracking the password is significantly higher, a determined attacker will hire thugs who will make people reveal their passwords in no time.

    ReplyDelete
  38. Have you considered this client side exploit? http://xkcd.com/538

    ReplyDelete
  39. Interesting analysis, but I think you're leaving out one detail:

    If an adversary is trying to brute-force a password that's simply encrypted (I'll leave the issue of salt aside), he will know the length but not its complexity. That gives him the ability to assume high complexity and know with certainty what the maximum cost will be to achieve a solution.

    An adversary with a digested password has an cheap escape hatch if he knows the algorithm was one prone to collision attacks (MD5 in 2^32 or SHA1 in 2^52).

    Otherwise, with a not-yet-broken digest algorithm (e.g., SHA-256 or Whirlpool), he has no a priori knowledge of the password's length or complexity, which is going to force the assumption of high complexity and unknown length. The unkown length automatically puts the solution into the high-priced "very long" bracket, but also adds the cost of computing everything shorter. It looks like that adds about 4% to the cost, which is trivial compared to the "long" cost but is a lot in real dollars.

    With just about everything using digested passwords and anything really important using good algorithms, social engineering and ThugWare become awfully attractive options.

    --MF

    ReplyDelete
  40. flawed artical.
    1) you assume the last password is the correct one.
    2) you assume hackers have been waiting for cloud computing to come along before they can crack passwords with speed.

    also your cloud passwd cracker is only doing 2,600,000 passwords a second which isnt very good.

    A hacker with a few grands worth of CUDA gfx cards could achieve a lot more.

    A hacker with a root on a super computer could do more again.

    And a hacker with a botnet of 250,000 independently cracking a password would be faster again.

    If that hacker with the botnet added CUDA support and had the nodes intelligently crack the password it would be one of the fastest cracking devices in the world for free.

    ReplyDelete
  41. Local security company suggested to write down your passwords, but leave something out from it...

    Your password is: s83=#sr1!"#QhHfd
    Write this on paper: s83=#sr1QhHfd
    Remember this: !"#

    Here:

    s83=# is just random text
    sr1 is string which you identify server to login
    !"# is passphrase to remember "add it before last fifth char"
    QhHfd is just some more random text

    Change order, length and amount of these components. This gives pretty good protection against brute forcing and password stealing.

    Also having your passwords on post-it saves from very expensive EC2 time... :)

    ReplyDelete
  42. Your password length discussion is possibly incomplete. Any in-depth discussion really needs to look at the technical details. Older versions of windows stored passwords as chunks 7 characters long (for passwords up to 14 characters I think). So a 12 character password might be cracked easily as two chunks, one 7 char, one 5 char. The thinking was that would be trivially easy to crack (especially for a-z)or to use a rainbow table. This was probably improved in later versions of windows, but who knows if the registry key for "maintain backward compatibility" (perhaps used for AFS connections) is turned on, and reverts to the old behavior.

    My default for a system I care about is a passphrase 15+ characters, containing all a-z, numerics, spaces and a few special characters. On the other hand, I would probably sell it to someone for offers of $100 :-)

    ReplyDelete
  43. that's so cool, most of you think that it's easier to crack the password than to obtain it non-technical way...

    good for you, you must live in a wonderfull world. And that link you gave me?

    "I recommend that people write their passwords down on a small piece of paper, and keep it with their other valuable small pieces of paper: in their wallet."

    yeah sure, and also, attach a business card to your keys so if anyone finds it he knows where to give it back... I mean, there is no chance that someone will use it in "bad way" right? I mean u just gave him the key and the address of your home...

    damn..i belive that when you have a bypass card to your server room u also sign it with room number and have this nice company branded strap connected with it... just great.

    ReplyDelete
  44. "Arvind: A good password is never a replacement for an idiot employee."

    sure but good policies are.

    "just hide it in some secure place, like your wallet"

    that actually made my day. Sure, wallet is the most secure place ever. Actualy I think wallets get stollen a lot more times than peopel hack into some security systems or break in some secured places... so, hey, nice one m8.


    One and only way to make people remember their password even when they are longer than - OMG OMG OMG - 10 chars is to EDUCATE YOUR EMPLOYEEEEEESSS... I know I know, u don't like to talk to people, but THAT IS THE ONLY WAY. Your system is always as weak as the weakest part, and that part equals = your worker. You can have MD5^1000000 and that will never be enough...

    ech, I'm so glad I found this post.. didn't have so much fun for a loong time... hehe, cracking passwords easier than lockpicking... lol.

    ReplyDelete
  45. I like how you can make a post devoid of any actual content (oh look graphs! too bad the assumptions of throughput/time/cost per time unit are not mentioned at all!) or new information and still garner lots of replies and attention

    ReplyDelete
  46. Cool article with an interesting application of Amazon's cloud, but your results at the end are not exactly groundbreaking. My training in mathematics includes only one college level course in probability, but even that is enough to know that password complexity increases exponentially with password length.

    Maybe I have overestimated the mathematical prowess of "elite" computer security researchers in general?

    ReplyDelete
  47. I'm no cryptologist, but I believe one very significant variable here is which algorithm was used to encrypt (or hash) the password. My comment assumes your attack is against cryptotext, rather than against a "password: " prompt. I recall a consulting job where I cracked old-school DES passwords on old HPUX systems simply by taking the hashes offline and onto a Pentium 3 running John The Ripper. I don't remember actual numbers, but I do recall that simple passwords <8 characters fell pretty quickly, but the ones with newer algorithms took days to crack.

    ReplyDelete
  48. I have a question about your slide data. You introduce your second slide by saying it's about passwords "containing upper and lowercase a-z, plus the numerals 0-9" but then the slide title only says [a-z0-9]. The dollar values would suggest the slide title is correct and your introduction to it is incorrect.

    If the second slide is truly only about [a-z0-9] then I would like to see an additional slide describing [a-zA-Z0-9].

    Thanks.

    ReplyDelete
  49. It's amazing how snarky some people can be in these comments.

    ReplyDelete
  50. memorizing long passwords is easy. Just memorize in 3-4 character blocks, one block at a time. memory works best with small chunks of info, but can remember many small chunks.

    Also, type, speak, and visualize. Utilizing motor, audio, and visual memory together improves recall.

    I use 24-32 char passwords for some applications. Memory is no problem. i can do them from motor memory alone (i.e. too drunk to remember but can still type).

    ReplyDelete
  51. The following post is a long way of saying that I whole heartedly agree with the view that long passwords, 15+ places, are my best overall advice. Below are potentially useful ideas or concepts for persons interested in genuine security gains in the password factor in their security plans.

    I would like to humbly define a few ideas for the password strength concerned world. I think they truly provide value in discussing what password strength as a term ought to mean.

    First, I must get the obvious out of the way for benefit of auditors who think 8 place passwords are a good idea.
    1) Strong passwords take longer to crack.
    This means in real terms than passwords less than 15 places must have extended ASCII or other symbols beyond 93 found on a keyboard to meet such a definition.

    2) The average password cracking time will defined by the time it takes to crack 50% of the password hashes found in the password file.

    3) The average time to self terminate a password cracking effort will be defined is the average time of continuous effort by a trained professional before self-terminating a cracking effort.

    If any of you wish to contribute your experience to the following numbers, I will accept entries based on the following information.

    A) Cracking Times: How many password hashes where in the file. A measure of the combinations per second used to brute force. A measure of the length, size, or number of dictionaries, rainbow tables or supporting pre-supplied tables to the cracking tool.

    B) Self Termination Times: How long was the efforts continuous computing run time before either completion or self-termination by the cracker. What certifications or effort hours in training did the cracker have.

    So far: the average password lasts between 2 to 3 minutes, as measured by dictionary and rule assisted brute force on a stock Pentium 4 desktop, 3 Million Combinations per second. Coincidentally, the average 14 place 93 key combination admin password against LM rainbow tables about 4 GB in size is about 2 to 3 minutes.

    So far: the average time to self terminate a password cracking effort among trained professionals is 2 hours. 85% of the time, the effort will last less than 36 hours. Note: this is not the time taking to build pre-computed hashes or rainbow tables, but the time taken to use such tools before quitting for reasons of human boredom, frustration or professional demand to re-task the computer(s) in question.

    Rainbow table building for 14 place LM hashes with 93 keystroke complexity continues to hold at about 8 months of highly parallel computing.

    Regards,

    Don
    http://www.linkedin.com/in/arctific

    ReplyDelete
  52. Someone else asked : "decrypting a PGP encrypted file through bruteforce cracking the passphrase - does that mean you were in possession of the (passphrase protected) private key?"
    "Or was the file encrypted using a symmetric key?"

    I guess my question is: are these PGP ZIPfiles somehow different from PGP encryption sent to a recipient - are they really just fancy password-protected zips?

    Seems no one is answering the Q when it is asked on page 1...

    ReplyDelete
  53. Thanks to all of you who had constructive feedback and good questions. We have answered many of the questions in this post.

    ReplyDelete
  54. In the figure "optimistic cost to brute complex passwords" the >$1m point is shown as 9 characters (estimated cost $10,100,151) but in the combined figure "best passwords (by cost to brute)" that same figure is given for 10 characters.
    Ok, it's hypothetical and it's for discussion, but given that CISOs and others responsible for security will likely read this article and base policy decisions on it at least in part, we need some clarification - seems like a proof-reading error somewhere that should have been spotted and fixed. Is it 9 or 10 characters for a truly complex password?

    ReplyDelete
  55. As my passwords tend to fall into the just under 1 billion -> over the 8 billion I'm not to worried

    ReplyDelete
  56. A typical PC desktop is capable of testing 3 million cominations a second by bruit force. Thus an 8 billion combination password might last 2667 seconds, substantially less than the typical 2 hr password cracking effort. Even as it is an improvement over a typical password. These favor leet versions of words.
    A language is lucky to have 100,000 words. Asumming ten language dictionaries and 10 leet variations per word, this amonts to 10 million combinations to test. Thus. Such a password should fall in 3 seconds.

    Upshot is that the average password falls in about 2 +/- 1 minutes.

    Last, cryptography is getting both easy to obtain and the 8 month computing efforts to build rainbow tables more common. Thus, LM Hashes of fully complex passwords up to 14 places can fall in 8 minutes or less.

    I took math classes too, but the world is getting a bit more dangerous for single factor passwords than it used to be.

    Mean time to cracking is only approximately an exponential game. Pre-computed tables benefit from sucessive cracking efforts that save their status of tested hashes. Moore's law for computing power over time also benefits the cracking tools.

    Slothful security planning does not mix well with reality. Unless one is the attacker, then murphy's law is your friend.

    So, no leet, not single words. Length improves the situation only after crypto problems are accounted for. Complexity only helps If the crypto attack skipped testing for it.

    Short advice. Good passwords must be 15 plus in length unless you can prove LM Hashes are not used. IF so, 10 plus in length is still needed to keep up with civilian level security needs. 8 places is out dated.

    ReplyDelete
  57. Cost estimate for password cracking needs help.
    14 place full complexity LM Hashes cost a one time fee of $99 or less to crack. See Source Forge. Ophcrack.

    ReplyDelete
  58. Nice! I never really thought of passwords in terms of dollar cost-to-crack before. Log plots please would be nice.

    ReplyDelete
  59. i know im reviving an old post but do you have any intention of repeating this research using Cluster GPU Instances

    ReplyDelete