7 ms·

Pure Randomness Extracted from Two Poor Sources

96 points by mmastrac 10y ago

jlgaddis 10y ago
> Some researchers have even speculated, especially since the disclosures by Edward Snowden, that commercial hardware sources could be subtly manipulated to make the codes easier to break by the U.S. National Security Agency or others. Speculated!? I think it's pretty well established by now that Dual_EC_DRBG was intentionally weakened. --- Abstract, etc.: http://eccc.hpi-web.de/report/2015/119/ http://eccc.hpi-web.de/report/2015/119/ Paper (PDF): http://eccc.hpi-web.de/report/2015/119/revision/2/download/ http://eccc.hpi-web.de/report/2015/119/revision/2/download/ Related article from 17 May 2016: "Academics Make Theoretical Breakthrough in Random Number Generation": https://threatpost.com/academics-make-theoretical-breakthrough-in-random-number-generation/118150/ https://threatpost.com/academics-make-theoretical-breakthrou...
- nickpsecurity 10y ago
  Concretely proven thanks to Edward Snowden leaking BULLRUN and Core Secrets: http://www.dcssproject.net/bullrun/ http://www.dcssproject.net/bullrun/ https://theintercept.com/2014/10/10/core-secrets/ https://theintercept.com/2014/10/10/core-secrets/
- lisper 10y ago
  Dual_EC_DRBG was software, not hardware. A hardware compromise would be much (much!) harder to detect.
  - nickpsecurity 10y ago
    Not necessarily. The hardware guy that got me started on all that was detecting them all the time. Some were really hard but others were obvious once the veil was pulled back. He said he stayed doing that sort of thing as did many others. Constant cat and mouse game. Your statement is true for software people where it will be anywhere from challenging to impossible for them to detect the hardware subversion.
    - lisper 10y ago
      I'm using the word "compromise" to mean the deliberate introduction of a vulnerability. I have a hard time believing that your friend was detecting those "all the time" because I have a hard time believing that there are a lot of deliberate hardware compromises in the field, and an even harder time believing that these are easily detectable. I can believe that your friend finds non-deliberately-introduced hardware vulnerabilities all the time, but that is not the same thing.
      - nickpsecurity 10y ago
        Oh no. You're assuming the hardware field is about simply producing hardware and that's it. He taught me that they (a) know R&D cost a lot, (b) assume patent trolls will hit them constantly so they obfuscate the hell out of everything anyway, and (c) therefore steal each others stuff in whatever way they can while not advertising specifics on how it works to avoid patent trolls. The result was all kinds of hardware companies were ripping off all kinds of others with constant remixes on top of a cat and mouse game for security that makes software security look lame (my impression). He said competitors even sometimes cloned the best stuff down to the transistors where even he had trouble telling the fakes of his company's parts. The defense was to make it hard to copy. They did crazy tricks on the digital level. He did stuff on analog level as well since his area was mixed-signal. His favorite technique was splitting the function between digital and analog since so few analog people existed to RE that stuff. He pointed out that digital tools couldn't even see analog stuff. Top that off with obfuscation to wild degrees. We stopped hearing from him after he changed employers, though. Some of the things he predicted came true. An example was the A2 backdoor which was the kind of analog subversion he told us happened regularly. Another included a fab compromise which his trust model got me thinking about and predicting in the abstract. That the guys statements started coming true too often in various ways among hardware people and in CompSci papers means I'm inclined to believe him that hardware is a scheming a business as he claimed it to be.
        lisper 10y ago
        OK... but none of that sounds like it would result in deliberately introducing security flaws of the sort under discussion here. Let's not forget the context of this discussion: "Some researchers have even speculated, especially since the disclosures by Edward Snowden, that commercial hardware sources could be subtly manipulated to make the codes easier to break by the U.S. National Security Agency or others." [Emphasis added] Obviously such attacks are possible, but are they likely? I can see how the cat-and-mouse game of IP protection would lead to all kinds of dirty tricks, but what would be the profit in introducing a backdoor that could be leveraged to break crypto or an RNG?
  - the_mitsuhiko 10y ago
    How so? Most hardware generators just run a cipher like AES. If you know the secret key you are in for the money.
tedunangst 10y ago
So the paper is called "Explicit two-source extractors and resilient functions". Not sure why the article goes out of its way to avoid actually telling you this, or why there's quotes from about seven people who aren't the authors. I think it's the same as the top link in further reading. The ACM cite for the STOC conference, which isn't linked, would be: http://dl.acm.org/citation.cfm?doid=2897518.2897528 http://dl.acm.org/citation.cfm?doid=2897518.2897528
nullc 10y ago
I'm amused by the paper's abstract stating that "explicit construction" when I can extract nothing so concrete from the paper (though a monotone boolean function on N bits resistance to any coalition of size N^(1-t) for any positive t sounds interesting to me-- achieving one for N^0.5 is well known and simple). I think I need a non-randomness extractor. :)
hannob 10y ago
The introduction is a very nice example of how a lot of academic cryptography works and what disconnect there is often between applied and academic cryptography. They quote Bruce Schneier, basically saying that nobody needs this and we already have plenty of ways to generate secure random numbers. This is countered with some handwavy arguments why you'd need them anyway that aren't really explained. The truth is: We don't need any theoretical work to generate better random numbers, because we know how to do it. All security problems about random numbers come from the fact that people aren't using the secure random number sources we have.
- more_original 10y ago
  A good understanding of randomness has much further implications than just generating random numbers for cryptography. This work is not indended as a practical method for generating random numbers, I think. Randomness is very important for algorithms. It is currently unknown if being able to make random choices adds expressive power to efficient algorithms (the P=BPP question). Being able to generate good random numbers from a weak source can lead to more efficient determinsitic implementations of randomized algorithms, for example.
  - hannob 10y ago
    Seeing it like this is totally fine. I.e. this is basic research to better understand the nature of random numbers. It just happens that all so often I see vague justifications of the form "Random numbers are important for crypto THEREFORE we need fancy random number thing X" - however the logical link between the two is not explained in detail (X may be quantum RNGs - or papers like the above). I won't blame anyone for doing basic research. I just don't like it if people advertise their basic research with practical implications that simply aren't justified.
amelius 10y ago
> The practical implications may be modest for now, though. Security specialist Bruce Schneier, for one, does not see any urgent need for better random numbers. Schneier helped create the widely used Fortuna pseudorandom-number generator, and says there are already many adequate sources. "In my world no one's worried about this," he said. "These systems already work" to provide secure communications when attention is paid to all of the other implementation details. "We have lots of problems; this isn't one of them." Is this true? It seems to me that /dev/random could use some serious speedup.
- mfukar 10y ago
  How fast do you need to read from /dev/urandom, and what throughput are you limited at now? Replace 'you' with the collective 'our applications' if you wish..
- nullc 10y ago
  /dev/random could be much faster if it was using state of the art techniques. Presumably it is difficult to change because of concern about bugdoors and whatnot-- an anyone who really needs it to be fast will implement those techniques in userspace and just use /dev/random to seed them.
rini17 10y ago
It's sad to see such immense effort to "extract" and "preserve" entropy, when anyone interested could have all the quality random numbers they need from simple and well auditable electric circuit. Somehow this is not in anyone's interest, just let's all use PRNG.
- nine_k 10y ago
  Isn't junction noise temperature-dependent? Aren't most hardware noise generators, like lava lamp, physically large?
  - rini17 10y ago
    Where did you get such impression that it must be either? There are many many possibilities, not just junction noise or lava lamps. Example: http://www.loper-os.org/?p=1427 http://www.loper-os.org/?p=1427
    - DanBC 10y ago
      I think Cardano uses avalanche noise. http://trilema.com/2013/snsa-first-product-the-cardano/ http://trilema.com/2013/snsa-first-product-the-cardano/ > E) Entropy generator. This is an avalanche noise array, with some sanity checking in place. Have I misunderstood?
  - Nomentatus 10y ago
    "Aren't most hardware noise generators, like lava lamp, physically large?" No: Spinthariscope, yielding RNG from fission. Safe, small.
  - nullc 10y ago
    > Isn't junction noise temperature-dependent? Part of the point of entropy extractors is being able to extract entropy from biased sources (even adversarially biased ones, in the case of multi-source or seeded extractors).
- Ar-Curunir 10y ago
  While the supposed practical application is not well-founded, this is a very important advance in the theory of pseudorandomness.
halma 10y ago
Does it relate in any way to Von Neumann's trick[1] to create a fair coin from a biased one? In short: if you don't trust the fairness from possibly biased coin flips, then don't look at individual outcomes in a sequence of (H)eads or (T)ails, but only at H,T or T,H combinations. [1] https://en.wikipedia.org/wiki/Fair_coin https://en.wikipedia.org/wiki/Fair_coin

96 points by mmastrac 10y ago

> Some researchers have even speculated, especially since the disclosures by Edward Snowden, that commercial hardware sources could be subtly manipulated to make the codes easier to break by the U.S. National Security Agency or others. Speculated!? I think it's pretty well established by now that Dual_EC_DRBG was intentionally weakened. --- Abstract, etc.: http://eccc.hpi-web.de/report/2015/119/ http://eccc.hpi-web.de/report/2015/119/ Paper (PDF): http://eccc.hpi-web.de/report/2015/119/revision/2/download/ http://eccc.hpi-web.de/report/2015/119/revision/2/download/ Related article from 17 May 2016: "Academics Make Theoretical Breakthrough in Random Number Generation": https://threatpost.com/academics-make-theoretical-breakthrough-in-random-number-generation/118150/ https://threatpost.com/academics-make-theoretical-breakthrou...

nickpsecurity 10y ago
Concretely proven thanks to Edward Snowden leaking BULLRUN and Core Secrets: http://www.dcssproject.net/bullrun/ http://www.dcssproject.net/bullrun/ https://theintercept.com/2014/10/10/core-secrets/ https://theintercept.com/2014/10/10/core-secrets/
lisper 10y ago
Dual_EC_DRBG was software, not hardware. A hardware compromise would be much (much!) harder to detect.
- nickpsecurity 10y ago
  Not necessarily. The hardware guy that got me started on all that was detecting them all the time. Some were really hard but others were obvious once the veil was pulled back. He said he stayed doing that sort of thing as did many others. Constant cat and mouse game. Your statement is true for software people where it will be anywhere from challenging to impossible for them to detect the hardware subversion.
  - lisper 10y ago
    I'm using the word "compromise" to mean the deliberate introduction of a vulnerability. I have a hard time believing that your friend was detecting those "all the time" because I have a hard time believing that there are a lot of deliberate hardware compromises in the field, and an even harder time believing that these are easily detectable. I can believe that your friend finds non-deliberately-introduced hardware vulnerabilities all the time, but that is not the same thing.
    - nickpsecurity 10y ago
      Oh no. You're assuming the hardware field is about simply producing hardware and that's it. He taught me that they (a) know R&D cost a lot, (b) assume patent trolls will hit them constantly so they obfuscate the hell out of everything anyway, and (c) therefore steal each others stuff in whatever way they can while not advertising specifics on how it works to avoid patent trolls. The result was all kinds of hardware companies were ripping off all kinds of others with constant remixes on top of a cat and mouse game for security that makes software security look lame (my impression). He said competitors even sometimes cloned the best stuff down to the transistors where even he had trouble telling the fakes of his company's parts. The defense was to make it hard to copy. They did crazy tricks on the digital level. He did stuff on analog level as well since his area was mixed-signal. His favorite technique was splitting the function between digital and analog since so few analog people existed to RE that stuff. He pointed out that digital tools couldn't even see analog stuff. Top that off with obfuscation to wild degrees. We stopped hearing from him after he changed employers, though. Some of the things he predicted came true. An example was the A2 backdoor which was the kind of analog subversion he told us happened regularly. Another included a fab compromise which his trust model got me thinking about and predicting in the abstract. That the guys statements started coming true too often in various ways among hardware people and in CompSci papers means I'm inclined to believe him that hardware is a scheming a business as he claimed it to be.
      - lisper 10y ago
        OK... but none of that sounds like it would result in deliberately introducing security flaws of the sort under discussion here. Let's not forget the context of this discussion: "Some researchers have even speculated, especially since the disclosures by Edward Snowden, that commercial hardware sources could be subtly manipulated to make the codes easier to break by the U.S. National Security Agency or others." [Emphasis added] Obviously such attacks are possible, but are they likely? I can see how the cat-and-mouse game of IP protection would lead to all kinds of dirty tricks, but what would be the profit in introducing a backdoor that could be leveraged to break crypto or an RNG?
- the_mitsuhiko 10y ago
  How so? Most hardware generators just run a cipher like AES. If you know the secret key you are in for the money.

tedunangst 10y ago

So the paper is called "Explicit two-source extractors and resilient functions". Not sure why the article goes out of its way to avoid actually telling you this, or why there's quotes from about seven people who aren't the authors. I think it's the same as the top link in further reading. The ACM cite for the STOC conference, which isn't linked, would be: http://dl.acm.org/citation.cfm?doid=2897518.2897528 http://dl.acm.org/citation.cfm?doid=2897518.2897528

nullc 10y ago

I'm amused by the paper's abstract stating that "explicit construction" when I can extract nothing so concrete from the paper (though a monotone boolean function on N bits resistance to any coalition of size N^(1-t) for any positive t sounds interesting to me-- achieving one for N^0.5 is well known and simple). I think I need a non-randomness extractor. :)

hannob 10y ago

The introduction is a very nice example of how a lot of academic cryptography works and what disconnect there is often between applied and academic cryptography. They quote Bruce Schneier, basically saying that nobody needs this and we already have plenty of ways to generate secure random numbers. This is countered with some handwavy arguments why you'd need them anyway that aren't really explained. The truth is: We don't need any theoretical work to generate better random numbers, because we know how to do it. All security problems about random numbers come from the fact that people aren't using the secure random number sources we have.

more_original 10y ago
A good understanding of randomness has much further implications than just generating random numbers for cryptography. This work is not indended as a practical method for generating random numbers, I think. Randomness is very important for algorithms. It is currently unknown if being able to make random choices adds expressive power to efficient algorithms (the P=BPP question). Being able to generate good random numbers from a weak source can lead to more efficient determinsitic implementations of randomized algorithms, for example.
- hannob 10y ago
  Seeing it like this is totally fine. I.e. this is basic research to better understand the nature of random numbers. It just happens that all so often I see vague justifications of the form "Random numbers are important for crypto THEREFORE we need fancy random number thing X" - however the logical link between the two is not explained in detail (X may be quantum RNGs - or papers like the above). I won't blame anyone for doing basic research. I just don't like it if people advertise their basic research with practical implications that simply aren't justified.

amelius 10y ago

> The practical implications may be modest for now, though. Security specialist Bruce Schneier, for one, does not see any urgent need for better random numbers. Schneier helped create the widely used Fortuna pseudorandom-number generator, and says there are already many adequate sources. "In my world no one's worried about this," he said. "These systems already work" to provide secure communications when attention is paid to all of the other implementation details. "We have lots of problems; this isn't one of them." Is this true? It seems to me that /dev/random could use some serious speedup.

mfukar 10y ago
How fast do you need to read from /dev/urandom, and what throughput are you limited at now? Replace 'you' with the collective 'our applications' if you wish..
nullc 10y ago
/dev/random could be much faster if it was using state of the art techniques. Presumably it is difficult to change because of concern about bugdoors and whatnot-- an anyone who really needs it to be fast will implement those techniques in userspace and just use /dev/random to seed them.

rini17 10y ago

It's sad to see such immense effort to "extract" and "preserve" entropy, when anyone interested could have all the quality random numbers they need from simple and well auditable electric circuit. Somehow this is not in anyone's interest, just let's all use PRNG.

nine_k 10y ago
Isn't junction noise temperature-dependent? Aren't most hardware noise generators, like lava lamp, physically large?
- rini17 10y ago
  Where did you get such impression that it must be either? There are many many possibilities, not just junction noise or lava lamps. Example: http://www.loper-os.org/?p=1427 http://www.loper-os.org/?p=1427
  - DanBC 10y ago
    I think Cardano uses avalanche noise. http://trilema.com/2013/snsa-first-product-the-cardano/ http://trilema.com/2013/snsa-first-product-the-cardano/ > E) Entropy generator. This is an avalanche noise array, with some sanity checking in place. Have I misunderstood?
- Nomentatus 10y ago
  "Aren't most hardware noise generators, like lava lamp, physically large?" No: Spinthariscope, yielding RNG from fission. Safe, small.
- nullc 10y ago
  > Isn't junction noise temperature-dependent? Part of the point of entropy extractors is being able to extract entropy from biased sources (even adversarially biased ones, in the case of multi-source or seeded extractors).
Ar-Curunir 10y ago
While the supposed practical application is not well-founded, this is a very important advance in the theory of pseudorandomness.

halma 10y ago

Does it relate in any way to Von Neumann's trick[1] to create a fair coin from a biased one? In short: if you don't trust the fairness from possibly biased coin flips, then don't look at individual outcomes in a sequence of (H)eads or (T)ails, but only at H,T or T,H combinations. [1] https://en.wikipedia.org/wiki/Fair_coin https://en.wikipedia.org/wiki/Fair_coin