[PATCH v3] Seed random generator in main()

Green, Paul Paul.Green at stratus.com
Tue Jun 16 09:58:50 MDT 2015


Volker wrote:

> On Mon, Jun 15, 2015 at 12:34:06PM +0100, Robin McCorkell wrote:
> > Remove srandom() from DFS shuffling, only seed once during process init.
> > Improves performance and gives better shuffling.
> > 
> > Use of random() replaced with sys_random() in places to improve
> > protection against renamed libc functions
>
> Just to give you a quick ack: Randomness is not an easy
> topic to review unfortunately. There's just two kinds of
> randomness we require: Cryptographically good for nonces and
> passwords and just "junk" randomness for everything else.
> For the "junk" randomness it's important for testability
> that it's seedable, I'm not sure about that requirement for
> the crypto randomness.

I'll second Volker's remarks, and add my own.

I've had some experience implementing seeding code for pseudo-random number generators (PRNGs). I've also read up on the subject using Bruce Schneier's excellent books, and I closely follow published reports about practical ways to defeat encryption algorithms by, among other techniques, attacking the PRNGs.

To continue with Volker's categorization, all you need from junk randomness is variability over a domain, so that timing-dependent and data-dependent code paths are tested. Predictability is not a concern. Here, I claim that almost any PNRG will do, even an antique linear congruential PRNG. This type of PRNG is so fast that re-seeding it is nearly free, and not worth optimizing. I've used this code-testing technique a number of times in my career, found it effective, and can recommend it. 

However, what you need for cryptographic-strength randomness is utter unpredictability in addition to variability over a domain. This is a far more difficult requirement, because there are few truly random events inside a computer, and many of the events used to seed a PRNG can be deliberately influenced by malware, or accidentally influenced by insufficient attention to detail on the part of the programmer. Just as one example, it is not a good idea to generate encryption keys shortly after an operating system has booted-up, because the randomness of the output of software-based PRNGs is poor until the OS has had some time to run. This is especially true for appliances with embedded software or firmware, which can be reset simply by cycling the power. Please read the section titled "Importance of strong random number generation" in https://en.wikipedia.org/wiki/RSA_(cryptosystem). 

Then, there is the question of provenance. Who should we trust when changes are proposed to the implementation of randomness in an open-source project? What sort of proof or self-tests should the author be required to submit to prove that his stated benefit is actually true? I'm no longer on the Samba Team, but if I was, I'd be demanding that authors submit proof that their changes have the intended benefits. Otherwise, how do we know that your motives are genuine? Sorry to be blunt, but let's assume for the moment that your intentions are to weaken Samba's implementation of randomness. Let's further postulate that you have found a way to influence or narrow the seeding of the random() function, or perhaps predict it altogether with a high degree of accuracy. In this case, it would be to your advantage to seed the PRNG only once, because you would have a *much* easier time of defeating the purpose of using PRNGs in the first place.

Finally, there is the question of the appropriate PRNG to use. Samba tends to adhere to the functions which are available in the POSIX standard, and POSIX-2013 (per www.opengroup.org) only provides rand() and random(). The former is clearly inadequate, as no specific minimum range is required. The latter requires a range of 0 to 2**31-1 with a period of 2**69 or better. In my opinion, the problem here is not the period; it is the range. In some applications, it is perfectly feasible, with modern hardware and modern attack techniques, to simply try all 2**31-1 cases and see whether any of them match the observed effect. In other words, 2 billion is no longer a very big number, and with such a limited range, an attacker can simply try all possibilities. So, in my view, the POSIX PRNGs aren't an adequate solution for cryptographic-strength PRNGs.

If you read OpenSSL ticket #2563 ( http://rt.openssl.org/Ticket/Display.html?id=2563 ), you can find an implementation of a hardware-independent PRNG seeding function for OpenSSL, which I wrote, that uses the low-order bits of a high-accuracy real-time clock to create an unpredictable value of an arbitrary length. I also provided the programs that I wrote to calculate and test the mathematical properties of the series of values produced by this function. All in all, it took me several weeks of research, coding, and testing to create this code, and I put it into the public domain so that anyone else could check my work.

I hope that this rather long-winded post sheds some light on the complexity of the situation.

Thanks
PG





More information about the samba-technical mailing list