Pure Randomness Extracted from Two Poor Sources | Hacker News Reader

Pure Randomness Extracted from Two Poor Sources

cacm.acm.org

96 pointsmmastrac38 comments

> 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/

Paper (PDF): 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-breakthrou...

Concretely proven thanks to Edward Snowden leaking BULLRUN and Core Secrets:

http://www.dcssproject.net/bullrun/

https://theintercept.com/2014/10/10/core-secrets/

Dual_EC_DRBG was software, not hardware. A hardware compromise would be much (much!) harder to detect.

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.

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.

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.

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?

I remember reading that the Linux kernel does not use Intel's hardware RNG alone for /dev/(u)random precisely because of concerns that Intel has backdoored the RNG.

Yes, that's true, and that is a legitimate concern. I personally would not trust Intel's RNG because it is implemented in a way that deliberately hides some of the underlying implementation in a way that would make it impossible to tell if it's backdoored. That is my original point: it is much harder to tell if hardware has a back door than software.

But does this not provide an example of an intentional backdoor in a hardware RNG?

I'm actually going to be diving into the literature on hardware verification, with a focus on how to design IP that can be objectively verified by a third-party. If I find something good, I might even do my PhD on this topic.

This is the kind of tangential thinking tptacek apparently fell for in the BitBabbler discussion. While they were talking Intel RNG's, I was focusing on the fact that Intel advertises a chip-level backdoor w/ its own TCP/IP stack & MCU that listens even when CPU is shutdown. It's called AMT. That he knew about it but focused on risk of their TRNG when whole chip is backdoored is beyond my understanding. Here it is in case you weren't familiar with its specifics:

https://en.wikipedia.org/wiki/Intel_Active_Management_Techno...

Also, as in my recent reply to lisper, the hooks that make it work are probably in all the chips of any family containing at least one with that technology. That's to reduce mask and production costs. They might be able to remotely activate it but can't know cuz it's a black box. :)

> But does this not provide an example of an intentional backdoor in a hardware RNG?

I don't know. No one knows outside of Intel. That's the whole point.

In fact, it's possible that even inside Intel no one knows because a backdoor could have been surreptitiously inserted by a rogue engineer working for, say, the Chinese government, who has since left the company! I have no idea whether Intel's internal design review processes are thorough enough to prevent this. For someone who knew what they were doing and who was in a position to influence the design to insert a back door without being noticed would not be particularly hard.

> I might even do my PhD on this topic.

Good luck! Keep us posted.

Ah yes, the insider threat is probably the toughest issue to deal with. At this point, I guess we can only hope that the RNG isn't backdoored.

Thank you. I'll be sure to post something to HN once I've made some progress. That will take time though.

Just saw your line about HW verification. That was my last project. Mostly done with it. I came up with a few ways to do it but you always need or leak source. No way to do it with gates only so far. There's potential but I wouldnt trust it. The standard cells will take mutually-suspicious parties reviewing by eye with expertise in analog and RF.

Email me and I'll send you some stuff. Summaries first then anywhere from a few to a pile of papers with specifics.

Interesting! Thanks, that would be really helpful! I'll email you today.

I was thinking of somehow combining a form of signature computation at each level (layout, schematic, RTL) with some low-overhead logic sprinkled throughout the circuit. The issue is mainly how and where to place the logic, but I'm hoping to get some ideas as I read through prior work.

"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?"

You get paid directly by the parties wanting it. That's what Crypto AG did for NSA a long time ago. They weren't making enough money so they risked whole business on a large sum of money to cripple machines sent to specific parties. The Snowden leaks quite clearly say this is going on domestically and with foreign companies although not clear on what (i.e. hardware) they're sabotaging to break the crypto:

https://theintercept.com/document/2014/10/10/national-initia...

For the locals, they paid between $30-80 million in one time fees to "SIGINT-enable" them per other leaks. Foreign nation-states, esp China, stay doing this sort of thing but usually with human assets working for the company to plant stuff. Now back to hardware. You're probably having a hard time imagining how it would look or even make sense commercially outside a shady deal with No Such Agency.

The first example was a wireless communications in non-online device. The embedded system just needed a cheap SOC. The engineers decided on an integrated one that was used in budget mobiles and data collection since they were already getting them dirt cheap for the phones. The RTOS was of course an insecure one common in embedded. Totally justified by the fact it was an offline device. The device could be hit with a software flaw that would enable remote access or location tracking via that silicon users had no knowledge of. In this case, though, they were just doing it to save development time & maybe quarters to dollars on each device.

Hardware guy said this stuff wasn't unusual due to three trends in ASIC development:

1. Need to add features to increase competitiveness.

2. Need to reduce number of new designs or components to keep costs down (esp mask costs).

3. Need to offer multiple tiers of capabilities and pricing on products ideally not paying for each individual one.

Hiding existing functionality they already bought or built in others is the natural solution to this. It's why 3G chips might be in CPU's or MCU's (eg Intel's ARC) might be in chips you didn't know had them. The hard disk companies are one of few that got caught doing it in that it's cheaper to mass-produce (for example) 1TB platters for all HD's of given model than many different platters. They just had a firmware or hardware setting in the chip to make it pretend to be lower space that they charged less for. AMD's triple-cores were another that was more open & reasonable where they were quad-cores with one defective core. They just turned it off then sold them as cheaper triple-cores. On mobile side, Shenzhen takes the cake with them cloning, modifying, and reselling anything you can think of. Their fake iPhone hit the Chinese market before the iPhone did officially at a fraction of the price. I'll let you wonder of security implications of high-ranking laypersons in business using an iPhone without any of its protection mechanisms built-in to CPU & OS. This doesn't even count all the counterfeit Chinese chips in U.S. products and military gear DOD reported on.

The weaknesses are already there. They're there for commercial rather than surveillance reasons. Many benefit the surveillance state with those parties bribing or coercing the companies to enable them for SIGINT. In some cases, like with RSA, they introduce backdoors directly for money that had no plausible explanation of benefit. Intel's chip-level backdoor, AMT, is sold as great for management & runs even when CPU is "off." Probably nothing to worry about. ;)

Hardware business is shady, dude. I can't tell you who is attacking, how much, and so on. Whole industry is full of NDA's from all the shit they pull. It's a black box outside the things above that leaked out.

I don't really want to say this on Christmas but: Holy shit. (Actually, I'm in Australia at the moment where it is already December 26 so I guess that makes it OK.)

Well, Im glad the shocking reality of it hit you. Ive done my part. Wait till you dig into the fab problem. It wasn't a can of worms: more like an underwater warehouse of electric eels. Current stance is we're stuck with 350nm and up for verifiability by eye. Shell games otherwise.

I'm having to rethink my entire world view. I was operating under the assumption that lower-profile manufacturers like STM were (probably) trustworthy because they don't sell into the consumer market and so there would be more to be lost than gained for them to compromise their chips. I was hoping that the company would reckon that professional customers would have less tolerance for bullshit than consumers, and so if a compromise were discovered that could damage the company's reputation enough to put them out of business, so they would not take the risk.

But if what you say is true (and it sounds plausible to me) then you really can't trust anything any more. Even at 350nm, how do you know that the part you just bought conforms to the spec? You'd have to verify every single individual part. And given that someone has already demonstrated a hardware compromise using a single transistor, even a visual verification will not necessarily catch that.

One of my protoges and I have been discussing groups like STM specifically. We're very torn about it given their strengths on verification & tamper-resistance but increased odds of subversion. I mean, if tamper-resistant market is just a few players, then it would make sense for every major agency to focus on them more using all available techniques. Many also own a fab on older technology that they might be consolidating on for cost reduction given how price-sensitive their chips are. Extra risk. It's still unknown to us far as those companies go.

"then you really can't trust anything any more"

Yep. My recommendation was security through diversity and obscurity at least on the hardware end. Plus developing open hardware and safe methods for making it.

"Even at 350nm, how do you know that the part you just bought conforms to the spec? "

250nm was the point where we stopped being able to see the components visually in a microscope. The 350nm or higher can be verified visually against an expected image/layout. You'd order a pile then verify a random percentage like other things. I also thought that image recognition tech could be trained to do it for you after enough samples come in from a given fab. At least, capture all the common stuff that should be there showing it to you. Leaves the rest to be inspected manually to see if it's a defect of the process or something malicious. Additionally, I was going to use it as the TCB for superior, modern chips that do heavy lifting on untrusted computation but get mediated by TCB chip.

For advanced stuff, there's companies like ChipWorks that tear them down for what's probably a fortune. There's also possibility of using your own eBeam workstation or whatever to print them plus obscuring whose using it. The printing and packaging systems probably cost millions even for 65-90nm. If you can do 65nm, then we're good as my Core Duo 2 was printed on that... not even best one can do... with it lasting 8 years of application bloat still performing well. So, 65nm is where we can stop if we find a way to produce that in a trustworthy way.

Note: Verification side works this way as you might keep the CPU or whatever small enough to verify samples from a fab with those workstations that can handle it. Similarly obfuscated, open software, whatever. Seems easier to control & create the chips instead of just verifying them.

Last idea was to get money together to do a FPGA architecture, regular and antifuse, on most cutting-edge node possible. Alternatively, raise money by interested parties to buy Achronix that has 1.4GHz (or similar) FPGA's with 1+ million slices, 10Gbps networking, etc. Idea being the FPGA is open, it's sold at cost by nonprofit, it's periodically verified by various parties, open tooling based on eg Qflow targets it, and it turns into whatever design we need. Gotta verify one, big-ass thing that is mostly same, symmetrical shapes all over with a few custom things (eg I/O). My hardware guy partly inspired this by saying go for the most cutting-edge node because PhD's can barely get them to work much less do clever, stealthy subversions on black boxes.

Note: Similar plan to boost open hardware by buying eASIC and their single-layer programmability. FPGA idea can be done that way, too, where the masks are verified by various parties and then monitored by them.

So, there's some ideas for this. I'm defaulting on 350-700nm option as (a) verifiable by eye, (b) cheapest to make masks for with MOSIS et al, and (c) gotta start somewhere with at least one thing I can trust. Probably make a Forth- or JOP-like processor to keep number of gates down much as possible. Earlier fabs also had fewer components available to print in terms of their categories. Less stuff to train eyes or computer vision on.

How so? Most hardware generators just run a cipher like AES. If you know the secret key you are in for the money.

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

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.

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.

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.

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. :)

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.

Isn't junction noise temperature-dependent? Aren't most hardware noise generators, like lava lamp, physically large?

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

I think Cardano uses avalanche noise.

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?

"Aren't most hardware noise generators, like lava lamp, physically large?" No: Spinthariscope, yielding RNG from fission. Safe, small.

> 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).

While the supposed practical application is not well-founded, this is a very important advance in the theory of pseudorandomness.

I reacted mostly to the Schneier bit, and similar assertions, that real RNGs aren't so necessary after all.

> 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.

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..

/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.

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

Reply on news.ycombinator.com