math/rand: Deterministic random by default is dangerous

[shazow]

Go's standard library is generally considered to have great security-focused defaults (like net/http validating certificates out of the box). In many cases, the default behaviour goes out of the way to prevent the programmer from employing bad practices (such as relying on map key ordering). I believe that the default behavior of math/rand can be improved to better represent these ideals.

There have already been incidents where people didn't realize that math/rand was deterministic by default (example), and even in security-related applications (example). Additionally, tutorials tend to forego mentioning this potentially-catastrophic default (example).

I want to acknowledge that the stdlib documentation mentions this behavior in the second paragraph.

Random numbers are generated by a Source. Top-level functions, such as Float64 and Int, use a default shared Source that produces a deterministic sequence of values each time a program is run. Use the Seed function to initialize the default Source if different behavior is required for each run.

Unfortunately, merely documenting dangerous default behaviour has not proven to be sufficient. Also worth pointing out that the math/rand docs don't mention crypto/rand (this should be fixed too).

To resolve this, I propose that the top-level math/rand functions be seeded by crypto/rand's Reader by default.

Context: PHP's mt_rand was recently torn down for generating only odd numbers when the max value given was too big (a reasonably easy mistake to make; HN thread). Some Twitter discussions started by @richo pointed out that default-deterministic random is a similarly easy mistake to make.

[ALTree]

To resolve this, I propose that the top-level math/rand functions be seeded by crypto/rand's Reader by default.

Would a change in the "random" sequence generated by math/rand functions be a break to the compatibility contract?

See discussion on #8013 and #8731. The community should probably decide about this once and for all.

[cespare]

If math/rand is being used for security-related code then that's already very dangerous, regardless of how the prng is seeded.

[richo]

So to clear a few things up, I was actually frustrated before the mt_rand debacle took hold, although it was illustrative of some of the problems here.

The underlying issue is multi part in my opinion, although some of it is easier solved. In my (humble) opinion having an RNG that isn't a CSPRNG is dangerous in and of itself. Much of Go's philosophy hinges on the fact that people cut corners and don't read docs, and so I tend to think that having a rand that isn't safe for crypto is unsavoury.

On the specific topic of math/rand, I think inheriting rand(3)s API is extremely regrettable. While there are cases for deterministic RNG's, they're almost certainly in the minority (eg, deterministic tests?) and supporting them first seems like a mistake. Especially when the rationale appears to be that "Noone would ever manage to ship software without noticing that the numbers are always the same", the threads that Andrey linked above demonstrate that isn't the case.

Finally, and getting a little offtopic, but while we're talking about Go's RNG's and user safety, having crypto/rand accept a plain old io.Reader seems like a footgun to me. It means that things like http://play.golang.org/p/4NDDz8FSDq work. Worse, it means that http://play.golang.org/p/0e9_Oke1xF works and kills the CSPRNG for anyone consuming your code.

That's the "why", onto the "how". I would propose one of two things:

• rename math/rand to math/deterministic_rand. This has the advantage of forcing a user to comprehend what they're getting themselves into. I rather doubt that the core team is willing to rename a module at this late stage of the game so;
• Seed math/rand with crypto/rands reader, as proposed by @shazow above.

Cheers

richo

[bnagy]

Much of Go's philosophy hinges on the fact that people cut corners and don't read docs

Settle down. If anything, the Go "philosophy" is the opposite.

I think that seeding math/rand from crypto/rand will make the problem even worse, because then one could make an (ill-advised) argument for its security.

I feel like providing NO options for a non-CSPRNG in a stdlib is a little opinionated, even for Go.

I doubt it would be palatable, but I would quite like to see an insecure package, in the same vein as subtle - in other words, you need a very good excuse to use it. We could hide all kinds of skeletons in this closet - RC4, MD5, DES ... and the PRNG. It would be difficult for anyone to mistakenly use insecure/rand for, eg, a password generator.

[cespare]

having an RNG that isn't a CSPRNG is dangerous in and of itself. Much of Go's philosophy hinges on the fact that people cut corners and don't read docs, and so I tend to think that having a rand that isn't safe for crypto is unsavoury.

I doubt people that don't read the docs enough to notice the difference between math/rand and crypto/rand would otherwise then be able to use crypto/rand to implement crypto primitives securely.

Can you point at other popular language standard libraries whose only PRNG is a CSPRNG? There are plenty of use cases for fast, non-crypto PRNGs. (The math/rand PRNG isn't particularly fast, but that's a separate issue.)

rename math/rand to math/deterministic_rand

Will not happen due to Go's compatibility promise

Seed math/rand with crypto/rands reader

That might lead people to think that math/rand has security properties that it doesn't.

[richo]

Re Go's philosophy- we can have it out on IRC if you like. Tl;dr I think this philosophy is actively positive because it turns out people are fallible and computers are better at diligently checking things.

I would be onboard with an insecure, although I suspect that the chances of upstreaming it are pretty slim for the compatibility reasons above.

I mostly don't buy the argument that people can't implement safe crypto primitives. It seems like conflating the concerns here. A password generator a perfect of an example that can be implemented safely by nearly anyone, but impossible to be implemented safely on top of a deterministically seeded RNG.

I also get the impression from nearly everything about Go's stdlib that it's optimised for the 90% case, with the suggestion that if you're in the 10% outliers you might need to dig a bit more to do what you want (Or reconsider whether what you're trying to do is actually correct). That seems to me like given the state of entropy pools on modern systems, backing onto a CSPRG should be safe, and in the event that you do manage to exhaust the pool, or that your program because untenably slow you can seek out alternative solutions.

It seems to me that cases where you can't use system RNG, or have specific needs about it's entropy would always fall into the 10% case.

[ianlancetaylor]

The question of whether math/rand should keep the same sequence of values it has had in the past is a question to raise on the golang-dev mailing list.

The Go 1 compatibility promise means that we can't rename or significantly change the math/rand package. We could add more documentation to it.

[rogpeppe]

FWIW I am +1 on randomly seeding math/rand at init time (probably just from the current time). Because it's global, unless you're writing a trivial program, repeatability isn't something you should be relying on anyway because any other package is free to get a random number at any time, disrupting your sequence. If you need a deterministic RNG, you can always make your own(which is faster too).

[cespare]

@rogpeppe that sounds like an improvement to me too, but can the math/rand API be changed like that at this point? Consider this language in the docs:

Top-level functions, such as Float64 and Int, use a default shared Source that produces a deterministic sequence of values each time a program is run. Use the Seed function to initialize the default Source if different behavior is required for each run.

Given the discussion in #8013, the emerging consensus seemed to be that it would be okay to change the deterministic sequence to a different deterministic sequence if necessary (it ended up not being necessary), but any more than that, such as random seeding, seems well outside the compatibility promise.

[shazow]

Another reference is #11372, for randomizing the scheduler to prevent people from depending on the current order that goroutines happen to run by default. This is in anticipation of future scheduler changes affecting the natural order of goroutines.

In general, it seems like a good idea to randomize things by default to prevent people from becoming dependent on implementation-specific values, whether intentionally or unintentionally.

[rogpeppe]

@cespare You are probably right. Much as I think the current behaviour is not that useful, there probably are programs out there that rely on the deterministic behaviour, generating random numbers from only a single known thread of control. That's a pity because that's exactly the case where a newly made Source is appropriate.

[colinnewell]

While I agree with the principle of making sure that people use a secure random when it's appropriate, secure random isn't the only random that is necessary. Simply replacing math/random with a secure random is likely to break existing promises about number distributions.

Adding the reference to the crypto/rand in the documentation would definitely be a good idea.

If you make common tasks like random password/token/key generation really easy via the crypto/rand library then you are likely to encourage a lot more people down the secure path. This may well be in a separate library, but so long as it's really really easy to use and google, it should help guide people onto the correct path.

[shazow]

Seems there is agreement that, at minimum, we need to improve the rand/math docs to urge the consideration of the crypto/rand package for security-sensitive work. I opened a CL here: https://go-review.googlesource.com/#/c/12900/, phrasing suggestions are welcome.

[gopherbot]

CL https://golang.org/cl/12900 mentions this issue.

[FiloSottile]

My 2 cents: things like randomizing map orders are meant to discourage developers from relying on unreliable things. It's not random > deterministic, it's "clearly unreliable" > "apparently reliable".

Here what's unreliable is security, not determinism. You CAN'T use math/rand for security sensitive operations, however it's seeded. So IMHO the "clearly unreliable" option is for it to be deterministic. If it yielded different numbers every time, more developers would be fooled into thinking it's safe to use ("apparently reliable").

So if it's deterministic it's clearer that it's unsafe, and that's good, let's leave it like that.

What I think would be useful and not barred by the compatibility promise is adding friendly APIs to crypto/rand, so that when I have to securely pick a number from a range, for example, I'm not tempted to use math/rand. I'll go as far as saying that crypto/rand should support all math/rand APIs, also because some of them are damn hard to get right on top of a []byte (see: modulus bias).

[rsc]

If there is concern about people incorrectly using math/rand in security settings, it seems like it would be better to have the same seed every time than to give the appearance of unpredictability. That is, it is better without any attempt at time-dependent or otherwise unpredictable automatic seeding.

[shazow]

I think the argument is that it has been proven that appearance of predictability is not effective. For examples, search Github code with keywords like "math/rand" and "password", "key", or "token".

In terms of best-to-worst, what a person could do in a security/cryptographic context:

1. Use crypto/rand. (Best by a big margin since it has an ongoing source of entropy unlike math/rand)
2. Use math/rand but seed it with crypto/rand—unlikely anyone would do this because if they think to use crypto/rand then they probably wouldn't be using math/rand in this context to begin with.
3. Use math/rand but seed it once with the current time—this bad because if you can guess when the app was launched (or force a restart), you can significantly reduce the brute forcing space. Anecdotally, most examples using math/rand where they should be using crypto/rand are doing this.
4. Use math/rand but seed it with the current time every time a random number is needed—this is bad because you often have control of when the request is made so you can force a limit on the brute forcing space. Anecdotally, a moderate number of examples that were written without reference are doing this.
5. Use math/rand without seeding it at all. Not extremely common but I found at least half a dozen examples on Github with some casual searching.

Please correct me if my ordering of these scenarios is wrong.

What kind of information would help us make an informed decision here? Would a big dump of brutally-vulnerable codebases be helpful? Would a comparative analysis of what other languages are doing regarding seeding be helpful?

I understand that renaming the package is not a viable solution for Go 1.x. Changing the default output of math/rand seems more of a blurry line regarding compatibility but I respect if this proposal is deemed too incompatible regardless of benefits.

[bradfitz]

Don't forget option 6) file bugs against broken code identified in searches. We could also 7) write new vet checks.

[ALTree]

@shazow Here's my ordered list

1. Use crypto/rand -> GOOD
2. everything else -> equally BAD

You argue that using a randomly seeded math/rand is somehow better than using a deterministic rand/math. I don't agree. Either your application is cryptographically secure, or is not. There's no "more secure than" among applications that use math/rand for cryptography.

[FiloSottile]

Exactly. You get owned, or you don't. Only way not to get owned: crypto/rand.

So the question is, what makes less devs pick the "you get owned" door?

1. make it clearer that math/rand is unsafe by leaving it unseeded, as @rsc and I are suggesting
2. make the docs really scary, even more than 7cabade
3. go vet checks sound awesome as they would also help against goimports mistakes, but how would they recognize non-security sensitive cases? Are we just ok with 100% false positives?
4. make crypto/rand easier to use -> add math/rand style APIs

@shazow Even if 1. is not much effective, those that don't pick crypto/rand are 100% doomed, so anything that makes more devs pick crypto/rand is worth it, even if it makes math/rand "more doomed" (which it can't be).

[cespare]

@FiloSottile I'm not sure that

(4) make crypto/rand easier to use -> add math/rand style APIs

is a good idea because the sorts of APIs that are in math/rand but not crypto/rand aren't that useful in crypto settings. It might only give a false sense of security.

[FiloSottile]

@cespare Well, the case at hand, password generation needs a Intn() API which is hard to get (right) from a []byte.

Can you elaborate on the false sense of security? I mean, crypto/rand APIs might be not much useful, but how would they not be secure?

[colinnewell]

With regard to the API's what would make sense for security and be easily searchable? Generating security tokens and passwords are the things that spring to my mind. If there was an obvious call to make to generate something like that, and it allowed you to specify all the bells and whistles you wanted like length and format, there would be no good reason not to use it.

In python they have SystemRandom which provides exactly the same API as the regular random, and that's great when you're fixing code that has used the wrong random, but I have to agree that I'm not sure whether giving it the exact same API is the best idea.

[adg]

On 31 July 2015 at 03:59, Filippo Valsorda notifications@github.com wrote:

make the docs really scary, even more than 7cabade
7cabade

Something like:

"Package rand implements pseudo-random number generators. It is not
suitable for security-sensitive programs."

?

go vet checks sound awesome as they would also help against goimports

mistakes, but how would they recognize non-security sensitive cases? Are we
just ok with 100% false positives?

It seems unlikely that there should be goimports mistakes, because the APIs
are disjoint.

[FiloSottile]

I think a practical message might reach more developers. Like

"Package rand outputs might be easily predictable however it's seeded. It is never suitable for security-sensitive applications, see crypto/rand instead."

It seems unlikely that there should be goimports mistakes, because the APIs are disjoint.

Oh, my bad.

[colinnewell]

That documentation suggestion hits the nail on the head @FiloSottile. It's clear and concise.

[robpike]

Fixed by https://go-review.googlesource.com/12900