6

I recently came up with the problem, that I have much more accounts, than I'm able to remember passwords. I don't want to use a password-safe, because I cannot access it on another computer, I lose all logins if I lose this safe and an attacker gets a much logindata, if he compromises the safe. Instead I wished for a method, to generate safe passwords with a method you can always reproduce and only remember one password/phrase/secret. To find such a method, I asked this question.

In the meantime, a friend and I came up with such a generation-method. Now I want to know, if it is insecure, which weaknesses it contains and how it can be possibly improved.

The method we came up with needs one central secret. This should be a text, that no one else knows, but is easy to remember for yourself. A poem might be easier to remember, but you should create something personal, so that no one can conclude to the text. So don't take the Jabberwocky, as everyone knows this text. (But I will choose Jabberwocky for the example).

Now you take the name of the platform you need an login. That can be something like HOMEPC or STACKEXCHANGE. Take the first character of your account and search for the first word containing it in your secret. For Jabberwocky the first word with a 'h' (HOMEPC) is 'the' and the first word with an 's' (STACKEXCHANGE) is 'Twas'. Now take the next word with the following character, and so on. This way you generate the specific password. The examples are:

HOMEPC -> 'the toves gimble the vorpal Jabberwock'
STACKEXCHANGE -> 'Twas the and Jabberwock took time manxome Jabberwock with flame And through The'

If the secret is not long enough, start over at the beginning. If the platform-name is too short take it double or three times. Same if you have the feeling, the password is not good enough.

EBAYEBAY -> 'the gimble wabe mimsy were borogoves And my'

The secret should contain every character at least once (Jabberwocky missses q and z).

What are the weaknesses in this method? How you can attack passwords generated by this, or even worse - conclude to other passwords if intercepted some?

Community
  • 1
Mnementh
  • 773
  • 6
  • 13

7 Answers7

9

This is a poor method for password generation.

  1. It requires memorizing a very long secret. This is very difficult for most users, particularly if you want it to have a lot of entropy.

  2. What's the weakest link? The same as it always is: the human. The weakest link is the human who is picking the poem (the central secret). I suspect that in practice, a large fraction of users are going to pick a poem that has relatively low entropy: i.e., is one of a fairly small set of possibilities. I'd bet that there are at most about 2^20 poems in the world, and a significant fraction of users might use one of those 2^20 poems. If so, this is a weak method. Any web site that knows any one of your passwords can recover the poem and then guess all your passwords at all other sites.

  3. Also, an attacker who knows nothing about you and wants to break into your account on some site can just start trying poems, in order of decreasing popularity, and try each password that results. There are good reasons to think that this will succeed with a depressingly high success rate. For instance, look at studies of passwords (see references below); you find that a small dictionary of common passwords suffices to break a significant fraction of user's passwords. I suspect the problem will be even worse with this scheme. It's bad enough to try to memorize a 6-8 character password; trying to memorize an entire poem would be horrible.

  4. This is trivially defeated with Google. You listed three examples of site passwords for HOMEPC, STACKEXCHANGE, and EBAY. Pick any one of those site passwords, and cut-and-paste it into Google. In each case, the very first response is the Jabberwocky poem. Thus, in each case, someone who knows a single site password can learn all of your other site passwords. That's no good. I would expect this to be a general problem for many users: not specific simply to your example, but one that would be successful against a very large fraction of users.

As always, the hard problem in this space is usability: the scheme has to be designed to work well for a typical user. I suspect that this scheme ranks poorly on that criteria.

There's a tremendous amount of prior work on this subject. It turns out that this is a challenging problem, but there are some quite good solutions. I suggest looking at PwdHash (www.pwdhash.com) and Passpet (passpet.org). Either one of them is a reasonable solution. Passpet is probably more secure, but harder to use. I definitely do not recommend trying to invent your own homebrew solution, especially if you're not already aware of the prior work on this problem.

Alternatively, many browser password managers offer the ability to sync across multiple machines or multiple browsers (using storage in the cloud). Why not try one of them? (I don't understand your statements about not being able to use it on another machine. The good solutions all provide a way to use your passwords from multiple machines.)

D.W.
  • 98,420
  • 30
  • 267
  • 572
  • That's why I said, you should create your secret instead of picking an existing poem. Jabberwocky was just the example. But it is good to point out, that choosing a common poem is bad. Thanks for the hints to PwdHash and Passpet. – Mnementh Jan 07 '11 at 09:53
  • 2
    @Mnementh, thanks for your comments. My criticism is this: long experience has shown that users are not good at choosing their own secrets. Developers tend to be wildly over-optimistic about the unpredictability of user-chosen secrets. – D.W. Jan 08 '11 at 05:01
  • @D.W. Assuming Mnementh *did* manage to usably use this algorithm (and of course kept his algorithm secret) then it wouldn't it be pretty workable? – Pacerier Apr 11 '14 at 18:06
7

I agree with User502 that for general website passwords that may well be fine. However...

it doesn't give you an option for the next password you choose if that website mandates password expiry and no reuse. I'd want something that could cope.

Rory Alsop
  • 61,367
  • 12
  • 115
  • 320
  • That's a problem. In that case I could prepend the year, using the first character of each number. But that means I have to remember the year I switched the password ... – Mnementh Dec 20 '10 at 21:42
  • Very true - I guess that could be less of an issue though, unless you really didn't visit a website more than once every few years:-) – Rory Alsop Dec 20 '10 at 21:51
  • 2
    A common problem I see is sites with differing requirements for passwords. All too often they don't allow a particular character I choose, or want it to be longer or shorter or require that particular classes of characters be used. So the algorithm has to tell you what to do in that case. – nealmcb Dec 21 '10 at 14:54
4

That method isn't cryptographically strong[1], but it looks like plenty to defeat casual database-grabbing attacks like Gawker's.

FWIW, there's a survey of web-based password management options on serverfault.

[1] Since you're choosing a phrase in English, the entropy is around 1 bit per letter, and your method could be fairly trivially guessed if someone going after you specifically recovered a password from one or two services you authenticated with.

Community
  • 1
user502
  • 3,261
  • 1
  • 22
  • 18
  • Because the method could be guessed I want to know about guessings, if you know about the algorithm but not the secret. 1 bit per letter is not too bad, the password for HOMEPC has 38 letters if I counted right. 2^38 is fairly big. But it could be improved, if your secret contains words in different languages. – Mnementh Dec 20 '10 at 22:33
  • As I explain separately in my answer to this question, I think the proposed scheme is unlikely to be sufficient to defeat database-grabbing attacks. – D.W. Jan 08 '11 at 05:03
4

This scheme depends a lot on the central secret you choose. If you use everyday text, like even an obscure poem, it generates long passwords with little entropy per character. The distribution of letters in site names is skewed, and the distribution of words in prose is hugely skewed and self-correlated.

With the right secret it probably would be fine, and with practice you could get pretty fast at doing the word-lookup by character.

You could generate a good secret (with substantial entropy for each word) with apg. Since you'll be using a number of words in your overall password, each could be small, e.g. 3 characters. Note also that by default apg produces "pronounceable" passwords, so these have a good deal less entropy than random 3-character strings.

$ apg -m 3 -x 3
Kip
Ab7
Jiz
jun
ted
yuc

If you turn off the "pronounceable" option it gets quite a bit harder:

apg -m 3 -x 3 -a 1
KIX
%(F
^hg
_Jy
!fb
QT3

Of course this is harder to memorize than a poem. It basically amounts to adding two (or more) random characters before-and-or-after each letter of the site name.

Both of these schemes are similar to another one I just ran across: Keep Your Passwords Safe on a Piece of Paper

nealmcb
  • 20,544
  • 6
  • 69
  • 116
  • So, how looks a good secret and how a bad one? – Mnementh Dec 20 '10 at 21:39
  • 1
    @Mnementh - check out User502's link, or sites listing entropy levels - one of the ways I used to test for password strength was to run John the Ripper on a mid range laptop on a SAM or passwd file and note which passwords were broken at 1 hour, 2 hours etc. Not exactly mathematically robust, but it could give you a good indication, so if you need a simple visual aid, try it. – Rory Alsop Dec 21 '10 at 08:29
4

This sounds like an incredibly difficult way to replicate http://passwordmaker.org/. It's available on every platform (including mobile and web-based, which can be loaded on your server if you're paranoid like me) and it's dead easy to use any variation, as long as you don't get too tricky with varying the rules. I've used the javascript generator many times on a remote PC. You just have to remember which sites don't accept your default configuration, if any. It even allows one to input a username or modifier to deal with password rotation.

Your method, on the other hand, will fail as soon as a site accepts only a short maximum password length.

SilverbackNet
  • 261
  • 1
  • 4
  • Note that passwordmaker is a browser plugin which just relies on your master password, and "Nothing is stored anywhere, anytime, so there's nothing to be hacked, lost, or stolen." Sounds good.... – nealmcb Dec 22 '10 at 07:04
  • I want specifically able to restore the password without software - only with information in my head. – Mnementh Dec 22 '10 at 10:29
  • Maybe you could look into something like the digits of PI and other transcendental numbers instead, where each digit has about 3 bits of entropy. (5 if you combine digits into letters.) Mathematical constants never change and they're always easy to get hold of in a library, plus counting across a table is easier than counting words. – SilverbackNet Dec 22 '10 at 22:49
4

Sounds to me like you’re suffering from some sort of password overload.

I'm not sure exactly how your systems are setup or what they are, but you could always consider authentication methods which are not based on passwords at all.

Passwords in this day and age seem to be always vulnerable to brute force, and given the availability of brute force tools and rainbow tables (and collisions within hashing algorithms - ie md5 and sha1) not to mention the ability to harness the power of GPU's on cloud infrastructure - it might something to consider.

You could possibly consider other methods of authentication which inherently rely on some other component which is considered to be "unbruteforceable" (in one sense of the word), such as biometrics.

Two factor authentication also comes to mind, ie, something you know (a password, pin etc) and something you have (rsa device etc).

One time passwords might also be interesting.

Kamic
  • 693
  • 2
  • 5
  • 20
Troy Rose
  • 141
  • 1
  • 1
    Or at least encourage your websites to move to OAuth or OpenID.... – nealmcb Dec 22 '10 at 23:06
  • 1
    As a user I have not much choice, but you're right, that would be helpful. @nealcmb: OpenID is much better. More sites should use it. – Mnementh Dec 24 '10 at 09:46
  • AFAIK SHA1 only has collision attacks against the inner compresion function and not the entire hash algorithm yet – Mr. E Dec 05 '16 at 18:15
0

Your passphrase generation algorithm is secure just by obscurity. If an attacker gets one or two of your passphrases he will get a pretty good subset of possible words in your passphrases and human languages can be partially recovered by context, so your passphrases will not get as much entropy as it seems

I'd suggest some way to circumvent the downsides of an offline password manager. For example, you could remember just 3/4 strong unrelated passphrases with special characters, numbers, etc. One of them for the safe, and the other ones for your email account and critic services you can't lose, also enable 2-factor authentication whenever possible on those services. Then you can upload your safe to one of those 2-factor accounts (Google drive, f.e.). Also I would suggest to append or prepend something you only know to the passwords in your safe so if an attacker gets access to it he won't be able to use your passwords without your secret

Even in case some attacker is able to access your safe cause you forgot to remove it from a certain computer you used or similar situation, he needs the secret. And in case he obtains it you can still access your critical accounts to recover the others

Mr. E
  • 1,954
  • 9
  • 18