I'm sure this is a common problem everybody has, but say we want to do the following:

1. Have a different password for every service
2. Not have to memorize all the passwords
3. Not have to write down or otherwise store passwords
4. Have passwords readily retreivable (without asking the service)

... and have passwords be secure even if an attacker

1. knows the method used to generate passwords
2. may have key loggers installed on any computer you can use
3. knows everything about you that's publicly accessible
4. knows some, or even all, of the passwords except the one he/she wants

So this is more of a fun puzzle than a real-world problem, although such a system could obviously be useful for the paranoid. Anyway, some friends and I were thinking about this, and we got distracted before getting far, but came up with some thoughts:

• We obviously need to use some form of secret information that's unknown/unknowable to the attacker
• One idea is to come up with a one-way function that's fairly simple to compute given your secret information, and apply it to another known string (your login name, or service name) on the back of a napkin (so we're assuming the attacker isn't around -- and you'll have to eat or burn the napkin)
• The problem with the previous algorithmic solution is that, whatever you can do on a napkin, a computer can do millions/billions of times faster, so it's potentially suseptable to brute force attacks (unless you can do arithmitic with 100 digit numbers on the back of a napkin)
• So another idea is to use information that humans (or more specifically, you) can easily store and retrieve, but would be very difficult for computers to figure out. For example, childhood memories, word associations, emotional things, graphical memory, etc.
• One possibility might be to memorize one word or idea, that leads to additional data. This might be the name of a song (to come up with the lyrics), chapter+verse of the Bible (if you happen to be one of those people who can quote the Bible verbatim), etc. The only requirement is that you have to be able to recite the data without error, and it has to contain most (preferrably all) letters of the alphabet. This can act sort of like a one-time pad.
• From there, you can do a number of things, like write down the text in a grid, and use grid coordinates to go from say, the service name to a sequence of numbers (which you may need to map back to a larger aphabet).

Any other thoughts? [Tagged: passwords cryptography ]