13 ms·

Lessons learned from cracking 2 million LinkedIn passwords

215 points by ibotty 14y ago

ams6110 14y ago
no matter how elaborate a password you choose, as long as it is based on words and rules, even if there are many words and many rules, it will probably be cracked So this is what I've been wondering about the current "best practice" to use long passphrases. How are those really any stronger than any other "rule" based password, the "rule" being that they are likely constructed of words and phrases from human language. Would the passphrase "My first car was a 1972 Monte Carlo" really be harder to crack (once the cracking tools are adapted) than a random 8 character password?
- JoachimSchipper 14y ago
  Calculating the entropy of such a passphrase is a bit of a black art, but note that it's a lot easier to remember than a random 8-character password!
- baq 14y ago
  obligatory xkcd reference: http://xkcd.com/936/ http://xkcd.com/936/
  - ralph 14y ago
    And note that assumes there are about 2,048 common words to choose from, not the 171,000 you can find in a dictionary.
  - donutdan4114 14y ago
    I've always disagreed with this XKCD. Given a passphrase dictionary attack, the passphrase would be discovered in less than a minute. And technically, if you didn't know the format of the password, and you were just trying to get a random 11 character password, that would take a long time to crack. There are (roughly) 94 character that you could safely use for your password pretty much universally on any website... 94^11 = 5.06x10^21 which means if your computer can generate 2 million hashes a second it would take: 80 million years to crack a truly random 11 character password. Passphrases are stupidly insecure unless you throw enough randomness in it. ex(quotes included): "My Phone Number is `(123)546-8794!!!`"
    - ohgodthecat 14y ago
      I see xkcd's passphrase is correcthorsebatterystaple and think that it is the wrong way to do it. The memorization of that password would work much better than a simple passphrase like that. I.E. the actual password would be: "That's a battery staple. Correct!" And I don't believe that people will easily be able to crack that even with the minimal randomness that has been put in with current techniques. Sure if natural language cracking becomes popular you may have to become a little more creative like using a made up word or name or a number but even your example if no one knows what your password is: "My Phone number is (123) 546-8794." should be sufficient for a very hard to crack password. And again is many times better than a simple dictionary passphrase with a few words combined.
    - leot 14y ago
      Given a passphrase dictionary attack, the passphrase would be discovered in less than a minute. Wait, what? 2,048^4 == 2^44 == 17,592,186,044,416 At 2 million hashes/second it would still take 101 [edit: actually, on average, 50] days to find this password, if it was unsalted. Perhaps if you had spent a few years of supercomputer time to generate some massive rainbow tables, you might be able to discover it quickly, but absent the need for your linkedIn password to be resistant to attacks from a nation state, you'd be pretty safe with such a password for a while. It's entirely unclear how you came to the conclusion that it could be discovered in "under a minute" with a passphrase dictionary attack.
      - rphlx 14y ago
        Diverging from your main point a bit: 2MH/s is unrealistically low. For a couple thousand dollars you can build FPGA HW that can do several billion SHA1 hashes/s. The bitcoin mining world is getting 400-450 SHA256 MH/s from a $130 chip. With similar technology, you can brute force a 2^44 SHA1 space in a lot less than 50 days.
        bostonvaulter2 14y ago
        Which is why no-one should be storing passwords in SHA1.
- nuttendorfer 14y ago
  They way I see it, and I'm no expert on this topic, a longer password is better than a short, completely random one. The attacker doesn't know how long your password is, so he will start with short passwords. Each additional character adds a lot more possible combinations, so thats where you get your safety from. Now if you include lower/upper case letters, digits and special characters you have increased the search space as well, so the attacker will have to try even more combinations.
  - unavoidable 14y ago
    But does it actually add entropy when a hacker could use a dictionary and combine those words in various ways? The best practice of using several random words is still 'rule based' - the individual 'units' in the password simply become words instead of characters, and the arbitrary length doesn't really matter. Start with the most common 40,000 words in English, and combine them in all possible orders - that gives 2.6e18 combinations. Compare that to the "random" password of length 10, with say, 40 possible characters: 1e16 combinations. I think OP has a point about the relative strength.
    - stan_rogers 14y ago
      Add a few fun prefixes and suffixes hither and yon, and you largely eliminate the "token" nature of words as well. Even a couple of well-placed (but ordinarily inappropriate) uns, antis, disens, ousitys and ishnesses increase the problem space dramatically without significantly decreasing (and perhaps even increasing) the memorability.
  - IvoDankolov 14y ago
    But that doesn't matter at all if the attacker is targeting your algorithm in particular. Say my algorithm is to pick the password "1" * 1000 (that's the character 1 repeated 1000 times) and also pretend that 90% of the sites didn't have stupid limits and it was a valid password. It's certainly a long password. The time it would take to brute force it by testing all possible strings in order of increasing length is an unimaginable number. It's not on the scale of the universe - not on the scale of a million universes either. But now let's say that this "the more characters the better" became a universal truth and everyone jumped on the same bandwagon and did the same quick hack of having 1000 1s. Suddenly, we're all screwed, because the algorithm "pick 1000 ones" is staggeringly weak. In fact, it provides no protection at all - the attacker already knows your password. The true measure of security measures is not how long they last when no one knows about them - it's how long they last when everybody knows. "Pick 10 random symbols" will last for a while. "Pick 'password'", not even a second. Where does "pick a meaningful English sentence" fall on the grand scale? That's one incredibly hard question to answer. It's also bloody difficult to break, for reasons of generating sentences, not password entropy.
- Cherian 14y ago
  One of the tricks I’ve learned and I think it stands vindicated now is to use the English translation of my vernacular language words as passwords. They stick on to your memory unlike "My first car was a 1972 Monte Carlo" I come from down-south India and I talk Malayalam.
- AgentConundrum 14y ago
  I have no idea. I thought they were, but your comment made be do some really naive analysis: For a typical password, each character can be one of around 92 characters, depending on what rules are in place - 26 lowercase letters, 26 uppercase letter, 10 digits, and ~32 special characters on the keyboard (I may have miscounted). Other characters could be used, but these are going to be the most common. This means that your 8 character password can have about 100^8 possibilities. To put that into more familiar, and more easily comparable terms, that's 1x10^16 password possibilities. According to Oxford Dictionaries, "The Second Edition of the 20-volume Oxford English Dictionary contains full entries for 171,476 words in current use." This means that, without reducing that space, a four word passphrase would have about 8.6x10^20 possibilities. Admittedly, there are some massive problems here. The most obvious of which is the fact that most of those 171k words aren't words a normal person would use. For this to be a valid analysis, you would have to believe that the average person would pick a passphrase like "gastroenteritis jurisprudence algorithm aberration", which is clearly ridiculous. Also, most people would, like your example, use a grammatically correct sentence. The possible combinations would be pretty severely reduced in that case. Now, more combinations are introduced by capitalization, punctuation, and the introduction of "numeric words", like the year 1972 in your example, but I have no idea how to account for that. In either case, the average person is going to have a much easier time remembering "My first car was a 1972 Monte Carlo" than they will remembering "8gj2;hg^".
  - amcintyre 14y ago
    >you would have to believe that the average person would pick a passphrase like "gastroenteritis jurisprudence algorithm aberration", which is clearly ridiculous. Oh how I wish my bank and mortgage lender would let me choose easy-to-remember passwords like that.
  - minikomi 14y ago
    I might have to start throwing in a non-dictionary word here and there .. "Don't touch the Snorlax after 4:45" .. "The Grue desires my 25th Triforce" ..
    - rargulati 14y ago
- richardw 14y ago
  With a passphrase, each word comes from a much bigger set than (alphanumeric + special characters), so it stands to reason that it'd be harder to brute-force. There are speech patterns, though, so it's likely that crackers would be able to reduce the search space somewhat by checking common phrases like "my first car". But change to something like "my first grandma was a 1927 haircut" and you're likely to future-proof it significantly.
  - MatthewPhillips 14y ago
    Or go completely nonsensical. "Vanilla elephant trampoline inverted cork routine" contains no common phrases and is just as easy to remember.
- dkokelley 14y ago
  Well, calculating the "true" strength is difficult to do, because even though sophisticated tools are available to aid the process, the attackers are still human, and can input their own guesses that may or may not be more accurate. If the attacker knows (or can closely guess) the password rules used to generate your password, he or she has a better chance of getting a hit. Let's look at a password like "My first car was a 1972 Monte Carlo". The password is 35 chars, 3 upper case, 6 special (spaces), and 4 numbers. The key space is all upper and lowercase english letters, all numbers, and all special characters. That's a key space of 95 characters, over 35 places. Objectively, there are 1.66 x 10^69 possible combinations. Given that the LinkedIn password crackers are slowed down at about 9 chars it seems like you're incredibly secure. But let's assume the attacker knows something about your password structure. Let's say they know that you use words (many people do, so it's a reasonable guess). Let's also assume that for numbers the attacker knows that years are popular for password numbers. Now instead of 35 chars, your password has 7 words and a date. We've changed the key space from 95 to about 100,000. (The exact number of words there are is a tricky number to pin down, but crackers have some good data on what the most popular ones are.) As for the date, there are really only a couple hundred interesting numbers, including all dates from this and last century, as well as common patterns. Password strength is (key depth) ^ (key length). An uninformed attacker has 1.66 x 10^69 possible combinations (95^35), while an informed attacker has roughly 1.0 x 10^40 possible combinations (100,000^8). Obviously, the less an attacker knows (or can guess) about your password structure, the better chances your password has against being cracked. Now, you asked about your password versus a random 8 char password. Let's take a "strong" password like "1~qQ%57h" This password also has upper and lowercase letters, numbers, and symbols. We can assume that there is nothing predictable about this password for this exercise. The password strength is 95^8, or 6.6 x 10^15, obviously much lower than the longer sentence, even if the attacker knows the sentence is 7 words and a date. Now remember, our passwords are being matched against human crackers attempting to guess the ways our passwords are most likely put together. For now, most passwords are 6-12 characters. In fact, most websites only allow passwords of these kinds, so it makes the most sense for crackers to go after these passwords. But it's still an arms race. If we assume that webmasters see the light and allow (or enforce) long, sentence-like passwords, the crackers will adjust. It's plausible I think that 5-10 years from now, we'll see articles like this one that use sentence structure syntax as an attack method. Until we discover and implement a better system that obsoletes passwords, the best we can really do is have long, complex, and unique passwords for everywhere we go, and have a system to manage them for us. I believe that something like LastPass or KeePass are the way to go for now. *Disclaimer: This was written on a groggy Sunday morning. Do not rely on my calculations. Do not use any of the examples as passwords. Do please check my work.
- tedunangst 14y ago
  Your passphrase reduces to the password Mfcwa1MC. Is Mfcwa1MC easier to crack than a random 8 character password? Even if the attacker "half-cracked" your passphrase and knew its initials, there's still more work to do. Making an intelligent phrase will affect the distribution of initials, but even something commonplace like "the quick brown zebra jumped over the mooon" or tqbzjotm hits the less frequent letters like q and z. It won't be completely random, but it's going to cover way more of the 8 letter space than words are.
- FixThisPOSSite 14y ago
  Another best practice is to avoid the worst practice - forcing people to use E-mail addresses as user IDs: http://goldmanosi.blogspot.com/2012/06/forcing-people-to-use-e-mail-address-as.html http://goldmanosi.blogspot.com/2012/06/forcing-people-to-use...
runeks 14y ago
Here's a useful one-liner to create a strong password in Linux: cat /usr/share/dict/words|egrep -v "é|'s$|[Åå]|[Øø]"|shuf --random-source=/dev/random -n4 This uses the dictionary /usr/share/dict/words and skips all the words containing characters like é, å, ø and all those ending in 's. The resulting word list has 72,940 words in it. Then it chooses 4 random words from this dictionary and prints them to the screen. This gives a password with about 65 bits of entropy. By adding another word, thus creating a 5-word passphrase, a botnet capable of checking 1,000 trillion passwords per second would spend, on average, 1600 years cracking away before it would find the correct passphrase. Here are some example 4-word passphrases produced using this method: poetically archaisms accept constrictors leukemia shuttlecocked checkout benevolently climactic gyrate dynamical predominates massage beef Concords recliners These are surprisingly easy to remember. I use a 7-word passphrase for the most important things and it didn't take me more than a day or two to learn it.
- aiscott 14y ago
  massage beef Concords recliners Damn you.
- ams6110 14y ago
  yes, but picking a handful of random words out of the dictionary is not the advice the passphrase advocates are giving. They are saying use a phrase that's meaningful to you and easy to remember.... which means most people are going to use a phrase in their native tongue, just like most people are using passwords like "mylinkedin!" for linked in. Edit: also, for anyone wanting something like the above technique, I recommend Diceware.
  - lotharbot 14y ago
    > "They are saying use a phrase that's meaningful to you" I haven't seen any passphrase advocates say that. The ones I've seen all say "use 4-5 random dictionary words". Come up with a meaning for the phrase, and it'll be easy to remember.
- waffle_ss 14y ago
tedunangst 14y ago
I always use site specific, but also site derived passwords. I think it's time to reevaluate that practice. I remember seeing that three of the top password fragments for LinkedIn were link, job, and work. My password was all three... oops.
- Periodic 14y ago
  You might want to look at a browser extension like PwdHash [1]. It uses a client-side script to generate a cryptographic hash from your common password and the domain name. I've been using it for about four years now and have been generally very happy. It means that if my password ever gets leaked the attackers are not only unlikely to find my password of "ngjO3uBJrvt", but if they get it they do not have any information about other sites, even if I reuse the password elsewhere. There are some newer password management/hashing tools. I've stuck with this one both because it works for me and I know and trust the authors, a group at Stanford. 1. https://www.pwdhash.com/ https://www.pwdhash.com/
  - tedunangst 14y ago
    I don't use that because of (unfounded) concerns that I will someday need to enter my password into some device where it's not available, or the domain will change, or some other scenario where bad things will happen because I do not actually know the password I told the site.
    - teach 14y ago
      This is why I use LastPass. I can log in (securely?) to their website and pull up the password out of a database in (rare) situations like that.
    - 16s 14y ago
      I call this 'primary authentication' which means you're in an environment where you can't execute code (staring at your xfce4 desktop log on prompt for example). Password managers and generators are only useful after you've logged on. Form there, you can execute code and use a password manager for 'secondary authentication' (websites, email, etc.).
donutdan4114 14y ago
I've always wondered why password hashing is not a law (at least in the US). There needs to be an agreed upon minimum level of security for storing credentials. Or, just make it where websites HAVE to state somewhere how they are storing the credentials. It's shocking how many places still use plain text, or encryption and store the key in the database.. It's pathetic that a major company like LinkedIn is simply storing credentials with a SHA1 hash. At LEAST use a really good salt...
- tedunangst 14y ago
  Mandatory https isn't a law, either. Good thing or HN would be in violation of it.
  - simonbrown 14y ago
    So?
    - simonbrown 14y ago
      To be clearer, my point was that HN not using HTTPS doesn't seem like a reason not to require sites to use HTTPS, let alone introducing any security regulations at all.
      - unimpressive 14y ago
        All standards become obsolete eventually. Mandating them by law is a sure road to legacy legal cruft hurting the legitimate aims it was put in place to help.
      - tedunangst 14y ago
        To be clear myself, the point is that there are bigger fish to fry. Mandating one practice when we can't even implement another smells like issue of the week.
- Periodic 14y ago
  There are problems with mandating standards. Mostly because they change a lot and will cause undue overhead to many companies. The government (NIST) already publishes standards, there is just no mandate that you use them. example: http://csrc.nist.gov/publications/drafts/800-118/draft-sp800-118.pdf http://csrc.nist.gov/publications/drafts/800-118/draft-sp800...
dhughes 14y ago
Well it's to the point now where I can't remember my passwords they are so long and complex plus I have so many accounts I need a password manager to manage all of that. With a password manager why bother restricting any password to anything less than the maximum? Gmail's password limit is 100 characters so I did that and any other account they are maxed out. Add to that extra authentication and also change them at least once every six month at minimum. The problem is my most valuable account, my bank, is stuck 15 years in the past.
- 16s 14y ago
  That because somewhere in the bank, they still have mainframes in use and old Unisys guys are on call to support them ;)
- SCdF 14y ago
  I've done the same, though I tend to limit it at about 24 characters, simply because if I come across a situation where I have to type it on a foreign computer while reading the password from the password manager on my phone, I don't want to be there all week..
deleted 14y ago
[deleted]
robomartin 14y ago
With all this talk about security I am still wondering why everyone isn't up in arms about the fact that Chrome makes all of your stored passwords plainly visible at the click of a button or two. This has been the case for years and many complaints have been recorded, but Google, for some strange reasons, seems to refuse to even attempt to put forth any effort to secure their browser.
- abraham 14y ago
  There are going to be much better discussions about this in Chromium discussion archives but I'll cover one of the main reasons why Chrome and Firefox (by default) do not have a master password. If someone has physical or remote access to your computer it is an endgame scenario and it does not matter if you have a master password enabled or not. The most basic attack is just to install a keylogger and steal the master password. They could also just copy the password database remotely and brute force it.
  - robomartin 14y ago
    I understand this very well. Here's one scenario: Busy office. Hundreds of computers. Open environment (no doors, just a bunch of desks/tables). Everyone using Chrome. The current version of Chrome would allow someone to, within a few clicks, grab a pile of passwords. Here's another scenario: Your mother takes her laptop to be repaired/updated. She uses Chrome. The entire repair shop has easy, unencumbered access to all of her passwords and logins. Similar scenario: Computer goes to IT guy where you work for repairs/updates. He now has any and all of your passwords and logins with no effort. My point is that for all this talk about security it seems really dumb for a prominent player (any prominent player) to not take extra steps to ensure that our valuable data is secure within reason. With LinkedIn the problem is, at the very least, the lack of anything beyond SHA-1 to protect passwords. Bad idea. In the browser case, it seems to me that, unless the intent is to provide a browser used only by those like us who understand and are very aware of security issues, it might just be a good idea to put in a few things that will make it harder for curious eyes or the 16 year old at the repair shop to grab all of your login data. I don't propose nor do I expect perfection or absolute security, but what Chrome does today is, in my opinion, at the very least irresponsible. The uninformed user has NO IDEA WHATSOEVER that a huge security hole exists in their browser. Maybe we need to stop thinking in our terms and focus on mom, dad, uncle or grandma. When you first install Chrome you should, at the very least, see a screen telling you about security and the options you might have. I think that a master passwords would most-definitely serve a purpose in the case of "innocent" peeking. Yes, with pro's all bets are off. It's only a matter of time until someone tracks identity theft to the lack of browser security and they sue the fuck out of the browser publisher.
16s 14y ago
How to calculate real-world password bit-strength: http://16s.us/word_machine/bits/ http://16s.us/word_machine/bits/
16s 14y ago
Linkedin allowed 6 character passwords. If a user selected six random uppercase ASCII, lowercase ASCII and numbers, this would be the bit-strength: print math.log(62) / math.log(2) * 6 35.72 bits That's easy to crack. Also, keep in mind that humans don't select chars randomly. So the bit-strength of these passwords was probably closer to 20 bits. I cracked 2.5 million with an old cpu and JtR within a few hours.
- 0003 14y ago
  This is the advice I give to my family members. The solution is to create a one-time-pad in excel(!) that contains all of your passwords. Store it on an encrypted thumb drive and carry it with your keys. There is the possiblity that your OTP may contain a character set that is not congruent with a web-service's password system, but these circumstances are rare.
  - saulrh 14y ago
    Just use keepass. If you're already carrying around a password file, you can carry around portable binaries of the program that reads your passwords. www.keepass.info
    - LinXitoW 14y ago
      sadly, Keepass is not very Mac/Linux friendly, because it's built on .NET, so it's only an option for pure Windows users.
      - benholmen 14y ago
        I use Keepass daily on Windows and Ubuntu and used it on OS X in the past without any issues. I highly recommend it.
      - dopo 14y ago
        I don't know about Linux, but I've been using KeePassX for Mac for about a year now. It only supports the older KeePass file format, and it's ugly, but it works great. There are also a few iOS apps you can use, my favorite of which is KyPass.
ronnier 14y ago
Were these just password hashes or did the leak include usernames and/or email addresses?
- josso 14y ago
  The file that got leaked to the public is only containing the hashes. The hackers behind the file probably has usernames or emails.
gambler 14y ago
Thus, it is highly recommended to use a strong random password generator that is known to be actually random. The whole point of a password is that you can remember it. The moment you need software to store and retrieve passwords, you're better off using asymmetric cryptography. That said, I really dislike the idea that it's the only way to achieve security. I would really like to see more discussions and propositions for solving this problem.
- fl3tch 14y ago
  It will get to the point that we need biometric scanners or implanted RFID chips with private keys to do authentication, since brute forcing even unrememberable passwords will be trivial eventually.
  - vegardx 14y ago
    Why? There are plenty of ways to make brute force hard or damn near impossible, it's just a little harder to implement. It has been discussed a lot of times here at HN and other places. Also, do you really think that storing private keys on RFID would be a wise choice? I would put that in the "stupid as fuck"-category, just above storing your keys on a USB-stick, as they are both easy to copy and duplicate, and with RFID I could do it remotely. A real solution to all of these problems would be for people to stop reusing passwords. You don't really need the account passwords when you basically have access to all the data there anyway.
    - gambler 14y ago
      That's the problem, though. If people didn't reuse passwords, if people didn't use words and personal information in passwords and if people had no problem changing them every day then a lot of problems with security would be solved. But those are not realistic expectations, and blaming users for not being computers does not solve the problem. Slow hash function certainly help, but I think we also need something that goes beyond straightforward cryptography to address authentication issues. Something that redefines the rules of the game to be more human-friendly and less computer-friendly. But then again, I never even heard the question being phrase this way: what do we want from "program-less" authentication and what we can use to achieve it.
rikf 14y ago
head -c x /dev/random | uuencode - where x is the length of the password you want.
- chmike 14y ago
  How do you remember it ? What do you do if you need to login from another computer ? This doesn't work on my windows computer. If we store this random password in a local pasword storage, how much different is that from using asymetric keys (rsa,...) ?
MetaCosm 14y ago
This week has finally got me off my ass, and I generated a truly random password for all 260 sites I have built-up in Lastpass over the past few years... as well strong Lastpass password (most likely going to be hardened with a two-factor via Yubikey in the near future). I must say, just finding the password reset function on some of these forums and less popular sites is a beast. Also, I was shocked by the number of 10 and 12 char limitations I hit.
peterkelly 14y ago
So here's an idea: Pretty much every site with a login facility has an "I forgot my password" option where you put in your username or email address, and it sends you a link to reset your password. This is effectively a second form of authentication - the ability to receive email at that address implies the ability to log in to that account. So what about an authentication mechanism that works as follows: 1. You type in your username 2. The site emails you a one-time authentication token (as part of a link) 3. You click on that link and then you're logged into the site Of course, there are a few obvious problems with this: it's a bit cumbersome to have to do for every login, email is unencrypted, and message reception uses a pull-based mechanism. So I could envisage a standard, incorporated into browsers, as follows: 1. When you first launch your browser, you log into an authentication server S, supplying your password (either manually, or automatically via a saved password) 2. When you want to log in to a site, you type in your username, and the site sends an authentication token to the server S 3. S sends a push notification to your browser with the authentication token 4. Your browser passes this token to the site, and you're logged in This way, your (hashed + salted) password need only be stored on server S (in the first example, this corresponds to your email server). This means that apart from S, none of the sites you use need to store any password information at all. I'm sure this basic idea has been implemented previously in other contexts. Why are we not using for all our web logins?
- peterkelly 14y ago
  A clarification of the second point 2: The site needs to know the address of server S, and your account name on that server (i.e. just like username@domain.com with email). So the system doesn't have to be centralised.
- daliusd 14y ago
  You are kind of reinventing BrowserID (https://browserid.org/ https://browserid.org/).
  - peterkelly 14y ago
    Hehe, I was expecting to get an "X already does that" reply pretty quickly. Surely this needs to be promoted more heavily to website developers, especially those behind major sites like linkedin. I'd never heard of it myself and I'm sure a lot of others haven't either. If some of the bigger sites started adopting it, awareness would grow very quickly and we could greatly reduce the risks involved with every website storing password info for all their users.
samhan 14y ago
Well heres an idea i use . If you know how to touch type just offset your fingers on the keyboard in a special way so you can turn a memorable password into slightly more random gibberish . Eg : I Love you o ;pbr upi
mmaunder 14y ago
20 years ago we called this crackerjack. http://web.textfiles.com/computers/jack14.txt http://web.textfiles.com/computers/jack14.txt

215 points by ibotty 14y ago

no matter how elaborate a password you choose, as long as it is based on words and rules, even if there are many words and many rules, it will probably be cracked So this is what I've been wondering about the current "best practice" to use long passphrases. How are those really any stronger than any other "rule" based password, the "rule" being that they are likely constructed of words and phrases from human language. Would the passphrase "My first car was a 1972 Monte Carlo" really be harder to crack (once the cracking tools are adapted) than a random 8 character password?

JoachimSchipper 14y ago
Calculating the entropy of such a passphrase is a bit of a black art, but note that it's a lot easier to remember than a random 8-character password!
baq 14y ago
obligatory xkcd reference: http://xkcd.com/936/ http://xkcd.com/936/
- ralph 14y ago
  And note that assumes there are about 2,048 common words to choose from, not the 171,000 you can find in a dictionary.
- donutdan4114 14y ago
  I've always disagreed with this XKCD. Given a passphrase dictionary attack, the passphrase would be discovered in less than a minute. And technically, if you didn't know the format of the password, and you were just trying to get a random 11 character password, that would take a long time to crack. There are (roughly) 94 character that you could safely use for your password pretty much universally on any website... 94^11 = 5.06x10^21 which means if your computer can generate 2 million hashes a second it would take: 80 million years to crack a truly random 11 character password. Passphrases are stupidly insecure unless you throw enough randomness in it. ex(quotes included): "My Phone Number is `(123)546-8794!!!`"
  - ohgodthecat 14y ago
    I see xkcd's passphrase is correcthorsebatterystaple and think that it is the wrong way to do it. The memorization of that password would work much better than a simple passphrase like that. I.E. the actual password would be: "That's a battery staple. Correct!" And I don't believe that people will easily be able to crack that even with the minimal randomness that has been put in with current techniques. Sure if natural language cracking becomes popular you may have to become a little more creative like using a made up word or name or a number but even your example if no one knows what your password is: "My Phone number is (123) 546-8794." should be sufficient for a very hard to crack password. And again is many times better than a simple dictionary passphrase with a few words combined.
  - leot 14y ago
    Given a passphrase dictionary attack, the passphrase would be discovered in less than a minute. Wait, what? 2,048^4 == 2^44 == 17,592,186,044,416 At 2 million hashes/second it would still take 101 [edit: actually, on average, 50] days to find this password, if it was unsalted. Perhaps if you had spent a few years of supercomputer time to generate some massive rainbow tables, you might be able to discover it quickly, but absent the need for your linkedIn password to be resistant to attacks from a nation state, you'd be pretty safe with such a password for a while. It's entirely unclear how you came to the conclusion that it could be discovered in "under a minute" with a passphrase dictionary attack.
    - rphlx 14y ago
      Diverging from your main point a bit: 2MH/s is unrealistically low. For a couple thousand dollars you can build FPGA HW that can do several billion SHA1 hashes/s. The bitcoin mining world is getting 400-450 SHA256 MH/s from a $130 chip. With similar technology, you can brute force a 2^44 SHA1 space in a lot less than 50 days.
      - bostonvaulter2 14y ago
        Which is why no-one should be storing passwords in SHA1.
nuttendorfer 14y ago
They way I see it, and I'm no expert on this topic, a longer password is better than a short, completely random one. The attacker doesn't know how long your password is, so he will start with short passwords. Each additional character adds a lot more possible combinations, so thats where you get your safety from. Now if you include lower/upper case letters, digits and special characters you have increased the search space as well, so the attacker will have to try even more combinations.
- unavoidable 14y ago
  But does it actually add entropy when a hacker could use a dictionary and combine those words in various ways? The best practice of using several random words is still 'rule based' - the individual 'units' in the password simply become words instead of characters, and the arbitrary length doesn't really matter. Start with the most common 40,000 words in English, and combine them in all possible orders - that gives 2.6e18 combinations. Compare that to the "random" password of length 10, with say, 40 possible characters: 1e16 combinations. I think OP has a point about the relative strength.
  - stan_rogers 14y ago
    Add a few fun prefixes and suffixes hither and yon, and you largely eliminate the "token" nature of words as well. Even a couple of well-placed (but ordinarily inappropriate) uns, antis, disens, ousitys and ishnesses increase the problem space dramatically without significantly decreasing (and perhaps even increasing) the memorability.
- IvoDankolov 14y ago
  But that doesn't matter at all if the attacker is targeting your algorithm in particular. Say my algorithm is to pick the password "1" * 1000 (that's the character 1 repeated 1000 times) and also pretend that 90% of the sites didn't have stupid limits and it was a valid password. It's certainly a long password. The time it would take to brute force it by testing all possible strings in order of increasing length is an unimaginable number. It's not on the scale of the universe - not on the scale of a million universes either. But now let's say that this "the more characters the better" became a universal truth and everyone jumped on the same bandwagon and did the same quick hack of having 1000 1s. Suddenly, we're all screwed, because the algorithm "pick 1000 ones" is staggeringly weak. In fact, it provides no protection at all - the attacker already knows your password. The true measure of security measures is not how long they last when no one knows about them - it's how long they last when everybody knows. "Pick 10 random symbols" will last for a while. "Pick 'password'", not even a second. Where does "pick a meaningful English sentence" fall on the grand scale? That's one incredibly hard question to answer. It's also bloody difficult to break, for reasons of generating sentences, not password entropy.
Cherian 14y ago
One of the tricks I’ve learned and I think it stands vindicated now is to use the English translation of my vernacular language words as passwords. They stick on to your memory unlike "My first car was a 1972 Monte Carlo" I come from down-south India and I talk Malayalam.
AgentConundrum 14y ago
I have no idea. I thought they were, but your comment made be do some really naive analysis: For a typical password, each character can be one of around 92 characters, depending on what rules are in place - 26 lowercase letters, 26 uppercase letter, 10 digits, and ~32 special characters on the keyboard (I may have miscounted). Other characters could be used, but these are going to be the most common. This means that your 8 character password can have about 100^8 possibilities. To put that into more familiar, and more easily comparable terms, that's 1x10^16 password possibilities. According to Oxford Dictionaries, "The Second Edition of the 20-volume Oxford English Dictionary contains full entries for 171,476 words in current use." This means that, without reducing that space, a four word passphrase would have about 8.6x10^20 possibilities. Admittedly, there are some massive problems here. The most obvious of which is the fact that most of those 171k words aren't words a normal person would use. For this to be a valid analysis, you would have to believe that the average person would pick a passphrase like "gastroenteritis jurisprudence algorithm aberration", which is clearly ridiculous. Also, most people would, like your example, use a grammatically correct sentence. The possible combinations would be pretty severely reduced in that case. Now, more combinations are introduced by capitalization, punctuation, and the introduction of "numeric words", like the year 1972 in your example, but I have no idea how to account for that. In either case, the average person is going to have a much easier time remembering "My first car was a 1972 Monte Carlo" than they will remembering "8gj2;hg^".
- amcintyre 14y ago
  >you would have to believe that the average person would pick a passphrase like "gastroenteritis jurisprudence algorithm aberration", which is clearly ridiculous. Oh how I wish my bank and mortgage lender would let me choose easy-to-remember passwords like that.
- minikomi 14y ago
  I might have to start throwing in a non-dictionary word here and there .. "Don't touch the Snorlax after 4:45" .. "The Grue desires my 25th Triforce" ..
  - rargulati 14y ago
richardw 14y ago
With a passphrase, each word comes from a much bigger set than (alphanumeric + special characters), so it stands to reason that it'd be harder to brute-force. There are speech patterns, though, so it's likely that crackers would be able to reduce the search space somewhat by checking common phrases like "my first car". But change to something like "my first grandma was a 1927 haircut" and you're likely to future-proof it significantly.
- MatthewPhillips 14y ago
  Or go completely nonsensical. "Vanilla elephant trampoline inverted cork routine" contains no common phrases and is just as easy to remember.
dkokelley 14y ago
Well, calculating the "true" strength is difficult to do, because even though sophisticated tools are available to aid the process, the attackers are still human, and can input their own guesses that may or may not be more accurate. If the attacker knows (or can closely guess) the password rules used to generate your password, he or she has a better chance of getting a hit. Let's look at a password like "My first car was a 1972 Monte Carlo". The password is 35 chars, 3 upper case, 6 special (spaces), and 4 numbers. The key space is all upper and lowercase english letters, all numbers, and all special characters. That's a key space of 95 characters, over 35 places. Objectively, there are 1.66 x 10^69 possible combinations. Given that the LinkedIn password crackers are slowed down at about 9 chars it seems like you're incredibly secure. But let's assume the attacker knows something about your password structure. Let's say they know that you use words (many people do, so it's a reasonable guess). Let's also assume that for numbers the attacker knows that years are popular for password numbers. Now instead of 35 chars, your password has 7 words and a date. We've changed the key space from 95 to about 100,000. (The exact number of words there are is a tricky number to pin down, but crackers have some good data on what the most popular ones are.) As for the date, there are really only a couple hundred interesting numbers, including all dates from this and last century, as well as common patterns. Password strength is (key depth) ^ (key length). An uninformed attacker has 1.66 x 10^69 possible combinations (95^35), while an informed attacker has roughly 1.0 x 10^40 possible combinations (100,000^8). Obviously, the less an attacker knows (or can guess) about your password structure, the better chances your password has against being cracked. Now, you asked about your password versus a random 8 char password. Let's take a "strong" password like "1~qQ%57h" This password also has upper and lowercase letters, numbers, and symbols. We can assume that there is nothing predictable about this password for this exercise. The password strength is 95^8, or 6.6 x 10^15, obviously much lower than the longer sentence, even if the attacker knows the sentence is 7 words and a date. Now remember, our passwords are being matched against human crackers attempting to guess the ways our passwords are most likely put together. For now, most passwords are 6-12 characters. In fact, most websites only allow passwords of these kinds, so it makes the most sense for crackers to go after these passwords. But it's still an arms race. If we assume that webmasters see the light and allow (or enforce) long, sentence-like passwords, the crackers will adjust. It's plausible I think that 5-10 years from now, we'll see articles like this one that use sentence structure syntax as an attack method. Until we discover and implement a better system that obsoletes passwords, the best we can really do is have long, complex, and unique passwords for everywhere we go, and have a system to manage them for us. I believe that something like LastPass or KeePass are the way to go for now. *Disclaimer: This was written on a groggy Sunday morning. Do not rely on my calculations. Do not use any of the examples as passwords. Do please check my work.
tedunangst 14y ago
Your passphrase reduces to the password Mfcwa1MC. Is Mfcwa1MC easier to crack than a random 8 character password? Even if the attacker "half-cracked" your passphrase and knew its initials, there's still more work to do. Making an intelligent phrase will affect the distribution of initials, but even something commonplace like "the quick brown zebra jumped over the mooon" or tqbzjotm hits the less frequent letters like q and z. It won't be completely random, but it's going to cover way more of the 8 letter space than words are.
FixThisPOSSite 14y ago
Another best practice is to avoid the worst practice - forcing people to use E-mail addresses as user IDs: http://goldmanosi.blogspot.com/2012/06/forcing-people-to-use-e-mail-address-as.html http://goldmanosi.blogspot.com/2012/06/forcing-people-to-use...

runeks 14y ago

Here's a useful one-liner to create a strong password in Linux: cat /usr/share/dict/words|egrep -v "é|'s$|[Åå]|[Øø]"|shuf --random-source=/dev/random -n4 This uses the dictionary /usr/share/dict/words and skips all the words containing characters like é, å, ø and all those ending in 's. The resulting word list has 72,940 words in it. Then it chooses 4 random words from this dictionary and prints them to the screen. This gives a password with about 65 bits of entropy. By adding another word, thus creating a 5-word passphrase, a botnet capable of checking 1,000 trillion passwords per second would spend, on average, 1600 years cracking away before it would find the correct passphrase. Here are some example 4-word passphrases produced using this method: poetically archaisms accept constrictors leukemia shuttlecocked checkout benevolently climactic gyrate dynamical predominates massage beef Concords recliners These are surprisingly easy to remember. I use a 7-word passphrase for the most important things and it didn't take me more than a day or two to learn it.

aiscott 14y ago
massage beef Concords recliners Damn you.
ams6110 14y ago
yes, but picking a handful of random words out of the dictionary is not the advice the passphrase advocates are giving. They are saying use a phrase that's meaningful to you and easy to remember.... which means most people are going to use a phrase in their native tongue, just like most people are using passwords like "mylinkedin!" for linked in. Edit: also, for anyone wanting something like the above technique, I recommend Diceware.
- lotharbot 14y ago
  > "They are saying use a phrase that's meaningful to you" I haven't seen any passphrase advocates say that. The ones I've seen all say "use 4-5 random dictionary words". Come up with a meaning for the phrase, and it'll be easy to remember.
waffle_ss 14y ago

tedunangst 14y ago

I always use site specific, but also site derived passwords. I think it's time to reevaluate that practice. I remember seeing that three of the top password fragments for LinkedIn were link, job, and work. My password was all three... oops.

Periodic 14y ago
You might want to look at a browser extension like PwdHash [1]. It uses a client-side script to generate a cryptographic hash from your common password and the domain name. I've been using it for about four years now and have been generally very happy. It means that if my password ever gets leaked the attackers are not only unlikely to find my password of "ngjO3uBJrvt", but if they get it they do not have any information about other sites, even if I reuse the password elsewhere. There are some newer password management/hashing tools. I've stuck with this one both because it works for me and I know and trust the authors, a group at Stanford. 1. https://www.pwdhash.com/ https://www.pwdhash.com/
- tedunangst 14y ago
  I don't use that because of (unfounded) concerns that I will someday need to enter my password into some device where it's not available, or the domain will change, or some other scenario where bad things will happen because I do not actually know the password I told the site.
  - teach 14y ago
    This is why I use LastPass. I can log in (securely?) to their website and pull up the password out of a database in (rare) situations like that.
  - 16s 14y ago
    I call this 'primary authentication' which means you're in an environment where you can't execute code (staring at your xfce4 desktop log on prompt for example). Password managers and generators are only useful after you've logged on. Form there, you can execute code and use a password manager for 'secondary authentication' (websites, email, etc.).

donutdan4114 14y ago

I've always wondered why password hashing is not a law (at least in the US). There needs to be an agreed upon minimum level of security for storing credentials. Or, just make it where websites HAVE to state somewhere how they are storing the credentials. It's shocking how many places still use plain text, or encryption and store the key in the database.. It's pathetic that a major company like LinkedIn is simply storing credentials with a SHA1 hash. At LEAST use a really good salt...

tedunangst 14y ago
Mandatory https isn't a law, either. Good thing or HN would be in violation of it.
- simonbrown 14y ago
  So?
  - simonbrown 14y ago
    To be clearer, my point was that HN not using HTTPS doesn't seem like a reason not to require sites to use HTTPS, let alone introducing any security regulations at all.
    - unimpressive 14y ago
      All standards become obsolete eventually. Mandating them by law is a sure road to legacy legal cruft hurting the legitimate aims it was put in place to help.
    - tedunangst 14y ago
      To be clear myself, the point is that there are bigger fish to fry. Mandating one practice when we can't even implement another smells like issue of the week.
Periodic 14y ago
There are problems with mandating standards. Mostly because they change a lot and will cause undue overhead to many companies. The government (NIST) already publishes standards, there is just no mandate that you use them. example: http://csrc.nist.gov/publications/drafts/800-118/draft-sp800-118.pdf http://csrc.nist.gov/publications/drafts/800-118/draft-sp800...

dhughes 14y ago

Well it's to the point now where I can't remember my passwords they are so long and complex plus I have so many accounts I need a password manager to manage all of that. With a password manager why bother restricting any password to anything less than the maximum? Gmail's password limit is 100 characters so I did that and any other account they are maxed out. Add to that extra authentication and also change them at least once every six month at minimum. The problem is my most valuable account, my bank, is stuck 15 years in the past.

16s 14y ago
That because somewhere in the bank, they still have mainframes in use and old Unisys guys are on call to support them ;)
SCdF 14y ago
I've done the same, though I tend to limit it at about 24 characters, simply because if I come across a situation where I have to type it on a foreign computer while reading the password from the password manager on my phone, I don't want to be there all week..

deleted 14y ago

[deleted]

robomartin 14y ago

With all this talk about security I am still wondering why everyone isn't up in arms about the fact that Chrome makes all of your stored passwords plainly visible at the click of a button or two. This has been the case for years and many complaints have been recorded, but Google, for some strange reasons, seems to refuse to even attempt to put forth any effort to secure their browser.

abraham 14y ago
There are going to be much better discussions about this in Chromium discussion archives but I'll cover one of the main reasons why Chrome and Firefox (by default) do not have a master password. If someone has physical or remote access to your computer it is an endgame scenario and it does not matter if you have a master password enabled or not. The most basic attack is just to install a keylogger and steal the master password. They could also just copy the password database remotely and brute force it.
- robomartin 14y ago
  I understand this very well. Here's one scenario: Busy office. Hundreds of computers. Open environment (no doors, just a bunch of desks/tables). Everyone using Chrome. The current version of Chrome would allow someone to, within a few clicks, grab a pile of passwords. Here's another scenario: Your mother takes her laptop to be repaired/updated. She uses Chrome. The entire repair shop has easy, unencumbered access to all of her passwords and logins. Similar scenario: Computer goes to IT guy where you work for repairs/updates. He now has any and all of your passwords and logins with no effort. My point is that for all this talk about security it seems really dumb for a prominent player (any prominent player) to not take extra steps to ensure that our valuable data is secure within reason. With LinkedIn the problem is, at the very least, the lack of anything beyond SHA-1 to protect passwords. Bad idea. In the browser case, it seems to me that, unless the intent is to provide a browser used only by those like us who understand and are very aware of security issues, it might just be a good idea to put in a few things that will make it harder for curious eyes or the 16 year old at the repair shop to grab all of your login data. I don't propose nor do I expect perfection or absolute security, but what Chrome does today is, in my opinion, at the very least irresponsible. The uninformed user has NO IDEA WHATSOEVER that a huge security hole exists in their browser. Maybe we need to stop thinking in our terms and focus on mom, dad, uncle or grandma. When you first install Chrome you should, at the very least, see a screen telling you about security and the options you might have. I think that a master passwords would most-definitely serve a purpose in the case of "innocent" peeking. Yes, with pro's all bets are off. It's only a matter of time until someone tracks identity theft to the lack of browser security and they sue the fuck out of the browser publisher.

16s 14y ago

How to calculate real-world password bit-strength: http://16s.us/word_machine/bits/ http://16s.us/word_machine/bits/

16s 14y ago

Linkedin allowed 6 character passwords. If a user selected six random uppercase ASCII, lowercase ASCII and numbers, this would be the bit-strength: print math.log(62) / math.log(2) * 6 35.72 bits That's easy to crack. Also, keep in mind that humans don't select chars randomly. So the bit-strength of these passwords was probably closer to 20 bits. I cracked 2.5 million with an old cpu and JtR within a few hours.

0003 14y ago
This is the advice I give to my family members. The solution is to create a one-time-pad in excel(!) that contains all of your passwords. Store it on an encrypted thumb drive and carry it with your keys. There is the possiblity that your OTP may contain a character set that is not congruent with a web-service's password system, but these circumstances are rare.
- saulrh 14y ago
  Just use keepass. If you're already carrying around a password file, you can carry around portable binaries of the program that reads your passwords. www.keepass.info
  - LinXitoW 14y ago
    sadly, Keepass is not very Mac/Linux friendly, because it's built on .NET, so it's only an option for pure Windows users.
    - benholmen 14y ago
      I use Keepass daily on Windows and Ubuntu and used it on OS X in the past without any issues. I highly recommend it.
    - dopo 14y ago
      I don't know about Linux, but I've been using KeePassX for Mac for about a year now. It only supports the older KeePass file format, and it's ugly, but it works great. There are also a few iOS apps you can use, my favorite of which is KyPass.

ronnier 14y ago

Were these just password hashes or did the leak include usernames and/or email addresses?

josso 14y ago
The file that got leaked to the public is only containing the hashes. The hackers behind the file probably has usernames or emails.

gambler 14y ago

Thus, it is highly recommended to use a strong random password generator that is known to be actually random. The whole point of a password is that you can remember it. The moment you need software to store and retrieve passwords, you're better off using asymmetric cryptography. That said, I really dislike the idea that it's the only way to achieve security. I would really like to see more discussions and propositions for solving this problem.

fl3tch 14y ago
It will get to the point that we need biometric scanners or implanted RFID chips with private keys to do authentication, since brute forcing even unrememberable passwords will be trivial eventually.
- vegardx 14y ago
  Why? There are plenty of ways to make brute force hard or damn near impossible, it's just a little harder to implement. It has been discussed a lot of times here at HN and other places. Also, do you really think that storing private keys on RFID would be a wise choice? I would put that in the "stupid as fuck"-category, just above storing your keys on a USB-stick, as they are both easy to copy and duplicate, and with RFID I could do it remotely. A real solution to all of these problems would be for people to stop reusing passwords. You don't really need the account passwords when you basically have access to all the data there anyway.
  - gambler 14y ago
    That's the problem, though. If people didn't reuse passwords, if people didn't use words and personal information in passwords and if people had no problem changing them every day then a lot of problems with security would be solved. But those are not realistic expectations, and blaming users for not being computers does not solve the problem. Slow hash function certainly help, but I think we also need something that goes beyond straightforward cryptography to address authentication issues. Something that redefines the rules of the game to be more human-friendly and less computer-friendly. But then again, I never even heard the question being phrase this way: what do we want from "program-less" authentication and what we can use to achieve it.

rikf 14y ago

head -c x /dev/random | uuencode - where x is the length of the password you want.

chmike 14y ago
How do you remember it ? What do you do if you need to login from another computer ? This doesn't work on my windows computer. If we store this random password in a local pasword storage, how much different is that from using asymetric keys (rsa,...) ?

MetaCosm 14y ago

This week has finally got me off my ass, and I generated a truly random password for all 260 sites I have built-up in Lastpass over the past few years... as well strong Lastpass password (most likely going to be hardened with a two-factor via Yubikey in the near future). I must say, just finding the password reset function on some of these forums and less popular sites is a beast. Also, I was shocked by the number of 10 and 12 char limitations I hit.

peterkelly 14y ago

So here's an idea: Pretty much every site with a login facility has an "I forgot my password" option where you put in your username or email address, and it sends you a link to reset your password. This is effectively a second form of authentication - the ability to receive email at that address implies the ability to log in to that account. So what about an authentication mechanism that works as follows: 1. You type in your username 2. The site emails you a one-time authentication token (as part of a link) 3. You click on that link and then you're logged into the site Of course, there are a few obvious problems with this: it's a bit cumbersome to have to do for every login, email is unencrypted, and message reception uses a pull-based mechanism. So I could envisage a standard, incorporated into browsers, as follows: 1. When you first launch your browser, you log into an authentication server S, supplying your password (either manually, or automatically via a saved password) 2. When you want to log in to a site, you type in your username, and the site sends an authentication token to the server S 3. S sends a push notification to your browser with the authentication token 4. Your browser passes this token to the site, and you're logged in This way, your (hashed + salted) password need only be stored on server S (in the first example, this corresponds to your email server). This means that apart from S, none of the sites you use need to store any password information at all. I'm sure this basic idea has been implemented previously in other contexts. Why are we not using for all our web logins?

peterkelly 14y ago
A clarification of the second point 2: The site needs to know the address of server S, and your account name on that server (i.e. just like username@domain.com with email). So the system doesn't have to be centralised.
daliusd 14y ago
You are kind of reinventing BrowserID (https://browserid.org/ https://browserid.org/).
- peterkelly 14y ago
  Hehe, I was expecting to get an "X already does that" reply pretty quickly. Surely this needs to be promoted more heavily to website developers, especially those behind major sites like linkedin. I'd never heard of it myself and I'm sure a lot of others haven't either. If some of the bigger sites started adopting it, awareness would grow very quickly and we could greatly reduce the risks involved with every website storing password info for all their users.

samhan 14y ago

Well heres an idea i use . If you know how to touch type just offset your fingers on the keyboard in a special way so you can turn a memorable password into slightly more random gibberish . Eg : I Love you o ;pbr upi

mmaunder 14y ago

20 years ago we called this crackerjack. http://web.textfiles.com/computers/jack14.txt http://web.textfiles.com/computers/jack14.txt