Telepathwords: A New Password Strength Estimator
schneier.com
schneier.com
It's not really the fact that perspicacious is a dictionary word that I'm complaining about; I get that this is basing its decisions on a predictive algorithm and we can obviously augment this with some of the more traditional heuristics as well. What confuses me is that perspicacious, while perhaps being a $10 word, is also phonetically fairly normal, which ought to be bad. I would, for example, expect the s at the end to be fairly expected, or the a after the c.
I salute the idea, though. I've tried to make the point that a markov-esque password guesser could guess a great deal more passwords than we've seen so far. (Recall that while HN may frequently see Markov techniques used to randomly walk the nodes, you can also use it deterministically to enumerate possibilities in probability order quite easily.) It would be great to have something to simply point at.
The difficulty, since this is intended a user aid, seems to be in balancing soundness (using a threshold) with user experience (sometimes predicting 3 letters, sometimes predicting 10, which would be overwhelming).
This will be a hard sell.
And, as always with password checkers, you can enter something similar to your actual password.
PHASE 1
1. Seed a first character with Lastpass password generator with all character classes enabled. Turns out to be an 'x'
2. Try the entire possible keyspace in the second character slot to see which characters are "expected". This turns out to be all but members of the set (h,H,b,B,n,N,6,8,~,#). That is, of 94 possible character (on my keyboard) 84 are "expected". That's 89% of the keyspace.
OK, so perhaps we can explain this by the simple expedient of the fact that any 2 character password is bruteforceable, though if this is the true explanation, I'm not sure why h,H,b,B,n,N,6,8,~, and # should be singled out as unpredictable.
Phase 2 tests whether password length explains the phenomenon of the applications seemingly lax definition of "expected".
PHASE 2
1. Seed first 31 characters with Lastpass password generator. This turns out to be 't4lzV%geWagnJW3&3tntDBWI5K0eL' (without the enclosing single quotes). Significantly, the app only considers 4 of the characters in this supposedly (pseudo)randomly generated 31 character string to be "unexpected".
2. Same as above, try each key in the entire keyspace to fill in the 32nd character slot. Again, all possible values are considered expected save for members of the set (a, A, l, L, e, E, 1, 3, 4, 7, @, ^, &). So the app "expects" 81 out of 94 possible values at that 32nd character slot. This constitutes 86% of the keyspace.
So... apparently bruteforceability doesn't explain the first result.
The prediction model seems to be so wildly unrealistic in judging the predictability of a password (or even in fact a particular character within a password) as to be completely unusable for any practical purpose. In fact, limiting your passwords to strings that maximize the number of "unexpected" characters seems incredibly ill-advised as it mainly reduces your keyspace on a per-character basis to ~15% of its potential size. And since this application exists and is accessible to everyone, it can be integrated into password cracking attempts (especially if the algorithm is published).
http://tgad.wordpress.com/2013/09/18/what-is-entropy/
But the main problem with your reasoning is the idea that passwords with large character pools are more secure (i.e. have more entropy). This is a common belief, but isn't necessarily true. If the characters in your passphrase are completely randomly selected from the pool, then yes, a passphrase of length n will have more entropy if the character pool is larger. But you aren't randomly selecting the characters, you're pulling them from a grammar which is a very small subset of all possible combinations. Therefore, the security of your password relies on the secrecy of the mechanism, which is not a good idea, since if your method becomes popular (and as they say, there's nothing new under the sun), then password crackers will just start generating passwords like yours.
In practice, it is a tradeoff. If you have already decided that the password for this particular computer/application/website does not entail the use of password DB, it is a good option.
You are on purpose selecting a low entropy password, just one whose underlying pattern is hard to guess by a would-be attacker. I would not use this kind of approach for any account that makes it obvious that I am a programmer (aajem, HackerNews)... but for the general population, the attacker is not likely to target YOU, but the average user of such and such site.
... a passphrase is most useful if you can remember it and use it. While having 100 bits of entropy is something nice to shoot for, one has to look at their threat models and decide if it’s worth it. Is having a passphrase 8 words long really the price you pay to keep hackers out of your lolcats.rus account? Maybe yes, maybe no. The truth is, for most web accounts, 100 bits of entropy is overkill.
My point is that there is no advantage of relying on a passphrase you don't know the entropy for, since it's usually lower than what you thought, and there are methods of generating memorable passphrases that you can actually measure the entropy.
I guess I just don't understand why one would ever let their security rely on the incompetence of a potential attacker, instead of relying on the math, when they're both basically just as easy.
No there are not! The minute you publish your method, the measure of the output's entropy stops being relevant. Your security theoretically relies on the input's entropy, which is likely to be much smaller.
But in practice, an actual attacker no longer produces brute force attacks in the blind. He actually has to model the desired target's strategy, and produce an attack suited to that. When you are modelling your attacker, you may consider that he may consider the aforementioned method, along with any other methods his model of his intended target (which may be you, personally, or some abstract model of either you or the average X's user, both based on demographic data) allows for.
For this reason, using programming language syntax instead of natural languages might be either a decent idea or a terrible idea, based on how accurate the attacker's model of yourself will predict you are likely to do so.
In my personal case, given this conversation, it will be an extremely poor strategy, if I choose to model my threat model as a targeted attack (I am leaving plenty of evidence that I am likely to do something like this, on a public forum)... but if I happened to have this 'my-little-pony' alter ego, not traceable to my professional persona, it would be somewhat solid strategy, (at least in the sense than few bronies are likely to choose such type of strategy).
And if the risk model is that of an attack on a compromised password database of thousands of not ipsec-sophisticated users, the strategy will be as good as any other for the same ((alphabet size) * (passphrase length)).
What? If we're applying Kerckhoff's principle, then the mechanism literally never generates entropy. The only place it can ever come from is the source, which means the only thing your methods can do is either keep the same amount of entropy or reduce it (anything else would require another source of entropy). This comes straight from the math: self-information can't increase using mappings alone, but it sure as hell can decrease. It's these decreases that are difficult to measure.
>He actually has to model the desired target's strategy, and produce an attack suited to that.
In theory, yes, but in practice, machine learning does that for you. The point is, a patterned method like using code will require very long passwords compared to just using diceware (or hell, just using /dev/random to pick words from your dictionary file) if you want them to both have the same amount of entropy. The only other argument that can be made to the contrary is that something other than entropy determines password strength, which isn't true if we assume a sufficiently advanced adversary (of which I consider machine learning algorithms + a gpu/asic cluster to be). Since the only things that really go into how "good" a password is is usability and security, and diceware passwords are probably just as or more memorable than code snippets, again, I don't see the advantage of the latter in any case.
Something as simple as "if(password){logmein()}" would be quite hard to brute force I believe.
I've taken to using 1Password, but constantly have to dumb down its password generator, and it's almost always for financial institutions (which tend to have maximum password lengths -- which is truly scary in its implications -- and generally don't allow most non alphanumeric).
Government website have been the biggest offenders here, in my experience.
Are they crazy?
A few numbers is enough when you need a physical card and to stand in front of a camera... but it's not when you are online.
This also seems to discourage passphrases because even though any good passphrase (such as "correct horse battery staple") will get 5 checks easily, you have to get through a lot of Xs to get to those checks, each one suggesting that what you are doing isn't a good idea.
The tool does however suggest an interesting alternative to passphrases: Only use as many letters of each word as are unpredictable. In other words, only type each word until the next letter is predictable. For "correct horse battery staple" this gives "c h bat stap". I really have no idea if this is a good password, but it does get 12 out of 12 checks and only one less check than the full phrase.
As with any password evaluation, there are patterns it doesn't know how to check. It takes a long time to figure out the pattern "a1 b2 c3 d4 e5" and still gives a check for each space. It doesn't detect spiral patterns on the keyboard at all ("gtrfvbnhy" on a qwerty keyboard for example).
Still, it will be interesting to see what they can do when they get more data and think through some of these issues.
EDIT
You can also use this to choose letters that make sense but aren't in the prediction. I came up with the password "pitabakes" (pita bakes), which is obviously pretty easy to remember and presumably fairly weak simply by deliberating taking something which seemed likely but not in the top 3.
One also has to wonder whether deliberately being unpredictable somehow becomes predictable. This tool, to some extent, suffers from the fundamental mistake of gamblers: seeing patterns where there aren't any. See jerf's post about getting X marks in a LastPass-generated password. If you tweak your random passwords to not be predicted by this engine, are you actually making them somehow more predictable?
EDIT AGAIN WITH MORE NEW FINDINGS
You can also get high numbers of checks (and a relatively high ratio of checks to X marks) using common dictionary words if you switch words in the middle. So, taking the words "grape", "pasta" and "toffee", using "grapastoffee" which gets a 50/50 ratio of checks to X marks (6 of each). This actually seems like a pretty good way to generate hard to guess passwords. "Pen", "noodle" and "duck" giving "penooduck" does even better, 7 out of 9 checks.
Do you mean that you think that passphrases aren't actually a good idea? Or do you just mean that the tool might make someone think that they're not a good idea?
10000^4 = 10^16 ≈ 2^53.15
So yeah, a randomly selected passphrase chosen from a pool for 10,000 words would work just fine. Assuming we're talking about secure software. For websites, use a password manager and then pick your poison for how you pick the master passphrase.
In reality you'd be lucky if all of it does one iteration. In which case it will only take a day on one machine.
You're also underestimating how massively parallel GPUs are becoming.
The more important question is - why settle for 53 bits and worry about it?
Trust nothing. KeePass let's you choose the number of iterations, and can autocalibrate. I believe it calibrated mine to >1mil iterations. I use KeePass to generate the passwords for pretty much everything else, except TrueCrypt (which uses ~1,000 iterations, but it's far more complicated than that). So the number of iterations everything else does is unimportant.
> You're also underestimating how massively parallel GPUs are becoming.
I'm a Bitcoin miner and developer. I know exactly how parallel GPUs, FPGAs, and theoretical cracking ASICs are. Only ASICs would be able to achieve 1 TH/s of cost effective cracking power, which is where I spec'd my estimate. Suffice it to say, that number I quoted is an underestimate; it would take a real attacker much, much longer. Unless we're talking about organized crime or the government here, in which case you can look forward to them spending a year of their entire computational power on just little ole you.
> The more important question is - why settle for 53 bits and worry about it?
That is why I asked what your criteria is. A line must be drawn somewhere. Humans aren't good at generating and/or memorizing passphrases. So picking a reasonable threshold is important. If 30 years of security against an unreasonably powerful attacker is not enough, what is?
Here's my comment in this same thread:
https://news.ycombinator.com/item?id=6864466
I agree that if you pre-hash your passwords 1 million times yourself, then it's much safer than using the password directly. You're basically slowing down the bruteforce attack by a factor of a million, which is equivalent to adding log2(1M) = 20 more bits.
53 bits is definitely not enough to protect anything important. I, personally, use 30 character passwords for anything mildly important, like email, which is around 170 bits. For bitcoins I go 40 characters - that's around 230 bits.
Per the table on page 107, 40-character user selected passwords have between 56-62 bits of entropy.
That's (ballpark) equivalent to 8 completely random characters, which is relatively hard to remember. I know, personally, I'd rather remember 1 word than 2 randomly chosen characters from a pool of ~100.
Easy to remember and easy to type.
What benefit does this have versus adding an additional word?
All my passwords are randomly generated, I set the minimum at 30 characters. My most important passwords are 40 to 50 characters.
I highly recommend a similar system. I feel a lot safer than when I had to remember passwords for my email accounts, banks, credit cards, Ebay, Paypal, my webservers, FTP, SSH.
I even store my credit card info in KeePass, so I don't have to type the 16 digits every time.
So if a single password is compromised, all of your randomly generated passwords are compromised? So what kind of password do you use for the keyring that you believe is better than memorizing a chain of words?
For reference, my longest pass phrase is a story constructed around ~30 random words, which using equivalency above, is about ~60 random characters. I don't have to rely on a password manager to keep it safe via a (probably weaker) password.
Anything beyond that is simply done via carrying a physical device with a key on it.
If you're using the printable ascii characters with fully random selection, that's 6.55 bits of entropy per character, for a total of 196.5 bits of entropy over 30 characters. For anything over 20 characters (=131 bits of entropy if randomly selected), you're implying that there is someone out there who can bruteforce the keyspace of AES (128 bits in the most common case), but can't install a keylogger on your system.
I also try to futureproof with using extra long passwords. Most of the time I copy-paste them anyway, so it doesn't matter.
The attacker wouldn't know which characters I used, so they will have to have a wider coverage anyway.
Keylogger is my worst fear, of course. But I try to be safe about the shit I download and how I browse the websites. I scan my PC for viruses, keyloggers and rootkits daily.
Mostly, he didn't say it was "good". Or that he liked it.
"Telepathwords is a pretty clever research project"
Clever doesn't mean "good".
"It's different from normal strength meters, and I think better."
"better and different" doesn't mean "good". (Burger King is different and better than a hamburger at a local high school).
"I like seeing new research in this area."
Also does not mean "good".
So Schneier is not doing anymore than reporting on this password strength estimator (his words). He is smartly not getting trapped into saying he likes it or thinks it does a good job only that it does a better job than "normal strength meters" and that he likes "seeing new research in this area".
Which is clever. Because nobody can come back and say he was wrong.
This is somewhat grammatically tricky to parse. A better way to phrase it would have been:
"If your password has many characters that Telepathwords was able to guess, attackers may also find your password easy to guess."
That's interesting. Has anyone ever used mouse movement data? How is it collated, displayed, used?
That seems like it would be a useful measure of strength.
This is one I found: fvckup.