4 ms·

This is one question I have always come across when working with crypto systems. Why is it impossible for one to have an algorithm that generates true cryptogr

by max_ 7y ago

This is one question I have always come across when working with crypto systems. Why is it impossible for one to have an algorithm that generates true cryptographically secure random numbers?

hannob 7y ago
> Why is it impossible for one to have an algorithm that generates true cryptographically secure random numbers? The answer alternates between "it's not" and "depends on how exactly you define algorithm". With algorithms we usually talk about deterministic instructions. In such a sense an algorithm can't create random numbers, because it'll always output the same thing with the same input. But give a few random inputs (which there are usually plenty in any complex enough system) we can build an algorithm that will take these random inputs and output an endless, secure stream of random numbers. Which is what every modern operating system does. You don't need any magic external random number source for that, just use what your OS gives you.
- max_ 7y ago
  Interesting. What "degree of complexity" in the system is a "complex enough system"?
  - hannob 7y ago
    Good questoin, it's hard to give a definite answer, but usually "if it has a harddrive and a network card you're unlikely to have any problem". Rule of thumb: Normal Desktops and Servers are unlikely to be problematic. Really the only realistic problem is that if you generate a cryptographic key right after booting the device and if the device is something like a router. Look here [1] for some research on that. That scenario can be avoided by newer APIs (newer linux kernels have the getrandom system call for that) that only will spit out random numbers once the RNG has been initialized with enough randomness - but in return you may get services blocking at boot. [1] https://factorable.net/ https://factorable.net/
espadrine 7y ago
Deterministic perfect random generation requires infinite memory. One way to see it is this: a perfect bit generator should output a 1 half the time on average. (Let’s not talk about variance for this.) Out of all sequences of two bits, it should output 11 a quarter of the time. It should output 111 an eighth of the time. Assume you have N bits of state, and some computation on it produces N random bits and changes the state. Then, at best, a single initial state will give you a sequence of N consecutive ones. (If multiple initial states give you that output, then some other output of N bits cannot be output, which is a deviation from true random output.) So the longest consecutive sequence of ones you can output is 3×N-2 (with the previous output being zero followed by N-1 ones, and the next output being the reverse). Therefore, you cannot output a sequence of 3×N-1 consecutive ones, which is a deviation from true random generation that can be statistically detected, given a long enough output. In some sense, physical processes that output true randomness rely on the large amount of information stored in the environment, and that environment’s diffuse state scrambling, that is presumably extremely hard for an attacker to detect. For instance, the fine trajectory of electrons attracted from atom to atom through an electrical circuit causing minuscule delays, or the chaotic motion of gaseous atoms, or stronger yet, quantum behavior of particles.

by max_ 7y ago

This is one question I have always come across when working with crypto systems. Why is it impossible for one to have an algorithm that generates true cryptographically secure random numbers?

hannob 7y ago

> Why is it impossible for one to have an algorithm that generates true cryptographically secure random numbers? The answer alternates between "it's not" and "depends on how exactly you define algorithm". With algorithms we usually talk about deterministic instructions. In such a sense an algorithm can't create random numbers, because it'll always output the same thing with the same input. But give a few random inputs (which there are usually plenty in any complex enough system) we can build an algorithm that will take these random inputs and output an endless, secure stream of random numbers. Which is what every modern operating system does. You don't need any magic external random number source for that, just use what your OS gives you.

max_ 7y ago
Interesting. What "degree of complexity" in the system is a "complex enough system"?
- hannob 7y ago
  Good questoin, it's hard to give a definite answer, but usually "if it has a harddrive and a network card you're unlikely to have any problem". Rule of thumb: Normal Desktops and Servers are unlikely to be problematic. Really the only realistic problem is that if you generate a cryptographic key right after booting the device and if the device is something like a router. Look here [1] for some research on that. That scenario can be avoided by newer APIs (newer linux kernels have the getrandom system call for that) that only will spit out random numbers once the RNG has been initialized with enough randomness - but in return you may get services blocking at boot. [1] https://factorable.net/ https://factorable.net/

espadrine 7y ago

Deterministic perfect random generation requires infinite memory. One way to see it is this: a perfect bit generator should output a 1 half the time on average. (Let’s not talk about variance for this.) Out of all sequences of two bits, it should output 11 a quarter of the time. It should output 111 an eighth of the time. Assume you have N bits of state, and some computation on it produces N random bits and changes the state. Then, at best, a single initial state will give you a sequence of N consecutive ones. (If multiple initial states give you that output, then some other output of N bits cannot be output, which is a deviation from true random output.) So the longest consecutive sequence of ones you can output is 3×N-2 (with the previous output being zero followed by N-1 ones, and the next output being the reverse). Therefore, you cannot output a sequence of 3×N-1 consecutive ones, which is a deviation from true random generation that can be statistically detected, given a long enough output. In some sense, physical processes that output true randomness rely on the large amount of information stored in the environment, and that environment’s diffuse state scrambling, that is presumably extremely hard for an attacker to detect. For instance, the fine trajectory of electrons attracted from atom to atom through an electrical circuit causing minuscule delays, or the chaotic motion of gaseous atoms, or stronger yet, quantum behavior of particles.