3 ms·

I'm not knowledgeable in the intricacies of cryptography, so this is something that bug me, how can the Random Number Generator be backdoored in a way that woul

by ama729 13y ago

I'm not knowledgeable in the intricacies of cryptography, so this is something that bug me, how can the Random Number Generator be backdoored in a way that would be usable for the NSA without being detectable? Surely you could graph the numbers that the RNG output and see if it's random or not, no?

sweettea 13y ago
A sequence can be completely deterministic and yet pass all randomness tests. For instance, if I tell you I randomly chose numbers between 0 and 16, inclusive, and got 14, 13, 10, 1, 6, 5, 2, 9, in that order, as far as you can tell it looks random. However, x_{n+1} was generated by taking (3 * x_n + 3) % 16, and hence I can predict the next random number in the sequence trivially. [This is a bad random number generator for other reasons --- see Wikipedia on LCGs for more --- but a good demonstration of how random numbers can appear random but be usable by $attacker.]
- dredmorbius 13y ago
  A sequence of digits take from pi or e would be randomly distributed but completely deterministic.
  - jjgreen 13y ago
    It is not known whether the digits of pi are evenly distributed.
    - dredmorbius 13y ago
      NB: what I said was "randomly", not "evenly". Though I doubt we'll ever get to the end of this one.
dredmorbius 13y ago
Surely you could graph the numbers that the RNG output and see if it's random or not, no? Actually, according to numerous people I respect on this (Ted T'so comes to mind): no. It's apparently possible to compromise an RNG in such a way that its output appears to be random -- unless you're aware of the secret.
- tptacek 13y ago
  It must be possible to do this, or else how would we have stream ciphers?
TacticalCoder 13y ago
(Disclaimer: I'm a dev, not a cryptographer) Take this example: the output of a cryptographically secure pseudo random number generator (CSPRNG) cannot be determined without knowing it's seed(s) (the initial seed and, optionally, additional seeds if/when re-seeding is done). Any CSPRNG must pass the "next bit" test or it is not a CSPRNG: the probability of the next bit being 1 is 0.5 (the probability of it being 0 is 0.5 too of course). So, no, you cannot graph the output of a CSPRNG and see if it's random or not. Because by their very definition outputs of CSPRNG look random. Yet CSPRNGs are fully deterministic. Now that is another topic but... The NSA may have an history of also backdooring CSPRNG (Dual_EC_DRBG comes to mind) ^ ^
ZoFreX 13y ago
You could tell whether it is evenly distributed (with some probability, as you can only inspect a range and not all the numbers it will output), but you cannot test whether or not a sequence is random. http://dilbert.com/strips/comic/2001-10-25/ http://dilbert.com/strips/comic/2001-10-25/

by ama729 13y ago

sweettea 13y ago

A sequence can be completely deterministic and yet pass all randomness tests. For instance, if I tell you I randomly chose numbers between 0 and 16, inclusive, and got 14, 13, 10, 1, 6, 5, 2, 9, in that order, as far as you can tell it looks random. However, x_{n+1} was generated by taking (3 * x_n + 3) % 16, and hence I can predict the next random number in the sequence trivially. [This is a bad random number generator for other reasons --- see Wikipedia on LCGs for more --- but a good demonstration of how random numbers can appear random but be usable by $attacker.]

dredmorbius 13y ago
A sequence of digits take from pi or e would be randomly distributed but completely deterministic.
- jjgreen 13y ago
  It is not known whether the digits of pi are evenly distributed.
  - dredmorbius 13y ago
    NB: what I said was "randomly", not "evenly". Though I doubt we'll ever get to the end of this one.

dredmorbius 13y ago

Surely you could graph the numbers that the RNG output and see if it's random or not, no? Actually, according to numerous people I respect on this (Ted T'so comes to mind): no. It's apparently possible to compromise an RNG in such a way that its output appears to be random -- unless you're aware of the secret.

tptacek 13y ago
It must be possible to do this, or else how would we have stream ciphers?

TacticalCoder 13y ago

(Disclaimer: I'm a dev, not a cryptographer) Take this example: the output of a cryptographically secure pseudo random number generator (CSPRNG) cannot be determined without knowing it's seed(s) (the initial seed and, optionally, additional seeds if/when re-seeding is done). Any CSPRNG must pass the "next bit" test or it is not a CSPRNG: the probability of the next bit being 1 is 0.5 (the probability of it being 0 is 0.5 too of course). So, no, you cannot graph the output of a CSPRNG and see if it's random or not. Because by their very definition outputs of CSPRNG look random. Yet CSPRNGs are fully deterministic. Now that is another topic but... The NSA may have an history of also backdooring CSPRNG (Dual_EC_DRBG comes to mind) ^ ^

ZoFreX 13y ago

You could tell whether it is evenly distributed (with some probability, as you can only inspect a range and not all the numbers it will output), but you cannot test whether or not a sequence is random. http://dilbert.com/strips/comic/2001-10-25/ http://dilbert.com/strips/comic/2001-10-25/