5 ms·

The solution here, which the article fails to mention, and which every security expert will undoubtedly tell you, is to make sure you use super random numbers

by chops 13y ago

The solution here, which the article fails to mention, and which every security expert will undoubtedly tell you, is to make sure you use super random numbers (that's the technical term, for the layperson) by adding two random numbers together.

deleted 13y ago
[deleted]
hueving 13y ago
No! You call a blocking rand function bound by available entropy. If your random source is compromised, adding two numbers from the same broken source does nothing. What you can do though, is XOR numbers from independent random sources to improve the entropy of the final output. (not sure if that's what you meant by adding random numbers together)
- brazzy 13y ago
  I believe that chops was being sarcastic in ascribing a typical naive and useless attempt at "improving" randomness to "experts". Come on, "super random numbers"??
  - chops 13y ago
    Yes, it was indeed a joke. And one which has apparentlly fallen flat.
    - dublinclontarf 13y ago
      No no, I got it, much enjoyed.
    - blumkvist 13y ago
      No, it worked perfectly. If you have to explain a joke to someone, that means the joke is making fun of them!
- MertsA 13y ago
  Doing nothing but an XOR is usually fine but one thing to keep in mind is that an attacker that can see one stream and control the other could completely eliminate any entropy yet make the data look completely random. This sounds like some unlikely scenario but for instance the Linux kernel uses a method like this for /dev/random. Entropy is collected and mixed in an entropy pool from many sources but at the end it is XORed with the output of Rdrand on processors that support it. The NSA could force Intel to sign a malicious microcode update that changes Rdrand to AES_encrypt(i++, NSA_KEY) ^ entropy_pool and then any random data coming from the kernel is completely predictable and without NSA_KEY it wouldn't be discernible from truly random data.
  - hueving 13y ago
    That's not really right. The other requirement for that scheme to work is to leak the entropy_pool as well. That's why the linux kernel random source IS safe from bad hardware. Even if the hardware source is completely known by a third party, they can't discern the output from random data because it has been XORed with random data. If it helps to think about, imagine that the evil hardware always output 00000000 for a byte of randomness. The kernel then XORs that with a byte from the entropy_pool, which is unknown to the adversary. The output byte is still completely unknown to the adversary even though it knows one of the inputs.
- tptacek 13y ago
  Oh, I get it. These are both joke comments that are commenting on the weird number of urban legends surrounding randomness.
  - logicallee 13y ago
    No actually the follow-on was serious. You can prove to yourself that XOR-ing independent sources of entropy works: Just remember that XOR is commutative, so you can rearrange the terms. Then realize that a XOR is how you implement a one-time pad. So if you xor together 5 sources of "entropy", #1 is super broken and outputs all zeros, #2 is secure and independent, #3 is an NSA program, and #4 and #5 are weak, broken RNG's....then it doesn't matter, because the XOR's can be rearranged in your mind so that it's clear that #2 is still acting as an OTP on the rest (comes last). As long as it is uniform and independent (key really does get thrown away) you are good to go -- by the definition of OTP. If it had less than full entropy, then that means an OTP would leave some recoverable information. Meanwhile, of course, the sources DO need to be independent. If #3 knows the stream that #2 is outputing, by coming later in the chain and producing its output after #2 has produced it, it can undo it by simply copying the output of #2. This is why independence is important. So in summary each XOR independently implements a one-time pad on all the rest of the xor results, whilst throwing away the key. If even one out of one hundred sources is actually random, doesn't matter which one, then the result is just as good as if that were the source yuo were using directly. As long as they are independent sources.
  - hueving 13y ago
    Really? I would have expected better from you for your reputation. :-) Read carefully what I said. Explained more clearly, XORing is at worst a ceiling function of the entropy of two random sources. If it weren't, that would imply one-time pad is insecure.
    - tptacek 13y ago
      I was reacting to "blocking function bound by available entropy".
- dublinclontarf 13y ago
  I guarantee you these guys were not using test driven development, they need to TEST that their random number generator is random enough. With TDD they would never have had these problems.
rlwolfcastle 13y ago
Strangely, the name of the submitters company is "Additive Analytics"
InclinedPlane 13y ago
Hah, nice one. For people not getting the joke, adding two random numbers reduces the randomness and concentrates the results around a mean. Interestingly, the perception that adding random numbers together results in even more random numbers is behind the popularity of the scam game "razzle". In razzle there's usually a board containing an array of depressions each lined up with a different value onto which is dropped a number of marbles (there are other ways to play as well, including dice). The important part is the scoring board. After each toss the values where all the marbles landed are added up and then a board is consulted to see how many "points" are scored from that value. The game is easy, get to 10 points and you win. However, there are two tricks. First, the scoring board is arranged in non sequential order. This is to conceal the fact that the group of middle numbers do not win any points. In actuality it is very difficult to win any points, since the probabilities are all concentrated in the middle. Second, because of the scattered nature of the scoring board it's very easy for the person running the game to cheat in your favor by "accidentally" giving you points when you shouldn't have earned them. The scam then works fairly simply. People pay money for each throw, and they are given the opportunity to win a high value prize. For the early throws the operator goes quickly and fudges the score lookups, building up points for the player that they haven't actually used, and giving them an unwarranted confidence in the game. After the player gets within a point or so of winning the operator then lets stops cheating and lets them play completely fairly on their own, at which point they have odds of worse than a thousand to one of winning (keeping in mind that it costs money for every throw).

by chops 13y ago

deleted 13y ago

[deleted]

hueving 13y ago

No! You call a blocking rand function bound by available entropy. If your random source is compromised, adding two numbers from the same broken source does nothing. What you can do though, is XOR numbers from independent random sources to improve the entropy of the final output. (not sure if that's what you meant by adding random numbers together)

brazzy 13y ago
I believe that chops was being sarcastic in ascribing a typical naive and useless attempt at "improving" randomness to "experts". Come on, "super random numbers"??
- chops 13y ago
  Yes, it was indeed a joke. And one which has apparentlly fallen flat.
  - dublinclontarf 13y ago
    No no, I got it, much enjoyed.
  - blumkvist 13y ago
    No, it worked perfectly. If you have to explain a joke to someone, that means the joke is making fun of them!
MertsA 13y ago
Doing nothing but an XOR is usually fine but one thing to keep in mind is that an attacker that can see one stream and control the other could completely eliminate any entropy yet make the data look completely random. This sounds like some unlikely scenario but for instance the Linux kernel uses a method like this for /dev/random. Entropy is collected and mixed in an entropy pool from many sources but at the end it is XORed with the output of Rdrand on processors that support it. The NSA could force Intel to sign a malicious microcode update that changes Rdrand to AES_encrypt(i++, NSA_KEY) ^ entropy_pool and then any random data coming from the kernel is completely predictable and without NSA_KEY it wouldn't be discernible from truly random data.
- hueving 13y ago
  That's not really right. The other requirement for that scheme to work is to leak the entropy_pool as well. That's why the linux kernel random source IS safe from bad hardware. Even if the hardware source is completely known by a third party, they can't discern the output from random data because it has been XORed with random data. If it helps to think about, imagine that the evil hardware always output 00000000 for a byte of randomness. The kernel then XORs that with a byte from the entropy_pool, which is unknown to the adversary. The output byte is still completely unknown to the adversary even though it knows one of the inputs.
tptacek 13y ago
Oh, I get it. These are both joke comments that are commenting on the weird number of urban legends surrounding randomness.
- logicallee 13y ago
  No actually the follow-on was serious. You can prove to yourself that XOR-ing independent sources of entropy works: Just remember that XOR is commutative, so you can rearrange the terms. Then realize that a XOR is how you implement a one-time pad. So if you xor together 5 sources of "entropy", #1 is super broken and outputs all zeros, #2 is secure and independent, #3 is an NSA program, and #4 and #5 are weak, broken RNG's....then it doesn't matter, because the XOR's can be rearranged in your mind so that it's clear that #2 is still acting as an OTP on the rest (comes last). As long as it is uniform and independent (key really does get thrown away) you are good to go -- by the definition of OTP. If it had less than full entropy, then that means an OTP would leave some recoverable information. Meanwhile, of course, the sources DO need to be independent. If #3 knows the stream that #2 is outputing, by coming later in the chain and producing its output after #2 has produced it, it can undo it by simply copying the output of #2. This is why independence is important. So in summary each XOR independently implements a one-time pad on all the rest of the xor results, whilst throwing away the key. If even one out of one hundred sources is actually random, doesn't matter which one, then the result is just as good as if that were the source yuo were using directly. As long as they are independent sources.
- hueving 13y ago
  Really? I would have expected better from you for your reputation. :-) Read carefully what I said. Explained more clearly, XORing is at worst a ceiling function of the entropy of two random sources. If it weren't, that would imply one-time pad is insecure.
  - tptacek 13y ago
    I was reacting to "blocking function bound by available entropy".
dublinclontarf 13y ago
I guarantee you these guys were not using test driven development, they need to TEST that their random number generator is random enough. With TDD they would never have had these problems.

rlwolfcastle 13y ago

Strangely, the name of the submitters company is "Additive Analytics"

InclinedPlane 13y ago

Hah, nice one. For people not getting the joke, adding two random numbers reduces the randomness and concentrates the results around a mean. Interestingly, the perception that adding random numbers together results in even more random numbers is behind the popularity of the scam game "razzle". In razzle there's usually a board containing an array of depressions each lined up with a different value onto which is dropped a number of marbles (there are other ways to play as well, including dice). The important part is the scoring board. After each toss the values where all the marbles landed are added up and then a board is consulted to see how many "points" are scored from that value. The game is easy, get to 10 points and you win. However, there are two tricks. First, the scoring board is arranged in non sequential order. This is to conceal the fact that the group of middle numbers do not win any points. In actuality it is very difficult to win any points, since the probabilities are all concentrated in the middle. Second, because of the scattered nature of the scoring board it's very easy for the person running the game to cheat in your favor by "accidentally" giving you points when you shouldn't have earned them. The scam then works fairly simply. People pay money for each throw, and they are given the opportunity to win a high value prize. For the early throws the operator goes quickly and fudges the score lookups, building up points for the player that they haven't actually used, and giving them an unwarranted confidence in the game. After the player gets within a point or so of winning the operator then lets stops cheating and lets them play completely fairly on their own, at which point they have odds of worse than a thousand to one of winning (keeping in mind that it costs money for every throw).