LWN: Comments on "OpenBSD routes around POSIX"

OpenBSD routes around POSIX

raven667 — Mon, 22 Dec 2014 16:33:41 +0000

I'm pretty sure that any PRNG given the same inputs will produce the same outputs and that is randomness that is suitable for crypto purposes. The randomness is introduced by seeding with something unpredictable and not knowing how far into the stream you have read not that the values produced will be unpredictable if you know the seed and how many bytes have been read.

OpenBSD routes around POSIX

mirabilos — Mon, 22 Dec 2014 15:51:11 +0000

If you want something that can be replayed, it’s not “random”. You list valid use cases, but I question that they can be use cases for an RNG. Sure, do it, but please don’t call it RNG, not even PRNG. Implementing an LFSR, LCG, etc. is dead easy.

Besides, POSIX doesn’t guarantee reproducibility between exec() anyway…

Per-process choosing could be problematic

cesarb — Fri, 12 Dec 2014 12:57:25 +0000

> So what happens when some library calls srand_deterministic() and changes the behaviour for the rest of the program? Or when the main program calls srand_deterministic() and thus affects any libraries it calls?

If your program or library uses the rand()/random()/etc family of calls, it's supposed to be able to work fine with a deterministic RNG (after all, that's what you get in non-OpenBSD systems).

The non-deterministic RNG for rand()/random()/etc is a bonus, like ASLR: if your program's security depends on it, you're doing something wrong.

Per-process choosing could be problematic

epa — Fri, 12 Dec 2014 12:38:29 +0000

So what happens when some library calls srand_deterministic() and changes the behaviour for the rest of the program? Or when the main program calls srand_deterministic() and thus affects any libraries it calls?

I want to be able to choose a seed so that I can repeat the same pseudo-random test case I did last time, but that doesn't mean I want any https: requests made by my test code to silently start using a weaker RNG. Partly this can be solved by having an explicit API for stronger random numbers: arc4random() will always be strong, no matter what srand() type things have gone on in the background. But it would also be good to have an explicit API for pseudo-random number generation, ideally with the new seed value returned each time so it can be passed along by the caller.

OpenBSD routes around POSIX

marcH — Thu, 11 Dec 2014 18:01:34 +0000

Every time anyone says or writes "Everyone just do this!", a kitten dies. Or worse.

This is why OpenBSD strives to be "secure by default" in all possible ways. Seems reasonably successful so far.

OpenBSD routes around POSIX

alankila — Thu, 11 Dec 2014 17:46:07 +0000

Since you mention MT, I thought I'll add a bit here. My new geek hero, Melissa O'Neill, recently invented a new family of random number generators called PCG, where P stands for permuted. It's basically linear congruential generator combined to an output improving step, usually some variant of xor and shifting, but the consequence is a generator whose performance is near theoretical optimum, as it seems to pass statistical tests using fewest possible bits of state, e.g. mere 32 bits suffice to pass the SmallCrush test suite.

OpenBSD routes around POSIX

itvirta — Thu, 11 Dec 2014 17:40:48 +0000

Yes.

But it's hard to know if a given use of rand() is security-sensitive or not.
It seems the argument here is that this is an easy solution to a certain class of
possible problems. Certainly easier than actually going through all the uses and,
educating the coders and replacing the calls with something more suitable.
Supposedly computers are fast enough to use a better rng, too.

OpenBSD routes around POSIX

lambda — Thu, 11 Dec 2014 15:52:11 +0000

3) Emit a warning whenever an application makes a call to time() and subsequently makes a call to seed the RNG with the same value.

Ted Unangst wrote a good blog post on all of the broken, bizarre ways that people seed random number generators in programs. Theo de Raadt also listed all of the arbitrary constant values people use as seeds. It goes way beyond just seeding it with time().

The sheer amount of dubious use of constant and other arbitrary seed values, coupled with the relatively low number of packages that actually depend on deterministic behavior, is part of the justification they used for doing the breaking change. Now, such a breaking change really wouldn't work well in the Linux world, but if you want to root this out, you're going to need to do better than just looking for the output of time().

OpenBSD routes around POSIX

mpr22 — Thu, 11 Dec 2014 14:14:26 +0000

Anyone who uses rand() for anything remotely security sensitive is sufficiently clueless about security (and C programming) that trying to remove the "sharp implements" from their environment is a lost cause.

OpenBSD routes around POSIX

marcH — Thu, 11 Dec 2014 09:57:03 +0000

> "If rand() is called before any calls to srand() are made, the same sequence shall be generated as when srand() is first called with a seed value of 1."

I imagine that the number of packages rely on this (not terribly useful...) property is even smaller than the number of OpenBSD that Theo wants to "break".

Breaking backward compatibility is bad. Preserving "insecure by default" behaviours is worse?

OpenBSD routes around POSIX

butlerm — Thu, 11 Dec 2014 07:29:23 +0000

Generating non-deterministic output if no seed is set is a violation of the POSIX and ISO C standards, unfortunately, which state:

"If rand() is called before any calls to srand() are made, the same sequence shall be generated as when srand() is first called with a seed value of 1."
http://pubs.opengroup.org/onlinepubs/9699919799/functions...

Emitting a warning could be problematic too, unless it were done during compilation instead of at runtime of course.

OpenBSD routes around POSIX

rsidd — Thu, 11 Dec 2014 05:44:01 +0000

Most people who do scientific simulations don't use the OS RNG functions -- they use, eg, the GSL versions (which support specifying a seed and replaying) or something else. Mainly, the OS-supplied versions are unreliable -- even if the OpenBSD version is excellent, the program needs to be portable.

OpenBSD routes around POSIX

jzbiciak — Thu, 11 Dec 2014 04:38:40 +0000

I actually use a deterministic random number generator in many of my programs, exactly for the purpose of reproducibility. But, I'm writing programs such as "random test generators" where a given input plus a given seed should produce the same test every time.

I also therefore use a dedicated random number class. (C++11 makes this very easy and very nice.) In fact, I use what I call "forked" random number generators, where a master generator (seeded by the test case seed) seeds child generators that I then hand to various subsystems. (Those children can be forked further for sub-subsystems, etc.)

The behavior of the whole tree depends on the original seed, but a tweak in behavior in one subsystem doesn't disturb the stream of pseudo-random numbers in another subsystem. This makes debugging and testing go much more smoothly.

All this to say: If you're writing simulation software that relies on the quality of the random numbers, reproducibility, and portability across multiple platforms, you likely abandoned the standard library rand()/random()/xrand48() a long time ago. You probably grabbed a copy of Mersenne Twister or any number of other, better generators and wrote your own wrappers around these things. I know I did eons ago. (And now with C++11's excellent random number library, I'm doing it with much less pain.)

I guess a part of me is a little surprised that 8800 packages showed up using rand() and friends. Then again, how many of them are actually negatively affected by bad random numbers?

OpenBSD routes around POSIX

mathstuf — Thu, 11 Dec 2014 03:45:55 +0000

I think that de Raadt probably sees the problem as serious enough to warrant the change. There are functions such as srand_deterministic and rand_deterministic already. But these have always been platform-specific anyways (so expecting Windows to give the same stream as Linux (or even glibc and musl) was already a lost cause for replays and such). de Raadt was also nice enough to come up with a list of projects which seem to actually expect the "deterministic" API, but that is of course limited to the OpenBSD ports selection.

OpenBSD routes around POSIX

josh — Thu, 11 Dec 2014 02:28:52 +0000

It seems like glibc could safely use a similar but slightly more conservative approach. rand() and family are deterministic but system-specific; the same seed value is *not* guaranteed to produce the same result on other systems, or even on a different version of the same system. So:

1) For applications that never seed the RNG, automatically use a cryptographically secure RNG.

2) For applications that do seed the RNG, use the result to seed a deterministic but otherwise secure PRNG (*not* a simple linear congruential generator).

3) Emit a warning whenever an application makes a call to time() and subsequently makes a call to seed the RNG with the same value.

OpenBSD routes around POSIX

JoeBuck — Thu, 11 Dec 2014 02:02:29 +0000

For uses of random numbers that are unrelated to cryptography, the ability to replay the sequence is an important feature. This is particularly true for simulation: if a bug is found from random simulation, fuzzing, or the like, you want to be able to find it again. If the seed is recorded the interesting traces can be replayed, and seeds can be produced using truly random processes to sample more of the simulation space.

Seems to me that it would be better to use a new API for applications that need truly random numbers rather than breaking portability on the old one.