7 ms·

I would go for a 128bit PID; a 64bit PID runs danger of collision if 2^32 processes have been created and killed. A 128bit PID is unlikely to ever collide and y

by zaarn 7y ago

I would go for a 128bit PID; a 64bit PID runs danger of collision if 2^32 processes have been created and killed. A 128bit PID is unlikely to ever collide and you can write code with the assumption that a PID is uniquely identifying to a process and will not be reused or collide in any reasonable timeframe (100 years or so).

im3w1l 7y ago
The pids are allocated sequentially rather than randomly, so birthday paradox isn't an issue here.
- zaarn 7y ago
  If going for big PIDs I'd do random assignment, means people will stop doign any kind of assumption about PIDs and stops potential side-channel leakage.
  - londons_explore 7y ago
    You can still do random assignment but never allocate the same ID twice. There are a bunch of methods to do that quickly and securely - for example use the result of encrypting a counter with a key only the kernel knows. There are benefits to sequential allocation - for one thing, the PID doesn't need to be stored anywhere (which can matter on very low memory machines), and optimizations can be made when there are only a handful of PID's.
    - perl4ever 7y ago
      "There are a bunch of methods to do that quickly and securely - for example use the result of encrypting a counter with a key only the kernel knows." That isn't a guarantee, technically though, is it? And if you consider it guaranteed, then why wouldn't a (P)RNG be just as trustworthy? Is there a mathematical argument why it's better?
      - wahern 7y ago
        For the inner parts of a cipher (before you get into "modes"), it is guaranteed. A cipher's transformation has to be reversible, otherwise you can't decrypt. If different inputs produce the same output, then it's not reversible. Block cipher modes like CTR, CBC, etc, are built by combining this basic, reversible building block--a permutation--with additional state. The modes provide additional features, but they necessarily require additional state so that transformations are reversible. Stream ciphers, like RC4, have implicit state, such that to decrypt you have to iterate the function from the beginning state. Modern stream ciphers are built more like CTR-mode block ciphers. You can build reversible transformations from non-reversible functions, such as a one-way hash function, using methods like the Feistel construction (https://en.wikipedia.org/wiki/Feistel_cipher https://en.wikipedia.org/wiki/Feistel_cipher), which was the traditional method for building block ciphers. For my DNS library I used a simple, 16-bit Feistel "cipher" to generate non-repeating QIDs.[1] Most DNS libraries shuffle a 65536-element array (e.g. using a Knuth shuffle), or keep a 65536-bit set to filter values generated by a PRNG. I preferred the cipher approach because the only state necessary was a single integer "key" for each DNS query context, which may need to send a small number of packets to resolve a record. Plus I got to try out a new technique. [1] Non-repeating until you've cycled through all 2^16 values. But even a cryptographically secure permutation becomes increasingly easier to guess the more values you can observe. And of course if you can observe the whole series then you can always guess with 100% accuracy successive values--it just cycles again. For my DNS library I got to generate a new key for every context, which resulted in a new permutation. But for system PIDs it's self-defeating to use a new key to produce a new permutation; the whole point was to avoid having to deal with potential collisions. That's why operating systems like OpenBSD don't bother with this technique for generating random PIDs or ephemeral port numbers.
        perl4ever 7y ago
        Yeah, I don't know why, but I translated "encrypt" into "hash".
    - zaarn 7y ago
      >There are benefits to sequential allocation - for one thing, the PID doesn't need to be stored anywhere (which can matter on very low memory machines), and optimizations can be made when there are only a handful of PID's. I doN't think those matter that much anymore, if the machine has low memory it won't run a lot of processes and those optimizations won't matter much and if it runs a lot of processes it's likely to have more memory.

by zaarn 7y ago

im3w1l 7y ago

The pids are allocated sequentially rather than randomly, so birthday paradox isn't an issue here.

zaarn 7y ago
If going for big PIDs I'd do random assignment, means people will stop doign any kind of assumption about PIDs and stops potential side-channel leakage.
- londons_explore 7y ago
  You can still do random assignment but never allocate the same ID twice. There are a bunch of methods to do that quickly and securely - for example use the result of encrypting a counter with a key only the kernel knows. There are benefits to sequential allocation - for one thing, the PID doesn't need to be stored anywhere (which can matter on very low memory machines), and optimizations can be made when there are only a handful of PID's.
  - perl4ever 7y ago
    "There are a bunch of methods to do that quickly and securely - for example use the result of encrypting a counter with a key only the kernel knows." That isn't a guarantee, technically though, is it? And if you consider it guaranteed, then why wouldn't a (P)RNG be just as trustworthy? Is there a mathematical argument why it's better?
    - wahern 7y ago
      For the inner parts of a cipher (before you get into "modes"), it is guaranteed. A cipher's transformation has to be reversible, otherwise you can't decrypt. If different inputs produce the same output, then it's not reversible. Block cipher modes like CTR, CBC, etc, are built by combining this basic, reversible building block--a permutation--with additional state. The modes provide additional features, but they necessarily require additional state so that transformations are reversible. Stream ciphers, like RC4, have implicit state, such that to decrypt you have to iterate the function from the beginning state. Modern stream ciphers are built more like CTR-mode block ciphers. You can build reversible transformations from non-reversible functions, such as a one-way hash function, using methods like the Feistel construction (https://en.wikipedia.org/wiki/Feistel_cipher https://en.wikipedia.org/wiki/Feistel_cipher), which was the traditional method for building block ciphers. For my DNS library I used a simple, 16-bit Feistel "cipher" to generate non-repeating QIDs.[1] Most DNS libraries shuffle a 65536-element array (e.g. using a Knuth shuffle), or keep a 65536-bit set to filter values generated by a PRNG. I preferred the cipher approach because the only state necessary was a single integer "key" for each DNS query context, which may need to send a small number of packets to resolve a record. Plus I got to try out a new technique. [1] Non-repeating until you've cycled through all 2^16 values. But even a cryptographically secure permutation becomes increasingly easier to guess the more values you can observe. And of course if you can observe the whole series then you can always guess with 100% accuracy successive values--it just cycles again. For my DNS library I got to generate a new key for every context, which resulted in a new permutation. But for system PIDs it's self-defeating to use a new key to produce a new permutation; the whole point was to avoid having to deal with potential collisions. That's why operating systems like OpenBSD don't bother with this technique for generating random PIDs or ephemeral port numbers.
      - perl4ever 7y ago
        Yeah, I don't know why, but I translated "encrypt" into "hash".
  - zaarn 7y ago
    >There are benefits to sequential allocation - for one thing, the PID doesn't need to be stored anywhere (which can matter on very low memory machines), and optimizations can be made when there are only a handful of PID's. I doN't think those matter that much anymore, if the machine has low memory it won't run a lot of processes and those optimizations won't matter much and if it runs a lot of processes it's likely to have more memory.