4

I'm asking a practical question. I was taught computers are bad at generating random data. Does this mean password generators, such as the one built into Keepass, suck? If yes, then would it help for the user to manually enter a character or two in the generated password?

3

Humans are rather terrible at generating random data. Ask a person to give you a random number between 1 and 20 one will get a lot more 7's and 17's than other numbers as we perceive those numbers to be more "random". (Source: http://scienceblogs.com/cognitivedaily/2007/02/05/is-17-the-most-random-number/)

Computers on the other hand are deterministic and as such cannot generate true random data on their own. So pseudorandom generators are used which are slightly complex equations. Those equations need a seed which should be somewhat random. To generate this seed here are some methods:

  • High resolution of time measurement (often clock cycles) at the time of execution
  • User input, often from the mice, good implementations use the human inability to perfectly control the mice
  • External randomness generator, there are external devices that use some not deterministic chemical or physical process or some environmental parameters that fluctuate a lot to generate random data.

So to answer your questions.

Does adding a random character to a pseudo-randomly generated password improve entropy significantly?

Adding characters to a password even when not perfectly uniformly distributed increases entropy. Is it significant? This mostly depends on the length the password already had, see Anonymous Coward's comment on this answer for an explanation.

Does this mean password generators, such as the one built into Keepass, suck?

This completely depends on the way the seed gets generated. I do not know how Keepass does this but there are definitely password generators that use very good seed generation methods (sometimes combinations of methods).

would it help for the user to manually enter a character or two in the generated password?

Assuming the resulting password stays the same length then it depends from your vantage point. As I said humans are very bad randomness generators and as a result this would theoretically reduce the entropy of the password. However it does add more variables to the password generation process which if correctly implemented could increase the strength of the password against attacks directed at the pseudorandom algorithm and seed process.

Edit: reply to comment

How could a human adding 1 or 2 random characters (in a random position of the existing password) decrease entropy?

I'll assume you mean replacing 1 or 2 random characters as like I explained above, in answering the title question, just adding random (even if not uniformly distributed) characters will always increase entropy.

So let's look again at the process of generating the random data:

  1. obtain a seed
  2. use the seed as an input to the pseudorandom generator
  3. obtain output from the pseudorandom generator (and use it somewhere)
  4. use the output as the next input to the pseudorandom generator (this is most often done behind the screens of the pseudorandom generator)
  5. repeat from step 3

A rather simple process and as a computer is deterministic the only unknowns to some attacker are the seed and the number of times the process is iterated before the output is used for the specific password we are trying to breach.

If one looks at this process one could wonder why not always calculate a seed and use that as random data, in the end the seed is what makes the process random. So what is the job of the pseudorandom generator? It's function is twofold, first of it allows multiple random data to be generated from one seed. This is important as good seeds are expensive. Next and maybe more importantly it creates uniformly distributed random data. And this is very important as the seed (say when we are using some time measurement) will often have some structure.

Now when you replace 2 characters of this uniformly distributed random data with less uniformly distributed random data (remember the 7's and 17's) then you are reducing the entropy of the password. However this does not necessarily mean the password is therefor harder to break, as it creates an extra unknown to the system next to the seed en # of iterations.

However as a side-note from a theoretical standpoint one could use those 2 characters of user input to help create the seed which could increase entropy in the system, depending on the previous seed method and what else is used to create the seed.

  • I really think you're over simplyfing things with humans being bad at generating randomness.Computers are bad at generating randomness too. How could a human adding 1 or 2 random characters (in a random position of the existing password) decrease entropy? This is assuming the human doesn't read the existing password, so it wouldn't be as if they see the letters ab and add a c to make abc. – Celeritas Sep 24 '15 at 20:32
  • @Celeritas I did try to keep it simple as the question was formulated somewhat simple (no offense intended). I'll extend my answer to provide more information. – Selenog Sep 25 '15 at 5:58
  • 2
    Long password benefits a lot MORE from the added character than a short one. In first approximation, a password of length n get k^n more entropy by adding a character (k being the size of the character set). It's exponential. Intuitively, a password of length 4 is no better than a password of length 3, while a password of length 16 is way better than a password of length 15. – Anonymous Coward Sep 25 '15 at 7:41
  • @AnonymousCoward You are of course correct, not sure where my mind was writing that part. I edited my answer and thank you for the correction. – Selenog Sep 25 '15 at 9:54
2

Your question seems to assume that the fact that password are only pseudo-randomly generated is bad. However, it actually does not matter that much, all that matters is that your password should be unpredictable, and this is not the same thing.

A true random value is a random value which just pops-up from "nowhere", or to better phrase it a value which will be generated in a non-deterministic way. True random number generator (TRNG) require specific hardware which will usually rely on a more or less large set of physical or electrical phenomenon combined to produce a smaller set of values which will be deemed as random. This value will not be the result of any algorithm of some sort.

At the opposite, a pseudo-random number generator (PRNG) will be a well-defined and tested algorithm which, given a initial internal state, will produce a defined value and switch to a next defined given state. All this need to be very well defined since it this which will permit scientists to analyze the algorithm and determine its cryptographic value.

As in a lot of other modern cryptographic areas, the secret is not in the algorithm, but here the secret lies in this given initial state. The number of different possible states at a given time may be more or less large: this will be what one calls entropy. The largest the number of possible states, the larger is the entropy.

With a large enough entropy, an attacker will have no way to determine the PRNG current state, and therefore he will not be able to determine the next value which will be generated. This is what is called unpredictability. As you can see, this is different than randomness since the resulting value will be the result of a well-known and controlled process where there is no room for fate.

This is precisely what you need for your passwords and other secret: it must be unpredictable. As you stated, without any specific TRNG hardware, a computer is not able to generate a random password. However as Selenog explains it in his also good answer the fact is that human brain is actually not better as it. But, when it comes to generate an unpredictable value, equipped with a proper PRNG and a proper entropy the computer will definitively beat human brain.

As per the specific case of KeePass, I did not checked its implementation personally. However, according to its documentation it doesn't seem to try to reinvent the wheel but instead rely on proven algorithms and OS provided PRNG sources. Moreover, this product being both open source and widely used, it most certainly goes through a lot of scrutiny. So I would certainly no affirm that "KeePass passwords sucks".

As explained in Anonymous Coward comment, if you generate an already safe password with KeePass, adding a few extra characters to it will never do any harm. So if you feel safer in doing so as an attempt to circumvent any yet unpublished KeePass passwords generation issue, the go for it (note that KeePass even offers an alternative as letting you provide mouse/keyboard input to increase his internal PRNG entropy during the password generation process). However, this must not lead you to configure KeePass into generating shorter passwords "because I will complete it myself" or replace some generated characters: what you would achieve here would be to replace computer generated unpredictable characters by human generated more predictable characters, and it would be of no good for your password security.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.