Re: random PID generation

Re: random PID generation

[Heusden, Folkert van]

>> I wrote a patch against 2.2.18 and 2.4.1 to have the kernel generate 
>> random PIDs. You can find it at http://vanheusden.com/Linux/security.php3

>> (amongst other patches). Beware: pretty much experimental and likely to 
>> make your linux-pc perform like a win95 platform. 
> Well - I'm not sure that this is a good idea. When PIDs increase 
> monotonically, chances are very small that the race condition implicit in 
> sending any signal to a process results in killing the wrong process (ie,
a 
> new process, but with the same PID) - you'd need to zoom through 32000
PIDs 
> in a very short time to make this happen. 
> With truly random PIDs, there is a much larger chance of a new process 
> sitting on a recently used PID. 

My code runs trough the whole task_list to see if a chosen pid is already
in use or not.

> What would work is to have cryptographically randomly generated PIDs which

> would then guarantee not to return a previously returned number within
32000 
> tries, and also not be predictable - there must be algoritms out there
which 
> do this. 

That's also an option!
But for simplicity-sake, I used the get_random_bytes() function (from
the /dev/random-device) combined with a loop. It's a simplistic hack, but
it'll work for my paranoia mind :o)


Greetings,

Folkert van Heusden

Re: random PID generation

[bert hubert]

On Fri, Feb 23, 2001 at 02:20:27PM +0100, Heusden, Folkert van wrote:

> > With truly random PIDs, there is a much larger chance of a new process 
> > sitting on a recently used PID. 
> 
> My code runs trough the whole task_list to see if a chosen pid is already
> in use or not.

But it doesn't check for a recently used PID. Lets say your system is
exhausting 1000 PIDs/second, and that there is a window of 20ms between you
determining which PID to send to, and the recipient process receiving it.

With truely random PIDs, there is now a chance of 1-(1-1/32000)^20 that a
new process will have the PID of the process you intended your signal for.
That's 0.06%, but historically, we care for those kind of chances.

The complete formula is: 1-(1-1/32000)^(dt*pps), where dt stands for the
time interval and pps for the number of pids created per second.

Currently, there are problems if your dt*pps product is bigger than 32000,
which in practice won't ever happen.

Regards,

bert hubert

-- 
http://www.PowerDNS.com      Versatile DNS Services  
Trilab                       The Technology People   
'SYN! .. SYN|ACK! .. ACK!' - the mating call of the internet

Re: random PID generation

[Heusden, Folkert van]

> I have already written a 2.2 implementation which does not suffer from
these 
> problems.

Yes, someone pointed me at it. To be honest (and with all due respect): I
found
it to be a bit over-complicated. Like; in my opinion it's only usefull to
have
absolute random chosen PIDs, or not. Not all those options are needed in my
opinion.

> It was rejected because Alan Cox (and others) felt it only provided 
> security through obscurity. 

Yeah, well, yeah. My patch wasn't actually ment to be included in the main-
kernel. I agree with the security-by-obscurity argument altough I think it's
_not ALWAYS_ a bad thing.
What I am trying to say is: I agree that sofware should be written so that
they can't be exploited in one way or another. But since software is written
by humans, it's likely that bugs stay always in. Furthermore; it's always
possible that in the future new exploits are invented which exploit things
the original programmer didn't think of, and also; new libcs might have
security-problems which affect your software. To prevent that your system
gets cracked by some script-kiddie, I found it a good thing to patch the
mainstream-kernel with patches that disable executable stacks, make the
/proc filesystem more restricted, etc. etc. And in my quest for creating a
secure-as-possible system which anticipates on future exploits I found that
using random PIDs is a good thing.
I hope I made myself clear; english is not my native language which makes
this a rather big chalenge.


Greetings,
Folkert van Heusden
[ www.vanheusden.com ]

Re: random PID generation

[Heusden, Folkert van]

>> My code runs trough the whole task_list to see if a chosen pid is already

>> in use or not. 
> But it doesn't check for a recently used PID. Lets say your system is 
> exhausting 1000 PIDs/second, and that there is a window of 20ms between
you 
> determining which PID to send to, and the recipient process receiving it. 

Ah, I get your point. Good point :o)

I was thinking: I could split the PIDs up in 2...16383 and 16384-32767 and
then
switch between them when a process ends? nah, that doesn't help it.
hmmm.
I think random increments (instead of last_pid+1) would be the best thing to
do then?

Re: random PID generation

[Matt Johnston]

OpenBSD has a working implementation, might be worth looking at???

Cheers,
Matt Johnston.

On Fri, 23 Feb 2001 23:34, Heusden, Folkert van wrote:
> >> My code runs trough the whole task_list to see if a chosen pid is
> >> already
> >>
> >> in use or not.
> >
> > But it doesn't check for a recently used PID. Lets say your system is
> > exhausting 1000 PIDs/second, and that there is a window of 20ms between
>
> you
>
> > determining which PID to send to, and the recipient process receiving it.
>
> Ah, I get your point. Good point :o)
>
> I was thinking: I could split the PIDs up in 2...16383 and 16384-32767 and
> then
> switch between them when a process ends? nah, that doesn't help it.
> hmmm.
> I think random increments (instead of last_pid+1) would be the best thing
> to do then?
>
>
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: random PID generation

[Sean Hunter]

I have already written a 2.2 implementation which does not suffer from these
problems.  It was rejected because Alan Cox (and others) felt it only provided
security through obscurity.

Sean

On Fri, Feb 23, 2001 at 11:40:37PM +0800, Matt Johnston wrote:
> OpenBSD has a working implementation, might be worth looking at???
> 
> Cheers,
> Matt Johnston.
> 
> On Fri, 23 Feb 2001 23:34, Heusden, Folkert van wrote:
> > >> My code runs trough the whole task_list to see if a chosen pid is
> > >> already
> > >>
> > >> in use or not.
> > >
> > > But it doesn't check for a recently used PID. Lets say your system is
> > > exhausting 1000 PIDs/second, and that there is a window of 20ms between
> >
> > you
> >
> > > determining which PID to send to, and the recipient process receiving it.
> >
> > Ah, I get your point. Good point :o)
> >
> > I was thinking: I could split the PIDs up in 2...16383 and 16384-32767 and
> > then
> > switch between them when a process ends? nah, that doesn't help it.
> > hmmm.
> > I think random increments (instead of last_pid+1) would be the best thing
> > to do then?
> >
> >
> > -
> > To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > Please read the FAQ at  http://www.tux.org/lkml/
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: random PID generation

[Richard B. Johnson]

On Fri, 23 Feb 2001, Sean Hunter wrote:

> I have already written a 2.2 implementation which does not suffer from these
> problems.  It was rejected because Alan Cox (and others) felt it only provided
> security through obscurity.
> 
> Sean

The following is a simple random generator that will never give two
consecutive like numbers (therefore it's not really random). It's
pretty good for things like non-guessible PIDs, TCP/IP ports, etc.
Just mask off the length that you don't need. It this was called 
occasionally from some timer or other interrupt, you don't even know its
starting value. With the current magic number, it's period is 0xfffnnnnn.
Several years ago, I ran an exhaustive search program (133MHz CPU) looking
for a magic number to produce a longer period. I'm told that there
is a magic number that will give a period of 0xffffffff.


static int rnn = 0;

static int rnd()
{
    int ret;
    __asm__ __volatile__(
    "\tmovl (rnn), %%eax\n"
    "\trorl $3,  %%eax\n" 
    "\taddl $0x586c3ec3, %%eax\n"
    "\tmovl %%eax, (rnn)\n"
		: "=eax" (ret) );
    return ret;
}


Cheers,
Dick Johnson

Penguin : Linux version 2.4.1 on an i686 machine (799.53 BogoMips).

"Memory is like gasoline. You use it up when you are running. Of
course you get it all back when you reboot..."; Actual explanation
obtained from the Micro$oft help desk.

random PID generation

[Heusden, Folkert van]

Hi,

I wrote a patch against 2.2.18 and 2.4.1 to have the kernel generate random
PIDs.
You can find it at http://vanheusden.com/Linux/security.php3 (amongst other
patches).
Beware: pretty much experimental and likely to make your linux-pc perform
like a
win95 platform.


Greetings,

Folkert van Heusden

Re: random PID generation

[bert hubert]

On Thu, Feb 22, 2001 at 04:35:35PM +0100, Heusden, Folkert van wrote:
> Hi,

Hi Folkert!

> I wrote a patch against 2.2.18 and 2.4.1 to have the kernel generate
> random PIDs. You can find it at http://vanheusden.com/Linux/security.php3
> (amongst other patches). Beware: pretty much experimental and likely to
> make your linux-pc perform like a win95 platform.

Well - I'm not sure that this is a good idea. When PIDs increase
monotonically, chances are very small that the race condition implicit in
sending any signal to a process results in killing the wrong process (ie, a
new process, but with the same PID) - you'd need to zoom through 32000 PIDs
in a very short time to make this happen.

With truly random PIDs, there is a much larger chance of a new process
sitting on a recently used PID.

What would work is to have cryptographically randomly generated PIDs which
would then guarantee not to return a previously returned number within 32000
tries, and also not be predictable - there must be algoritms out there which
do this.

Regards,

bert

-- 
http://www.PowerDNS.com      Versatile DNS Services  
Trilab                       The Technology People   
'SYN! .. SYN|ACK! .. ACK!' - the mating call of the internet

Re: random PID generation

[H. Peter Anvin]

Followup to:  <20010222232423.A18448@home.ds9a.nl>
By author:    bert hubert <ahu@ds9a.nl>
In newsgroup: linux.dev.kernel
> 
> Well - I'm not sure that this is a good idea. When PIDs increase
> monotonically, chances are very small that the race condition implicit in
> sending any signal to a process results in killing the wrong process (ie, a
> new process, but with the same PID) - you'd need to zoom through 32000 PIDs
> in a very short time to make this happen.
> 
> With truly random PIDs, there is a much larger chance of a new process
> sitting on a recently used PID.
> 
> What would work is to have cryptographically randomly generated PIDs which
> would then guarantee not to return a previously returned number within 32000
> tries, and also not be predictable - there must be algoritms out there which
> do this.
> 

It depends on the size of your number space.  If you have a 31-bit
pid_t (since it apparently must be sign-safe) then you can take random
16-bit numbers from the /dev/urandom code and add to the last used
value instead of simple increment.

	-hpa

-- 
<hpa@transmeta.com> at work, <hpa@zytor.com> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt