Telepathwords: A New Password Strength Estimator

https://www.schneier.com/blog/archives/2013/12/telepathwords_a.html

84 64 13 years ago

JoeAltmaier3• 13 years ago

A little scarey - type your precious passwords into our engine which records and transmits them to our server. For research! Really! We won't sell them, because we give them away. To researchers! Hackers totally won't ever see them, unless they pretend to be a researcher or something.

This will be a hard sell.

DanielStraight5• 13 years ago

"This log does not contain the actual characters you type, but it does indicate whether each character was among those predicted by Telepathwords."

And, as always with password checkers, you can enter something similar to your actual password.

JoeAltmaier3• 13 years ago

So they may actually be able to estimate what passwords are in use, by what people DONT type in? Interesting.

stevecooperorg• 13 years ago

"we send the characters you have already typed to query our prediction engine" (under 'What information does Telepathwords collect and why?')

BrokenPipe2• 13 years ago

I really don't get the point of password estimators that need to send the password server side. I may as well just not have a password then.

DanielStraight5• 13 years ago

Every time you log in to a site with a password, you are sending your password server-side. If you don't trust the recipient, don't send your password. But sending passwords to trusted servers is a normal part of using the web.

RossM• 13 years ago

In this case Microsoft say their prediction database is too large to load on the client, which sounds plausible. I certainly wouldn't put a real password in there though.

knowitall• 13 years ago

Unfortunately once I typed it in, I can not trust the password anymore.

ozh• 13 years ago

slightly off topic: I found this site's take on not preloading the Facebook, Linkedin and such social buttons rather interesting, for various reasons (privacy, load time)

DanielStraight5• 13 years ago

So this is very interesting. It's not exactly a strength estimator (note that Microsoft isn't calling it one, Bruce Schneier is) because it doesn't really retroactively evaluate the whole password. For example, "Entrolax" passes the test even though it's the name of a drug and therefore likely in dictionaries used for attacks. It passes though because the letter sequence is sufficiently strange. Similarly, the relatively unobscure "omnipresent" gets 4 checks for the same reason.

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.

Tloewald3• 13 years ago

Agreed. Fundamentally, picking a cutoff of "not one of the top 3 guesses" is part of the problem. I'd suggest that not being one of the top 16 guesses (i.e. less than half a byte of entropy) would be obvious the threshold.

ye6• 13 years ago

"correct horse battery staple" is actually not good. It's made up of 4 very common words. So the complexity to bruteforce is around

    10000^4 = 10^16 ≈ 2^53.15

So only 53 bits of security. I wouldn't protect something like bitcoins with that.

fpgaminer3• 13 years ago

What is your criteria which states that 53 bits of entropy is not good enough? 53 bits of entropy shoved into modern PBKDF2 (10,000 iterations) would require ~11,000 days to brute force on a machine doing 1 trillion PBKDF2 iterations per second.

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.

DerpDerpDerp3• 13 years ago

What kind of password are you suggesting that's nearly as memorable for the same level of security?

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.

6d0debc071• 13 years ago

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.

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?

DanielStraight5• 13 years ago

The latter. When you type a passphrase, you get a lot of discouraging X marks.

jerf• 13 years ago

I'm not sure the research here is done. "perspicacious", a dictionary word, gets three x's; bj3UJ@P8uy9XD, a password of the same length I just generated with LastPass (and do not and will not use, of course), gets two (on the j and the 9). (In both cases, this was the first thing I tried of that length; I did not go hunting for a good dictionary word or hunting for a "bad" random password. If I got particularly (un)lucky, it's legitimately so.)

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.

DanielStraight5• 13 years ago

It seems that rather than having some threshold of predictability, they are just taking the three most likely characters. So even though "ca" is a very common digraph, it isn't in the top 3 in the position you had it.

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).

VeejayRampay• 13 years ago

I think programmers should try to use code as much as possible for their password. Some simple expression involving an array of something and an operation on it complete with the result. Easy to remember and I think pretty hard to guess since it involves a lot of symbols, letters, numbers, underscores, dashes, spaces, equal signs, etc (unless I'm missing something obvious, which is totally possible given I'm no security expert).

Raphmedia2• 13 years ago

Awesome idea!

Something as simple as "if(password){logmein()}" would be quite hard to brute force I believe.

Tloewald3• 13 years ago

The problem for me is that as soon as you start using a clever password system like this you discover so many sites with idiotic restrictions (I'm looking at YOU banking websites) won't allow most of them.

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).

simbolit2• 13 years ago

I think what you are doing is creating a mnemonic for a long pass phrase, which is a good thing. A longer password is, ceteris paribus, a better password. The only problem is remembering it. If you can memorise code better than phrases, this is a good strategy.

aaronem2• 13 years ago

The only other problem is accurately blind-typing it, which I've found to be a drawback of the XKCD-style passphrase as well. Given a little practice, I can fit about a twelve-character password, complete with punctuation &c., into muscle memory -- anything longer than that, and the error rate rises to a point where logging in in the morning becomes a trial.

tga_d5• 13 years ago

Any time your password uses a pattern, it by definition has low entropy. I don't know of anyone that has calculated the entropy of code, but I'm guessing it's even lower than that of an English sentence (~1.1 bits per character is a common estimate) since the rules are more strict. If we estimate 1 bit per character (and honestly I think that might be high), then you'd need your password to have around 100 characters to be strong. I have a blog post where I try to explain entropy in easy to understand terms that might help understand this:

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.

crpatino2• 13 years ago

Theoretically, you are of course right.

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.

seniorsassycat• 13 years ago

Do strength estimators check a password against the contents of popular rainbow tables and dictionaries?

That seems like it would be a useful measure of strength.

aaronem2• 13 years ago

Most of the strength estimators I've used allow for a list of common passwords, but I've never seen one that checks against rainbow tables, presumably both because that would take a long time (and enormous resources on the server side -- rainbow tables are big!) and because, absent careful salting, the nature of a rainbow table would guarantee a positive result.

est2• 13 years ago

offset qwerty keyboard by one key - win

jotm2• 13 years ago

lol, no - brute force crackers have long had the option to do the same thing.

est2• 13 years ago

that's like urban myth. I have dealt with some pwd dict before. Never saw that in practice. People are more clever than you thought, e.g. offset in all 4 directions randomly, align with consonant letters, you can get imaginative about permutations.

privong• 13 years ago

" If your password has few characters that Telepathwords could not guess, attackers may also find your password easy to guess. "

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."

StuartSchechter• 13 years ago

Actually, it's perfectly fine if your password has many characters that Telepathwords is able to guess. The question is whether the password has a sufficient number of characters that are hard to guess. A 40 character password with 25 characters that are easy to guess is almost certain to be better than a four character password with none that Telepathwords could guess.

wildMatpublic• 13 years ago

It seems that to appease the search criteria and thus create a strong 'telepathword', I simply picked three random words, capitalized certain letters according to a simple scheme and typed it in backwards. Now letters were flagged as weak.

tmoullet• 13 years ago

"To measure how much of an effect Telepathwords has on your behavior, we also send and maintain a log of your mouse movements and the timings of when characters are added to or removed from your password."

That's interesting. Has anyone ever used mouse movement data? How is it collated, displayed, used?

rubycowgames• 13 years ago

Combining well known internet acronyms seem to pass the check: lmaoroflty!

shawn-furyan• 13 years ago

I don't think this tool says anything of value. A quick experiment:

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).

bradbeattie• 13 years ago

https://github.com/lowe/zxcvbn does a pretty good job of the same thing.

guoqiang2• 13 years ago

I am gonna to use this password, super strengthful... "intheworldworldworldworldworld"

teddyh• 13 years ago

Isn’t a “password strength estimator” equivalent with “random number detector”? My point is, of course, that detecting random numbers is, in principle, impossible¹.

1) http://dilbert.com/fast/2001-10-25/

larrys• 13 years ago

Let's parse what Schneier said (and didn't say):

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.

michaelochurch• 13 years ago

Here's a challenge. Find an obviously bad password, 6 characters, that gets 6 checks.

This is one I found: fvckup.

Telepathwords: A New Password Strength Estimator

Related Stories