4

I have written a short password generator which uses a mixture of words from a dictionary and randomly generated passwords, and I'm wondering if I did the entropy calculations correctly. Usually I use my generator to generate passwords that are easy to enter in situations where I can't copy+paste from a password manager, so the passwords generated tend to be made up of several words plus a short randomly generated password, e.g. lDX`htS!splenectomyfrenate.

To avoid bias, I tend to generate them such that the process has a known entropy, so the above password was generated using the rule "Give me a password with at least 80 bits of entropy, using an 8-character random password plus randomly selected words to make up the difference".

My question is, using a strategy like this, do I have to take into account the degeneracy that comes from the fact that you might be able to generate the same password via two paths? E.g. If my dictionary consisted only of: "sparks", "spark", "steam", "team", then if you generate a 2-word password by just concatenating words from the dictionary, sparksteam is going to be over-represented in the output, because it can be made from "spark" and "steam" or from "sparks" and "team".

I'm thinking this is likely to be just a very small reduction in the actual entropy of the passwords, with a sufficiently large word list, but is there a well-known way to account for this sort of degeneracy without actually enumerating all possible combinations and looking for collisions? Am I off-base in even thinking that you'd need to?

Improve this question
3
  • Truth is you need to calculate entropy relative to how often specific words appear in real-world password datasets. "Password entropy" as it is often understood (the number of bits it takes to store all passwords written with the same alphabet as your password) is simply not an appropriate metric. Roughly, make sure to eliminate commonly found words from your generator, and avoid passwords that have very frequent patterns (e.g. starting with Upper, series of Lower and then Digit or Symbol at the end).
    – Steve Dodier-Lazaro
    Commented Oct 19, 2015 at 14:26
  • @SteveDL I think that password entropy (i.e. actual characterization of the process) is still the best method for characterizing the strength of the generator, because that characterizes their best strategy against me in the average case, even if I can do even better than that by adjusting my strategy to counter common password cracking strategies.
    – Paul
    Commented Oct 19, 2015 at 14:37
  • 2
    You could always add a word separator. It wouldn't significantly change the password complexity, particularly if the method of generation is known, but it would remove these types of "collisions" between words. spark.steam is certainly different from sparks.team.
    – user
    Commented Oct 19, 2015 at 15:35

1 Answer 1

Reset to default
1

There are many ways to calculate entropy in this situation and not all of them are in your favor. Depending upon your commitment to true entropic randomness and your level of paranoia, I think word concatenation is the least of your problems. For purposes of analysis, I'm going to assume the password example you gave above is standard for all types of passwords you create (8 complex password characters + N words containing 18 total characters -- or 26 total characters).

Method 1

Assume every character in your resulting password contributes entropy to the result. Furthermore, every character may be within the range [33..126] or 94 possibilities. In this analysis, total range of passwords is 94^26 or 2*10^51. That sounds really big, and it is. However, I'm not sure that's your password range. We could stop here if we believed that an attacker could only guess from the complete range. You already know dictionary attacks are possible. Let's look at the next method.

Method 2

Really, only the first 8 characters are in the complete range, the remainder (if I can guess your word component) is only lowercase, so 26 characters. This gives us a lower upper limit on your range of passwords: 94^8 * 26^18 = 1.8*10^41. That's still pretty big, but we're not done, yet.

Method 3

Let's look more closely at your password structure. The first section is the only one that can have the full 94 characters, so for that we have 94^8 or about 10^16. For the second section, should we count the letters as part of the range of your passwords? I suggest they don't count, and instead we should use the total word range from which you choose and the number of words. Why? Think of the words as unique symbols rather than the characters. Your second section will never have the sequence "xxyqrzt" because there's no word that looks like that. Really, your second section follows a specific structure and that structure is determined by your dictionary. I'm going to assume 100,000 words in the dictionary, although you might only have 10,000 and that they are all lowercase. Now, the second section range is (10^5)^3 - I'm assuming three words to get to 18 characters. Our new upper bound for the password range has dropped to 10^31. Still, pretty big. We're done, yet.

Method 4

OK, so this one requires us to go a bit deeper on entropy calculations across the range of passwords and then do the proper entropy calculation for your situation.

First off, password range and entropy are not the same thing, although they are related. To get the entropy of a password (or any information), we need to take the log of it's possible range. We should use base 2 for our log because it's easier and computers use it, too. In this case, we have the following entropy calculations for each of the above methods of analysis.

  • Log_2(2.0*10^51) = 2^170 or 170 bits
  • Log_2(1.8*10^41) = 2^137 or 137 bits
  • Log_2(1.0*10^31) = 2^103 or 103 bits

It's easier to think of entropy in terms of bits.

Here's the thing. You've now published your password generation algorithm. Also, security through obscurity is not really security, so theoretically or practically, someone could discover your algorithm. In that case, the only real security for your system, the only real entropy introduced is the seed for your random number generator. If you're not using a secure RNG or a securely seeded PRNG, you've already skewed your password distribution.

What this means is that to get the full effect of your password entropy, you need to introduce at least 103 bits of true random seeding to your random number generator to select from the complete range of passwords available from Method 3.

I suspect you aren't doing this (or, at least haven't, up until you read this). So, if the RNG you use seeds itself with current time or process ID or MAC address or IP address, you might have a lot less entropy than you realize. The entire MAC address, IP address and time don't count because most of the bits therein aren't really random, they can in fact be known. Think about it. The difference between now and a few seconds from now is only a few bits of data. If I can guess when you generated the password, it might be NO bits of data. You might only have a handful of bits, perhaps no more than one dozen.

That would be a range of passwords of about 2^12 or 4000. More passwords than you'll ever need, however, you'd never know the range was so small because the passwords look so big. You can't generate more entropy from less entropy in this situation. If you don't believe me, test it yourself by running numbers from the range [1...4000] through SHA1. The results look really random. However, that's it for your hashes - 4000 only. None of the other potential SHA1 hashes are available to you because you're limited to inputs between 1 and 4000 inclusive. In this case, the entropy of the range is still 12 bits even though it looks really large. Looks can be deceiving, especially to humans.

So, forget all of your fancy analysis and multi-word fears. Instead, figure out how to get true randomness into your RNG seed. Go look up the body of research on proper RNG seeding. It's fascinating and it's really, really hard to do!

Improve this answer
6
  • The point is not to have a hard-to-guess algorithm. The question is about what the actual entropy of the algorithm is (since this is the worst-case scenario attacker). The question of the implementation is separate from this, though in the actual implementation, all random numbers are pulled from python's random.SystemRandom(), which is suitable for cryptographic randomness.
    – Paul
    Commented Nov 7, 2015 at 6:32
  • I'm not sure you can separate implementation from the analysis, but if your implementation and algorithm follows the above examples, then I imagine you can use that as a guideline. If Python's RNG can get you 100 bits of entropy, then that'll match the Method 3 analysis, which I think is a good model for you.
    – Andrew Philips
    Commented Nov 7, 2015 at 17:55
  • Now, for your original question: double words substituted for double words. What's the ratio of these to over all dictionary? I'm guessing a MAX of P(Alt 2 Words | 2 Words) = .01%. Modify #3 by Log_2(1/1000) or -13 bits. So, 103-13 or 90 bits of entropy. You could generate 10^7 word pairs and test the frequency of any alternate word pairs. Substitute that sampled probability in the equation (103-Log_2(Probability)) to get a sample adjusted estimate. I bet P(sample) < .0001. You could also check for single words made up from double words (book, keeper).
    – Andrew Philips
    Commented Nov 7, 2015 at 18:00
  • It's more complicated than that (doubled words), really, because think of the word axhead, which can be 'ax' + 'head' or 'ax' + 'he' + 'ad'. The computational complexity of enumerating these is the main reason that it's difficult to estimate the loss of entropy. I was hoping for some sort of formalism to at least put an upper or lower limit on these sorts of things.
    – Paul
    Commented Nov 7, 2015 at 20:19
  • It depends upon the data, the frequency of the various combinations and how creative you are in discovery the variations. You could code up an algorithm that exhaustively looked for every possible combo. The formal method to do this would be list all the methods and cover the combinatorics or permutations, whichever was appropriate (M choose N or M!/N!). You could make a reasonable guess, which is what I did above (see Fermi estimation). Finally, you could sample the data. I suggest you sample your data - that would be a really fun pgm to write and make fast.
    – Andrew Philips
    Commented Nov 7, 2015 at 20:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .