2

We have a script to stand up a new web server at my job. The script involves creating a number of accounts to run services, app pools etc.

We needed to create a password for each of these users -- i.e. generate a 32-or-so-character ASCII string to be used as a logon password.

We had a disagreement as to whether one ought to use a cryptographically-secure PRNG for this job, or whether using a non-cryptographically secure PRNG (with a time-dependent seed) would suffice (we work in .NET, so the concrete decision was between generating strings with System.Random and using a RNGCryptoServiceProvider -- however, this is not a language-specific issue).

Must one use cryptographically-secure randomness for generating passwords, or is a sensibly-seeded plain PRNG sufficient?

Peter
  • 3,619
  • 3
  • 31
  • 37
  • How big a number of passwords would you have to generate? If you have access to a pseudo random number generator, then why *shouldn't* you use it? 32 characters is way too much to remember. You are basically asking your users to write things down. – Maarten Bodewes Aug 29 '13 at 01:16
  • @owlstead The passwords I'm talking about are for automatic services. No-one logs on with them on a day-to-day basis. They get held in a secure key store and no-one has to remember them. The question is simply regarding the specific method by which such passwords are generated. – Peter Aug 29 '13 at 01:34
  • How many passwords do you have to create? Is it really worth having the argument? – user207421 Aug 29 '13 at 02:23
  • It's really just a matter of interest, @EJP. – Peter Aug 29 '13 at 02:34
  • Curiosity is OK, as long as you use the OS random as RNG or seed for a secure random number generator afterwards :). 32 characters is fine - provided that the login procedure is secure of course. You should even be able to generate a hexadecimal string directly from bytes, 128 bits of secure random is plenty. – Maarten Bodewes Aug 29 '13 at 07:29
  • 1
    I recommend my answer to [How can I generate random 8 character, alphanumeric strings in C#?](http://stackoverflow.com/a/13416143/445517) for generating passwords. – CodesInChaos Sep 01 '13 at 11:07
  • Thanks, @CodesInChaos. We converged on a very similar solution using `RNGCryptoServiceProvider`. – Peter Sep 01 '13 at 23:15

2 Answers2

3

In many cases, an attacker can easily recover the state of a (non-cryptographic) random number generator from a few output values – without knowing anything about the seed. After that, it's trivial to predict all future and all previous random numbers.

How many outputs are required for this depends on the algorithm. In the case of a linear congruential generator, such as Java's java.util.Random, the state can be recovered from two outputs. For Mersenne Twister, used in PHP and Python among others, you need to obtain 624 outputs. I'm not familiar with .NET, but I'd think it's a similar story.

There is no complex math involved at all. See for yourself:

Conclusion: Use a cryptographically secure random number generator for anything that has to do with security.

ntoskrnl
  • 5,714
  • 2
  • 27
  • 31
  • So if I interpret the links correctly, if one generated a 128-bit password consisting of sequential integers from `java.util.Random` (turned into 8-bit ASCII characters or 4-bit hex characters or suchlike), the password space would effectively be only 64 bits (at most), because the first two 32-bit outputs would deterministically decide the remaining 64 bits. Scary. – Peter Aug 29 '13 at 09:31
  • @Peter Not to mention that if you use the same instance of Random to generate several passwords, the rest of them can be entirely predicted. Also, as Lee Daniel Crocker pointed out, the seed can be guessed too, and remember that trying 1,000,000 different seeds is fast on a computer. – ntoskrnl Aug 29 '13 at 09:39
  • @Peter In .net it's even more scary, `System.Random` only has a 31 bit seed. – CodesInChaos Sep 01 '13 at 11:08
2

Theoretically, if an attacker knows your exact algorithm for producing random passwords (say, he got his hands on your code), and he knows that you seeded your PRNG with system time, then he could reproduce the passwords generated at each instant in time to whatever resolution your system timer has, reducing his brute-force password search by orders of magnitude.

System timer has essentially zero entropy. If you seed a RNG with something like /dev/random (on Linux/ OSX) or CryptGenRandom (Windows), then the fact that the PRNG itself is not CS probably won't matter, because an attacker would have to get more than one password's worth of data to be able to crack it. But then if you're already using a CSPRNG to seed a PRNG, you might as well just use it to create the password in the first place.

Non-CS PRNGs are fast, and great for things like game simulations and Monte Carlo integration, but security passwords, nonces, keys, and such should really use secure algorithms.

That said, security, as always, is not a "yes/no" question--it's always a matter of cost/benefit. The right choices always depend on the value of what you're protecting, the cost of your efforts to protect it, your likely attackers, the cost of failure, and so on, so there's no single right choice for every situation.

Lee Daniel Crocker
  • 12,927
  • 3
  • 29
  • 55
  • I hadn't considered the scenario where an attacker could replicate all the potential passwords which a time-seeded PRNG could generate. That's a good point. I think the point I had in mind is touched upon in your second paragraph: that an attacker who has got hold of N passwords might be able to use PRNG weaknesses to guess more passwords. In the absence of either attack, then, in a hypothetical situation where I generate a single password in a one-off process, unknown to any attacker, is there any way in which passwords generated by a PRNG and a CSPRNG would differ in quality? – Peter Aug 29 '13 at 02:07
  • I suppose what I'm getting at in the above question when I say 'quality' is 'guessability' -- ease of brute-forcing. – Peter Aug 29 '13 at 04:33