An Idea: Upending the Password Strength Problem

July 14, 2006 by Ping

I had an idea yesterday evening inspired by Cynthia Kuo’s talk on phrase-based passwords.  Cynthia’s research started with a popular method for choosing memorable passwords and evaluated the strength of passwords created using that method.  And there was a questioner from the audience who noted that, whenever you popularize a particular formula for making passwords, attackers can develop dictionaries tailored to that formula.

What if we turn the problem around?  What if, instead of treating memorability as the constant and strength as the variable, we treat strength as the constant and memorability as the variable?  Suppose we have the computer choose a completely random password, to guarantee good password entropy.  The phrase-based technique shows that a phrase can be turned into a random-looking jumble of letters and numbers.  With a sufficiently large word list and a basic knowledge of grammar, can a computer turn a truly random jumble of letters and numbers into a memorable phrase?

I do not see a lot of promise in this approach, because I do not think you can make an algorithm that will generate passwords that are memorable across a large enough portion of the population without drawing from a relatively predictable pool. Memorability is more personal than that - this is why I want to provide real-time feedback and base minimum password requirements on an entropy estimate - so that people can create something memorable for themselves that is of at least a constant strength.

However, one idea some colleagues at NEU had suggested was a password selection system where the random algorithm is trained based on passwords a user enters in the system. Say the user inputs a list of passwords they feel they’ve been able to remember - the algorithm would look for patterns and try to replicate those in passwords generated for that user. When it generated a new password it could generate a set and let the user select from amongst them - which would also further train the algorithm. The problem, of course, is the development of said algorithm. This would be an interesting approach, but I think real-time feedback and dynamic help systems offer more generally applicable promise.

 
Andrew Probert wrote:

I’ve seen a site which uses nonsensical alphabets which are randomly generated but phonetically (for English) correct. It made them memorable e.g. pevofenu which ’sounds’ memorable.

In which case a large number of passwords / phrases can be generate (> dictionary-size).

 

This idea reminds me of an idea of Norm Hardy’s:

http://www.cap-lore.com/code/Mem.html

 

Strong password anyone?…

I find this idea from Ka-Ping Yee very compelling.

What if, instead of treating memorability as the constant and strength as the variable, we treat strength as the constant and memorability as the variable? Suppose we have the computer choose a co…

 

This is impractical.

Fact: Users hate complex passwords and will always choose the same weak password given a chance

Observation: Users will write down complex passwords on a post it note and leave it around their computer. (Don’t get me wrong - there is *nothing* wrong about writing down a password if you store that properly)

Observation: I have a 20 or so character password, but I bet most of you do not. Don’t write security protocols that make freaks like me happy - do it for the general case. Security is only as strong as the weakest link, and that’s my Mum.

==> Therefore, we have to work with humans in mind, rather than tin foil hat brigade.

Fact: DVDs containing all possible MD5 and SHA1 hashes cost $20 at DefCon

Fact: Rainbow cracking takes less than a second on modern hardware after the tables have been loaded

Fact: Rainbow cracking is extremely effective. Brute forcers can find > 30% of all passwords inside an hour.

Fact: lost and forgotten passwords cost industry billions each year. It’s totally unproductive use of operational expenditure.

==> Forcing users to change passwords frequently is a waste of time. Don’t do it.

The day of the password is over.

We must stop investing in passwords and backdoors like Q&A’s password recovery schemes. Passwords have a non-zero cost, so let’s invest that non-zero cost in something users can handle easily and securely without making them tin foil hat lovers.

 

It is possible to inject a fairly large amount of randomness out of phrases; the problem with phrase-based passwords arises when you let the users pick their own sentences. The paper that is mentioned in the post confirms this.
We have explored what Ping has suggested, i.e. creating phrases for people that actually encode random passwords:

U. Topkara, M. Topkara, M. J. Atallah, “Passwords for Everyone: Secure Mnemonic-based Accessible Authentication”, Proceedings of the 2007 USENIX Annual Technical Conference, Santa Clara, CA, June 17-22, 2007.
U. Topkara, M. J. Atallah, M. Topkara,”Passwords Decay, Words Endure: Secure and Re-usable Multiple Password Mnemonics “, Proceedings of 22d Annual ACM Symposium on Applied Computing (SAC 07), Seoul, Korea, March 2007.
S. Jeyaraman, U. Topkara, “Have the cake eat it too: Infusing Usability into Password Authentication Systems”, Proceedings of the 21st Annual Computer Security Applications Conference, Tucson, AZ, December 5-9, 2005.

Despite the problems in generating natural language text, you can do a fairly good job. Our systems first generate a random password. Then we use sentences that we collect from newspaper headlines, and modify these sentences so that they encode this random password. It is possible to reach the security of an 8 letter ASCII password easily.

However, once you are able to solve this problem with one password, you face the next problem of, having to remember many phrases for many passwords. We addressed this problem in the SAC 2007 paper, but that was just a first step and we are far from a complete solution.