I guess it remains to be seen whether content sites will actually implement this, or whether it'll just be another tool in the black-hat SEO bag. I can see how this may be useful on, say, Wikipedia, which is content-dense and could be rapidly renovated; however, I kind of get the feeling that Wikipedia doesn't really need the help getting to the top of Google's results list.
The problem with the concept of a semantic lies at the feet of human nature.
The people who would benefit the most are not those that are publishing the information. The publishers receive little, if any, gain by making their information available in such a manner. Many, if not most, people are lazy by nature which means they will only expend effort on what benefits them personally. And because these tags will generally not be visible to the end-user or the web designer's boss, there's no "in your face" way of telling whether or not the web team has done their job. "Out of sight, out of mind" will be the order of the day and making sure the tags are correct will end up on the bottom of the pile.
On the flip side, the black-hat SEO operatives, phishers, and other black hats have a big incentive to mark-up their content in a fraudulent manner. Either to drive more traffic their way, to confuse the search engines, or to commit fraud in some other manner.
About the only exception to the first issue is if applying semantic tags to your content results in increased sales by being listed when someone wants to buy something. And the temptation there will be to not play fair unless forced to (hidden transaction fees, hidden S&H fees, fake rebates to drive the listed price down, etc.).
But this is only when you have access to a very fast hash table of the passwords. Trying to brute force over the network to a server that has a proper failure backoff timeout, it gets a lot harder to brute force a decent (6-8 character) password, assuming you don't do stupid stuff like 'password' or '12345'
Agreed.
But when planning for password security, minimum length and complexity requirements - you assume that the attacker has the hash.
It's a very reasonable assumption to make unless the server is locked in a concrete and steel box, a kilometer or three below the surface, with no external connections, you've filled the box with magma, and you have honey badgers living in the tunnels. Maybe some cazores living at the entrance.
14 is not bad. At a minimum, that's probably 62 possibles per position, which is 62^6 better then 8 character passwords. If it allows symbols, then you can assume 80^6 or 92^6, but only if the entire thing is complete gibberish. Otherwise stick with about a 60^6 estimate.
Eight would be too few. Even 10 positions is borderline now. But once you get up into the 12-15 character range, you're past the point where opportunistic attackers will bother. It's faster for them to get the password some other way (shoulder surfing, phishing, social engineering, spyware, physical intrusion/theft, etc.).
The problem with a lot of password theory is it assumes the attackers knows something about the password. The attacker typically doesn't know you're using a phrase of simple words, they don't know what your entropy is or how large your alphabet is. Assuming the dictionary attack didn't work, all they can do is brute force and go through EVERY combination. Use a simple word, throw in an upper case somewhere and toss in a special char, and add another word if you want to make sure you're at least 12 chars.
"Blueplanet[69]" is 14 chars. The attacker doesn't know anything about my password and it won't show up in a dictionary attack. It would have to be brute forced.
That depends on the attacker. Smart attackers know that most users fall into a predictable pattern, such as preferring lower-case letters over upper-case, only using 1-3 extra digits / symbols, typically putting extra junk between words instead of in the middle of words, and sticking to words that they commonly use. That narrows the search field a lot. Instead of 200,000 - 300,000 words, they only need to use about 8,000-10,000 in their search.
If you don't care about which particular account in a list of hashed passwords you break, then you start with the easy stuff. Such as a list of the N most frequently used passwords. Then you proceed to try the typical patterns (and "word-word-numbers/symbols" is a fairly common pattern). Maybe if you didn't get enough results from the first two methods, you'll try doing a random brute-force search of the entire space.
But is that time worth it? Probably not for most attackers. They'll go after the other accounts in the list first and probably break at least some of them in a matter of hours. After which, unless you are a special target, they don't care enough to spend the effort to break your password.
You only have to run faster then your buddy when being chased by a hungry bear if it doesn't care which of you it eats.
But if you specifically made yourself a target by annoying the bear, then your assumptions have to change.
Another factor is the application - it's certainly not worth while to spend $1,000,000 to crack my Slashodot account password, but it may be worth $100,000,000 (or more!) to crack the password of a notorious criminal or dictator, or the encryption system used by evil alien spies to communicate their plans to the invading fleet of star cruisers!
And there is the salient point that many people forget.
Unless the attacker is irrational or specifically targeted, the resources put forth to attack a particular password hash will be proportional to the value of what is being protected by the password hash. In the case of common user accounts on random websites, this generally means a miniscule amount of computation time because account X is the same as account Y. Why spend hours trying to track X's password when Y used a trivial password that was easily brute forced? Both accounts get you into the system / site which is what the attacker wants. They don't care which account gets them in.
So for most cases, your password only needs to be complex enough that it can't be cracked for less then a modest amount of money. That's enough to dissuade opportunistic attackers.
For normal accounts, I put that value at about $10. Very few opportunistic attackers are going to spend $10 to break into a common user's account. For superuser or administrator accounts, it is worth being more paranoid, but even then the upper limit on most systems is only a few hundred dollars before an opportunistic attacker goes elsewhere.
And at that point, you're dealing with an attacker who is specifically targeting you, and password strength quickly becomes the least of your worries. Social engineering, physical intrusion, flaws in the O/S or programs, bribes, etc. will all be used.
If someone got a hand of the password hash, its gameover - doesnt matter if its a week or 2 month to crack it.
We need to get our collective heads out of the sand and triage the REAL security values!
All sane, opportunistic, attackers operate under the principle of cost/benefit. Is it really worth 2 weeks of computer time to break a password of moderate strength? (12+ characters, reasonable complexity) Is it worth 2 months? Most attackers are going to give up after about an hour and go after the rest of the account hashes that were stolen. Why spend the extra time break into user X's account when they can get the same benefit by breaking into user Y's account (who used a weaker password)?
So unless the attacker is insane or is specifically targeting your account, then no - it is not automatically "game over, man".
(And in the case of a targeted attack - there are probably other avenues of attack being used. Such as physical intrusion, social engineering, spyware, etc.)
It seems that standard username and password as authentication may be coming to an end. Anyone agree?
It's dire, but not as dire at that.
8 characters or less, with little to no complexity is truly dead (and has been for years).
Longer passwords (10-15 characters), with complexity checks and not reusing passwords across sites is still fine for 90% of use cases. In 90% of those cases, you're not protecting anything of much value and an accidental exposure does not lead to loss of life or massive theft.
Banks and financial institutions will have to either start enforcing minimum password lengths of 12-15 characters or add two-factor authentication soon. But even that is not perfect as many attackers simply do a MitM attack, capturing the credentials in transit and executing transactions that were not what the user wanted.
The reason why longer passwords are still going to be fine is that every character you add to the password increases complexity by 40x to 80x. Add four letters to the average password and search difficulty increases by anywhere from 2.6 to 41 million times.
The attacker will just shift more towards sniffing / spyware rather then brute-force.
Which sounds like they're storing the passwords in plain text.
(Yet another reason to just use randomized passwords across different websites. At least an attack on one site won't lead to accounts on other sites being exposed due to password re-use. Heck, for sites like talk forums and community sites where you don't have financial information exposed, just let the browser remember the password. Or use a program or a few GPG encrypted text files.)
An issue is, however, hash security. But salts help with that.
Not really. If I know that your password is short, comprised of common english words (say 4,000 common words that are short enough), something like "football123" is going to be cracked in a matter of hours.
4000^2 x 1000 = about 4.4 hours at 1 million/sec
Worse, since "football" is itself probably in that list of the 4000 most common words, my search space is only 4000 x 1000, or 4 seconds.
And probably even faster then that since I would probably try "123" and "1234" as common suffix values to the word list.
Doesn't matter if you salt or not if I'm brute-forcing your password. Salt just means that I probably (assuming you were smart and used a 12-16 bit or larger salt) can't use a pre-calculated rainbow table against the password hash.
That depends on whether you assume that the attacker has your password hash and can brute-force it at an increased rate. For $1000, an attacker can easily build a unit capable of attacking most password hashes at a rate of say 1 billion per second.
If your password is 8 character or less, it will be spit out by that machine in 2-48 hours.
The math:
Assume 60-80 possibles per letter in the password, weaker passwords that are mostly lower-case can be as low as 40 possibles per letter.
Search time at 1 billion / second:
5.33 bits per character, 8 characters = 1.97 hours
5.91 bits per character = 47.5 hours
6.32 bits per character = 461 hours
So for fairly complex password, that $1000 machine can break about 180 passwords per year. And since most passwords are much weaker then 5.91 bits per position, it might be as high as 5000 passwords per year.
Which means the attacker only spends $0.20 per password cracked for passwords of 8 character or less that are not completely random. And that assumes that they're paying for the hardware and electricity and time.
Do your short passwords protect items / time worth more then $0.20? You say that you use more random passwords, which means the attacker would probably have to spend about $5.00 to break it if it's 8 characters or less.
For every letter that you add to your password length, you increase the attacker's workload by 40x to 80x.
And if you write the pwd down, it will be lost/stolen anyway...
Do you also leave your wallet, credit-cards or money laying around so that they get lost/stolen all the time?
Writing the password down is fine, as long as it gets stored in a safe place (safe deposit box, home safe, sealed envelope, even tucked in a wallet). The weakness is not that the password is written down, it's that it is not kept secure against the eyes of others. Like putting it on a sticky note attached to the monitor/keyboard.
Increasing the time to calculate the hash is fine. But only up to a certain point. There are cheaper ways to increase the search space.
When you get into the scenarios of increasing calculation time by 10,000 or 1 million times, then you've probably gone too far. You would gain more from enforcing the use of slightly longer passwords with complexity checks. Each additional character adds 60x to 80x to the search space. (Depends on the mix of upper / lower / numbers / symbols.)
Forcing your passwords to be an average of 2 characters longer:
60^2 = 3600 or 80^2 = 6400
Which is already a bigger gain then switching to a hash algorithm that takes 1000x longer to calculate.
And if you force passwords to be 3 characters longer:
60^3 = 216,000, 80^3 = 512,000
The difference between an 8 character password and a 12 character password is not that big. But it increases the possibilities by a very large amount (13-40 million times). Especially when coupled with a modest (1000x) increase in hash calculation time.
And past a certain time investment to crack a single hash, you've exceeded the reach of opportunistic hackers to break in. Now you're into the realm where only targeted attackers, specifically out to get you, will bother. And they will employ other methods like social engineering, exploits, vulnerabilities, spyware, physical intrusion, intimidation, etc.
Eh, all your doing is increasing your cost. If you make the assumption that the attacker always has orders of magnitude more resources then you do, then it's a losing game. Beyond a very small amount of increased time per iteration, you're just harming yourself.
And the attacker may not even be paying for those resources (think botnet). Can you afford to increase your costs 100 fold to fend off against a 10,000 machine botnet?
Using a hash that takes longer to calculate is fine - up to a point. But it has rapidly diminishing returns. And if it suddenly takes a noticeable amount of time for regular users to authenticate, then the attacker has won by forcing you to DoS yourself.
You gain far more, for cheaper, by enforcing longer password lengths and checking complexity. If that is still not enough, then a 2-factor system which adds a physical token to the mix may be cheaper then adding dozens of servers to calculate password hashes.
With the advent of password cracking power that GPUs bring, it does indeed look like keyspaces the size of 8.65x10^20 and similar that those who think about such things traditionally believed were reasonably secure is starting to become attackable by entities smaller than governments. This'll continue, and it should.
And, as always, risk assessment comes down to knowledge of your attacker. Are they opportunistic? Or are they specifically targeting you (insane attacker, country-sized government, or you are a high value target such as Sony)?
It makes a huge difference. The opportunistic attacker is defended against by merely not being the low-hanging fruit. The latter is generally a no-win situation because they will attack from multiple angles and their resources vastly (1,000,000 or larger multiplier) outstrip your resources. It's still worth being smart about your password hashes in the latter situation, but you probably have other larger security holes through which they will gain access.
I guess what I'm saying is, from the perspective of one person who wants to protect their individual account, yeah, you might not worry too much. But if you're the guy in charge of protecting the server itself -- and by extension, the security of every account on that server -- then worrying seems justified.
Excessive worrying is only justified if:
- You allow passwords shorter then 8 characters.
- You do not enforce password complexity.
- You do not uniquely salt your passwords on a per-account basis.
Change at least two of those things and you're protected against opportunistic attackers (which is probably 99% of the threat). Force passwords to be at least 10-11 characters (I suggest 12-15). Force passwords to have at least some numbers / symbols / mixed-case feature. Make sure you use a different salt for each account, of at least 12 bits, for storing the password.
Maybe switch to a hash that takes 100x longer to calculate then MD5. (The other steps will buy you the equivalent or better time over using a difficult hash method.)
If the information is that valuable, consider adding a 2-part authentication system (password + token, or password + biometrics).
Once you drive the time to brute-force a password hash into the hundreds of years (even assuming that everything gets 1000x faster before we hit the physical limits of the universe), then you're pretty much done. No attacker is going to spend a year cracking a single password. Now you need to worry about the other dozens of ways to get at the information - like social engineering, exploits, vulnerabilities, sniffing, spyware, physical intrusion or intimidation.
The problem is that if you compose your pass-phrase from 3 common words with only spaces between, the complexity is only about 10,000 ^ 3. (10,000 = about 13.29 bits of complexity.)
At best, you're looking at a 40 bit password. And if you only go with the "short" common words (under say 8 letters), it drops to about 11 bits per word (33 bit password). In comparison a 6-character, 80-possibles per position password is about 6.325 bits per position (about 38 bits) and a 8-character random password is roughly 50 bits.
You need to pick from less common words, and mix in symbols / upper-case / numbers. If you use the ~290,000 less common words and special words in the English language, then you've got about 18.2 bits per word chosen. Change the space between words into numbers/symbols and you have about 5 bits of entropy per word break. So for a 2-word set with 5 bits between, you have 18.2 + 5 + 18.2 = 41 bits. Use a 3rd word and that grows to 64.6 bits.
It won't be quite 18.2 bits per word chosen though as some words are too long or too difficult to be spelled properly, so say 17 bits instead (about 131,000 words). But you can gain about 2 more bits of complexity per word if you randomly capitalize letters at the start of syllables.
(Always assume that the attacker knows the pattern of how you construct your passwords.)
So your password is "a phrase, modified a bit". Would you care to estimate how many bits of entropy are in that?
Well, there are about 10,000 common words in english and maybe 300,000 words in a large english dictionary. So if it's a phrase composed of common words, then it's not very good. And if it's a phrase of related words, a markov chain could make short work of it.
Five to seven words picked out of the less common end of the dictionary would be 290,000 ^ 5 or 290,000 ^ 7. That's a pretty large number.
The presence or absence of things like periods, commas might add 2-4 bits to each word position.
This raises the question, at predictable rates of increase in computing performance (per $) and projected advances in cryptography and decryptography, how many years will this longer password be reasonably secure? I think that's a very interesting and provocative question, with many subtopics to consider including users.
Increases in computing performance per dollar are steadily slowing. The last big bump was the move to multi-core and even that has a limit in feature size.
How many more bumps are left before we get transistor sizes that are too small to use? The current state of semi-conductors is down in the 25-45nm range. If we get down to 4nm, we're in the realm of transistors that are only 7 atoms across.
So let's assume that someone figures out how to do 4nm (100x smaller size) and that it runs at 20GHz (10x faster then current). Unless CPU architecture changes radically, you're looking at a 1000x increase in computing power per square centimeter.
A 1000x improvement? That's not much. Moving to a slightly stronger hash algorithm that takes 10x longer to calculate combined with adding just 2-4 characters to passwords gets you that.
I would say that 8 chars or less is basically broken now. It still falls in the realm of targeted attacks though. And the attacker will probably be working from a "most commonly used password" list instead of blindly attempting all of the possible permutations.
Or they'll use a weighted permutation (say 65% lower case letters, 20% upper case, 10% numbers, 5% symbols). Which covers an awful lot of passwords that normal users will come up with. And is a lot faster to iterate through.
If an 8 character password of the above complexity takes 9 hours (at 5 billion/sec) to crack, then a 9 character password will take 22 days. So each character added is about a 60x multipler.
Get out to 11 characters and you're up to 79,000 days (216 years). Go to 12 characters and the time is measured in millennia (13,000 years). Combine that with a modest increase in the complexity of calculating the hash (something that takes 1000x as long) and it buys you time.
The rate of increase of computer power per dollar has definitely slowed. At best, for embarrassingly parallel problems, it's maybe a 50% increase per year and that rate is slowing down. That means in 3 years, N currency will only buy 3.4x computer power, and in 10 years it will buy 58x computer power. So a machine that currently costs $1000 and has 6-cores would need to have 348-cores doing the same amount of work per hour as the 6-core version. And I don't see that rate of advance as being sustainable.
10 is probably okay for a few years, but 12-15 is more likely to stay safe for a few decades. Past that, 2-factor authentication will have to become commonplace.
You should really use a slow hashing function that takes around 0.1 to 1 seconds to calculate one hash on the server.
All you're doing is moving the decimal point a few positions when you use an iterative hash. Plus if the server takes a full second to calculate the hash, you're going to have some very pissed off users. What happens when the average server load has a dozen users all logging in at the same time? Each one probably has to wait 6-12 seconds as the server tries to handle calculating the passwords at the same time as getting work done.
Sure, if you're protecting billion dollar secrets, then it's worth going that distance. But for the average attacker, it's pure overkill and does nothing but drive your costs up.
The average attacker is opportunistic. They're not going to spend a million to break into a system that is only worth a few thousand. As long as your passwords are long enough (i.e. not 8-chars or less), complex enough (not dictionary words, requiring a mix of alphabetic, numbers and symbols) and you use a per-account salt, most attackers are going to give up after a few days. Heck, most won't spend more then a few hours against a single hash.
Attackers which are specifically targeting you are a completely different story. They will go after your systems in multiple ways and will have resources in excess of you. Social engineering, trojans, worms, exploits, physical intrusion and intimidation / torture will be used and your ultra-difficult password hash algorithm will be for naught.
It is well known that if someone gets your hashed password, it is as good as cracked.
It still depends on how much time / money the attacker is willing to spend. If you use slightly longer passwords / passphrases, then you won't be the low-hanging fruit. A dedicated, targeted attacker is still a big problem, but the opportunistic attackers will check the hashes, fail to crack them and move on to the next target.
I did an analysis on this a few years back, when CUDA and GPUs first started getting popular. Back then, my estimated speed was 5 billion hashes per second for a single GPU. A bit of an overestimation, but in line with the ~3 billion/sec of current GPUs. Passwords were assumed to be semi-random with 65% lower case letters, 20% upper, 10% numbers, 5% symbols. A big assumption, but it provides a starting point.
Very few attackers are going to spend more then a day on a single account. Even with a large botnet of 10,000 GPUs at their disposal. The ones that will go that distance are targeted attackers and they will be trying other methods as well to compromise your security.
Brute force times:
chrs
8 = 9 hrs
9 = 22 days
10 = 1325 days (44 months)
11 = 79,000 days
12 = 4.7 million days
13 = 282 million days
14 = 16.8 billion days
15 = 1 trillion days
The lesson from that was that 8 characters or fewer (of the stated complexity) passwords are screwed. You really have to go out to 11-12 characters and enforce some measure of password complexity to be safe.
It happened to me once (I have nothing left to demonstrate it, that machine is long gone): I could login on a single linux user account with 2 different password (neither was 1-letter long, but still).
And if it was an old box, back when "crypt" (?) was the hash method used. It would discard anything after the first 8 letters in the password prior to calculating the hash and comparing it against what is in the password field. Salt was typically one of 4096 possible combinations (12 bits) and the password hash was probably only 56-64 bits. Which gives a pretty high chance of collision for such a small hash size.
So, if both passwords were identical in the first 8 letters, that could be the answer. Otherwise it was the issue that with so few bits in the hash, having two different passwords hash to the same value was quite possible.
(Note: I'm sure about the 8-character truncated password. Saw it happen on Solaris boxes from the early 2000s. Not so sure about how big the stored hash value was. I don't have those shadow files any longer. But 56-64 bits is likely if it was using single-DES as DES operated with 56bit keys.)
Except that when you create a rainbow table, the size is not primarily determined by the size of the hash. It's determined by the size of the search space - which is the passwords that can be entered on a standard keyboard. Then it gets multiplied by the size of the salt in use.
Assuming A-Z, a-z, 0-9, and 24 symbols, you have about 86 possibles for each character position. We'll be lazy and call it an even 90 possibles.
The size of a rainbow table for all 8-character passwords using 90 possibles per position is: 90^8 = 4,304,672,100,000,000. Assuming 32 bytes of storage per password / hash pair, you end up with needing about 128,289,226 GB worth of storage (roughly 122 petabytes). Which is still a lot, but a lot less then what you think.
If your users are lazy (most are) and your password complexity requirements are weak, then you can assume that (a) the password is comprised of dictionary words (b) upper-case probably only happens at the start of the word or at the start of a syllable and (c) the use of numbers and symbols will happen on word boundaries.
Which means your search space drastically shrinks and there are a lot less possibles. Figure 300,000 words in the dictionary, and most passwords will contain words from a list of about 10,000. If the password is constructed from those 10,000 words, plus a few numbers thrown in at word boundaries, there's not much complexity there. A rough estimate would be that you could see user-created passwords, that meet modest complexity requirements, that might only have 30-36 bits of entropy. Which means your table only has to contain between 1 and 16 billion different hashes. At 32 bytes per hash-password pair, that's only 512GB, multiplied by the size of the salt.
If the salt is less then 8-12 bits, it might still be worth doing a rainbow table. For larger salts, it is better to identify key accounts and attack those hashes directly rather then rely on the rainbow table. An attack like that is embarrassingly parallel and can be farmed out to a cluster or to machines with multiple GPU cores.
Slashdot Mirror
Perhaps they kept them around for initializing more fobs if necessary without having to transfer the root key again.
In simpler terms - convenience won out over security.
I guess it remains to be seen whether content sites will actually implement this, or whether it'll just be another tool in the black-hat SEO bag. I can see how this may be useful on, say, Wikipedia, which is content-dense and could be rapidly renovated; however, I kind of get the feeling that Wikipedia doesn't really need the help getting to the top of Google's results list.
The problem with the concept of a semantic lies at the feet of human nature.
The people who would benefit the most are not those that are publishing the information. The publishers receive little, if any, gain by making their information available in such a manner. Many, if not most, people are lazy by nature which means they will only expend effort on what benefits them personally. And because these tags will generally not be visible to the end-user or the web designer's boss, there's no "in your face" way of telling whether or not the web team has done their job. "Out of sight, out of mind" will be the order of the day and making sure the tags are correct will end up on the bottom of the pile.
On the flip side, the black-hat SEO operatives, phishers, and other black hats have a big incentive to mark-up their content in a fraudulent manner. Either to drive more traffic their way, to confuse the search engines, or to commit fraud in some other manner.
About the only exception to the first issue is if applying semantic tags to your content results in increased sales by being listed when someone wants to buy something. And the temptation there will be to not play fair unless forced to (hidden transaction fees, hidden S&H fees, fake rebates to drive the listed price down, etc.).
But this is only when you have access to a very fast hash table of the passwords. Trying to brute force over the network to a server that has a proper failure backoff timeout, it gets a lot harder to brute force a decent (6-8 character) password, assuming you don't do stupid stuff like 'password' or '12345'
Agreed.
But when planning for password security, minimum length and complexity requirements - you assume that the attacker has the hash.
It's a very reasonable assumption to make unless the server is locked in a concrete and steel box, a kilometer or three below the surface, with no external connections, you've filled the box with magma, and you have honey badgers living in the tunnels. Maybe some cazores living at the entrance.
PS. My bank allows 14 characters... *facepalm*
14 is not bad. At a minimum, that's probably 62 possibles per position, which is 62^6 better then 8 character passwords. If it allows symbols, then you can assume 80^6 or 92^6, but only if the entire thing is complete gibberish. Otherwise stick with about a 60^6 estimate.
Eight would be too few. Even 10 positions is borderline now. But once you get up into the 12-15 character range, you're past the point where opportunistic attackers will bother. It's faster for them to get the password some other way (shoulder surfing, phishing, social engineering, spyware, physical intrusion/theft, etc.).
The problem with a lot of password theory is it assumes the attackers knows something about the password. The attacker typically doesn't know you're using a phrase of simple words, they don't know what your entropy is or how large your alphabet is. Assuming the dictionary attack didn't work, all they can do is brute force and go through EVERY combination. Use a simple word, throw in an upper case somewhere and toss in a special char, and add another word if you want to make sure you're at least 12 chars.
"Blueplanet[69]" is 14 chars. The attacker doesn't know anything about my password and it won't show up in a dictionary attack. It would have to be brute forced.
That depends on the attacker. Smart attackers know that most users fall into a predictable pattern, such as preferring lower-case letters over upper-case, only using 1-3 extra digits / symbols, typically putting extra junk between words instead of in the middle of words, and sticking to words that they commonly use. That narrows the search field a lot. Instead of 200,000 - 300,000 words, they only need to use about 8,000-10,000 in their search.
If you don't care about which particular account in a list of hashed passwords you break, then you start with the easy stuff. Such as a list of the N most frequently used passwords. Then you proceed to try the typical patterns (and "word-word-numbers/symbols" is a fairly common pattern). Maybe if you didn't get enough results from the first two methods, you'll try doing a random brute-force search of the entire space.
But is that time worth it? Probably not for most attackers. They'll go after the other accounts in the list first and probably break at least some of them in a matter of hours. After which, unless you are a special target, they don't care enough to spend the effort to break your password.
You only have to run faster then your buddy when being chased by a hungry bear if it doesn't care which of you it eats.
But if you specifically made yourself a target by annoying the bear, then your assumptions have to change.
Another factor is the application - it's certainly not worth while to spend $1,000,000 to crack my Slashodot account password, but it may be worth $100,000,000 (or more!) to crack the password of a notorious criminal or dictator, or the encryption system used by evil alien spies to communicate their plans to the invading fleet of star cruisers!
And there is the salient point that many people forget.
Unless the attacker is irrational or specifically targeted, the resources put forth to attack a particular password hash will be proportional to the value of what is being protected by the password hash. In the case of common user accounts on random websites, this generally means a miniscule amount of computation time because account X is the same as account Y. Why spend hours trying to track X's password when Y used a trivial password that was easily brute forced? Both accounts get you into the system / site which is what the attacker wants. They don't care which account gets them in.
So for most cases, your password only needs to be complex enough that it can't be cracked for less then a modest amount of money. That's enough to dissuade opportunistic attackers.
For normal accounts, I put that value at about $10. Very few opportunistic attackers are going to spend $10 to break into a common user's account. For superuser or administrator accounts, it is worth being more paranoid, but even then the upper limit on most systems is only a few hundred dollars before an opportunistic attacker goes elsewhere.
And at that point, you're dealing with an attacker who is specifically targeting you, and password strength quickly becomes the least of your worries. Social engineering, physical intrusion, flaws in the O/S or programs, bribes, etc. will all be used.
If someone got a hand of the password hash, its gameover - doesnt matter if its a week or 2 month to crack it.
We need to get our collective heads out of the sand and triage the REAL security values!
All sane, opportunistic, attackers operate under the principle of cost/benefit. Is it really worth 2 weeks of computer time to break a password of moderate strength? (12+ characters, reasonable complexity) Is it worth 2 months? Most attackers are going to give up after about an hour and go after the rest of the account hashes that were stolen. Why spend the extra time break into user X's account when they can get the same benefit by breaking into user Y's account (who used a weaker password)?
So unless the attacker is insane or is specifically targeting your account, then no - it is not automatically "game over, man".
(And in the case of a targeted attack - there are probably other avenues of attack being used. Such as physical intrusion, social engineering, spyware, etc.)
It seems that standard username and password as authentication may be coming to an end. Anyone agree?
It's dire, but not as dire at that.
8 characters or less, with little to no complexity is truly dead (and has been for years).
Longer passwords (10-15 characters), with complexity checks and not reusing passwords across sites is still fine for 90% of use cases. In 90% of those cases, you're not protecting anything of much value and an accidental exposure does not lead to loss of life or massive theft.
Banks and financial institutions will have to either start enforcing minimum password lengths of 12-15 characters or add two-factor authentication soon. But even that is not perfect as many attackers simply do a MitM attack, capturing the credentials in transit and executing transactions that were not what the user wanted.
The reason why longer passwords are still going to be fine is that every character you add to the password increases complexity by 40x to 80x. Add four letters to the average password and search difficulty increases by anywhere from 2.6 to 41 million times.
The attacker will just shift more towards sniffing / spyware rather then brute-force.
Which sounds like they're storing the passwords in plain text.
(Yet another reason to just use randomized passwords across different websites. At least an attack on one site won't lead to accounts on other sites being exposed due to password re-use. Heck, for sites like talk forums and community sites where you don't have financial information exposed, just let the browser remember the password. Or use a program or a few GPG encrypted text files.)
An issue is, however, hash security. But salts help with that.
Not really. If I know that your password is short, comprised of common english words (say 4,000 common words that are short enough), something like "football123" is going to be cracked in a matter of hours.
4000^2 x 1000 = about 4.4 hours at 1 million/sec
Worse, since "football" is itself probably in that list of the 4000 most common words, my search space is only 4000 x 1000, or 4 seconds.
And probably even faster then that since I would probably try "123" and "1234" as common suffix values to the word list.
Doesn't matter if you salt or not if I'm brute-forcing your password. Salt just means that I probably (assuming you were smart and used a 12-16 bit or larger salt) can't use a pre-calculated rainbow table against the password hash.
That depends on whether you assume that the attacker has your password hash and can brute-force it at an increased rate. For $1000, an attacker can easily build a unit capable of attacking most password hashes at a rate of say 1 billion per second.
If your password is 8 character or less, it will be spit out by that machine in 2-48 hours.
The math:
Assume 60-80 possibles per letter in the password, weaker passwords that are mostly lower-case can be as low as 40 possibles per letter.
40 = ~5.33 bits per position, 60 = ~5.91 bits, 80 = ~6.32 bits.
Search time at 1 billion / second:
5.33 bits per character, 8 characters = 1.97 hours
5.91 bits per character = 47.5 hours
6.32 bits per character = 461 hours
So for fairly complex password, that $1000 machine can break about 180 passwords per year. And since most passwords are much weaker then 5.91 bits per position, it might be as high as 5000 passwords per year.
Which means the attacker only spends $0.20 per password cracked for passwords of 8 character or less that are not completely random. And that assumes that they're paying for the hardware and electricity and time.
Do your short passwords protect items / time worth more then $0.20? You say that you use more random passwords, which means the attacker would probably have to spend about $5.00 to break it if it's 8 characters or less.
For every letter that you add to your password length, you increase the attacker's workload by 40x to 80x.
And if you write the pwd down, it will be lost/stolen anyway...
Do you also leave your wallet, credit-cards or money laying around so that they get lost/stolen all the time?
Writing the password down is fine, as long as it gets stored in a safe place (safe deposit box, home safe, sealed envelope, even tucked in a wallet). The weakness is not that the password is written down, it's that it is not kept secure against the eyes of others. Like putting it on a sticky note attached to the monitor/keyboard.
Increasing the time to calculate the hash is fine. But only up to a certain point. There are cheaper ways to increase the search space.
When you get into the scenarios of increasing calculation time by 10,000 or 1 million times, then you've probably gone too far. You would gain more from enforcing the use of slightly longer passwords with complexity checks. Each additional character adds 60x to 80x to the search space. (Depends on the mix of upper / lower / numbers / symbols.)
Forcing your passwords to be an average of 2 characters longer:
60^2 = 3600 or 80^2 = 6400
Which is already a bigger gain then switching to a hash algorithm that takes 1000x longer to calculate.
And if you force passwords to be 3 characters longer: 60^3 = 216,000, 80^3 = 512,000
The difference between an 8 character password and a 12 character password is not that big. But it increases the possibilities by a very large amount (13-40 million times). Especially when coupled with a modest (1000x) increase in hash calculation time.
And past a certain time investment to crack a single hash, you've exceeded the reach of opportunistic hackers to break in. Now you're into the realm where only targeted attackers, specifically out to get you, will bother. And they will employ other methods like social engineering, exploits, vulnerabilities, spyware, physical intrusion, intimidation, etc.
Eh, all your doing is increasing your cost. If you make the assumption that the attacker always has orders of magnitude more resources then you do, then it's a losing game. Beyond a very small amount of increased time per iteration, you're just harming yourself.
And the attacker may not even be paying for those resources (think botnet). Can you afford to increase your costs 100 fold to fend off against a 10,000 machine botnet?
Using a hash that takes longer to calculate is fine - up to a point. But it has rapidly diminishing returns. And if it suddenly takes a noticeable amount of time for regular users to authenticate, then the attacker has won by forcing you to DoS yourself.
You gain far more, for cheaper, by enforcing longer password lengths and checking complexity. If that is still not enough, then a 2-factor system which adds a physical token to the mix may be cheaper then adding dozens of servers to calculate password hashes.
With the advent of password cracking power that GPUs bring, it does indeed look like keyspaces the size of 8.65x10^20 and similar that those who think about such things traditionally believed were reasonably secure is starting to become attackable by entities smaller than governments. This'll continue, and it should.
And, as always, risk assessment comes down to knowledge of your attacker. Are they opportunistic? Or are they specifically targeting you (insane attacker, country-sized government, or you are a high value target such as Sony)?
It makes a huge difference. The opportunistic attacker is defended against by merely not being the low-hanging fruit. The latter is generally a no-win situation because they will attack from multiple angles and their resources vastly (1,000,000 or larger multiplier) outstrip your resources. It's still worth being smart about your password hashes in the latter situation, but you probably have other larger security holes through which they will gain access.
The rule of thumb that I've used is:
About 10,000 common words (13.325 bits).
About 300,000 words in a large dictionary (18.2 bits).
(Most attackers will probably attempt to build the pass-phrases out of common words first. It's a much smaller search space.)
I guess what I'm saying is, from the perspective of one person who wants to protect their individual account, yeah, you might not worry too much. But if you're the guy in charge of protecting the server itself -- and by extension, the security of every account on that server -- then worrying seems justified.
Excessive worrying is only justified if:
- You allow passwords shorter then 8 characters.
- You do not enforce password complexity.
- You do not uniquely salt your passwords on a per-account basis.
Change at least two of those things and you're protected against opportunistic attackers (which is probably 99% of the threat). Force passwords to be at least 10-11 characters (I suggest 12-15). Force passwords to have at least some numbers / symbols / mixed-case feature. Make sure you use a different salt for each account, of at least 12 bits, for storing the password.
Maybe switch to a hash that takes 100x longer to calculate then MD5. (The other steps will buy you the equivalent or better time over using a difficult hash method.)
If the information is that valuable, consider adding a 2-part authentication system (password + token, or password + biometrics).
Once you drive the time to brute-force a password hash into the hundreds of years (even assuming that everything gets 1000x faster before we hit the physical limits of the universe), then you're pretty much done. No attacker is going to spend a year cracking a single password. Now you need to worry about the other dozens of ways to get at the information - like social engineering, exploits, vulnerabilities, sniffing, spyware, physical intrusion or intimidation.
The problem is that if you compose your pass-phrase from 3 common words with only spaces between, the complexity is only about 10,000 ^ 3. (10,000 = about 13.29 bits of complexity.)
At best, you're looking at a 40 bit password. And if you only go with the "short" common words (under say 8 letters), it drops to about 11 bits per word (33 bit password). In comparison a 6-character, 80-possibles per position password is about 6.325 bits per position (about 38 bits) and a 8-character random password is roughly 50 bits.
You need to pick from less common words, and mix in symbols / upper-case / numbers. If you use the ~290,000 less common words and special words in the English language, then you've got about 18.2 bits per word chosen. Change the space between words into numbers/symbols and you have about 5 bits of entropy per word break. So for a 2-word set with 5 bits between, you have 18.2 + 5 + 18.2 = 41 bits. Use a 3rd word and that grows to 64.6 bits.
It won't be quite 18.2 bits per word chosen though as some words are too long or too difficult to be spelled properly, so say 17 bits instead (about 131,000 words). But you can gain about 2 more bits of complexity per word if you randomly capitalize letters at the start of syllables.
(Always assume that the attacker knows the pattern of how you construct your passwords.)
So your password is "a phrase, modified a bit". Would you care to estimate how many bits of entropy are in that?
Well, there are about 10,000 common words in english and maybe 300,000 words in a large english dictionary. So if it's a phrase composed of common words, then it's not very good. And if it's a phrase of related words, a markov chain could make short work of it.
Five to seven words picked out of the less common end of the dictionary would be 290,000 ^ 5 or 290,000 ^ 7. That's a pretty large number.
The presence or absence of things like periods, commas might add 2-4 bits to each word position.
This raises the question, at predictable rates of increase in computing performance (per $) and projected advances in cryptography and decryptography, how many years will this longer password be reasonably secure? I think that's a very interesting and provocative question, with many subtopics to consider including users.
Increases in computing performance per dollar are steadily slowing. The last big bump was the move to multi-core and even that has a limit in feature size.
How many more bumps are left before we get transistor sizes that are too small to use? The current state of semi-conductors is down in the 25-45nm range. If we get down to 4nm, we're in the realm of transistors that are only 7 atoms across.
So let's assume that someone figures out how to do 4nm (100x smaller size) and that it runs at 20GHz (10x faster then current). Unless CPU architecture changes radically, you're looking at a 1000x increase in computing power per square centimeter.
A 1000x improvement? That's not much. Moving to a slightly stronger hash algorithm that takes 10x longer to calculate combined with adding just 2-4 characters to passwords gets you that.
I would say that 8 chars or less is basically broken now. It still falls in the realm of targeted attacks though. And the attacker will probably be working from a "most commonly used password" list instead of blindly attempting all of the possible permutations.
Or they'll use a weighted permutation (say 65% lower case letters, 20% upper case, 10% numbers, 5% symbols). Which covers an awful lot of passwords that normal users will come up with. And is a lot faster to iterate through.
If an 8 character password of the above complexity takes 9 hours (at 5 billion/sec) to crack, then a 9 character password will take 22 days. So each character added is about a 60x multipler.
Get out to 11 characters and you're up to 79,000 days (216 years). Go to 12 characters and the time is measured in millennia (13,000 years). Combine that with a modest increase in the complexity of calculating the hash (something that takes 1000x as long) and it buys you time.
The rate of increase of computer power per dollar has definitely slowed. At best, for embarrassingly parallel problems, it's maybe a 50% increase per year and that rate is slowing down. That means in 3 years, N currency will only buy 3.4x computer power, and in 10 years it will buy 58x computer power. So a machine that currently costs $1000 and has 6-cores would need to have 348-cores doing the same amount of work per hour as the 6-core version. And I don't see that rate of advance as being sustainable.
10 is probably okay for a few years, but 12-15 is more likely to stay safe for a few decades. Past that, 2-factor authentication will have to become commonplace.
You should really use a slow hashing function that takes around 0.1 to 1 seconds to calculate one hash on the server.
All you're doing is moving the decimal point a few positions when you use an iterative hash. Plus if the server takes a full second to calculate the hash, you're going to have some very pissed off users. What happens when the average server load has a dozen users all logging in at the same time? Each one probably has to wait 6-12 seconds as the server tries to handle calculating the passwords at the same time as getting work done.
Sure, if you're protecting billion dollar secrets, then it's worth going that distance. But for the average attacker, it's pure overkill and does nothing but drive your costs up.
The average attacker is opportunistic. They're not going to spend a million to break into a system that is only worth a few thousand. As long as your passwords are long enough (i.e. not 8-chars or less), complex enough (not dictionary words, requiring a mix of alphabetic, numbers and symbols) and you use a per-account salt, most attackers are going to give up after a few days. Heck, most won't spend more then a few hours against a single hash.
Attackers which are specifically targeting you are a completely different story. They will go after your systems in multiple ways and will have resources in excess of you. Social engineering, trojans, worms, exploits, physical intrusion and intimidation / torture will be used and your ultra-difficult password hash algorithm will be for naught.
It is well known that if someone gets your hashed password, it is as good as cracked.
It still depends on how much time / money the attacker is willing to spend. If you use slightly longer passwords / passphrases, then you won't be the low-hanging fruit. A dedicated, targeted attacker is still a big problem, but the opportunistic attackers will check the hashes, fail to crack them and move on to the next target.
I did an analysis on this a few years back, when CUDA and GPUs first started getting popular. Back then, my estimated speed was 5 billion hashes per second for a single GPU. A bit of an overestimation, but in line with the ~3 billion/sec of current GPUs. Passwords were assumed to be semi-random with 65% lower case letters, 20% upper, 10% numbers, 5% symbols. A big assumption, but it provides a starting point.
Very few attackers are going to spend more then a day on a single account. Even with a large botnet of 10,000 GPUs at their disposal. The ones that will go that distance are targeted attackers and they will be trying other methods as well to compromise your security.
Brute force times:
chrs
8 = 9 hrs
9 = 22 days
10 = 1325 days (44 months)
11 = 79,000 days
12 = 4.7 million days
13 = 282 million days
14 = 16.8 billion days
15 = 1 trillion days
The lesson from that was that 8 characters or fewer (of the stated complexity) passwords are screwed. You really have to go out to 11-12 characters and enforce some measure of password complexity to be safe.
It happened to me once (I have nothing left to demonstrate it, that machine is long gone): I could login on a single linux user account with 2 different password (neither was 1-letter long, but still).
And if it was an old box, back when "crypt" (?) was the hash method used. It would discard anything after the first 8 letters in the password prior to calculating the hash and comparing it against what is in the password field. Salt was typically one of 4096 possible combinations (12 bits) and the password hash was probably only 56-64 bits. Which gives a pretty high chance of collision for such a small hash size.
So, if both passwords were identical in the first 8 letters, that could be the answer. Otherwise it was the issue that with so few bits in the hash, having two different passwords hash to the same value was quite possible.
(Note: I'm sure about the 8-character truncated password. Saw it happen on Solaris boxes from the early 2000s. Not so sure about how big the stored hash value was. I don't have those shadow files any longer. But 56-64 bits is likely if it was using single-DES as DES operated with 56bit keys.)
Except that when you create a rainbow table, the size is not primarily determined by the size of the hash. It's determined by the size of the search space - which is the passwords that can be entered on a standard keyboard. Then it gets multiplied by the size of the salt in use.
Assuming A-Z, a-z, 0-9, and 24 symbols, you have about 86 possibles for each character position. We'll be lazy and call it an even 90 possibles.
The size of a rainbow table for all 8-character passwords using 90 possibles per position is: 90^8 = 4,304,672,100,000,000. Assuming 32 bytes of storage per password / hash pair, you end up with needing about 128,289,226 GB worth of storage (roughly 122 petabytes). Which is still a lot, but a lot less then what you think.
If your users are lazy (most are) and your password complexity requirements are weak, then you can assume that (a) the password is comprised of dictionary words (b) upper-case probably only happens at the start of the word or at the start of a syllable and (c) the use of numbers and symbols will happen on word boundaries.
Which means your search space drastically shrinks and there are a lot less possibles. Figure 300,000 words in the dictionary, and most passwords will contain words from a list of about 10,000. If the password is constructed from those 10,000 words, plus a few numbers thrown in at word boundaries, there's not much complexity there. A rough estimate would be that you could see user-created passwords, that meet modest complexity requirements, that might only have 30-36 bits of entropy. Which means your table only has to contain between 1 and 16 billion different hashes. At 32 bytes per hash-password pair, that's only 512GB, multiplied by the size of the salt.
If the salt is less then 8-12 bits, it might still be worth doing a rainbow table. For larger salts, it is better to identify key accounts and attack those hashes directly rather then rely on the rainbow table. An attack like that is embarrassingly parallel and can be farmed out to a cluster or to machines with multiple GPU cores.