2
$\begingroup$

This is a replication of this question on Stack Overflow. There's class Random in .NET runtime which is designed for use as a cheap fast source of pseudo-random numbers for simulation - very fast, seed can be passed in explicitly, emits easily reproducible sequences.

This class is often misused for generating passwords and similar secret stuff. Here's a question showing one possible attack on this PRNG, but it only works in a very specific scenario (when a lot of data is emitted in series) and also takes some time - up to a year on a single CPU.

Is there a clearer and faster way to show that passwords generated using data from class Random() are much weaker than typically expected?

$\endgroup$

2 Answers 2

3
$\begingroup$

There are two key things that a secure PRG should have that you probably won't have with Random in this case. A secure PRG should not allow someone with access to some of the output to learn more about any of the other output, and it should be securely seeded.

On the first point: If you're generating passwords that are supposed to be independently secure, you have to assume that the other passwords are going to be known to a malicious adversary at some point. (Perhaps the attacker is actually a user of your program and thus given these passwords directly.) If an attacker somehow learns a large number of passwords, it raises concern that he could derive (fully or partially) other passwords he should not know. I don't know much about Random's PRG in specific, but this is why an attack like one mentioned by Ilmari would be important.

On the second point: The seed space is pretty much guaranteed to be insecure. The default constructor for Random says:

"The default seed value is derived from the system clock [...] different Random objects that are created in close succession by a call to the default constructor will have identical default seed values".

This implies that the seed is determined purely based on the timestamp.

However: Any PRG seeded only by a timestamp is insecure. There is a temptation to think that it's hard for an attacker to guess exactly what time a timestamp was generated, but this is not true. If the attacker has any idea about the time frame when the timestamp seed was created, it limits the range of seeds they need to attack (because they will only need to test timestamps from the interval of time that the seed was generated from). But modern timestamps on personal computers do not have a small enough resolution to provide a total space that is large enough to resist brute-force attacks.

For example, assume you can get a timestamp accurate to one microsecond (a thousandths of a millisecond). That's better than any modern PC (that I am aware of) will provide. That provides 1,000,000 possible timestamps per second, which yields 86,400,000,000 timestamps per day, which is roughly 37 bits of total space. This is not cryptographically secure and easily brute-forcible if the attacker knows a 24-hour time frame the seed was generated. Over the course of an entire year, the timestamp space is still only about 45 bits, which also not cryptographically secure. If the attacker merely knows the year the seed was generated for the PRG, they can still brute-force it.

The numbers are more bleak with a more realistic timestamp resolution of only 1,000 timestamps per second. (Ilmari's answer suggests C# may only be as accurate as a millisecond.) That yields a timestamp space of only about 35 bits per year. (For reference, I think my old laptop can attack that in less than two weeks.)

It gets worse: The constructor for Random that takes a user argument as the seed only takes a 32-bit integer. This prevents you from possibly generating your own superior seed and using that, because you can only provide 32 bits of a seed. It also implies that the internal seed is limited to 32 bits for the default constructor case. 32 bits is not cryptographically secure, and would allow the attacker to brute-force the seed regardless of whether he knows the original time it came from.

In contrast, the secure PRG provided by C# should resist attacks using known output and should consult a good entropy source (it may be a wrapper to the same source as CryptGenRandom) for the seed.

So ignoring the cryptographic strength of the actual PRG implemented in class Random, I would say that it is insecure based on it's seeding alone. The default seed is too predictable and is not large enough.

$\endgroup$
2
$\begingroup$

The rate of 6,000,000 guesses per day you report in your SO post seems extremely low — that's only 70 per second!

Are you perhaps trying to generate a whole set of 10,000 strings for each seed? That should not be necessary; just keep generating strings until you find one that's not in the given set, which should happen in only a few iterations if you have the wrong seed. (If you only have a subset of the original strings, there are other optimizations you may be able to make, but that gets more complicated.)

You may also not need to test every possible seed; this page seems to imply that the default random seed in .NET is (int) DateTime.Now.Ticks & 0x0000FFFF. I ran a quick test on ideone.com, and it seems that at least there the DateTime.Now.Ticks value (which is defined as counting tenths of a microsecond) increments in steps of 10. Thus, if you know the time when the seed was generated to within 7 minutes or so, you only need to test every tenth seed; even if you don't, you can still at least skip all odd seed values.

All that said, it might be more efficient to attack the generator directly rather than to focus on the seeding. From what I could tell from the documentation, the .NET Random class appears to be using a subtractive lagged Fibonacci RNG; I believe there are known methods for inferring the state of such generators from a relatively small sample of their output, although I'm not particular familiar with them myself.

$\endgroup$
3
  • $\begingroup$ I don't think that page implies that the default seed is literally (int) DateTime.Now.Ticks & 0x0000FFFF. As far as I can tell, they only use that to provide an example seed. The page you linked to is for the constructor that takes an int argument as the seed, but this page is for the default constructor. All I see there is the description "The default seed value is derived from the system clock". $\endgroup$
    – B-Con
    May 5, 2012 at 18:19
  • $\begingroup$ Of course, it is entirely possible that they are using that method, but I just wanted to point out that I didn't see that stated anywhere. $\endgroup$
    – B-Con
    May 5, 2012 at 19:04
  • $\begingroup$ You're right, I should've made that cleared. I do suspect that they may indeed be using exactly that method, but they don't actually come out and say so. $\endgroup$ May 6, 2012 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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