Re: Random PIDs, etc.

Colin Plumb (
Sat, 28 Feb 1998 01:05:12 -0700 (MST)

(This message was went in reply to Chris Wedgewood and Cc'd to
various relevant places including,
which didn't work so well. Repost.)

> (2) If we are to allow random PIDs, then on a moderately busy system, PID
> re-use (within a short amount of time) is going to occur, and a highly
> loaded really busy systems its going to occur fairly often....

The problem is that PID re-use can already occur. You can even make it
occur. Just have a long-lived process that waits until the PIDs wrap and
the dies just before the fork().

Now, what you can say is that if a process is short-lived, or generates
time() concat getpid() type IDs *early in its life*, it will not suffer
re-use *with another instance of itself*. This is of use to mailers,
news systems, etc.

> Normally I would say get entropy for the /dev/random driver (intercept
> bits?, we only need a few bits every now and then and this is perhaps
> more important), but for a cleanly booted system there isn't much to go
> around... (and the Debian system where saving entropy from /dev/random
> on shutdown and restoring on power-up is horrendous IMO and should be
> discontinued. Consider what could occur by poisoning this data then
> having someone generate a PGP key or something).

The Debain technique of saving /dev/random across reboots is VERY highly
recommended. There is no "poisoning" worse than having no such file
at all. Thus, if the file is known or controlled by an attacker, it
is useless, but no worse than that. (Because of the use of a reversible
LFSR as opposed to a one-way hash in the input mixing pass of the generator,
this can be proven rigorously. It's not *just* there for speed.)

If, however, the data is good (unknown to an attacker; note that it
is overwritten immediately upon boot to helpo keep it this way),
then it makes at attacker's life completely miserable because it's
a huge pile of high-grade entropy.

/dev/random does not "trust" the saved data (it does not credit its
accumulated entropy estimate), so no harm can come from it. PGP uses
a randseed.bin file in the same way.

If people are worried, I can easily device a system that provides for
circular PID allocation *and* random PIDs.

All you do is divide the PIDs into two phases and first randomly allocate
every PID in the first phase (without repeating), then randomly allocate
from the second. Then go back to the first with a fresh and different
random order. This lets an attacker predict only one bit of the PID (e.g.
even/odd), while guaranteeing a minimum of 1/2 of the full pid wrap time.

Devising the random-order-generator will take a moderate amount of ingenuity,
but bothing too heroic.


- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to