6 ms·

“We show that if you have two low-quality random sources—lower quality sources are much easier to come by—two sources that are independent and have no correlati

“We show that if you have two low-quality random sources—lower quality sources are much easier to come by—two sources that are independent and have no correlations between them, you can combine them in a way to produce a high-quality random number,” So Math.random() * Math.random() ? :)

thaumasiotes 10y ago
That sounds more like one source. :p
deleted 10y ago
[deleted]
Ramiuz 10y ago
Math.random() * hwclock ?
- BugsBunnySan 10y ago
  If your hwclock is a source of randomness, maybe you should be worried ;)
plainOldText 10y ago
Perhaps Math.random()@computer1 and Math.random()@computer2
- willvarfar 10y ago
  As long as you ensure they are different algos and have different seeds...? As I write that I get a funny "no way" feeling. This is so unnatural feeling, if Its true it is indeed a breakthrough. I have to read the paper again. When people complained about Linux mixing in the Intel hardware rng Linus replied that mixing low quality sources have good entropy - and he got a lot of stick for that. That they are on different computers is immaterial.
  - mwpmaybe 10y ago
    > Linus replied that mixing low quality sources have good entropy Hopefully this research yields a wonderful new algorithm for combining the sources and makes it a simple kernel patch away.
  - merijnv 10y ago
    Linus actually argued something slightly different. That discussion was about whether a "bad" random source can weaken a "good" source. This paper is about constructing a "good" source from two independent "bad" sources. The problem with Linux was people complaining that mixing the Intel RNG into the existing entropy pool would lower the entropy of the entire pool, effectively letting a backdoored Intel RNG render the random system untrustworthy. Linus' response was the fairly simple/logical observation that "that's not how entropy works". Suppose we have a random bit string with entropy X and we xor the bit string with a completely deterministic bitstring, what's the result? Clearly you have a bitstring that STILL has entropy X, because the result is completely dependent on our initial bitstring. Mixing with a deterministic bitstring doesn't make the output of our XOR any more predictable then the original bitstring, it's equally random. So Linus' argument was that "IF the Intel RNG is completely backdoored and deterministic mixing it with the entropy pool will have no effect on the entropy in the pool. HOWEVER, if the Intel RNG is anything but completely deterministic, i.e. there is even a tiny bit of randomness in it, this will actually INCREASE the pool's entropy. So mixing a completely backdoored RNG will have no negative impact, but mixing anything that's not 100% predictable will have a positive impact, so there's no reason to not always mix the hardware RNG with the pool.
    - Natanael_L 10y ago
      That's also assuming it isn't maliciously correlated to produce an output that after XOR leaks secret entropy.
      - merijnv 10y ago
        Sure, if you're hardware RNG is inspecting your RAM and trying to compromise your entropy pool that could be done, but: 1 - The entropy mixing is more complex than simply XOR, making such a thing considerably harder 2 - If you expect this level of backdooring from your CPU, you have bigger problems :)
- goldenkey 10y ago
  See my post about why multiplying two sources of random numbers will actually reduce the entropy to less than even a single one of the sources: https://news.ycombinator.com/reply?id=11719840&goto=item%3Fid%3D11719543 https://news.ycombinator.com/reply?id=11719840&goto=item%3Fi... It is imperative to use a binary hash that leaves all possible input pairs equally probable for the output. That is what this paper is about.
fragsworth 10y ago
No, the article says "two sources that are independent and have no correlations between them".
goldenkey 10y ago
F(a,b) = ab = ba leaves rather hideous properties of the input apparent. Because your operation is both associative and commutative, your operation is an abelian group. Any result ab says a lot about the probability of a certain input pair. Because Math.random returns a real number between 0 and 1, with finite bits, a<1 and b<1 ab < b and ab < a 2ab < a + b 2 < (a+b)/ab 0 < (a+b)/ab - 2 This equation has roots. Given that there is a finite bitspace, IEEE float/double -- if ab is .9 for example, then the possible (a,b) pairs for the result are 2^(number of bits) * (1-.9) = one tenth of the bitspace You planned to have 2X where X was the entropy of Math.random alone. Instead you got 1/10 of 2X, 1/5 of the entropy of just using Math.random. A total failure. Hows that for shits and giggles. This is why crypto should be left to mathematicians. Dont invent your own hashes, don't invent your own crypto. And don't try to combine two entropy sources with novel approaches, you'll most likely fail. I'm not very versed on mathematics yet, just getting into it. But you can already see multiplication is a terrible terrible choice versus an actual hash. But even a hash will leave us vulnerable considering our random source is the same.
- Natanael_L 10y ago
  The * signs botched your formatting
  - goldenkey 10y ago
    Thanks for letting me know -- that was a curious annoyance. I am not going to edit the post but I'll make sure I don't slaughter my future posts.

thaumasiotes 10y ago

That sounds more like one source. :p

deleted 10y ago

[deleted]

Ramiuz 10y ago

Math.random() * hwclock ?

BugsBunnySan 10y ago
If your hwclock is a source of randomness, maybe you should be worried ;)

plainOldText 10y ago

Perhaps Math.random()@computer1 and Math.random()@computer2

willvarfar 10y ago
As long as you ensure they are different algos and have different seeds...? As I write that I get a funny "no way" feeling. This is so unnatural feeling, if Its true it is indeed a breakthrough. I have to read the paper again. When people complained about Linux mixing in the Intel hardware rng Linus replied that mixing low quality sources have good entropy - and he got a lot of stick for that. That they are on different computers is immaterial.
- mwpmaybe 10y ago
  > Linus replied that mixing low quality sources have good entropy Hopefully this research yields a wonderful new algorithm for combining the sources and makes it a simple kernel patch away.
- merijnv 10y ago
  Linus actually argued something slightly different. That discussion was about whether a "bad" random source can weaken a "good" source. This paper is about constructing a "good" source from two independent "bad" sources. The problem with Linux was people complaining that mixing the Intel RNG into the existing entropy pool would lower the entropy of the entire pool, effectively letting a backdoored Intel RNG render the random system untrustworthy. Linus' response was the fairly simple/logical observation that "that's not how entropy works". Suppose we have a random bit string with entropy X and we xor the bit string with a completely deterministic bitstring, what's the result? Clearly you have a bitstring that STILL has entropy X, because the result is completely dependent on our initial bitstring. Mixing with a deterministic bitstring doesn't make the output of our XOR any more predictable then the original bitstring, it's equally random. So Linus' argument was that "IF the Intel RNG is completely backdoored and deterministic mixing it with the entropy pool will have no effect on the entropy in the pool. HOWEVER, if the Intel RNG is anything but completely deterministic, i.e. there is even a tiny bit of randomness in it, this will actually INCREASE the pool's entropy. So mixing a completely backdoored RNG will have no negative impact, but mixing anything that's not 100% predictable will have a positive impact, so there's no reason to not always mix the hardware RNG with the pool.
  - Natanael_L 10y ago
    That's also assuming it isn't maliciously correlated to produce an output that after XOR leaks secret entropy.
    - merijnv 10y ago
      Sure, if you're hardware RNG is inspecting your RAM and trying to compromise your entropy pool that could be done, but: 1 - The entropy mixing is more complex than simply XOR, making such a thing considerably harder 2 - If you expect this level of backdooring from your CPU, you have bigger problems :)
goldenkey 10y ago
See my post about why multiplying two sources of random numbers will actually reduce the entropy to less than even a single one of the sources: https://news.ycombinator.com/reply?id=11719840&goto=item%3Fid%3D11719543 https://news.ycombinator.com/reply?id=11719840&goto=item%3Fi... It is imperative to use a binary hash that leaves all possible input pairs equally probable for the output. That is what this paper is about.

fragsworth 10y ago

No, the article says "two sources that are independent and have no correlations between them".

goldenkey 10y ago

F(a,b) = ab = ba leaves rather hideous properties of the input apparent. Because your operation is both associative and commutative, your operation is an abelian group. Any result ab says a lot about the probability of a certain input pair. Because Math.random returns a real number between 0 and 1, with finite bits, a<1 and b<1 ab < b and ab < a 2ab < a + b 2 < (a+b)/ab 0 < (a+b)/ab - 2 This equation has roots. Given that there is a finite bitspace, IEEE float/double -- if ab is .9 for example, then the possible (a,b) pairs for the result are 2^(number of bits) * (1-.9) = one tenth of the bitspace You planned to have 2X where X was the entropy of Math.random alone. Instead you got 1/10 of 2X, 1/5 of the entropy of just using Math.random. A total failure. Hows that for shits and giggles. This is why crypto should be left to mathematicians. Dont invent your own hashes, don't invent your own crypto. And don't try to combine two entropy sources with novel approaches, you'll most likely fail. I'm not very versed on mathematics yet, just getting into it. But you can already see multiplication is a terrible terrible choice versus an actual hash. But even a hash will leave us vulnerable considering our random source is the same.

Natanael_L 10y ago
The * signs botched your formatting
- goldenkey 10y ago
  Thanks for letting me know -- that was a curious annoyance. I am not going to edit the post but I'll make sure I don't slaughter my future posts.