Interesting, I tried this with a bunch of different passwords (though using php's sha1 function, which obviously gives the same output as ruby's), and found no matches. You're using the "combo_not.txt" file from the zip file in the ggp, right?
The dump is not complete -- my password is also missing. As other people said, that file contains about 6.5 million hashes, while LinkedIn has 30 times more users.
Considering how usernames weren't leaked, there's a big chance that the intruder is just sitting on them and the other passwords.
My password is missing too (if i've done right the hash generation as illustrated above). It's strange that only hashes starting with "000000a9" are present, someone said here that it's just presentation but my hashed password is 40char long as those leaked including the 000000a9
Either you don't have a complete file or you haven't scrolled through it. Only the first 277 hashes start with that string (and some others scattered throughout).
i was talkin about hashes starting with 0000 (i just looked at the beginning and the end of the file). jgrahamc posts is useful, if i dont consider this 0000 (that could be a sign of "ok we've decrypted it" i can find my hash (password was not very difficult)...
I wonder how many LinkedIn users use the same passwords for all their accounts. The article talks about identity theft and "confidential contacts" but I think the real danger is that people tend to use the same password everywhere. It's their other accounts that might have real value.
EDIT - As I think about it, e-mail accounts would be especially valuable as most of your other sites could be compromised using the "recover my password via e-mail" feature if the hacker could read the resulting mail.
Me. Admittedly, it's stupid as hell, but has generally been too much of a pain to do anything else (for things outside of banking, email). I've started to get serious about KeePass lately, but I bet a significant percentage of users take the lazy approach.
Ha. I'm in the same boat. This is my second account after the first one got ghost banned (for a single comment and the followups attempting to explain).
I take things a step further -- I have no idea what my password is on sites like HN or reddit. If the cookie is ever gone, my account is gone.
I don't like the idea of identity permanence.
Instead of shitty passwords though, why not use something like 1Password to store the logins? I use that (or an old fashioned piece of paper in a secure location) for meaningful security tokens.
Having to type in my Apple password on iOS once every few hours inevitably means I have to use something memorizable and quick to type. There are certain trade-offs with different passwords.
I've developed a system (kept only in my head) where every password I use is based off on the name of the service. This means that with just one of my passwords, you're most likely not getting anywhere. With two, you have a bigger chance of figuring out the differences and thus the system, but it works fine for me at the moment.
Don't underestimate me. It contains many numbers extracted from the letters according to various rules (order in alphabet, backwards, etc), along with special characters.
I generally use the same password for what I feel are non-critical sites like LinkedIn, twitter and Facebook. Another password for testing new services/apps etc. As a rule any site that may contain my credit card data or sensitive information I use a separate password. I feel this is the best compromise to having complex passwords for each account.
I used this in the past as well. But then started thinking about what non-critical is. As a "internet professional", even my Facebook account being compromised would be negative impact on my image; on LinkedIN doubly so due to it's professional character. So I basically decided that I'm not going to distinguish at all (sliding slope) and just have randomly generated passwords for all sites (not for my Mac though, too much hassle/attack vectors are different).
Safe >> Sorry
EDIT: Just checked, and my randomly generated password is in the leaked list of hashed passwords. I'm not using that same password anywhere else, so the source MUST be LinkedIN through whatever means (or it's some Mac/PC based attack vector, and these folks only leaked LinkedIN accounts which sounds very implausible).
I just looked into the file (combo_not.txt). There are only hashes. Who decided that the hashes posted in the forum are related to linkedin in any way ? Thank you.
Those paranoid tinfoil-hat wearing lunatics that generate absurdly long unique random passwords for every site are wringing their hands with glee because they found the hash of their LinkedIn password in the file. You're welcome.
To expand on that, to store passwords don't just use salt+sha1, or try to do your own nested sha1, just use bcrypt: http://en.wikipedia.org/wiki/Bcrypt
If a database of bcrypted passwords from LNKD had been leaked, we'd be having a totally different conversation right now. (Same, of course, with scrypt etc.)
These hashes were posted on a forum as a plea for help: the guy did not have enough computational power to crack them all on his own. Had they been salted bcrypt hashes, it might have actually discouraged him to the point of not even trying.
So yeah, the weakest passwords will always fall, but good solutions will go to great length to protect even the most clueless of users.
Am not a cryptographer by any means, so please correct me if I'm wrong:
If you use any reasonable cost for bcrypt, you're talking hundreds of milliseconds per attempt on a modern CPU. For each 6-character password (since you can't generate a rainbow table) at 100ms per pop, you're talking about something on the order of 2+ years per password divided by the number of CPUs. With something like 900 CPUs running continuously, you could expect to recover one 6-char every day if the passwords were randomly distributed in the 6-char alphanumeric space. So, pretty feasible, assuming a 100ms cost. Short passwords do hurt you; I agree.
Now for 8-char alphanumeric passwords, you'd have to run ~1 million CPUs continuously to expect to recover one per day at a 100ms-per-pop cost. This is more of a stretch, assuming you're trying to do this with, e.g., botnets. It seems that someone asking for help cracking a password list on a forum would probably not be able to assemble this much computing power.
Or 1 billion CPUs continuously to expect to recover one 10-char alphanumeric password per day.
Of course, the assumption of random alphanumerics is wrong, both because many people will use common passwords and because others will use non-alphanumeric character substitution.
At any rate, it seems to me that leaking non-salted SHA1 hashes is virtually the worst case disaster scenario, short of plaintext passwords.
But suppose tomorrow it takes 10ms. Also, tomorrow, available spaces will increase, so the likelihood of a space vs time tradeoff (even partial) increases
WEP was considered "good enough" at first (even though it had obvious problems at first like key size), WAP was considered unbreakable at first, today it's feasible with cloud computing or GPUs.
And then we'll be complaining on HN that they didn't use xyzcrypt or something instead of bcrypt.
" it seems to me that leaking non-salted SHA1 hashes is virtually the worst case disaster scenario"
The time bcrypt takes is configurable, so in the future you can adjust the amount of work per password -- this is literally a one-character change in your code -- and be alright again. Ditto for the rest of the decent password hashing schemes.
I think you are propagating the myth that a scheme can be secure forever.
It's ok if WAP is breakable with cloud computing, because the whole point was to secure it for the next X years so that it takes more than Y dollars to break it. You only need to protect million dollar data enough that it costs 10 million dollars to get it.
If the data is valuable enough and protected heavily enough with crypto, the cheapest way to get it is through a meatspace attack (break-in, abduction, etc).
> WEP was considered "good enough"
Not by security professionals once they saw the effective size of the key. It's the downgrading of what looked like a 64bit key into a 48bit key that was the biggest problem.
The math doesn't sound right. Google allows any ASCII character for their passwords, which is 95 chars. I calculate 2330 years to crack each password. Did I get something wrong?
(95^6 * .1sec per hash) / (60sec 60min 24hrs 365days)
The key difference is bcrypt does ~10 hash/sec. A GPU-enabled password cracking machine can do over 500 million hashes per second. That generates a rainbow table in ~30 minutes.
Please stop stirring up drama about this issue. While you are technically incorrect (PBKDF2-SHA1 is faster than and thus inferior to bcrypt), it's irrelevant: all three of [scrypt, bcrypt, PBKDF2] are just fine, and you can safely pick one at random.
I just had to make this choice a few days ago and bcrypt seemed like the best option with working PHP implementations. And I sure as hell am not going to try to roll my own.
I wonder, why do people saying "just use bcrypt" never, ever bother to elaborate on what benefits it has, and which of them are relevant to the subject of the conversation? Believing in some function without understanding implications of its use does very little for real security.
It's not an in-depth answer. It does not say, for example, why bcrypt is more secure than nested SHA1. (I believe it has to do with the possibility to efficiently implement SHA algorithms in GPUs.)
People are using unsalted SHA1, because someone told them in the past "just use sha1". Now someone else tells them "just use BCrypt". Without understanding why, it's nearly impossible to to decide which security policy is sensible. There are many different types of advice competing for attention, and not all of them are good.
Somebody once said fire was composed of phlogistons. Later, different people said that fire was instead a process of decomposing fuel molecules and a release of visible light due to the energy of the chemical chain reactions taking place inside the flame.
The guy who said "phlogistons" was wrong. So was "just use SHA1" guy.
Bcrypt does not require your understanding. The most important thing is that you use a strong password hashing method -- of which bcrypt is the best-known, and an excellent choice. For a basic level of understanding, here's a slightly exasperated blog post that a lot of people link to:
I wonder why people who make this complaint never ever bother to google: "why use bcrypt". It's like they somehow forget they have the best magical oracle to answer questions at their fingertips, which can answer the question better than most people who understand bcrypt could.
stef25, this is known as key stretching, as others have already explained elsewhere in this thread. Essentially the idea is to make computing the final hash of the password slower by iterating the hash function many times.
This additional slowdown is unlikely to be noticed by a user during an interactive login (hashing the password may take 1ms instead of 1us -- an imperceptible difference to a human) but it dramatically slows down the speed at which an attack can compute hashes to try and recover the password for a leaked hash. It also increases the amount of storage space required for (a naive implementation of) a rainbow table since the attacker would need to store the output for 1, 2, ..., n iterations of the hash function.
I'm not familiar with iterations, anybody care to clue me in? I would have thought salted sha-1 would be decent for password hashing, though not the most solid possible, but at least not laughable. Is that not the case?
It is not. Sha1 is designed to be fast. You want your password hash function to be slow, so that an attacker has to spend as much resources as possible to brute force it.
Of course, it does not mean you should take a slow implementation of a fast hash. You need a hash that, when implemented to be as fast as possible, still is pretty slow.
I've just downloaded the database linked and it only contains the hashed passwords, not the account usernames / e-mail addresses.
I wonder if someone has the account details to match up otherwise you've no idea which password belongs to who, and you'd hope that LinkedIn would have lockout functionality.
LinkedIn allows you to sign in using any of your verified email addresses, so it seems likely that the usernames are at least stored in a different table.
MD5 isn't the issue - it's the lack of salting. Without a salt, almost any hash can be cracked with a rainbow table. With a salt, you'd need to know the salt for each hash, and then generate a new rainbow table, in order to recover the original password.
This isn't really the issue. The real issue is that MD5 (though these hashes are SHA1, which has the same problem) are too easily computed; they are practically byte-forceable. I don't need a rainbow table to compute hashes when I can slam out millions in short order using a GPU. You have a good point about needing to know the salt, but getting the salt is generally easy because it's usually stored in the same place as the hashes (and this practice is fine, because hiding the salts doesn't improve security significantly on its own).
What prevents developers from adding a large DB-wide salt (in addition to normal salt) to every password? Wouldn't that prevent bruteforce attacks regardless of the hashing algorithm?
128 bytes is not "large". I was thinking more along the lines of megabyte+. There is no question that it will slow down hash computations, because you would need to process more data. The question is, can you efficiently parallellize this in a commodity hardware (GPUs)?
Random nonces have very little to do with what makes SHA1 insecure and bcrypt secure. Developers have a very weird and totally misplaced faith in the ability of random "salts" to secure passwords.
We're speaking about a very specific attack here: bruteforce. And I'm speaking about a very specific type of "salt" (which could probably be called something else, since it's not the same as normal unique-per-password salt): large, database-wide string of random bytes.
If every password is padded with such a string before hashing, computing the hash would be slower. Obviously, it would be slower because you would have to process more data. An interesting question is whether this would also make it less parallelizable by the virtue of having more information than would fit into GPU cache.
None of this makes much sense to me, sorry. Brute-force password cracking has worked on salted passwords since Alec Muffett released Crack in the early '90s. The amount of extra computational power required to hash a password and a salt is negligible.
The only thing "salts" do is prevent rainbow table precomputation, but it's just a quirk of the late '90s and early '00s that "rainbow tables" ever became a mainstream attack method: one bad Microsoft password hash and a series of bad web applications. Long before the MD4 LANMAN hash was ever released, people were breaking salted Unix passwords with off-the-shelf tools, on much, much slower computers than we have now.
Computing a hash on 1MB of data is slower than computing a hash of 6-8 bytes of data. Brute-force attacks are based on trying different passwords and seeing that after being salted they generate the same hash as in the database. Therefore, adding a large string to the password before hashing would force the attacker to hash that string. The question is, can this be pre-computed once or efficiently parallelized?
You're advocating creating a 1MB "salt" string to slow down hashes? That's the same as simply iterating your hash function enough times to invoke the block function repeatedly.
Just use bcrypt, scrypt, or PBKDF2. People have already figured this problem out.
First, I do not advocate anything here. I asked a question.
Second, working with a large string of bits is the same as recursive hashing only if you can pre-compute some small intermediate state of the hash function for that string independently from the password you're trying to guess. If you can't, you would have to work with the entire string for every new password tried.
1MB of data will have 16384 SHA 256 blocks. So that's roughly the slowdown I would expect, minus the time it takes to initialize the algorithm for a particular message.
That's not that interesting by itself, but it is interesting to think about how this would affect computing the hashes on GPUs.
The difference is that if it's salted you need to work to get a specific password. Without salting you can test a generated hash (rainbow table) against all 6.9 million hashes at the same time.
Not defending the choice - bcrypt is obviously a much better way to go.
The thing is, though, that it's trivial to slam through that set of salted passwords. It's like unsecured Wi-Fi versus WEP: "door unlocked" versus "'No Trespassing' sign."
To be clear, MD5 (or SHA1 as these apparently are) is a problem. Passwords should be stored using a cryptographic hash function that is designed to hash passwords (read: be slow), not a generic cryptographic hash function (which are designed to be fast). This is exactly the problem that bcrypt was created to solve (among others).
I think people are missing the point that SHA2 is light years ahead of MD5. MD5 has had known security flaws for years.
>Do not use the MD5 algorithm
Software developers, Certification Authorities, website owners, and users should avoid using the MD5 algorithm in any capacity.
Still, it doesn't matter. As long as one can generate a rainbow table for the hash function, then password lookups will be a O(1) operation. The rainbow table for md5 is moderately small, sha1 is bigger, and I'm sure sha2 is even bigger than the sha1 table.
The security differences between SHA2 and MD5 are irrelevant to the matter at hand. If they were MD5 hashes they'd be broken approximately as quickly and in exactly the same way.
Keep in mind that whoever leaked the hashes is probably keeping the usernames / emails for themselves. The forum in question doesn't allow posting of user-identifiable information according to the forum guidelines.
The leaked hashes seems to be SHA-1. I've also confirmed that the hash of my own (semi-complex) LinkedIn password is in the list.
Accidentally this is the same password as I had for HN and that I've now changed (phew! THAT'd been bad! :-)
It would still take a moderate amount of time for a single password if it's long and complex -- you're essentially generating the rainbow table. You might as well just download a sha1 rainbow table and just perform a O(1) lookup. You could reverse all the 6.5M password hashes in mere seconds.
Actually, for a large enough list of unsalted password hashes, bruteforcing is faster that rainbow tables:
- a rainbow table may require a constant amount of time to reverse 1 hash, but it has to be repeated N times for N passwords.
- when bruteforcing, a password candidate can be checked against N hashes in a constant amount of time (look up the candidate hash in a hash table)
For example if it takes 10 minutes to look up a hash in a very large rainbow table (such as the A5/1 GSM tables published a few years ago), it would take 123 years to attempt to reverse these 6.5M hashes. On the other hand, millions of the leaked SHA1 hashes can be cracked in mere hours on a GPU with oclhashcat which tests billions of candidate hashes per second.
true, for extremely large rainbow tables. SHA1 tables are around 20-60GB depending on how large your base character set is. If you shoved all this data into a giant database, query speed is still under a few milliseconds. In general, rainbow tables can be sharded fairly easily, so if your data set is a few hundred terabytes, just split it across a few machines and you'll retain the millisecond query times. Storing and querying easily partitioned data will usually be faster than a brute force calculation.
Calculating it is like saying you want to find the fibonacci number for any given N, and you have a really fast processor to calculate it to that N, but if you just persisted pre-calculated values up to C, you'd only need to calculate N-C hashes. So even if you are bruteforcing the password, it is still faster to have rainbow tables up to a certain length.
What I say is true for any size of rainbow table. It seems you forget that RT lookups require CPU resources in addition to mere I/O resources. There is always a number of hashes beyond which brute forcing them is faster than RTs. Sometimes this number is very high (billions of hashes), sometimes it is lower (thousands of hashes). It depends on many factors: RT chain length, speed of the H() and R() functions, speed of the brute forcing implementation, etc.
To take your example of a small SHA1 rainbow table of 20GB, assuming it has a chain length of 40k, looking up a hash in it will require on average 200M calls to the SHA1 compression function (assuming a successful lookup). A modern CPU core can do about 5M calls per second. Therefore looking up one hash will take at least 40 sec, and looking up these 6.5M LinkedIn hashes would take 8.2 years! (This is just counting CPU time, I assume the RT is loaded in RAM for a negligible I/O access time to its data.) A RT of this size would cover a password space of about 2^44. For comparison a decent GPU can brute force this many hashes concurrently at a speed of roughly 500M per second (see oclhashcat perf numbers on an HD 7970). Covering the same password space would take only 9.8 hours. Compare 8.2 years vs. 9.8 hours: obviously the LinkedIn hashes that have been cracked so far have been brute forced, not looked up in RTs!
And even if you leveraged GPUs to perform RT lookups, they would speed up the computations by roughly a factor 100x, reducing the 8.2 years down to 30 days, still unable to match the short 9.8-hour brute forcing session. (My friend Bitweasil is doing research on GPU-accelerated rainbow tables, see cryptohaze.com)
The rar with ~100k cracked passwords in it. If you tried to find your own, perhaps you're one of the ~144 million accounts that wasn't published?
Edit: I'm not sure I understand what you mean - there was 100k passwords in one file, already cracked, and another with all 6.5M hashes. I found my hash in the hashes file.
As a more general question: why is it not an industry standard to salt with the username/email in addition to the random key? (i.e. Sha1($salt + $email + $password). Even if the random salt were excluded, I would think that this is much more secure. Existing rainbow tables would not be anywhere near as helpful, and attempts to generate a rainbow table for a specific salted database would be ineffective because the salt changes on a per-user basis.
As a more general question: why is it not an industry standard to salt with the username/email in addition to the random key? (i.e. Sha1($salt + $email + $password)). Even if the random salt were excluded, I would think that this is much more secure. Existing rainbow tables would not be anywhere near as helpful, and attempts to generate a rainbow table for a specific salted database would be ineffective because the salt changes on a per-user basis.
Why would you use the email? Mostly when passwords/usernames are stolen the email is there too. For my site I have an unique 128-bit token for every user. I also have a 128-bit site_key (which is in the application, not db) and mix those with the password and then hash.
Then the password has to be updated whenever your email changes. I believe Amazon does it like that, literally "forking" whenever you change password; at one point it was possible to simply log on with the old password and live an "alternate reality" where all changes you'd done after changing pwd had not been applied. Don't know if it's still the case today.
The solution is to use a better method of storing passwords. Hashes like SHA1 are designed to be really fast (great for hashing data but also great if you want to brute force).
You can perform this check even if they were salted.
Otherwise how could linkedin check if you correctly entered your password?
The salt is contained in cleartext as part of the hashed password, so that you can repeat the hashing the secret and match the two hashes.
The salt improves the security because:
1. even if two users use the same password, you cannot tell that by simply comparing the hashes
2. makes brute force checks much slower because you have to recompute the hash for every hashed password entry rather than once for every dictionary entry
Which should be done, but which doesn't help those users where it matters most; the real value of this database is that some people (~everyone) reuses passwords across sites.
To get a sense of it, I downloaded it from a link here. Below is the structure of the first few lines. Caveat: it's garbage/useless data below -- I intentionally changed around the actual numbers to give a sense of the structure, only:
The pattern 000000a9 is just in presentation - I counted the occurrences of different bytes in that position (also misled by the apparent pattern, where many lines in a row would have the same 4th byte), and each possible value is present more or less equally often.
It seems like it's just sha1.
EDIT: however, 3.5 million hashes start with 5 zeroes, which is way too many for just coincidence. Possibly they used multiple hash functions?
Can we please start using BrowserID or some other standard so we can secure that one provider and do away with all this? I'd like it if we could authenticate with Google using 2-factor authentication and be less worried about my password getting hacked.
A single point of failure sounds dangerous.
People should just avoid using the same password for different websites. (That's what KeePass is for..) Perhaps a clever extension / browser feature could ensure that. (e.g. "Warning: You are probably using the same password for facebook.com")
By centralizing authentication, you make that central provider an even bigger target and you risk losing access to other services as you lose your main account (Google is known to sometimes terminate accounts with no way of recurse).
Finally, when that central provider gets hacked, all your dependent services are now also compromised.
And as we know from the CloudFlare story over the weekend, not even Google with their 2 factor authentication is devoid of issues.
No. Centralizing your login to one third-party as as bad as the current practice of reusing your password for every service you have an account with. The only way that is reasonably safe is to use different random credentials for every service and store these credentials somewhere under your (and only your) control (i.e. a password manager or a piece of paper)
Browserid is not a centralized authentication protocol. Although currently all implementations I know of rely on browserid.org, this is not required by its design.
There's also the fully decentralized openid, you know. I'd 100% rather be able to use openid for sites like Linkedin and this one than rely on every site implementing sane password management.
There is no reason why we should centralize password management and put the world's authentication into one giant pinata for black hats to take a swing at.
Wow. Not only is every single reply to StavrosK completely wrong about how BrowserID works, they're actually doubly wrong. Not only is it NOT centralized, it also can be used with:
- 2 factor auth
- asymmetric encryption (aka, a challenge/response ala PGP)
- whatever security mechanism you want, frankly. It's up to the browserid provider.
My rationale is that it's much easier to secure one provider (the attack surface is much smaller), and you can also run one yourself, making you responsible for all your authentication needs.
OpenID was great in that you could choose any provider you wanted, and nobody could attack them all (not that they'd have to). It just seems like a good solution to use someone whose only job is to provide secure authentication.
When Twitter recently had accounts and passwords leaked, many were attached to spam accounts or duplicate records. Most had obvious passwords (like 1234).
Are these legitimate active accounts? Can you do anything with the hashed passwords alone?
In fairness to Twitter, it was never actually known if the accounts/passwords came from Twitter.com (proper) or (more likely) leaked from some 3rd-party Twitter-integrating app that had pre-OAuth integration.
This makes me wonder. I've been relying on Django's built in user authentication lately. Does anyone know if that's pretty safe? Is it doing the right thing for hashing passwords?
I sincerely mean no offense but this statement came directly out of your butt. Read the table on page 14 of Colin Percival's Usenix paper "Stronger Key Derivation Via Sequential Memory-Hard Functions" (which you could have found by Googling [scrypt paper]); PBKDF2 is ~5x faster (ie: costs ~5x less to break) than bcrypt; PBKDF2 and scrypt aren't even in the same ballpark.
From exactly where did you derive the idea that PBKDF2 is "extremely good"?
The reality is that all three of PBKDF2, bcrypt, and scrypt are just fine. But PBKDF2 and scrypt have drastically poorer library support than bcrypt; nobody should delay using a strong password hash so that they can optimize which one they use.
Eh? PBKDF2 has configurable complexity and has found many more applications than bycrpt, from WPA2 to disk encryption. The crypto research behind PBKDF2 is much more rigorous.
Please cite one academic cryptography paper that presents an analysis of PBKDF2, other than Colin's paper which damns it.
There is virtually no "rigorous" research into KDFs of any sort, let alone password KDFs. Most academic crypto research simply presumes passwords are taken from cryptographically secure random number generators and stored securely.
And with that said I want to remind you that I just cited a source, accepted at Usenix, that measured PBKDF2, bcrypt, and scrypt and found PBKDF2 inferior to bcrypt. You seem to want to pretend otherwise.
All three are extremely good for this use case, when the competition is SHA-1. Beyond that, I don't know enough to compare the three. So yeah, it came out of my butt.
If Colin has a paper on it then I trust his comparison. What I really meant to say is what you said: all three are just fine.
Also, I thought I remembered my comment's parent saying something stronger, either it was edited later, or I was drunk when I decided it was worth commenting on.
Django has chosen a fine default and for the next several years it's probably unnecessary to second-guess it. Over time, GPU and (more importantly) FPGA-assisted hash cracking may or may not become more common, at which point you'd want to transition to something like scrypt.
You could literally flip a coin to decide between bcrypt and PBKDF2 and it wouldn't matter which side came up.
I'm not an authority on this, but django_bcrypt is generally considered a best-practice in the Django community. Scrypt may replace that in the future, once implementations are widely available and battle-tested.
I know a lot of companies just keep your account including your password in there database while you removed your account.
Can I be sure my account was totally removed when I removed my LinkedIn account? Because the "please change your password as soon as possible" won't help me much.
What riddles me though, is how come 6.5 million?
LinkedIn has what, 150M users?
Did they not post the entire load (and are in fact sitting on _all_ the hashes?)
Is the dump an old backup or breach from when they had fewer accounts?
Is it just one DB partition / file that's been lost, an archive?
Given that these hashes are not salted, running a 'uniq' on the list of all users' password hashes would probably already cut it by half, if not more. Then you eliminate all the easy ones from wordlists, and post the remains on the internet for people with excess computing power to bruteforce.
I assume the first line you meant to pipe it through uniq afer the sort? Otherwise the only thing you've demonstrated is that sorting a file doesn't change its line count. :)
And a follow-up: "Our team continues to investigate, but at this time, we're still unable to confirm that any security breach has occurred. Stay tuned here."
Good Guy Startup Founder would cross reference this password list with their own password system and force those that match to reauthenticate and change their passwords.
This wouldn't be difficult to do and your users would appreciate it.
I've found '1234678', 'password', 'qwerty', 'linkedin' and few other common phrases (already 00000'd, obviously), so it doesn't look like a list of just the hard ones.
Or, they could take the Zappos route and just force everybody to reset their passwords. This route would make adopting a different (e.g. salted) password system quite straightforward.
The released passwords are hashed with SHA1. Assuming you use the same algorithm and linkedin does not use a salt (they probably do), then you could just compare the hashes.
You can't compare the hashes unless you have access to the clear passwords of your users. Unless you mean to do the comparison just as they log in. Seems like a lot of hassle for not much though.
LinkedIn passwords are not salted. You can only make comparisons if your database contains unsalted passwords. And if both databases used salted-passwords, then you still can't compare unless you all shared the same salting key.
you'd compare the hashes in your database with those from the file. The users with a hash contained in the file would be notified.
Because the passwords aren't salted(stupid), you might get multiple hits for the same hash(for example, for the good old "1234" password), meaning you might end up contacting more users than actually affected. Better safe than sorry.
You'd do it at login time. User enters user/pwd -> hash with unsalted sha-1, check if in list -> if yes, alert to change / if no, proceed with normal hashing.
Easy, just convert all the hashes into passwords using a rainbow table. Should only take a few seconds to convert all 6.5M passwords -- O(n) operation here. Then run all the passwords through each user's password algorithm, this is a O(n^2) operation. Essentially you're making 6.5M password attempts for each of your users. It could be slightly faster because I'm sure there are quite a few duplicates in 6.5M passwords.
What's wrong? They exist... they're bigger than md5 tables, but not significantly larger. If you don't have 50GB of free disk space, you could get a table with lower complexity for around 20GB or so.
A cross-reference is only feasible in very bad situations:
- no-salt or same-salt and same hashing
- trivial/common passwords (password1 etc)
- password(hashed/unhashed) and email are paired.
A cross-reference could be accomplished for all known cracked linkedin passwords, but this would be no different then you running a dictionary attack of known passwords against your own users... This seems very bad. Enforcing strong but sane password strength rules should mitigate this need.
Cross reference only has value if both the hash and email pairs are leaked.
The bitcoin leak fell into one of these very bad situations:
- [<email>, <hash>] where leaked together
- poor hashing (just sha1, no salt if memory serves)
- unfortunate number of people reuse passwords
That's easy to do it you have the email addresses, but impossible to do if you only have the SHA-1 hash, as in this case (unless you're also using unsalted SHA-1 hashes, which is a much bigger issue by itself).
i agree, but think about the backlash this would create amongst the userbase. the majority of the users will probably never even realize / read that their passwords have been stolen and thus linkedin probably does best in keeping a low profile about this (and start from now on using a better encryption). this is obviously not in the interest of the users, but it is in the interest of linkedin.
It's possible to test this when your user re-authenticates, assuming you're not using a challenge-response authentication mechanism (as sadly most sites do not).
You're free to hit "delete" on linkedin, but there's a very high likelihood that it will only mean "hide my profile". Anyone who got your user/pass would probably be able to reinstantiate your account and do anything to it they wanted.
I took the step of markedly decreasing the information on my current legit profile. It includes my name and general title, but no job history. Public disclosures of connections, etc., are highly limited.
Having a fictional LinkedIn account can be amusing.
What's kept me away from such solutions are these questions: How can you trust one service with all your passwords? What if their configuration has a vulnerability?
Use open-source tools such as SHA1-Pass. The passwords it generates can be recreated with openssl and any other standard crypto library.
Edit: I wrote SHA1-Pass, so I'm biased, but I know what you mean about having trust issues with closed-source password tools. That's one of the reasons I wrote it.
I use open source tools such as "pwgen", "emacs" and "gpg". Open up the encrypted file in the editor, type your pass phrase if you haven't this session, cut and paste, close file. The built-in keyboard navigability makes this faster than everything but the in-browser form filling.
You might consider renaming it. I've been looking for several minutes and can't find it via that name.
Is it this: http://manpages.ubuntu.com/manpages/natty/man1/sha1pass.1.ht... I don't see how you would use this the same way you'd use the other tools mentioned here. I can imagine a way, but it's no where near as convenient and still has it's own major usability problems.
I use 1Password, rather than lastpass. On that system, your password file is stored locally by default, so their isn't a centralized password store to attack. If you do syncing of passwords between machines, you keep an encrypted password file in your dropbox account.
Nothing, really. However, I trust the LastPass guys to keep their shit secure as much as I trust myself to keep my own system secure.
After all, if my own system is compromised, I just get a lot of hassle. If LastPass ever gets hacked and leaks their passwords, they lose their business overnight. That's pretty good motivation for them to keep on top of their stuff.
I used to use 1Passwd, which stored the passwords in a local file, and that could be said to be marginally more secure, except that it generally uses something like iCloud or Dropbox to sync the passwords, so there's still a single point of failure... The main reason I moved away from 1Password was that they gave me a shitty response when I asked them if they were going to support Chrome. I decided at that point that I didn't want to give them my money anymore, and so I didn't upgrade to 1Password 3.
The big difference between "hosted service" and "encrypted file in the cloud" is that the hosted service has, by definition, to store the key next to the lock to be practical.
The key for your encrypted file stays in your head (and/or in your wallet), so even a full-on total breach of Dropbox/iCloud, your key is safe, and 8 million rounds of 265-bit AES and a good password (my current KeePass settings) is still unbreakable[1].
1: Unless (perhaps) you have the attention of certain governments. And they always have the option of using a $5 wrench on you, anyway.
Why can't the hosted service use an "encrypted file in the cloud" as its implementation? As long as it requires client-side code to do the decryption, the key stays in your head alone.
As far as I know, LastPass does not "store the key next to the lock."[1] The browser extension encrypts/decrypts locally. If you use your password file through the web site you're still downloading your encrypted DB from them and encrypting/decrypting locally (whether with the extension, or I believe they also have a pure JS implementation).
[1] Or so they say. I've never MITMed their SSL, and their software is not open source AFAIK. This is not to say someone couldn't e.g. distribute a trojaned version of their browser extensions. If you poke around the developer(s) have at least revealed the encryption method for the your DB so you can verify how it is encrypted for yourself, which is a good sign if nothing else.
> except that it generally uses something like iCloud or Dropbox to sync the passwords, so there's still a single point of failure
No. This is the strength of two-factor authentication, something you know, and something you have. If someone gets your 1Password keyfile, it's useless without your decrypting password.
KeePass works well too - open source, offline solution that has an "Autotype" function.
I actually only run into passwords that are a pain on mobile devices. Now that my Android phone has no keyboard but tons of power, that's becoming more and more significant.
I use keepass too. I keep my database in dropbox and use the android dropbox and keepass clients on my android. Logging into an app or website involves opening dropbox, clicking on the database[1], entering my password, choosing the site, and clicking on "copy password to clipboard." It's a few extra steps, but it's not that much of a hassle.
[1] I find this easier than opening keepass and selecting the database from dropbox for some reason that might be as simple as dropbox having an easier to spot icon.
You can also use the favorite feature on Dropbox to keep a fresh copy of the database on your phone and have KeePassDroid remember that location. Then your flow is 1) open KeePassDroid 2) enter password 3) select site 4) copy/paste
One more KeePass user here (actually KeePassX). But I'm using it only for not my own passwords, provided by others and so on.
For my personal ones I'm keeping few algorithms in my brains. I'm using resource type (website/some server/device) and name (e.g. domain/model) as variables and after few steps in my head I always have different password for each kind of service.
The enter (long alphanumeric and symbols) password/copy/paste/switch window was a little clunky in Android 2.2. Little better in ICS, so need to get back to using this.
I think it's a risk with a solution like this, but much less of a risk of having to remember all these passwords myself (a practice which tends to devolve to re-using passwords).
This is why I use 1password and not LastPass - the encrypted password file is stored locally - optionally in Dropbox, which is what enables moble and remote (http online through Dropbox) to work.
LastPass encrypts your passwords using your master password as (at least part of) the key. This means that they do decryption of passwords client-side as well. The entire password file is not stored locally but they had an intrusion of some sort a number of months back which demonstrated that they have a pretty good system set up along with quite a bit of monitoring. Truecrypt in dropbox is obviously a good choice if you're super paranoid but after seeing LastPass respond to security really well and it having an overall pretty simple UX, I don't have any reason to not recommend it.
I use KeePass right now synced with Dropbox - what keeps me up at night is the fact that if the bad guys got my password file today, there could turn out to be a vulnerability in it discovered years from now that could allow them to get my password.
It saddens me that every, single, time this topic comes up, HackerNews, of all places, displays an immense lack of knowledge of current password storage applications, how they work and what value they bring.
I think it's really humorous that people feel safe putting an encrypted file in something like Dropbox, but don't trust LastPass (who are doing the exact same thing, everything is local, client side encryption). Especially when you're missing out on all of the benefits of browser integration.
Please, take a whole 3 minutes and do a tiny bit of research. Your future self will thank you when people like swombat and myself get to laugh at LinkedIn, change our passwords and never think about it again.
I think the difference you're missing is that LastPass offers the OnlineVault option.
I much prefer the security of being in control of my file, and having its online option controlled by someone else (Dropbox); and logging into Dropbox to then see my passwords 'online' on the go.
If Lastpass.com is compromised, the attacker can MitM compromise my credentials.
If 1Password.com is compromised, that is not the case. (Yes, if Dropbox is compromised, they could capture my dropbox credentials, but it would be more difficult for them to then capture my 1password credentials)
>I much prefer the security of being in control of my file, and having its online option controlled by someone else (Dropbox); and logging into Dropbox to then see my passwords 'online' on the go.
You can't even do that. You have to install a local client. Download the file, open it in your new client, edit it, manually reupload it. If you don't want to use the on-web LastPass vault, then don't, but it's still doing local decryption and you can still used the signed Chrome extensions to carry out ops if you don't trust LastPass.com proper.
>If Lastpass.com is compromised, the attacker can MitM compromise my credentials.
Which part of "local, client-side encryption" is confusing?
edit: 1PassAnywhere is the exact same thing as what LastPass is doing with it's LastPass.com-served Vault.
edit2: There's even multifactor auth available for it and the Online Vault feature.
I apologise for my immense lack of knowledge of current password storage applications (i'm not a programmer and come here for the other stuff), but what is the benefit of these services (lastpass etc)? This is a genuine question.
It seems to me that instead of having several passwords in my head (i can remember random long strings of characters pretty well, and have a heirachy of randomness/longness depending on what I care about), I only have to remember one. But if that one's compromised, aren't all the rest then available?
Reminds me of the bit in hitchhikers guide to the galaxy (life the universe and everything i think) where passwords and biometrics etc had become really difficult and secure, so a datacube thing was created to store them all. Which was then found by a character before hilarity ensued.
1. Your physical machine, or the LastPass/Dropbox server.
2. Your master password
3. (optionally) a second-factor auth source
Then yes, they have access to all your passwords. But this is vastly superior to having one password that alone compromised grants access to all of your accounts, right?
I mean, the most secure way imaginable would be perfect biometric signatures, or humans smart enough that they could perform asymmetric encryption in their heads to sign challenges in a verifiable manner. Outside of that, this is decentish.
You could use a text file in a Truecrypt volume with keys that are stored on separate jumpdrives (but what if someone compromises a machine that you plug those drives into), etc, etc.
I'm worried in a few years LastPass could become a target, and now instead of someone having a password that 'could' be shared among your multiple accounts, you have now given the complete keys to the city by listing all of your logons great and small in a central repository.
This central repository then becomes a very appealing target.
I say this as a LastPass user, as I think it is the best of the current offerings, but I'm uncertain how to shield this huge central list. I wish it had multiple logon PW so that you could at least segment the risk and reduce the time the high PW is used to when you really need it.
First rule of software design: users are lazy.
Second rule of software design: users are stupid.
"Use your own lock" is fine for us Übergeeks, but for the vast majority of the populace, they just want the provider to put a system in place so they don't have to worry about it.
"We were curious what would happen to our share price if our company did something incredibly stupid"
The above comment might seem incredibly harsh, but really, there's no good excuse for a site this prominent to not have a salted, secure password hashing system. Even if they started with an unsalted password system, users can be migrated to the newer more secure system on next login.
The only way I could regain respect for LinkedIn is if we find that these unsalted hashes were from users who never logged in to LinkedIn after the security upgrade. From the replies of other HN users who have found their password hashes in the leaked list, this doesn't seem to be the case though.
I can understand database leaks. Bad things happen. Not being prepared for such an event however is where I draw the line. These leaks impact users far beyond just the site at fault.
It's not enough to say users should use LastPass. They don't, and that's the world we live in, for better or worse.
If computer security doesn't take into account problematic users, then it's flawed computer security.
Regarding requiring users to log in; wouldn't it be better to run their current hash through another password hashing scheme (while we're at it bcrypt, scrypt, PBKDF, etc)? Then, the next time they log in, verify them by running their password through the old algorithm, and the result through the new one.
That could be a good transition strategy if you're worried about being compromised before all your users have logged in again, but you would still want to move them over to using just the new system when they do. It probably would be fine, but when it comes to crypto you don't take chances when you don't have to.
Surely just hashing the username|password would massively reduce the effectiveness of leaks like this? Sure, a hacker would know what the "salt" is, but since it now varies between users you would expend the same amount of effort breaking one person's login as you previously would spend breaking everyones (on average).
(Not recommending it, just wondering if my reasoning is correct.)
It would make it a lot easier for LinkedIn to identify whose hashes were leaked because with a salt, all passwords would be unique. It would also make rainbow tables useless.
But in this day and age, the bigger problem is how fast you can compute the hashes, salt or no. With GPUs you can calculate a few hundred million(depending on the hashing algorithm) per second, making the algorithm used the real vulnerability.
Best practice involves increasing the calculation time of you're algorithm. Theoretically, you could just rehash y few thousand times in a loop, throwing in a salt here and there, but practically, you should just use bcrypt or scrypt.
I hear this commonly, so it is a good idea to clear it up.
Usernames have lower entropy than a random salt and are predictable in many cases. People re-use usernames and some usernames are common. If your password system became common on the web, or if I knew the workings of your password system (i.e. open source / leaked codebase / Kerckhoffs's principle[1]), I could generate a rainbow table for either common or targeted users. This means I could generate a rainbow table for "Jabbles", gain access to your password and compromise your account before the website is likely even aware of a breach or has time to warn you. Salts only act to slow down, not prevent, compromising leaked password hashes (as you can always brute force which is quite practical with MD5/SHA1). Thus, using a username defeats one of the stated purposes of salting.
It's also said ad nauseam (with good reason) but rolling your own in security is a bad idea, especially when libraries exist that do exactly what you'd intend to do just as easily. Algorithms such as bcrypt and scrypt exist and are well vetted. bcrypt is easy to integrate with many languages and provides a trivial interface and sane defaults for iterations/rounds [brute force] and salts [rainbow table]. bcrypt can also handle increasing the security of your system over time as the metadata is stored as part of the hash.
tl;dr Using a username for salting means a targeted attack against a single or small number of users would be damn near impossible to stop as the second they have the password hashes they also have the passwords.
Often people say "Don't roll your own security" but the reality is that developers aren't trying to roll their own. They are trying to solve a problem, and if a quick google doesn't turn up a good library then they'll try and figure it out. Googling for password security implementations is likely to be fraught with horrible horrible advice.
I guess what I'm saying is that it's not enough to say don't do it, instead the defaults need to be there (and very visible).
I think we've reached a point with bcrypt that a good secure password system is within reach and comes with sane defaults and ease of use as features for most programming languages.
If it's just an issue of getting the word out there, then I'm hopeful things can improve.
You need more than just bcrypt. You've hinted at other things, but a few random things popping in to my mind:
* Preventing password logging (many web frameworks log parameters)
* Secure password recovery
* New alternative attack vectors (eg. Facebook, Twitter auth)
* XSS and CSRF
There are so, so many simple to make security errors, and worse - many of them are inter-related so that forgetting one will make another vulnerable. This is why you need safe defaults and more Security education.
A strong password hash doesn't gate on any of those things, so, while you do indeed need to pay attention to them, you don't need to pay attention to them before you deploy a strong password hash.
You should deploy a strong password hash immediately.
True point and this is probably off topic, but out of curiosity, what is the recommended approach for his point about logging messages/requests?
On previous projects, we've gone through all sorts of machinations to detect a password in our SOAP logging. This usually involves XML parsing (slow, ineffective on malformed messages) and Regexes (ineffective on malformed or "unusual" messages).
I can't think of anything better, short of "you can't leak what you don't log" which is nice in theory but not always practical.
There are defaults bcrypt and PBKDF2. There is no excuse for anyone to do anything less than salted hashes even if the decide not to follow bcrypt or PBKDF2.
While not entirely random, would a "date based" salt work as well? Say, the date that the entry was added? This would still negate rainbow tables as a specific user entry needs to be targeted.
It would probably work well enough, but... why not just add a proper random salt field that isn't tied to anything an attacker could guess? Is something like 8 bytes per user too expensive?
Having a password salted with the username fairly easily balloons out the complexity of building and searching a rainbow table by a factor of the number of usernames you want to be useful for. This factor is larger then you'd expect, given the sheer quantity and variety of usernames in various systems.
For a targeted attack it really doesn't matter as the time complexity to produce the rainbow table is equivalent to that of simply brute forcing the hash, ie, you can't say 'well assume the rainbow table contains only some small number of usernames"...
It also is entirely unlike the WPA2 rainbow tables in that you don't have millions of users all sharing the same username (ie. factory default SSIDs).
Overall it's more secure then it seems at first glance but you still have to ask yourself why you'd use that over a random salt.
The targeted attack does matter though, for the reason I pointed out above.
I can produce a rainbow table offline before I compromise the targeted system as I know the username of my target. This is not possible if the salt is random. This means I can crack a targeted user's password hash _instantly_ upon gaining access to the system.
With a random salt, you can only perform the brute force attack on that targeted user _after_ you've gained access to the system and likely alerted them to a compromise.
If the response time of the compromised system and team is a factor, this means using a username as a salt compromises your security greatly.
tl;dr Using a username for salting means a targeted attack against a single or small number of users would be damn near impossible to stop as the second they have the password hashes they also have the passwords.
1) You know the hash function beforehand
2) You know that they are salting in exactly this way
3) You know how they are doing their salting (HMAC vs., vs.)
4) You have enough time to create this new rainbow table
5) You have only just enough access to the system to dump the hashes (ie. the easier routes are blocked off from you)
That would in fact, with some probability (based upon the complexity of your rainbow table and the complexity of the users password), give you the passwords for a particular set of users.
I did say that it was more secure then it seems, not that it was perfectly secure :)
In a password hashing scheme with a salt, you're supposed to consider everything except the cleartext to be public, for the purposes of analysis. The password should be unrecoverable even if the attacker knows the algorithm and any salts.
Remember salts don't need to be secret to do their job. The goal is to change the algorithm slightly (by adding additional input) for each user. That means you can't mass-precompute (rainbow tables), and just look up what matches, you have to break each user individually.
Your reasoning about how salts work is correct.
There's also something called a pepper which is another additional bit of input data, that is only stored in the app code (fixed for entire app). So an attacker who only manages to get a database dump would need to guess yet another chunk of data (making it near impossible). So a well-seasoned hash would be SLOW_HASH(pepper+salt+password).
Security is all about layers. Each layer protects a bit more, or prevents things from being easy for the attacker.
Edit: Don't do this yourself. Know it for the theory part - but then just use a well-vetted library to do it.
Please refer to my comment above. You can precompute a rainbow table if you know the username (trivial) and the method of hashing[1]. Whilst usernames as salts would increase security over no salt, it results in a potential exploit / vulnerability that would not exist if the salt was truly random. Hence, suggesting the use of usernames as salts is not wise.
I read cschneid's comment twice, and nowhere to I see where he or she specifically recommends using the username as a password; he or she simply recapitulates the logic behind using a unique salt value for each stored hash, and describes using an additional non-unique value which is not stored with the passwords ("pepper"), which is a new and interesting idea, at least to me.
Re: pepper - The devise plugin for Rails uses it. The idea is that the attacker must now steal both the app code AND database, which are often on separate servers.
It's true that that would be an improvement, however we try to avoid discussing things like that seriously because of the risk that someone new to the game will actually try to do it. The easy answer is to use an out-of-the-box secure password strategy, anything else is adolescent.
What do you recommend users do instead? Unfortunately there will probably always be websites storing passwords in unsecure ways. I mean I'd certainly rather not have to deal with the hassle (however small) of using LastPass, but as you said, that's the world we live in. Hoping for competence by the writers/maintainers of websites is also flawed computer security, is it not?
Hoping for competence is indeed flawed from both sides.
I would hope users use distinct, random passwords for each site they visit and that developers store those passwords in a safe secure way. I also assume both sides won't listen to logic however :)
The reason I'm annoyed with this particularly is that larger sites are more likely targets due simply to their size. Larger sites generally have the developer resources to provide a good solution to the problem from their end but commonly don't.
This makes them look bad and means their users are left in more danger than before. No-one wins.
>> Even if they started with an unsalted password system, users can be migrated to the newer more secure system on next login.
In thinking about this, I wonder if in that scenario you'd even have to wait until next login. You could just use the weak hash as the input to your salted hash function and keep a flag of whether or not you need to 'pre-hash' the password before using your v2.0 salted hash. As users log in you could replace slowly replace the double hashed entries with single salted hash versions and flip the flag.
I didn't see it in the post, but does anyone know if these were current passwords (as of this post)? I use a unique password for linked-in, but some number of months ago I used a password I shared with another site. Wondering if I need to change that one too. Guess I might as well.
Assuming LinkedIn used SHA1 unsalted passwords and will continue to do so, and many of us do not want to delete our LinkedIn accounts, what should be the minimum number of characters we should use in our new password? 15? 20? 100? (I know, 100 is probably higher than they allow)
546 comments
[ 3.4 ms ] story [ 378 ms ] thread(Source: twitter, haven't looked at it myself)
Edit: '12345678' is in there, further bolstering the length requirement theory.
From LinkedIn: "Passwords are case-sensitive and must be at least 6 characters."
> irb
> require 'digest/sha1'
> Digest::SHA1.hexdigest 'my_password'
=> hash_string
Then I searched the file with the hash string and found my password. I really hope they don't also have the usernames somewhere.
Considering how usernames weren't leaked, there's a big chance that the intruder is just sitting on them and the other passwords.
http://blogs.computerworlduk.com/unscrewing-security/2012/06...
http://thenextweb.com/socialmedia/2012/06/06/bad-day-for-lin...
EDIT - As I think about it, e-mail accounts would be especially valuable as most of your other sites could be compromised using the "recover my password via e-mail" feature if the hacker could read the resulting mail.
E.g. my hacker news account would probably be relatively unproblematic to compromise. If that were to happen, I'd just make a new one though.
I don't like the idea of identity permanence.
Instead of shitty passwords though, why not use something like 1Password to store the logins? I use that (or an old fashioned piece of paper in a secure location) for meaningful security tokens.
If you're doing something that makes that normal procedure, consider using the browser inside 1Password for iOS.
Usually something like "domainname"+"common password for all sites"
74 sites... including gmail, openid, facebook, skype, amazon, dropbox, reddit and this site.
Safe >> Sorry
EDIT: Just checked, and my randomly generated password is in the leaked list of hashed passwords. I'm not using that same password anywhere else, so the source MUST be LinkedIN through whatever means (or it's some Mac/PC based attack vector, and these folks only leaked LinkedIN accounts which sounds very implausible).
http://forum.insidepro.com/viewtopic.php?p=96122&sid=133...
A saved copy of my local cache...
Are you kidding me? LinkedIn stored their passwords using (salted) SHA1 using no iterations? Jesus.
http://www.tarsnap.com/scrypt.html
It requires a lot more memory to brute-force it, thereby defeating any speed gains from parallelism.
"use bcrypt" has become an HN meme, with all the bad implications of it
As if scrypt, pbkdf2 didn't exist. Or as if bcrypt has always existed and doesn't have any weakness
The weakest link, either in bcrypt or MD5 is the password quality.
Of course, in pure MD5 today you're a google search away and modern computers can eat salted MD5 for breakfast
But the easiest passwords are going to be broken first
So yeah, the weakest passwords will always fall, but good solutions will go to great length to protect even the most clueless of users.
If you use any reasonable cost for bcrypt, you're talking hundreds of milliseconds per attempt on a modern CPU. For each 6-character password (since you can't generate a rainbow table) at 100ms per pop, you're talking about something on the order of 2+ years per password divided by the number of CPUs. With something like 900 CPUs running continuously, you could expect to recover one 6-char every day if the passwords were randomly distributed in the 6-char alphanumeric space. So, pretty feasible, assuming a 100ms cost. Short passwords do hurt you; I agree.
Now for 8-char alphanumeric passwords, you'd have to run ~1 million CPUs continuously to expect to recover one per day at a 100ms-per-pop cost. This is more of a stretch, assuming you're trying to do this with, e.g., botnets. It seems that someone asking for help cracking a password list on a forum would probably not be able to assemble this much computing power.
Or 1 billion CPUs continuously to expect to recover one 10-char alphanumeric password per day.
Of course, the assumption of random alphanumerics is wrong, both because many people will use common passwords and because others will use non-alphanumeric character substitution.
At any rate, it seems to me that leaking non-salted SHA1 hashes is virtually the worst case disaster scenario, short of plaintext passwords.
But suppose tomorrow it takes 10ms. Also, tomorrow, available spaces will increase, so the likelihood of a space vs time tradeoff (even partial) increases
WEP was considered "good enough" at first (even though it had obvious problems at first like key size), WAP was considered unbreakable at first, today it's feasible with cloud computing or GPUs.
And then we'll be complaining on HN that they didn't use xyzcrypt or something instead of bcrypt.
" it seems to me that leaking non-salted SHA1 hashes is virtually the worst case disaster scenario"
Yes. Salt is password storage 101!
Sure, you can increase the work, but you'll still be limited by bcrypt size
Otherwise, you could just MD5 hash stuff X times and be done with it
Sure, bcrypt today is very safe, but I wouldn't be surprised if attacks are found today (even if they rely only on bruteforce)
And let's not forget implementation issues that may happen in specific bcrypt libraries
It's ok if WAP is breakable with cloud computing, because the whole point was to secure it for the next X years so that it takes more than Y dollars to break it. You only need to protect million dollar data enough that it costs 10 million dollars to get it.
If the data is valuable enough and protected heavily enough with crypto, the cheapest way to get it is through a meatspace attack (break-in, abduction, etc).
> WEP was considered "good enough"
Not by security professionals once they saw the effective size of the key. It's the downgrading of what looked like a 64bit key into a 48bit key that was the biggest problem.
(95^6 * .1sec per hash) / (60sec 60min 24hrs 365days)
The key difference is bcrypt does ~10 hash/sec. A GPU-enabled password cracking machine can do over 500 million hashes per second. That generates a rainbow table in ~30 minutes.
I just had to make this choice a few days ago and bcrypt seemed like the best option with working PHP implementations. And I sure as hell am not going to try to roll my own.
The #1 google response for info about Scrypt for php now points to an article arguing about the semantics of the question with no answer. Classic!
People are using unsalted SHA1, because someone told them in the past "just use sha1". Now someone else tells them "just use BCrypt". Without understanding why, it's nearly impossible to to decide which security policy is sensible. There are many different types of advice competing for attention, and not all of them are good.
The guy who said "phlogistons" was wrong. So was "just use SHA1" guy.
http://codahale.com/how-to-safely-store-a-password/
This additional slowdown is unlikely to be noticed by a user during an interactive login (hashing the password may take 1ms instead of 1us -- an imperceptible difference to a human) but it dramatically slows down the speed at which an attack can compute hashes to try and recover the password for a leaked hash. It also increases the amount of storage space required for (a naive implementation of) a rainbow table since the attacker would need to store the output for 1, 2, ..., n iterations of the hash function.
Edit: they are salted though.
Of course, it does not mean you should take a slow implementation of a fast hash. You need a hash that, when implemented to be as fast as possible, still is pretty slow.
I wonder if someone has the account details to match up otherwise you've no idea which password belongs to who, and you'd hope that LinkedIn would have lockout functionality.
This is a major reason to use bcrypt.
What prevents developers from adding a large DB-wide salt (in addition to normal salt) to every password? Wouldn't that prevent bruteforce attacks regardless of the hashing algorithm?
If every password is padded with such a string before hashing, computing the hash would be slower. Obviously, it would be slower because you would have to process more data. An interesting question is whether this would also make it less parallelizable by the virtue of having more information than would fit into GPU cache.
The only thing "salts" do is prevent rainbow table precomputation, but it's just a quirk of the late '90s and early '00s that "rainbow tables" ever became a mainstream attack method: one bad Microsoft password hash and a series of bad web applications. Long before the MD4 LANMAN hash was ever released, people were breaking salted Unix passwords with off-the-shelf tools, on much, much slower computers than we have now.
Just use bcrypt, scrypt, or PBKDF2. People have already figured this problem out.
Second, working with a large string of bits is the same as recursive hashing only if you can pre-compute some small intermediate state of the hash function for that string independently from the password you're trying to guess. If you can't, you would have to work with the entire string for every new password tried.
Modern password crackers are extremely fast without precomputing anything.
That's not that interesting by itself, but it is interesting to think about how this would affect computing the hashes on GPUs.
Not defending the choice - bcrypt is obviously a much better way to go.
>Do not use the MD5 algorithm Software developers, Certification Authorities, website owners, and users should avoid using the MD5 algorithm in any capacity.
http://www.kb.cert.org/vuls/id/836068
This is from over 3 years ago.
Wind the clock back 3-5 years and it's still stupid to use MD5. I could kind of understand some old code laying around that was less secure.
The leaked hashes seems to be SHA-1. I've also confirmed that the hash of my own (semi-complex) LinkedIn password is in the list. Accidentally this is the same password as I had for HN and that I've now changed (phew! THAT'd been bad! :-)
Darren, you should check out output encoding.
- a rainbow table may require a constant amount of time to reverse 1 hash, but it has to be repeated N times for N passwords.
- when bruteforcing, a password candidate can be checked against N hashes in a constant amount of time (look up the candidate hash in a hash table)
For example if it takes 10 minutes to look up a hash in a very large rainbow table (such as the A5/1 GSM tables published a few years ago), it would take 123 years to attempt to reverse these 6.5M hashes. On the other hand, millions of the leaked SHA1 hashes can be cracked in mere hours on a GPU with oclhashcat which tests billions of candidate hashes per second.
Calculating it is like saying you want to find the fibonacci number for any given N, and you have a really fast processor to calculate it to that N, but if you just persisted pre-calculated values up to C, you'd only need to calculate N-C hashes. So even if you are bruteforcing the password, it is still faster to have rainbow tables up to a certain length.
To take your example of a small SHA1 rainbow table of 20GB, assuming it has a chain length of 40k, looking up a hash in it will require on average 200M calls to the SHA1 compression function (assuming a successful lookup). A modern CPU core can do about 5M calls per second. Therefore looking up one hash will take at least 40 sec, and looking up these 6.5M LinkedIn hashes would take 8.2 years! (This is just counting CPU time, I assume the RT is loaded in RAM for a negligible I/O access time to its data.) A RT of this size would cover a password space of about 2^44. For comparison a decent GPU can brute force this many hashes concurrently at a speed of roughly 500M per second (see oclhashcat perf numbers on an HD 7970). Covering the same password space would take only 9.8 hours. Compare 8.2 years vs. 9.8 hours: obviously the LinkedIn hashes that have been cracked so far have been brute forced, not looked up in RTs!
And even if you leveraged GPUs to perform RT lookups, they would speed up the computations by roughly a factor 100x, reducing the 8.2 years down to 30 days, still unable to match the short 9.8-hour brute forcing session. (My friend Bitweasil is doing research on GPU-accelerated rainbow tables, see cryptohaze.com)
Edit: I'm not sure I understand what you mean - there was 100k passwords in one file, already cracked, and another with all 6.5M hashes. I found my hash in the hashes file.
I think this is a pretty good overview: http://codahale.com/how-to-safely-store-a-password/
Otherwise how could linkedin check if you correctly entered your password?
The salt is contained in cleartext as part of the hashed password, so that you can repeat the hashing the secret and match the two hashes.
The salt improves the security because:
1. even if two users use the same password, you cannot tell that by simply comparing the hashes
2. makes brute force checks much slower because you have to recompute the hash for every hashed password entry rather than once for every dictionary entry
3. Prevents building rainbow tables
(probably other reasons, I'm not a crypto expert)
000000a94d47b9cb82ca8a3b492a51263b40a66e 000000a98a624314892af97c6f1a0635472eae38 000000a9ba60e7f13fcac444a5a791af7807a3a3 000000a97ea34e74a97a6d1ce08ebc68d3e9aab2 000000a9b4b2a3497aaa51e212ac9efdb00aaf4e
It seems like it's just sha1.
EDIT: however, 3.5 million hashes start with 5 zeroes, which is way too many for just coincidence. Possibly they used multiple hash functions?
My password it not in there, but some people have already reported finding theirs.
Anyway, they use Unsalted SHA-1, a really weak option.
I only build tiny websites compared to linkedin and even I take the time to use a proper hashing scheme with a salt. Shame on you, LinkedIn.
Finally, when that central provider gets hacked, all your dependent services are now also compromised.
And as we know from the CloudFlare story over the weekend, not even Google with their 2 factor authentication is devoid of issues.
No. Centralizing your login to one third-party as as bad as the current practice of reusing your password for every service you have an account with. The only way that is reasonably safe is to use different random credentials for every service and store these credentials somewhere under your (and only your) control (i.e. a password manager or a piece of paper)
There's also the fully decentralized openid, you know. I'd 100% rather be able to use openid for sites like Linkedin and this one than rely on every site implementing sane password management.
There is no reason why we should centralize password management and put the world's authentication into one giant pinata for black hats to take a swing at.
- 2 factor auth
- asymmetric encryption (aka, a challenge/response ala PGP)
- whatever security mechanism you want, frankly. It's up to the browserid provider.
OpenID was great in that you could choose any provider you wanted, and nobody could attack them all (not that they'd have to). It just seems like a good solution to use someone whose only job is to provide secure authentication.
Are these legitimate active accounts? Can you do anything with the hashed passwords alone?
https://docs.djangoproject.com/en/dev/topics/auth/
Django by default uses the PBKDF2 algorithm, which is better than nothing/md5/no salt sha1.
I'd use bcrypt or scrypt by default, better be safe than sorry.
It's also better than salted sha1 since it performs multiple iteration rounds leading to (configurable) higher computational complexity.
From exactly where did you derive the idea that PBKDF2 is "extremely good"?
The reality is that all three of PBKDF2, bcrypt, and scrypt are just fine. But PBKDF2 and scrypt have drastically poorer library support than bcrypt; nobody should delay using a strong password hash so that they can optimize which one they use.
There is virtually no "rigorous" research into KDFs of any sort, let alone password KDFs. Most academic crypto research simply presumes passwords are taken from cryptographically secure random number generators and stored securely.
And with that said I want to remind you that I just cited a source, accepted at Usenix, that measured PBKDF2, bcrypt, and scrypt and found PBKDF2 inferior to bcrypt. You seem to want to pretend otherwise.
If Colin has a paper on it then I trust his comparison. What I really meant to say is what you said: all three are just fine.
Also, I thought I remembered my comment's parent saying something stronger, either it was edited later, or I was drunk when I decided it was worth commenting on.
You could literally flip a coin to decide between bcrypt and PBKDF2 and it wouldn't matter which side came up.
Can I be sure my account was totally removed when I removed my LinkedIn account? Because the "please change your password as soon as possible" won't help me much.
1. They do not have a mechanism to resurrect your account and 2. You do not use the same password elsewhere
then it should not matter.
http://jssha.sourceforge.net/
Did they not post the entire load (and are in fact sitting on _all_ the hashes?) Is the dump an old backup or breach from when they had fewer accounts? Is it just one DB partition / file that's been lost, an archive?
sort -u combo_not.txt | wc -l 6458020
wc -l combo_not.txt 6458020
• Someone got in to one user database, but not all of them.
• Someone got into the complete user database, but were found out during the intrusion and cut off.
• Someone found a sharded DB dump or backup.
• Someone found/stole/virus'd a dev laptop with DB dumps.
• Someone sat on the network for a while and grabbed app server -> DB traffic.
Replace "Someone" with "russians," "brazilians," or "something behind tor" for more accurate portrayals.
https://twitter.com/LinkedIn/status/210390233076875264
This wouldn't be difficult to do and your users would appreciate it.
edit: From reading comments bellow I learned that LinkedIn indeed didn't salt.
Because the passwords aren't salted(stupid), you might get multiple hits for the same hash(for example, for the good old "1234" password), meaning you might end up contacting more users than actually affected. Better safe than sorry.
A cross-reference could be accomplished for all known cracked linkedin passwords, but this would be no different then you running a dictionary attack of known passwords against your own users... This seems very bad. Enforcing strong but sane password strength rules should mitigate this need.
Cross reference only has value if both the hash and email pairs are leaked.
The bitcoin leak fell into one of these very bad situations: - [<email>, <hash>] where leaked together - poor hashing (just sha1, no salt if memory serves) - unfortunate number of people reuse passwords
Why, yes, yes, I am. I've now changed my LinkedIn password, too, just in case.
Having a fictional LinkedIn account can be amusing.
Edit: I wrote SHA1-Pass, so I'm biased, but I know what you mean about having trust issues with closed-source password tools. That's one of the reasons I wrote it.
Is it this: http://manpages.ubuntu.com/manpages/natty/man1/sha1pass.1.ht... I don't see how you would use this the same way you'd use the other tools mentioned here. I can imagine a way, but it's no where near as convenient and still has it's own major usability problems.
What stops being hacked / keyloggered and them exfiltrating all your long, complex passwords?
After all, if my own system is compromised, I just get a lot of hassle. If LastPass ever gets hacked and leaks their passwords, they lose their business overnight. That's pretty good motivation for them to keep on top of their stuff.
I used to use 1Passwd, which stored the passwords in a local file, and that could be said to be marginally more secure, except that it generally uses something like iCloud or Dropbox to sync the passwords, so there's still a single point of failure... The main reason I moved away from 1Password was that they gave me a shitty response when I asked them if they were going to support Chrome. I decided at that point that I didn't want to give them my money anymore, and so I didn't upgrade to 1Password 3.
The key for your encrypted file stays in your head (and/or in your wallet), so even a full-on total breach of Dropbox/iCloud, your key is safe, and 8 million rounds of 265-bit AES and a good password (my current KeePass settings) is still unbreakable[1].
1: Unless (perhaps) you have the attention of certain governments. And they always have the option of using a $5 wrench on you, anyway.
[1] Or so they say. I've never MITMed their SSL, and their software is not open source AFAIK. This is not to say someone couldn't e.g. distribute a trojaned version of their browser extensions. If you poke around the developer(s) have at least revealed the encryption method for the your DB so you can verify how it is encrypted for yourself, which is a good sign if nothing else.
No. This is the strength of two-factor authentication, something you know, and something you have. If someone gets your 1Password keyfile, it's useless without your decrypting password.
[1] I find this easier than opening keepass and selecting the database from dropbox for some reason that might be as simple as dropbox having an easier to spot icon.
For my personal ones I'm keeping few algorithms in my brains. I'm using resource type (website/some server/device) and name (e.g. domain/model) as variables and after few steps in my head I always have different password for each kind of service.
Works excellently!
I think it's really humorous that people feel safe putting an encrypted file in something like Dropbox, but don't trust LastPass (who are doing the exact same thing, everything is local, client side encryption). Especially when you're missing out on all of the benefits of browser integration.
Please, take a whole 3 minutes and do a tiny bit of research. Your future self will thank you when people like swombat and myself get to laugh at LinkedIn, change our passwords and never think about it again.
I much prefer the security of being in control of my file, and having its online option controlled by someone else (Dropbox); and logging into Dropbox to then see my passwords 'online' on the go.
If Lastpass.com is compromised, the attacker can MitM compromise my credentials. If 1Password.com is compromised, that is not the case. (Yes, if Dropbox is compromised, they could capture my dropbox credentials, but it would be more difficult for them to then capture my 1password credentials)
Ref: LastPass Online Vault: http://helpdesk.lastpass.com/full.php 1Password Anywhere: http://help.agile.ws/1Password3/1passwordanywhere.html Services I use, and why: http://www.mikeschroll.com/blog/2011/12/07/services-i-use-an...
You can't even do that. You have to install a local client. Download the file, open it in your new client, edit it, manually reupload it. If you don't want to use the on-web LastPass vault, then don't, but it's still doing local decryption and you can still used the signed Chrome extensions to carry out ops if you don't trust LastPass.com proper.
>If Lastpass.com is compromised, the attacker can MitM compromise my credentials.
Which part of "local, client-side encryption" is confusing?
edit: 1PassAnywhere is the exact same thing as what LastPass is doing with it's LastPass.com-served Vault.
edit2: There's even multifactor auth available for it and the Online Vault feature.
It seems to me that instead of having several passwords in my head (i can remember random long strings of characters pretty well, and have a heirachy of randomness/longness depending on what I care about), I only have to remember one. But if that one's compromised, aren't all the rest then available?
Reminds me of the bit in hitchhikers guide to the galaxy (life the universe and everything i think) where passwords and biometrics etc had become really difficult and secure, so a datacube thing was created to store them all. Which was then found by a character before hilarity ensued.
thanks
1. Your physical machine, or the LastPass/Dropbox server.
2. Your master password
3. (optionally) a second-factor auth source
Then yes, they have access to all your passwords. But this is vastly superior to having one password that alone compromised grants access to all of your accounts, right?
I mean, the most secure way imaginable would be perfect biometric signatures, or humans smart enough that they could perform asymmetric encryption in their heads to sign challenges in a verifiable manner. Outside of that, this is decentish.
You could use a text file in a Truecrypt volume with keys that are stored on separate jumpdrives (but what if someone compromises a machine that you plug those drives into), etc, etc.
This central repository then becomes a very appealing target.
I say this as a LastPass user, as I think it is the best of the current offerings, but I'm uncertain how to shield this huge central list. I wish it had multiple logon PW so that you could at least segment the risk and reduce the time the high PW is used to when you really need it.
Then I get to choose what strength lock I put on it.
"Use your own lock" is fine for us Übergeeks, but for the vast majority of the populace, they just want the provider to put a system in place so they don't have to worry about it.
The above comment might seem incredibly harsh, but really, there's no good excuse for a site this prominent to not have a salted, secure password hashing system. Even if they started with an unsalted password system, users can be migrated to the newer more secure system on next login.
The only way I could regain respect for LinkedIn is if we find that these unsalted hashes were from users who never logged in to LinkedIn after the security upgrade. From the replies of other HN users who have found their password hashes in the leaked list, this doesn't seem to be the case though.
I can understand database leaks. Bad things happen. Not being prepared for such an event however is where I draw the line. These leaks impact users far beyond just the site at fault.
It's not enough to say users should use LastPass. They don't, and that's the world we live in, for better or worse. If computer security doesn't take into account problematic users, then it's flawed computer security.
(Not recommending it, just wondering if my reasoning is correct.)
But in this day and age, the bigger problem is how fast you can compute the hashes, salt or no. With GPUs you can calculate a few hundred million(depending on the hashing algorithm) per second, making the algorithm used the real vulnerability.
Best practice involves increasing the calculation time of you're algorithm. Theoretically, you could just rehash y few thousand times in a loop, throwing in a salt here and there, but practically, you should just use bcrypt or scrypt.
This is why you don't use really fast hashes for passwords and you iterate (key stretch). Bcrypt like you said.
Usernames have lower entropy than a random salt and are predictable in many cases. People re-use usernames and some usernames are common. If your password system became common on the web, or if I knew the workings of your password system (i.e. open source / leaked codebase / Kerckhoffs's principle[1]), I could generate a rainbow table for either common or targeted users. This means I could generate a rainbow table for "Jabbles", gain access to your password and compromise your account before the website is likely even aware of a breach or has time to warn you. Salts only act to slow down, not prevent, compromising leaked password hashes (as you can always brute force which is quite practical with MD5/SHA1). Thus, using a username defeats one of the stated purposes of salting.
It's also said ad nauseam (with good reason) but rolling your own in security is a bad idea, especially when libraries exist that do exactly what you'd intend to do just as easily. Algorithms such as bcrypt and scrypt exist and are well vetted. bcrypt is easy to integrate with many languages and provides a trivial interface and sane defaults for iterations/rounds [brute force] and salts [rainbow table]. bcrypt can also handle increasing the security of your system over time as the metadata is stored as part of the hash.
tl;dr Using a username for salting means a targeted attack against a single or small number of users would be damn near impossible to stop as the second they have the password hashes they also have the passwords.
[1]: http://en.wikipedia.org/wiki/Kerckhoffs%27s_principle
I guess what I'm saying is that it's not enough to say don't do it, instead the defaults need to be there (and very visible).
If it's just an issue of getting the word out there, then I'm hopeful things can improve.
You should deploy a strong password hash immediately.
On previous projects, we've gone through all sorts of machinations to detect a password in our SOAP logging. This usually involves XML parsing (slow, ineffective on malformed messages) and Regexes (ineffective on malformed or "unusual" messages).
I can't think of anything better, short of "you can't leak what you don't log" which is nice in theory but not always practical.
For a targeted attack it really doesn't matter as the time complexity to produce the rainbow table is equivalent to that of simply brute forcing the hash, ie, you can't say 'well assume the rainbow table contains only some small number of usernames"...
It also is entirely unlike the WPA2 rainbow tables in that you don't have millions of users all sharing the same username (ie. factory default SSIDs).
Overall it's more secure then it seems at first glance but you still have to ask yourself why you'd use that over a random salt.
I can produce a rainbow table offline before I compromise the targeted system as I know the username of my target. This is not possible if the salt is random. This means I can crack a targeted user's password hash _instantly_ upon gaining access to the system.
With a random salt, you can only perform the brute force attack on that targeted user _after_ you've gained access to the system and likely alerted them to a compromise.
If the response time of the compromised system and team is a factor, this means using a username as a salt compromises your security greatly.
tl;dr Using a username for salting means a targeted attack against a single or small number of users would be damn near impossible to stop as the second they have the password hashes they also have the passwords.
1) You know the hash function beforehand 2) You know that they are salting in exactly this way 3) You know how they are doing their salting (HMAC vs., vs.) 4) You have enough time to create this new rainbow table 5) You have only just enough access to the system to dump the hashes (ie. the easier routes are blocked off from you)
That would in fact, with some probability (based upon the complexity of your rainbow table and the complexity of the users password), give you the passwords for a particular set of users.
I did say that it was more secure then it seems, not that it was perfectly secure :)
There is every reason to use it and none not to.
Your reasoning about how salts work is correct.
There's also something called a pepper which is another additional bit of input data, that is only stored in the app code (fixed for entire app). So an attacker who only manages to get a database dump would need to guess yet another chunk of data (making it near impossible). So a well-seasoned hash would be SLOW_HASH(pepper+salt+password).
Security is all about layers. Each layer protects a bit more, or prevents things from being easy for the attacker.
Edit: Don't do this yourself. Know it for the theory part - but then just use a well-vetted library to do it.
[1]: http://en.wikipedia.org/wiki/Kerckhoffs%27s_principle
Just make their life harder.
The reason I'm annoyed with this particularly is that larger sites are more likely targets due simply to their size. Larger sites generally have the developer resources to provide a good solution to the problem from their end but commonly don't.
This makes them look bad and means their users are left in more danger than before. No-one wins.
In thinking about this, I wonder if in that scenario you'd even have to wait until next login. You could just use the weak hash as the input to your salted hash function and keep a flag of whether or not you need to 'pre-hash' the password before using your v2.0 salted hash. As users log in you could replace slowly replace the double hashed entries with single salted hash versions and flip the flag.
If you find your hash in the list, you should change your password. If you don't, you should change your password.
I use LastPass to manage my passwords so I just generated another random 20+ char password and forgot about it.
In that case, when you change your password and feel all secure again, what's to say the hackers haven't just lifted your new hash as well?
It's buried under "your name" (top right) > settings > password > change (just below your e-mail, left side)