Schneier on Security
A blog covering security and security technology.
« Heartwave Biometric |
| Bruce Schneier Facts T-Shirts »
December 6, 2013
Telepathwords: A New Password Strength Estimator
Telepathwords is a pretty clever research project that tries to evaluate password strength. It's different from normal strength meters, and I think better.
Telepathwords tries to predict the next character of your passwords by using knowledge of:
- common passwords, such as those made public as a result of security breaches
- common phrases, such as those that appear frequently on web pages or in common search queries
- common password-selection behaviors, such as the use of sequences of adjacent keys
Password-strength evaluators have generally been pretty poor, regularly assessing weak passwords as strong (and vice versa). I like seeing new research in this area.
Posted on December 6, 2013 at 6:19 AM
• 54 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
In a 36 character passphrase (battery staples style) it guessed 21 leaving me with a 15 character password. I think it missed all five spaces which looks like a shortcoming.
Btw, 36 seems to be the maximum as the original phrase was much longer.
My 8 character random (based on initial letters of a phrase I remember) was pretty secure, only 2 characters guessed. My 4 random word passphrase (XKCD-style) had about 70% of the letters guessed. The flaw seems to be you give it one character and it guesses the next. But in real password cracking, you don't get an answer that the next character is right or wrong. I would go with the 4 word phrase any day.
It might be good for eliminating the stupid passwords, but I don't think it is that good on smart ones...
That's amazing, looks like a great way to speed up that classic scene from the movie wargames where the launch keys get hacked.
I will never willingly reveal my passwords to NSA^H^H^HMicrosoft! :)
The fact that you can't test your real password is a bit annoying, but it can be useful enough
That's amazing, looks like a great way to speed up that classic scene from the movie wargames where the launch keys get hacked."
Yup, they should have known that the launch keys were "00000000".
"But in real password cracking, you don't get an answer that the next character is right or wrong. I would go with the 4 word phrase any day."
That is not the point. It implements a Battery Staples type of search in single characters. But it augments it with numbers and the 1337 speech type of changes.
Actually, the xkcd battery staples pass phrases were designed to beat this type of search.
As a short test I fed it with several 96-bit pieces of pseudorandom data, base64'ed into 16-character-long sequences. It "guessed" 1-4 characters out of each sequence.
I think these are "string or nothing"-style guesses, that is cheating :-) Basically, it openly declares three "top" guesses before you type some characters, but not how many "guesses" it has actually considered. It could have internally flagged almost all characters as "probable" at any given point then declare a success.
It is no more that grepping /dev/urandom for dictionary words or alterations of them. You WILL find some.
Telepathwords could gather some very interesting data about how people think and what they use as passwords, which could then be included in algorithms designed to crack passwords.
I tried both passwords from Wargames.
It predicted the last 5 characters of "joshua" (not surprisingly)
It only predicted the very last character of "cpe1704tks"
Tried the same with Sneakers' famous phrases.
Guessed 6 char from "SetecAstronomy"
Guessed 8 char from "TooManySecrets"
Guessed 13 from "My voice is my password" though it seems to skip all of the spaces as Winter noted.
I wonder if it gets smarter as more people try it, adding strings to the dictionary.
This in yesterday, which seems timely. From @NightValeRadio as retweeted by @StevenBrust:
Your password must contain at least 1 number, 1 capital, a photo of your least favorite insect, taffeta trim, and a rigid, uncertain smile.
It only guessed two out of an 18 digit password I use, the 3rd and the 15th. The 3rd was purely coincidental, but the 15th was a good prediction because the last eight were a mmddyyyy date and it recognized and predicted the "1" in the year (1yyy). My password was the first letters and all numbers of a sentence like, "My wife's maiden name was Jessica Parker, and we got married on 02-17-1975." It has the advantage of letters, numbers, and mixed case which some sites require. Maybe I'll change that last clause to "we got married on February 17th of 75" though.
This is a great talk by a pentester on the predictability of corporate passwords:
DerbyCon: Cracking Corporate Passwords Exploiting Password Policy Weaknesses (Minga Rick Redm)
The problem is passwords themselves. We have to get rid of them and devise a stronger alternative.
I have used passfault as a means of evaluating password strength. Comparing between the two sites will be interesting.
If you care even a little bit about the security of your passwords the only sane approach is to use a password manager and automatically generate random passwords. This tool is probably useful to help you choose a suitably-strong yet still memorable passphrase for your password store but that should be the only "password" you need to remember (and never be transmitted anywhere), so random generation will provide you the best security for all of your actual passwords.
There is no way that an average human is going to remember a different secure password for every login they use, and doubly so when you factor in password rotation policies. A scheme based on variations of the same password for different sites isn't much better than just using the same password for everything, since as soon as one password is cracked or leaked it will most likely be clear that's what you are doing.
I used PasswordSafe for many years, and it's a good option. These days I'm using KeePass, mostly because of the plugin system which allows me to also store SSH keys and integrate it with my web browser, as well as automatically sync with a remote copy of the password archive for use across multiple machines.
Hm. It says it can guess a few characters even from strings generated by randomly hitting the keyboard. And actually a great way to collect more data ;)
hi folks! crypto-ninja is back :-D
eat this, you slimy microsoft-nsa-password-spying tool :-P
crack time (seconds): 3.736709727215436e+111
I wanna see how the heck somebody or something in universe could crack such a password. Well, maybe the alien-mothership :-))
Note: the only thing it's looking for is English. It thought "plugh" was okay except it needed three more characters, and that "elberethgilthoniel" is a good password. (I'm not feeding it my actual passwords, but "elberethgilthoniel" wasn't a good password even before the movies came out.)
Interesting that it doesn't know plugh, but it does know xyzzy. Was xyzzy in more than just the Cave Adventure (Advent) game, but plugh only in Advent?
It recognizes some non-English common phrases, such as "e plurbus unum" and other Latin words.
Needs more work. It thought this was a reasonably good password: bitemyshinymetalass
Obviously not a Futurama fan...
Agreed. It would be great if more people used password managers but I'd worry about "still memorable passphrase for your password store". I think a lot of users would end up with one weak key storing a lot of strong ones.
On something like KeePass a safer approach is memorized key+ keyfile. Or instead of a keyfile a long random character key could be entered from something like a Yubikey. On LastPass you can do the same sort of thing and add one of their OTP/2F options as well. for even more security, bump up the key strengthening. On KeePass there is a default of 6000 encryption rounds. Click the one second delay option and you get millions of rounds.
Well, this NSA-Microsoft-spyingsite can not "predict" anything when you generate a random super-pw.
Always use a unique pw for anything. Store them in a good pw-tool like Keepass or Passwordsafe.
Using some latin gibberish or any words as a pw is not so smart, trust me. :-)))
I put a number of 30 character 'full spectrum' (i.e. full keyboard) passwords generated by Password Safe into the tester. The tester always guessed at least 1 character right, sometimes more than 2, but the median (informal) was 2. Is this consistent with a proper PRNG in Password Safe?
It strikes me that, if I wanted to build up a good dictionary of passwords that slightly security-conscious people use, this would be a great way to go about it...
So the really interesting questions about something like this is are two, I think.
- How many people type their real passwords into it, or subsequently use passwords that it thinks are good? Given what we now know, it's probably not a good idea to assume that this is ever a good idea.
- If you are not willing to do that, is it any use at all to you?
The second question is interesting. The most obvious way it might be useful is if it lets you type a password which is somehow "close" to the one you actually want to use, while not being the same. Well there are two options: either it is actually close, in which case you have just dropped a big hint to the system as to what password you might be using, or it's not actually close, in which case you probably have not learnt anything about the guessability of the password you are really going to use. In either of these cases it turns out that the system is not useful.
This is a slightly extreme position, of course.
It doesn't appear to target NIST's random word algorithm. Feed it these:
perl -e 'use Crypt::RandPasswd; print Crypt::RandPasswd->word( 20, 24), "\n";'
perl -e 'use Crypt::RandPasswd; print Crypt::RandPasswd->letters( 20, 24), "\n";'
perl -e 'use Crypt::RandPasswd; print Crypt::RandPasswd->chars( 20, 24), "\n";'
"But in real password cracking, you don't get an answer that the next character is right or wrong."
That's not how these estimates work/apply. The point isn't that the attacker would get to use the same methodology as the site, it's simply one attempt at a measure of the entropy in how you made your passsphrase. As long as the entropy is low, then there is some method of guessing that password without having to try every possibility. I wrote a blog post related to this:
in particular, note 7:
I think it's irresponsible of them to put this up without a warning to never enter your real password into random sites on the internet, password checkers or not.
Phishing is easy enough already. This is not behaviour we should reinforce.
Pretty neat! Time to change my password :(
I typed the first three letters, and it found out the remaining 5 - It didn't guess the other 4 - 5 characters (a little random), but it reduced my belief in my password strength significantly!
It had a hard time with this password:
"the six million dollar man" -- I guess it needs some enhancments...
Damn, I tried the password I use for everything; I typed in the first letter, "p", and it immediately had the next 7 characters.
Shannon measured the entropy of English text by showing text snippets to volunteers and asking them to guess the next letter in the sequence. ("Prediction and Entropy of Printed English", 1950).
His result: each letter has about 1 bit of entropy in normal text. A password might have more by including uppercase, letters, or symbols, but those are usually added at the end to satisfy a web form.
The best password-picking scheme I've seen is to use a memorable phrase.
For example, consider: "look, up in the sky, it's a bird...". Using the 1st characters of that phrase gives you my WiFi password. It's easy to remember, and has high entropy.
My WiFi password: "luitsiabiapis"
The problem with passwords, the single most important aspect that drives all this controversy, is that we need so many of them. Every two-bit website on the planet demands a username and password, and we're told we need different ones for each for maximum security.
If only there was a way for a user to authenticate using a single password, and let the system manage passwords based on that. A bluetooth device the size of a key-fob that provides an encrypted authentication service to the PC/Phone, or some such.
Pick strong passwords from the printable (typable) set but be aware: *any* kind of pattern is a problem. You need to know what sets your remote accepts - some may be silently folded or ignored but you mightn't know what they are.
Plus we tend to assume the crummy alphabet we westerners use, we have not the rich cyrillic or katana/kanja set.
One good thing about password managers is they would allow code on the client end to implement a login algorithm other than "send the contents of the password field as is".
SRP, for instance, has the advantage that the data sent back and forth, if intercepted, is not sufficient to determine the password. But the server's SRP database, if revealed, allows offline password guessing.
If the client has some secret data other than just the password, and can execute an algorithm, then we have the possibility of authentication through a zero-knowledge proof. E.g. my password decrypts an ECC private key locally, and I authenticate via an interactive zero-knowledge proof that I hold it. The data sent back and forth reveal nothing about the private key, and the server's authentication database contains only users' public keys. No offline password guessing would be possible by eavesdropping on the authentication data being sent back and forth and/or revealing the server's authentication database. Granted, finding the client's secret data would allow password guessing, but that would be on a per-user basis, not thousands of users in a single hack.
A zero-knowledge proof requires some CPU cycles on the server, but fewer, I think, than are used for robust key-stretching.
Will I just tried two test. The first was the two word name of a stream. It guessed the two letters that were substituted in the name and "run" that was appended. It didn't guess any of the five letters (no substitutions) that are the name of the small mill town where I live. It's so small it must not have been in their dictionary until I gave it a try. ;-)
Don't Password strength tests only matter because they predict which passwords will or will not be easy to crack, and doesn't that depend on the cracking methods?
2. If you are not willing to do that, is it any use at all to you?
I thought the same thing. At best this is an amusing program with no real-world value. At worst it is building a dictionary for future attacks.
As for evaluating the "strength" of your passwords, it's probably okay for showing the really bad ones (already in dictionaries or guessable from dictionaries, password, password1, password2).
But once you get past the "already cracked" situations (LM hash, dictionaries, etc) I don't see how this would help.
Unless more information was "leaking". Such as the length of the password or some method of detecting specific keys. But that places this into the "already cracked" category.
Damn, I tried the password I use for everything; I typed in the first letter, "p", and it immediately had the next 7 characters.
Haha! Good one! Didn't anyone tell you "00000000" is not not a particularly strong password? Or do you happen to work for these guys
Amused that a site hosted on microsoft.com does not appear to work in Internet Explorer (8).
Based on some examples I tried (and the guesses it listed) it doesn't seem like it guesses well against first-letter-of-every-word-in-a-sentence style passwords; it only guessed 2 in "2bon2btitq" (to be or not to be...)--one was for the repeat ("2b" appears twice) and the other one I didn't understand the reason it gave.
It didn't guess any letters at all in "3rftekuts" (3 rings for the elven kings under the sky).
(Note: I do use first-letter-of-every-word passwords for some of my actual accounts; I don't use any based on famous phrases from famous authors like the examples above.)
One problem with estimating entropy is that as password databases are leaked, password entropy declines.
The approximate time to brute force a password when using an ideal strategy is somewhere along the lines of:
If you choose an already leaked password:
(size of DB)/2
For dictionary words:
n random dictionary words: (size of dictionary)^n/2
Capitalized first letters: no improvement if upper case letter required, multiply by two if not
Random capitalization? multiply by 2^(length of password)
l33t text? multiply by 2^(length of password)
Add a digit to the end of a word? multiply by 10 for each word
Add a digit in the middle of a word: multiply by (length of password)
4 digit year? Multiply by 100
Note that using more words adds significantly more entropy than things like l33t text and random capitalization, however, if it's in a list of phrases, it's just a larger dictionary attack.
Also, note that attackers will likely try the most common passwords and passphrases first. This can be a small benefit if you choose something uncommon, but a huge disadvantage if you choose something common.
If you are using made-up words, or something that is not in a dictionary, then that gets more complicated, as it depends on using patterns to minimize search time. I have no clue how to etimate how long that would take.
@DanS re: "still memorable passphrase for your password store"
My PWSafe vaults (I'm required by employer policy to submit my passwords on demand, so I have a vault for any password I'm willing to comply on, and another for the rest) are on a Defender F200 (Imation was the brand on mine, but the tech has been changing hands), so my fingerprint is the first line of defense, and my vault passwords the second. I know many here loath fingerprint scanners, but the F200 does not appear to have a vulnerable manager app (I can actually authenticate to it pre-boot if I choose) and the scanner is aperture, not full print. If my finger is moist or greasy, I have considerable difficulty with recognition, so I suspect anyone trying the "jelly bean" ploy would face a challenge. The amputation strategy is different story, I have other counter measures "on hand" for that.. I'd be 100% satisfied with this solution if I could use it on my phone as well. I've found Password Safe ports for iOS and Android, but nothing equivalent to the F200.
@Mort re "Phishing is easy enough already"
I completely agree. I despise the practices of many banks & sw vendors who stupidly send legit notifications that look exactly like phishes - this is even more indefensible. OTOH it's Microsoft, so what did you expect?
@Wael re "six million dollar man"
Perhaps allowances were made for inflation?
@MikeAmling: Something similar to this, perhaps?
I haven't seen this discussed here, and I'm very curious about what the good folks here might think about it.
"Persona also takes a novel approach to protecting user privacy by putting the user's browser in the middle of the authentication process: the browser obtains credentials from the user's email provider, and then turns around and presents those credentials to a website. The email provider can't track the user, but websites can still be confident in the user's identity by cryptographically verifying the credentials. Most other systems, even distributed ones like OpenID, require that the sites "phone home" before allowing a user to log in.'
The website seems to be censoring itself -- I just tried typing in "yourmotherwasahamster", and at "yourmother", one of the guesses was "F as in mother****er".
Its telling me "pieare3" is better than "pieare^3" -- How strange! Or am I reading it wrongly?
Perhaps! Been a long time since 1974!
Does this advice from Bruce still hold true (Jan. 11, 2007)?
[Comment and Answer]
This comment by New Boy at January 11, 2007 12:13 PM [40% down page]
“Which passphrase below will likely be broken first in real life situation by government agencies?
1. E5&crW9C@8#x (12 random characters)
2. aaaaaaaaaabbbbbbbbbbccccccccccdddddddddd (4×10 = 40 characters)”
Can anyone give a comment on that now? How secure is such a “long password strategy”? Similarly, I’ve seen some people advocate using a long sentence as password. A related strategy would be to repeat a simple word multiple times and then add some other stuff. For example:
“soccersoccersoccersoccersoccer$$soccer”. That’s an easily memorized password: 5 soccer, 2 dollars, 1 soccer. But how secure is it?
Posted by: Rom at February 10, 2007 7:45 AM
@ Rom and @ New Boy
"Neither password will ever be broken by the current — and forseeable future — generations of password guessers."
Posted by: Bruce Schneier at February 10, 2007 8:53 AM [70% down page]
If the attacker knows the strategy, it's weak. If you copy a known strategy, it should be considered weak. If you learn how existing password generators work, then pick a strategy that it does not cover (which there are probably more strategies than words in a dictionary), then it is strong only because it's obscure.
If everyone, or sufficiently many, came up with password strategies of their own, you would have so many that it would not be security by obscurity anymore, security would be because of the sheer number of combinations of strategies and dictionary words.
Interesting. Length used to be a major factor. I guess with the newest best guess technology it is not.
I can't tell from looking over that Persona web page just exactly what who sends to whom when. It does look like it's using digital signature rather than zero-knowledge proof.
Length is helpful but not as important as how the password is constructed. If you know the password policy requires an upper case character, lower case character, number, and 8+ characters, you can do a quick pass through a password database looking for common passwords, then go through an english dictionary and test words (or names), capitalizing the first letter and testing the numbers 1,2,3..,9,123,[year],0,00-99, 000-999,[birthday] at the end, then the beginning. Regardless of how long of a word you choose, if it is a word, it's going to be found if it fits that format.
Also, if your password is in a leaked database, it is weak regardless of how well constructed it is.
I use a common password for stuff I don't care about, and I use different passphrases I have memorized for things like email, banks, amazon, etc. At one point I also had a random 6 digit number I memorized to append to my more secure passwords (although the phrases weren't reused, the number was), to add an extra 20 bits of security.
The best solution is just to use a good open-source PW-manager. Use Keepass or "Password Safe".
Just remember ONE PW, that is the master-PW for the database, all other PW are random and long, generate them with the PW-manager, then you get stuff like
crack time (seconds): 1.374662112589785e+92
"Good luck NSA-schmuck" when you try to crack or "predict" that :-)
For every account or purpose, use an unique PW, so if some website or so gets cracked, all your other accounts are safe.
In addition to choosing your own strategy, you must resist the temptation to tell anyone you know anything about it. That can be more difficult than it may sound, particularly if your profession involves educating others on choosing good passwords...
Schneier.com is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc.