Shared publicly  - 
 
I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction.   To quote from the article below:

"By this year, the Sigint Enabling Project had found ways inside some of the encryption chips that scramble information for businesses and governments, either by working with chipmakers to insert back doors...."

Relying solely on the hardware random number generator which is using an implementation sealed inside a chip which is impossible to audit is a BAD idea.
641
304
Carlos Lopez's profile photoLeon Nardella's profile photoAaron Toponce's profile photoClaire Farron's profile photo
259 comments
Alan Cox
+
5
1
2
1
 
And I wonder how much they lean on the binary distro providers that have a major US presence.
 
+Theodore Ts'o I seem to recall facing the same pressure, RE rngd "it's pointless when you just have a CPU instruction"
Alan Cox
+
49
50
49
 
+Jan Wildeboer if I was the US government in that position I would make damn sure it was. It's used by all the worlds major banks, and by agencies like GCHQ.

So its hugely valuable as a target against financial fraud, and against other spy agencies (and its very clear the US spy on their 'friends')


Remember we still don't know if the Android rng fiasco was a "bug"
 
This is why being able to do reproducible builds ala rPath is so important.  Being able to demonstrate that binaries correspond to the sources in a way that any one can verify is very important.

Yes, or you could build all of the sources from scratch ala Gentoo, but realistically most of the enterprise users (think: I/T staff being paid minimum wages because at an auto company or an insurance company, I/T is the lowest of the low on the organizational totem pole) aren't going to willing or able to do that.
 
+Alan Cox If I were the NSA, and I wanted to gimmick an RNG, whether it be the one inside the Intel chip or the Android build, it would be a counter encrypted by an AES key known by the NSA.  (Why AES?   Because RDRAND is documented as using AES in its final whitening stage; so someone taking a quick look at the RDRAND implementation would be expecting AES).   The rng bug in Android was too easy to exploit to be something that the NSA would do, IMHO.....  

After all, the NSA doesn't want the Chinese using the same hole that they might have created --- better that the MSS have to work at it --- you know, by getting their own system administrator working at Dell and Booz Allen to rob the NSA blind.   :-)
 
+Theodore Ts'o re Gentoo: Brian Kernighan Ken Thompson showed decades ago that you can't just recompile everything from source and be sure that the binaries correspond to the source.
 
Wow this is worse than my worst nightmares. How can any sovereign nation use any modern computing equipment in a security related environment?
 
+Theodore Ts'o  RE reproducible builds:  bitcoin has been an innovator in this area.  Due to the danger of a trojan stealing your private keys (==money), our built binaries are produced by gitian.  All three major platforms (linux, OSX, windows) are independently built by multiple bitcoin developers.  Each developer PGP-signs the hashes of the resulting binaries.  Bitcoin releases do not ship until multiple signatures are obtained for the same hash (thus byte-for-byte identical).

In another G+ thread covering this same topic, +Michael K Johnson mentioned rPath's deterministic build technology, and commented that "the open source world yawned."  That is sad.

We have proven with bitcoin software that, with multi-party agreement and deterministic build software, it is very possible to create a trusted, provable build process.

We had not had as much success getting users to verify the wonderful PGP signatures we create, alas...
 
+Noah Friedman You can create conditions where multiple parties may independently confirm a build production, given a git source code commit ID.
 
+Jim Gettys That's exactly the example I was thinking of, and my misattribution was a braino.  Thanks for the correction.
 
So I guess people really shouldn't use AES either as they clearly worked on that too. Threefish as new default, anyone? DJB clearly isn't a big fan of the US Government (he sued them once and won) so maybe Cryptobox is good too.
 
+Jeff Garzik Reproducibility does not imply correctness.  The implication from Ken Thompson's hack is that any toolchain that shares any common ancestry may be compromised and generate compromised artifacts, including later versions of the toolchain.
 
Also this is the first Snowden leak that makes me really really sad it's not Wikileaks but fucked up main stream press doing the reporting. Intentionally weakening encryption standards should be just as much a red line as using chemical weapons and the Times redacting itself and willingly leaving out details for me feels like the biggest betrayal imaginable.
The only reasonable action here is full disclosure and yes this will enable China to close their security holes but then again how can peace be guaranteed when in the end the NSA controls all military power in the world.
 
+Noah Friedman Certainly.  But that is no excuse for avoiding wide deployment of deterministic build technology in FOSS projects.
 
+Noah Friedman Reproducible builds are a necessary but insufficient condition. Yes, Reflections on trusting trust certainly made that clear long ago. The rPath technology that I helped build and +Theodore Ts'o referenced kept a full provenance chain, including (optionally) PGP signatures that could be tracked back through repository history. In a trust violation, once discovered, you could trace back to ascertain where it was introduced. It's one element of a defense in depth against this kind of subversion.

I also think this is a reason that having multiple independent compilers that are structurally very different (gcc/llvm) could give a potential security advantage. It's harder in practice to create a "rtt" attack that works simultaneously against two independently moving targets.
 
+Michael K Johnson <shameless-plug>The +LLVMLinux project is working on getting the Linux kernel building with llvm.</> I plan to quote your reasoning for having multiple compilers in my upcoming talks at LNCA/LPC/ELCE. It's always good to have another good reason to add to the list. :)
 
A few years ago I was pissed that nobody was doing FDE on Linux that was convenient by tying it to TPM chips.

I'm not so pissed now! I will keep typing my long passphrase, thankyouverymuch.
 
I'm pissed that people keep telling people that there's an NSA back door in my RNG. There isn't.
 
+David Johnston With respect, the problem is your statement is one that can't be proven.  This is the advantage of open source code versus something sealed in hardware.   So even if it is safe, from the perspective of perception and Linux's reputation, it's better that we not make that assumption.

Make no mistake, I'd much rather that we have RDRAND than not have it.   I devoutly wish that ARM chips had a hardware random number generator that we could rely on, and so I'm very glad RDRAND is in the newer Intel CPU's.  I just don't want to depend on it as the only source of randomness for my crypto needs.

And even if there is no back door in your RNG, how can we be sure that your RNG is what actually ended up getting shipped in the chips that ended up in consumer's hands?  By its very nature, it's hard to test that an RNG is working as designed.  You can try to do statistical tests, but a counter encrypted by a key known to the NSA will pass the statistical tests.

At least, with open source, people can recompile their software, and while we do need to worry about trojan'ed compilers, there are ways around that problem.   But in terms of a potential back door in the hardware, there's really nothing we can do.
 
I'm not quite sure how much verifiability you want.  Every time something of this nature comes up, I'm reminded of Ken Thompson's C compiler/login hack.  Even if you Gentoo'ed everything, how are you going to ensure to yourself the provenance of the copy of the GNU toolchain you have?

What do you want to do?  Be able to go into a chip fab yourself to examine everything which goes into making your microprocessor and all peripherals (NB, SB, RAM, NIC, whatever else) so you can be sure your CPU isn't cryptographically screwing you by leaking enough info to the NSA?  Such a level of scrutiny I suppose in theory would be nice, but at some point, I think you have to back up and settle on some level you're going to trust the stuff people give/sell to you in good faith.  With that level of suspicion, even things like your NIC which might deliver your gcc or g++ could be handing you the answers you want to see on say a Web page, such as the published SHA hash of said gcc package, rather than the true answers.  It's kind of frightening to think of all the possible parts in the chain which could be messin' with you.
 
Oh, I should add that just today I had to fight back an attempt by a Red Hat engineer to add a configuration option to blindly trust RDRAND and bypass the entropy pool: https://lkml.org/lkml/2013/9/5/212

The timing was particularly ironic....
 
+Joe Philipps If the NIC card is trying to play games by supplying the a gimmicked gcc tarball when you try to download it, this is the sort of thing which is much easier to detect.   Especially if the releases are digitally signed.   (There's a reason I independently sign e2fsprogs releases using my PGP key...)   The problem with a HWRNG is that it's extremely difficult to independently verify correct operation using black box testing.

Yes there are scary hardware-based attacks that might be possible.  For example, Jitterbugs[1] installed in between the USB interface and your keyboard, or installed in your Lenovo laptop courtesy of the MSS is a pretty scary possibility.   But even something as scary as this is something that could be subjected to testing, and if there was funny business going on, there is a very high probability that someone would notice (by looking for timing irregularities in the responsiveness of the keyboard controller), and that would destroy Lenovo's brand.  So hopefully this would be a deterrent against Lenovo doing something dastardly like this (not that someone shouldn't try to independently verify this, of course!).

[1]  Gaurav Shah, Andres Molina and Matt Blaze, Keyboard and Covert Channels, paper published at the 2006 Usenix Security Symposium. https://www.usenix.org/legacy/event/sec06/tech/shah/shah.pdf

The problem with a gimmicked HWRNG hidden inside an Intel CPU is that there literally is no way for us to be able to know for sure, short of having a whistleblower like Snowden leak the information out to the press.  For that reason, it's better not to assume that it is trustworthy, when it might possibly not be.
 
It is for this line of reasoning that crypto systems fail. We keep cutting out the bits we don't have absolute trust in until there's no source of entropy left. Then we increase the attack surface by mixing in a non entropic source into a huge pool kept in memory. The theory is all very comforting, but calling the only solid entropy source on your platform 'gimmicked' without considering the much more likely attack vectors is denying users the security features they paid for.
 
 
+David Johnston Linux's random driver is designed such that mixing in partially entropic or fully non-entropic data won't hurt and could help. If you believe otherwise, I await your proof/evidence of how that might be. 
 
+David Johnston as Linux did with the entropy contribution from network devices several years ago.  Problem is, on a home router you have very few sources of any entropy.  The enemy of the good is the perfect...
 
The path from entropy gathering device to device driver to rngd to linux API to the random pool to the file system interface to the application is long and winding. The benefits of bypassing that path and delivering random numbers right into the register space of the application are those of attack surface reduction and performance. The entropy distillation and PRNG algorithms of the kernel are not 'wrong' they are just in the wrong place for a security model that admits that memory and timing attacks are real and present dangers.

Mixing RdRand output into the kernel pool may improve the kernel pool but it certainly does not improve the RdRand security model. It subjects it to the same memory and timing attacks that the pool is already subject to. If mixing were to take place it would be more logical to mix the output of the kernel random service with a RdRand result, in the registers of the application, without the RdRand result ever leaving the register space. The AES instructions enable robust mixing.

As it stands I quit relying on /dev/random to not block. It simply isn't that reliable across multiple platforms, distributions and kernel versions and so /dev/random comes second in a chain of sources with RdRand at the top in my random library.
 
 
+Jim Gettys The problem with modern data center deployments is that the kernel probably is running in a VM with quantized interrupt timing, SSDs and no human interaction IO, so all sources of entropy are gone and the kernel doesn't even know it. This is the way technology is moving. It is necessary to bring something to the table that punches through the VM to deliver entropy to applications bypassing all the attack vectors and unquantifiable alternative entropy sources that fail in these situations.
 
+David Johnston and by removing that from the network drivers, it deprived embedded devices such as your home router from any useful source of entropy.  You should always mix potential sources of entropy; it can't hurt, and may help.  

These embedded processors also lack any hardware RNG; so by banishing that source of entropy, in one stroke, home routers and other embedded devices became much less secure.

Stop thinking of the world as just data centers.  It's not....  There are many more embedded devices out there than there are data center machines...
 
I don't work for all chip vendors. But I am putting my RNG into every new Intel chip, from server to desktop to laptop to phone chips. It was one of my goals to encourage other device vendors to do the same so the world can be a more secure place.
 
+David Johnston If you are worried about an attacker who can read arbitrary kernel memory, then security of the /dev/random pool is the least of your worries.   The attacker will then just grab the private key that you're generating.

As far as /dev/random blocking, what most software systems use is /dev/urandom, which means that in practice, the entropy estimator (which I freely admit is at best a guess and very rough) is out of the picture.   What's more important that we've mixed enough entropy in from as many sources as possible such that if there is a failure in any of the sources, hopefully that will be mitigated by the fact that we are mixing in entropy from other sources.

So where you see "a larger attack surface", I see "a more robust design that doesn't require us to blindly trust that Intel didn't get paid off by the NSA" (or perhaps the CEO was personally threatened with jail time under secret law if he didn't cooperate; and maybe you don't even know about how your RNG was subverted by the order of the US government).   And if you think this could never happen in the US, Exhibit 1: Lavabit.
 
I've always thought that depending on the system RNG for anything but a partial entropy source in seeding your own PRNG was sloppy. And using your human operator for entropy is always best. Here, scribble on this screen, move your mouse around a bunch, hit keys until I tell you to stop...
 
+David Johnston look, I want RNG's in all hardware going forward; but as Ted notes, it is much more robust to have other sources of entropy, and removing such sources, even before sources of entropy such as hardware rng's are available was lunacy... For an unlikely corner case, most systems were made much less secure.

 
+Joe Philipps Rebuild the GNU toolchain from scratch using a bootstrap compiler written in your own dialect of Forth, of course! And don't forget to change the base of the dictionary every time you key the Forth interpreter in from memory.
 
+Theodore Ts'o I've examined my own RNG with electron microscopes and picoprobes. So I and a number of test engineers know full well that the design hasn't been subverted. For security critical systems, having multiple entropy sources is a good defense against a single source being subverted. But if an Intel processor were to be subverted, there are better things to attack, like the microcode or memory protection or caches. We put a lot of effort into keeping them secure, but as with any complex system it's impossible to know that you've avoided all possible errors, so maintaining the security of platforms is an ongoing battle.
I got into the RNG business because I needed random numbers for my crypto protocols and I wasn't at all satisfied with the options. It turned out to be way more involved than I expected.
But the implication at the top of this thread is that we were leaned on by the government to undermine our own security features. I know for a fact that I was not leant on by anyone to do that. X9.82 took my contributions and NIST is taking about half my contributions, but maybe they're slowly coming around to my way of thinking on online entropy testing. If I ultimately succeed in getting those specs to be sane, we better hope that I am sane.
  
 
+Peter da Silva Oh, certainly.  That was part of the advice I was giving +Jim Gettys when I talked to him this afternoon.  Home routers should wait until the very last moment to generate their private keys; that is, after the user has connected to the device and has started configuring the device.   That way we can start mixing some randomness that is coming from user interaction.  What's really insane is devices who think the first thing they should do when they boot up is to create an RSA key, before we have a chance to capture entropy from the environment.  (And ARM and MIPS CPU's don't have RDRAND, so the only thing we can do is to get entropy from the environment.)
 
+Peter da Silva the problem is, you can't do a dns lookup securely. if you want to run dnssec, you need to have two things: correct time within a day, and you need a cert. no random bits, no cert gets generated.... Even with random bits, you still have to get the time, but you have no TOY clock and no battery. So you can't get bits from the network to use for random bits.

But as a old forth hacker, maybe I should start by writing a C compiler anyway ;-).
 
About the same way you quantify the entropy from someone scribbling on the screen. How expensive is it to get a million times as many bits as you think you need?
 
+David Johnston The only implication I wanted to make is that Snowden leaks indicated that the US government had leaned on at least one chip maker.  We don't know which one(s).   For that reason, I think it's a bad idea to (as that misguided Red Hat engineer tried to do today) make it optional to blindly trust the hardware rng.  Maybe Intel's RNG hasn't been tampered with.   But maybe Qualcom's chips have.  That's the point:.   We don't know.

I hear what you've said, but when the DNI Clapper lied in front of Congress and wasn't prosecuted for perjury after giving "the least untruthful answer possible" (his words), it's better if we don't have to trust the word of a single human being, or trust a single entropy/rng source, but rather have a design which can be independently verified and has an open, auditable implementation.
 
+Theodore Ts'o just would like to say thank you for holding the line and fighting in this battle! 
 
I was under the impression that people were asking for a policy choice. Today I choose by either executing RdRand or reading /dev/[u]random. OpenSSL does the same thing. Many crypto libraries do the same thing. It would be nice for a certain class of user to have the freedom to make that choice through configuration rather than having to write their own software or check library versions.
CRI came and did a very deep audit and published a paper (FWIW we ultimately fed all their advice back into the design because they were right).  The certification process is very white box and we've published the circuit diagrams and algorithms. 
Silicon isn't software. There are limits to how much use publishing ever more detailed information is if people won't believe that the information isn't representative of the thing on the chip.
When you dig into the pros and cons, opening up the insides for arbitrary inspection opens up a can of security worms much bigger than we otherwise face.
 
I have my opinions about the 'device manufacturer' thing. But I don't know I'm right and I'm not pointing fingers.
 
Ted, all 'quantum' solutions raise my snake oil antennae. Ultimately all our understanding of the sources of entropy comes from quantum physics. Any old noise will do as long as your method of sensing it and turning it into bits is subject to min-entropy analysis and online testing. The standards could be a lot better in encouraging good behavior. Making RNG hardware is easy, making it well is hard work.
 
+Jim Gettys If the DNS server in your data center is compromised, then it's probably game over no matter whose RNG you're using. If the application isn't a data center, then you can wait and leave the generation of keys until you have access to reality, and can sample human typing or birdsong or gearshift timing or whatever.

Re: C compilers in Forth... I once wrote a compiler for a cross between Forth and C that I called "Ratforth". I wish I still had it, even if 21 year old me was probably writing horrid code (as well as making horrid puns), but when I finally had a chance to slot the RL02 that I thought had my old account on it, I found that I'd grabbed a sysgen pack by mistake.
 
+David Johnston the fact that you checked your chip with microscopes or whatever is not relevant.  We don't have a hope in hell of doing that.  (That does not mean most of us have a hope in hell of understanding the code that produces /dev/random, but at least it's possible).

All your posts sound like you'd like us to take your word for it.  With absolutely no offense intended (how could I, since I don't even know you), I'd say that's about the silliest thing I ever heard.
 
I understand that I'm in the privileged position of being able to understand and examine my own design, where most people cannot.
What I would like is for people to stop presenting the straw-man argument that the government leant on someone, so they must have subverted my RNG design. I would like (and we've made this argument to the kernel developers) that there should be a policy option so people can choose to benefit from the hardware they paid for and choose to trust, or can decide to be more conservative and require the kernel to mix more sources.
 
Wouldn't it be safer to call rdrand directly instead of context switching to read from /dev/random anyway?
 
Kernel hackers are software guys, who are trained by bitter experience to not trust:  (a) BIOS / firmware or (b) hardware.  One must assume that either or both of these is flaky or failing or compromised, and requires software to rescue or at least notice this.  :)
 
+David Johnston my question was aimed at the option of mixing rdrand into the entropy pool vs. using it directly; the latter case could just be a user-level call in a library routine. No kernel option needed to toggle.

(I suppose this might be a poor idea to rely on in a VM where the emulator could trap the instruction and provide bogus data, though.)
 
+David Johnston  I never said that the NSA had definitely subverted your design.  Just that it is prudent and responsible to acknowledge that they might have done so, and so we need to make sure the Linux kernel is robust against that kind of failure.  And remember, the random driver is generic code.  Even if Intel is clean, maybe AMD, TI, or Qualcomm were successfully leaned on by the US Government, and their chips are dirty.   We don't know, and we can't know.

As far as making it be an option to the user, I fail to see the benefit.   If you can't trust the kernel because the attacker can read arbitrary kernel memory, you're doomed anyway.   But unlike the proprietary intel chip, at least it's possible to audit the kernel to look for security breaches.  We can't do that with any hardware RNG.    So it's nothing personal, really.   To quote former President George H. Bush, "Not going there.  Wouldn't be prudent."
 
+Noah Friedman We are already mixing RDRAND into the entropy pool.   The switch in question being pushed by the misguided Red Hat engineer was to disable all other sources of entropy, and to just blindly trust RDRAND.   Yes, if you want to do that in userspace, userspace is certainly capable of making that choice.  And if they did, that's fine (although I think it's horribly misguided, especially given that we know at least one chip manufacturer was compromised by the NSA).

But if the userspace wants to do use RDRAND exclusively, they can.   Just leave me and the kernel out of it.    (And I'll probably avoid using said userspace program unless I can patch it.  :-)    Of course, such a userspace program would end up being x86 specific, which is perhaps why the Red Hat engineer wanted to tamper with the random driver.
 
Out of curiosity, anyone know off-hand if signed microcode updates can alter rdrand behavior? (Ignoring other instructions or signed ME payloads.)
 
+Will Drewry When you execute RdRand microcode fetches the number from the DRNG and presents it to the register. So arbitary microcode could do whatever it wanted. But that's true of any other instruction too. When you run on a CPU, you trust a whole bunch of behaviors within the chip to behave. The alternative is to buy your own factory and design team, but I hear that that is expensive.
 
+David Johnston  Thanks! That's roughly what I expected.  I mention it only because it there's a difference (to me, at least) between a fab-time subversion and an "on the fly" subversion of chip behavior.  Of course, hardware verification is ... not easy even without signed field updates.

(Edit: Of course, the difference is the remote-attacker versus the local-attacker with the trust boundary being a 2048-bit RSA key)
 
Thought Experiment: Imagine for a moment that you control a root CA certificate in everyone's browser, have a network tap device at the major Internet backbones, and can re-sign any SSL traffic on the fly using your root CA to man-in-the-middle any SSL / TLS encrypted services (HTTPS, SMTPS, etc). Now pause for a moment to consider the damage that will be done with this and how you would detect it. The SSL Observatory tries to do this, but it fails. There are numerous ways around avoiding detection. Further, there are ways to MITM / backdoor JavaScript libraries to compromise HTTP sessions without even worrying about SSL. You think this is not being done? Look at all the JS libraries you import into your browser sessions every day over HTTP from major websites.

Eventually you realize everyone and everything is pwned and you can't do a thing about it. The NSA knows this. We only have the illusion of privacy...
Ho ng
+
4
5
4
 
+Theodore Ts'o Can you even trust any machine instruction? A meaningful set of Internet services are running inside Amazon AWS virtual machines. NSA can compromise those virtual machines in some way, and RDRAND instruction can return some very interesting result. :P

US government was worried about those "Made in China" products. I am sure other countries will have the same feeling about "Made in USA" stuff.
 
Obvious questions department:  are there any established procedures for verifying / testing RNG quality?
 
+Edward Morbius Yes. There are a variety of test suites that attempt to determine if data is indistinguishable from random (a pass/fail test) E.G. Dieharder, SP800-22 and others. There are tests to estimate min-entropy (a quantitative measure) such as those in SP800-90B (the draft) and conventional statistical metrics, such as the chi-square test of randomness, average, serial correlation etc.
The trick is in knowing what sort of test is appropriate in what situation. This is not a small topic.
 
+Junio C Hamano -- It may work for the SSL cases, at a huge cost to user experience, but is still no help for HTTP (non-SSL) sourced JavaScript libraries that get MITMd in your browser...
 
What I'd like is for all my firmware and binary packages to be signed separately by groups in different jurisdictions (lets say US, China, Germany) and then I'd want to only accept stuff if they all agreed, that way it would be much harder for authorities in any one to inject a poisoned update.
 
+David Johnston can you publish the microscopic research you did as open data? Transparency and peer review is always A Good Thing. 
 
+David Johnston or even better: Can you put your RNG design under an Open Hardware License so we could maybe soon have RNG hardware for everyone at a low price? 
 
+Jim Gettys If BIND requires that you generate a certificate just to do DNSSEC lookups, someone needs to be fired / removed from the project for being incompetent.   That's like saying you need to have a private key in order to verify someone else's digital signature; that's just wrong.
 
+Kristian Hermansen Consider what it means if the NSA has to MITM every connection on a single tier1 provider's fiber running at hundreds of gigbits per second.   That's a huge amount of computing power, and more importantly, that has to be done on-site at the tier1 provider (since if you had to direct all of that traffic to the supercomputers at NSA's data center and then back, people would notice the increased latencies due to speed-of-light delays).   That's very different from having a passive tap which is hidden inside a closet at a tier 1's NAP.    We're talking about racks and racks of servers and all of the power and cooling for those servers.  That's not subtle, and it's not cheap.

So even if though the NSA has subverted a top-level CA and can MITM SSL certificates, it's still valuable to do SSL.   If they are going to violate our privacy, we should make them really work to do it.   That means enabling TLS over SMTP is a good thing, even if your cert is self-signed, or signed by some CA like CAcert.org.   It forces the adversary to do that MITM attack, and an active attacker is always easier to detect than a passive attacker, and an active attacker has to spend a lot more resources than a passive attacker.   If everyone enabled TLS, or some other unsigned D-H for all of their TCP connections, it wouldn't make it impossible for the NSA/GHCQ to invade our privacy in a bulk fashion --- but it would make it a lot more expensive, and a lot harder for them to do it covertly.
 
+Theodore Ts'o -- Of course you are correct that they wouldn't tap everyone due to resource issues. However, if you are on the NSA "watch list" -- maybe coincidentally because you replied to a mailing list email thread that was started by an international member of WikiLeaks (unbeknownst to you) -- then they may associate your Internet sessions for interception. The US law currently states that associates of suspected 'international persons of interest' may also be intercepted. So, when the NSA analyst puts into their PRISM query 'john.doe@wikileaks.com'/ 'john.doe.1234@gmail.com' and you happened to email on the tor-dev mailing list to 'john.doe.1234@gmail.com' with an X-ORIGINATING-IP of 1.2.3.4 ... then your future connections from 1.2.3.4 to encrypted.google.com may certainly and lawfully be intercepted (or siphoned from the provider directly via nsa.ftp.google.com) as you have communicated with a 'targeted international individual'. Sad, but true, story. And who doesn't unknowingly send emails to international suspected persons of interest on mailing lists? Surely anyone active in the open source community has done so. The fact that such an action lawfully allows for interception is the real issue. And that's where these targeted interceptions usually get leveraged. Just ask Jacob Appelbaum. Google handed over all his data to the gov because they were legally compelled to, even if Google employed a member of WikiLeaks on their own staff...
 
+Kristian Hermansen The fact that NSA's "3 hops" means 2.5 million is a different problem.    The point remains that if we all use TLS/DH it increases the cost for them to tap an individual's data connections increases significantly.  Maybe they could decide to tap every single open source developer's network connections, but that would still take a lot of resources.  And those of us who are more technically competent can at least try to do things like certificate verification/pinning.

BTW, while I was at Yosemite at a team-building event for my department at $WORK, I caught an attempted MITM attack against all connections between the Tenaya Lodge and all of MIT's centrally-managed IMAP servers (PO*.MIT.EDU).   How did I catch it? Because my IMAP client (http://isync.sourceforge.net) uses certificate pinning, and I investigated by using openssl s_client and dumping the (badly) forged certificate for po14.mit.edu,  I then worked around the MITM attack by using ssh socket forwarding, and confirmed that access via a different network path resulted in my getting the correct/expected certificate for po14.mit.edu.   Do I know who tried to do it?  No, but I actually kind of doubt it was the NSA, because the attack was so sloppy, both in how the certificate was forged, and the sloppiness in how the targetting was done (why attack all of MIT's IMAP servers, instead of just the one used by the person for which they were trying to steal the user's password / email)?
 
+David Johnston , wait, what did you say? "microcode"? So, you mean, Intel can subvert RDRAND post-distribution?
 
hmm as I understand it most TLS still doesn't do DH so they can do offline decryption with access to the private keys. I think deploying DH should be the first step. Anyone know how to check whether a site uses it? Also I'd guess the NSA probably does a lot of persuasion to keep people from using Diffie Hellman
 
+Samium Gromoff - Intel architecture - every instruction gets rewritten into cisc-like microcode early in the pipeline, it's been that way since, what, the 486 'cisc core' days.
 
+Niklas Schnelle Chrome-derived browsers will tell you what algorithm they're using in the bubble you get when you click on the padlock icon. You're looking for something with EDH in its' name.

You're also looking for something preferably without RC4 or CBC in its' name :-)
 
<Removed to not be political>
 
I guess I'm a pretty strict liberal than when I believe that secure communication should be a human right and yes that includes AlQaida as bad as they might be.
 
+Niklas Schnelle I don't think anyone disagrees with you about government accessing communications (with the possible exception of specifically-targeted, warranted investigations), but my point is that when you pass information through lots of hands in lots of ways you accept some degree of risk that someone along the way will read it.

I'm going to delete my earlier comment to avoid this thread becoming political rather than technical.
 
+Samium Gromoff , that's right. I don't know where field-correctable microcode began in Intel's processor line, but I know from personal experience it's been at least since the Pentium II. I would see something like "Applying microcode update [OK]" at each boot. I think it was a (Red Hat) package I installed, and I may have downloaded a file of those corrections from Intel; not sure (it was a LONG time ago).
 
Anyone have an opinion on the various user space entropy gathering daemons like audio-entropyd, video-entropyd, or timer-entropyd? I'd be really interested to read an expert's take.
 
Regarding Gentoo and the provenance of the source packages, we strongly prefer upstream signed releases and our package manager handles checksum verification. We are also encouraging (soon requiring) devs to sign their commits of ebuilds and source patches to the portage tree. In general, we care a lot about this for obvious reasons. It is also quite easy to test built packages for binary equivalence. 
 
Matthew, the entropy gathering daemons are fine algorithmically as far as I have seen. I'm wholly unconvinced by the way the kernel just trusts that the userland source isn't lying about how entropic it is. This is exactly one of the vectors thought which non entropic data gets tagged as entropic in low entropy devices. My hypothesis is that low rate, unqualified sources lead to systems that are designed for famine. I.E they have a huge entropy pool and stir any old crap into it. Hopefully the pool will become entropic to an adversary and its size will carry you through times of low entropy. The pool itself becomes the a great attack vector due to its size and permanence.
When you have an overabundance of entropy (RdRand's source is about 2.5Gbps) you use the smallest pool you can get away with (the width of the crypto function you are using to distil entropy) and refill it every time, before the user asks for another number. All EGDs are starvation mode designs. That's OK when you have limited sources but they are no substitute for having high throughput sources designed specifically for the purpose.
 
I would like to include any and all entropy gathering techniques into the rngd package.  It's silly to create a new daemon for each entropy source, and it divides programmer attention (many review rngd as it's a standard distro component, very few review audio-entropyd)
 
+David Johnston, do the current crop of processors (Core i5, Core i7, Xeon, etc.) have microcode update capabilities?  (I ask because I wonder if someone could load an update file into it to somehow influence the behavior of executing a RDRAND instruction.)
 
+David Johnston The rngd daemon is running as root or else we won't trust the entropy estimate, so the question is whether it is malicious (in which case you're toast anyway) or it's just wrong/mistaken.    That's a possibility, but ultimately, as I've said before, I'm not sure the entropy estimator is all that useful at this point.   It might have been useful to make sure that we don't hand out any random numbers until we had accumulated sufficient number of samples.  With the changes that we made last year, by the time userspace starts up, there shouldn't be a problem (or we have a kernel bug).

The bigger problem is situations such as how the in-kernel ASLR gets initialized super-early in the boot process, where we recently found a problem with the ARM platform.   But that's again a bug that we can fix by reinitializing the ASLR state once we have more entropy (which we do on x86) --- and long run, ARM hosts really need a HWRNG to be guaranteed to be present as part of their platform.
 
+Owen Shepherd ok I just looked at Facebook and Google and they both seem to use RC4 but at least with ECDH. I also beefed up my Cipher choices for SSH. Seems stupid that the default even in current SSH is aes-ctr, do you think blowfish-cbc or aes256-gcm is better? As I understand it gcm is combined authentication and cbc suffers from padding problems, are these relevant for blowfish too? And why the hell does SSH not have Salsa and Threefish and maybe some from ESTREAM? Seems stupid not to have a few more options at least with matching client/server versions...
 
For Solaris support if both RDRAND and the SPARC hyper privileged random register we choose to use them as entropy providers that feed into the main /dev/random which does its own mixing as per FIPS requirements. We assume the entropy being passed from any source outside the generator (especially from userspace even thought it requires all privilege) is 0 - we take it, mix it but don't increase our entropy count with it. I hope to be able to post the writeup on how it works on my company blog soon. 
 
+David Johnston Intel needs to release the schematics to the part(s) of the CPU that RdRand associates with. Don't hide behind patents. I want researchers to see whats going on inside of it, how the sausage is made.

If Intel missteps in anyway, witholds anything for even business reasons, I'm switching to completely open FPGAs as AMD is compromised as well I'll assume.

I know the software is open and I generalyl trust you, the maintainer. It's Intel I'm not trusting right now, and sadly....sigh I might as well get it out of the way Debians lost my trust, I can't trust Linus right now. Not with the way this was shoehorned into the kernel and that the chips aren't open.

Whats so shady about this is it's not a module I can enable or disable. It's baked into the kernel. It's how the kernel gets randomness.
 
+Mirosław Baran Thats not true it can be inferred from their major fuckups, like Debians OpenSSL quagmire. The guys still on the staff, the bug went unnoticed for two years, which means security staff incompetence or subterfuge. You don't make a boo boo that specific (2 lines) and bad, have it get okayed by a lot of people, have it be there for 2 years, then when found keep your admin privileges without there being collusion.
 
>Whats so shady about this is it's not a module I can enable or disable.

Making it a module you can enable and disable is exactly the request that Ted was 'resisting'. 
 
Does anyone have an opinion on haveged?
 
+David Johnston I respect you for standing behind your product after an uproar. Google/Facebook et al are silent in the face of revilations like this, or express feigned outrage just one time like Yonatan Zunger (Googler) , but when pressed for details after more rounds of leaks zip their lips.

Like I said, your code is kosher very probably. It's the hardware I'm not trusting right now.
 
+Paul Henning We published the circuit, the algorithms and referenced the specs (SP800-90 CTR-DRBG) it complies to. The sausage is there for all to see.
 
+David Johnston, people on this thread consider this not to be enough, as:
1. it's not the whole chain -- what of the silicon?
2. an element of the chain (microcode) can be subverted post-deployment
 
+David Johnston, unless "all" means "everyone with access to electron microscopes, picoprobes and tools required to peel crystal layers".
 
+Samium Gromoff "What of the silicon?" It's CMOS. The ES circuit is made from CMOS transistors. The schematic has been published. 
 
+Paul Henning My code is the hardware. I'm only making claims about the specific bit of hardware that I designed. There is nothing new here that I haven't argued elsewhere, like at IDF, the NIST RNG workshop, the published documents and at the pub.
 
+Paul Henning You do realize that +David Johnston is not the /dev/random maintainer, right?   He's the designer of the RDRAND implementation in the Intel CPU's.  (Some of your comments on G+ were a bit confusing.)

RDRAND is not the only source of randomness used for /dev/random.  It was at one point, but that's because the Intel engineers pushed a patch into the kernel.  Matt Mackall, the previous /dev/random maintainer, claimed to have "objected strenuously", but I saw no evidence of that in any of the mailing lists archives (and I do monitor LKML, so I should have seen it).  If he did "resist strenuously", it must have been done privately.  And although he claimed he "resigned", he never removed himself from the MAINTAINERS file, which is the normal way people resign.   He just stopped doing work.  I (and others) assumed he was just busy with other projects.   It was only when we needed to respond in a hurry and I discovered that Matt was basically inactive that I took over the /dev/random maintainership again.

If I had to guess, some Intel engineers included the change in one of the x86 git trees, and Linus just pulled them in, perhaps without even noticing what the implications were since he has to trust his lieutenants, and so there wasn't much discussion before they went into mainline.   I wasn't paying attention, since at the time, I wasn't the /dev/random maintainer, so I wasn't reviewing all of the commits affecting drivers/char/random.c --- but I would have noticed if there had been a "strenuous" discussion on LKML.

Bottom line is I don't think there was any malice.  The Intel folks were sure that RDRAND was perfect, and they honestly thought their changes were an improvement.  (They still do, and they're unhappy that I reverted that change.)   I'm a bit annoyed that if Matt resigned, or "objected strenuously", it appears from my perspective to have been done in a very passive-aggressive manner, and for him to make himself as the martyr who tried and failed to stop those dastardly Intel folks was a bit over the top IMHO.
 
+David Johnston, you are wonderfully insistent in your attempts to portray RDRAND-on-Haswell-as-shipped as the same stuff you designed.  This is even ignoring the microcode update issue, which is a separate can of worms.
 
+Theodore Ts'o I know what RdRand does :)

a very passive-aggressive manner ....You mean like Lavabit shutting down? That kind of mellow-dramatic marytrdom? Just playing devils advocate here.
 
With Lavabit, the CEO shut down the company down in a very public way.   I wouldn't call that passive-aggressive at all.  He took a brave stand for what he thought was right.  It might or might not have been legal, but that's a criticism of the Patriot Act, not of what he did.

Matt didn't resign publicly.  He (from my perspective) went AWOL, quietly, and only claimed to have resigned and to have "objected strenuously", years later, after the fact, and without any proof of this that I could find in the historical record.
 
+Samium Gromoff I'm saying nothing about microcode updates, because I know nothing about microcode updates. RdRand on Haswell is pretty much the same as RdRand on Ivy Bridge. It looked like my design when I tested it. I don't know anyone more qualified than myself on this very specific thing.
I highly recommend that people check that the microcode the OS is uploading is the standard issue code. Maybe the NSA cracked the signing algorithms, reverge engineered the chips and have uploaded their version into your machine. It would be a lot simpler than backdooring the RdRand hardware without my knowlege.
 
+David Johnston Maybe the NSA secretly ordered Intel to include the change denaturing RDRAND into some other microcode patch claiming to contain critical security fix which was officially issued by Intel; we can't know for sure whether or not they did that.  Compare and contrast that with a FDIV divide by zero bug.  That is something that we could test for and observe externally, unlike a gimmicked RNG.   Yes, I hear your objection that the NSA could have also gimmicked the microcode to screw over page table protections, or some such.   But that is much more likely to be something that could be noticed via people doing black box testing, and would require that they introduce exploit code into target computer to take advantage of the vulnerability.

If I were the NSA, I'd much rather compromise RDRAND, and then try to convince people that it's safer and faster to just use the raw RDRAND when creating session keys for IPSEC and GPG and SSH.  You wouldn't need to get compromised code into the target machines, other getting out a meme out to developers that using the output of RDRAND directly as a session key was somehow "best practice".   Wouldn't that be much easier than introducing a vulnerability into the page table handling, especially if the goal is to do bulk data collection, dragnet-style?
 
Addendum: with apologies to Matt, "lambda" on Hacker News found the mail thread in question where Matt resigned[1].  I completely didn't remember this mail thread.   Looking back at it, Matt's arguments were (and still are) a bit hard to follow, and it was never clear whether he really resigned or was throwing a temper tantrum.    Note that at one point in the mail thread, Linus did say: "Test it - or more reasonably - make it just one small part of the entropy pool.  But don't make it something heavy-weight, when the whole point of having the hardware is to make it light-weight."    

[1] http://thread.gmane.org/gmane.linux.kernel/1173350/focus=1173517

If you look at my git description, although I completely had forgotten about this earlier mail thread when I was hacking the /dev/random driver on July 4, 2012 at the top of the parking garage at the Boston Muesum of Science, while waiting for the Boston fireworks to start, the git commit description basically dealt with all of Linus's issues, and made RDRAND be just one part of the random pool --- exactly as Linus suggested a year earlier:  http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=c2557a303ab6712bb6e09447df828c557c710ac9
 
Anyone ever think about just asking him his side of the story beyond that thread?

If y'all havn't yet, I will. I care about and rely on the security of Linux entropy.
 
+Theodore Ts'o I remembered that exchange, but I didn't have time today to dig it up. You beat me to it.  
 
+David Johnston
We published the circuit, the algorithms and referenced the specs (SP800-90 CTR-DRBG) it complies to. The sausage is there for all to see.
Intel didn't even publish the AES variant (i.e., 128/192/256) used in CTR_DRBG [1], which raises questions about attention to implementation and its quality. If I were worried about RDRAND being subverted, ES (which you are mainly referencing in this thread) would be the least of my worries — because it is probably possible to analyze in a reverse-engineering lab, so it is not a good attack vector. I would worry about a minor bug/flaw in CTR_DRBG implementation, since it apparently cannot be verified. E.g., Google didn't even manage to identify a completely flawed SecureRandom backend (taken from Apache Harmony a few years back), and that flaw would be easily visible in the simplest code coverage test. That's Google, a software development company, and their core Android library. Intel is a hardware company. How could anyone verify that an embedded engineer is interpreting NIST SP 800-90A correctly, wrt. algorithm itself, possibility of side-channel attacks, etc.? Is there a direct ES access, to be compared with RDRAND output? My impression is that there isn't, since CRT_DRBG is implemented on-chip, and not in microcode. Another worry would be that any encryption scheme implementation that directly takes advantage of RDRAND is now reducible to the security of AES (again, variant unknown from Intel specs). How about the following conspiracy theory (which I don't believe, but it's just an example): NSA influenced Intel to delay deployment of SHA instructions, so that RDRAND would depend on CTR_DRBG with AES (compromised by NSA) and not on (possibly faster) Hash_DRBG? All things considered, it would be completely foolish for Linux kernel to stream RDRAND directly from /dev/[u]random.

[1] http://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide
 
+Theodore Ts'o
"If I were the NSA, I'd much rather compromise RDRAND, and then try to convince people that it's safer and faster to just use the raw RDRAND when creating session keys for IPSEC and GPG and SSH."

They're not stupid, you know.
 
+Theodore Ts'o - "If I were the NSA, and I wanted to gimmick an RNG, whether it be the one inside the Intel chip or the Android build, it would be a counter encrypted by an AES key known by the NSA."

You'd have to be a lot sneakier than that. People would notice that every Ivy Bridge chip generated the same sequence of number.  Heck they'd also notice that they got the same set of numbers every time they powered on.

At minimum you'd need a per-chip key, and some persistent storage so that you didn't see the same numbers in either of these scenarios. The former requires some complex (but probably tractable for the NSA) logistics to know which of the million Ivy Bridge chips per day flowing out of the Intel fabs are in a particular machine. The latter has a high probability of discovery by someone with the resources to scan the chip (in particular other governments that the NSA would not like to have access to this same trick).

So what are the other options?  If the NSA can execute arbitrary code on your machine they could poke a magic value to a magic MSR to turn on a counter+AES mode like you describe. But if they can execute arbitrary code - they can just steal your private keys!  On a laptop they might have a hook in the wireless card that would trigger a limited sequence to set counter+AES mode on receipt of a special packet - though that requires chipset->core traffic that might be spotted.

How else might they make this work?
 
+Tony Luck Use a fixed "NSA key", and then encrypt the CPU serial number concatenated with the counter to get the RDRAND output.   If you can ever get the raw output of RDRAND for that CPU (for example, you do a single MITM attack and grab the session key), you can use the fixed key to decrypt that RDRAND output, extract the serial number of your target, and now subsequent attacks against that CPU are much easier; you can estimate what the counter value might be, and then brute force it to get the exact value.

This would be a great exercise for a cryptography class: "Think like an NSA agent".   How do you compromise commercial encryption gear in a way which is hard to detect, but still easy for the NSA to exploit operationally?
 
+Tony Luck Couldn't they use the real HRNG to pick a large (128 bits or more) random number, then start the counter from there? It would be almost impossible for two people to see the same sequence, and if the attacker sees one of the "random" numbers, they can decrypt it and know exactly where your sequence is.
 
+Brendan's solution looks better. Both need to capture some raw RDRAND output to do identification. But we likely leak that in a dozen different ways as it isn't considered secret.
 
What if we took the output from RDRAND and fed it through AES using our own key (generated by rolling some dice when installing the machine)? It would add some latency (but ivy bridge has instructions to accelerate AES so perhaps not too much).
 
Tony. We thought of that. You are supposed to be able to take the output of rdrand and feed it into other crypto instructions without the values ever leaving the registers. Thus protecting you from a wide class of memory and timing attacks.
 
Ted. You would need to mix in something known to the attacker that keeps changing so that the output doesn't repeat each time from power up.
 
("/sub" is for "subscribe", i.e. "I have nothing substantial to say but am commenting so that I'll receive updates".)
 
+David Johnston If there is a bit of SRAM that could be used to preserve the counter across power downs that would be sufficient. Your idea of using the time would work too, assuming the CPU had access to a TOD clock.
 
+Tony Luck Yes, there are plenty of ways to get access to the raw RDRAND output if it is considered "secure". For example, if the host is running a https or ssh server, no need to download a MITM. Just connect to the server and drop the connection after the D-H exchange. 
 
Encrypting RDRAND with a key is a good idea, but you still need to get a secure key to begin with. For consumer devices, requiring the user to roll dice as part of the out of box experience is not, alas, realistic.
 
the bsd kernel does entropy pools in software properly with yarrow.. I guess you could patch your systems to use fortuna (??) but that's above my pay grade.
 
+Nomen Kultur Linux's /dev/random driver does take a lot large number of design inspirations from Yarrow, including the idea of catastrophic reseeding.
 
Ted. If I had a bit of SRAM that retained data across power ups, I'd be doing all sorts of cool things with it rather than futzing with RNGs.
 
+David Johnston 

>I have my opinions about the 'device manufacturer' thing. But I don't know I'm right and I'm not pointing fingers.

It's Cisco?
It's Cisco
 
It's interesting to see the debate that the NSA revelations have created. I think that completely changing the RDRAND code/design would probably be too obvious and to this end, I believe the actual design made it into the final silicon.

One possibility might be to ensure that the output from RDRAND is not the final output but rather perhaps it would allow only a subset of the random bits (e.g. 32 bits) to make it though and counter encrypted by an NSA AES key. The output is indistinguishable from random, but the NSA can brute force the 32 random bits that creates the random stream.

With the current revelations, it would not be unreasonable to expect that output of the RDRAND instruction on the chips going to China has been effectively hobbled. Though perhaps also all chips...
 
+Theodore Ts'o it's really funny that you posted this, because I read Intel's whitepaper on RDRAND for fun and was equally offput by their magic box in the middle that salts the hardware RNG with some magic FIPS algorithm involving some "secret" Intel key which presumably the NSA has a copy of as well (and maybe UK, Israel, who knows who else?). And you can't disable that box and get at the h/w RNG directly, ever. That's not suspicious...
 
oh and Intel's RDRAND whitepaper also makes a big deal about the elaborate self-tests that the cascade PRNG runs through before the CPU will allow you to use the instruction. They claim it's to make sure the output is sufficiently statistically random... Liars?
 
If someone has a security clearance, does that make them immediately less trustworthy to others? The Dark Mark.
 
+Theodore Ts'o - You don't ask them to roll dice, you ask them to do just about anything. Like, tap on the screen or talk into a microphone.
 
 It's funny that red hat engineers want the option of compiling the kernel to use only intel's rdrand.

  Ecce signum; should they start patching RHEL to only use intel's rdrand, I would say that it's more than compromised.

 NSA being the NSA, I'm sure would love to have 'little options' on gathering information from multinationals, foreign corporations, even  security agencies... one OS they would likely be using? RHEL.

 I'd much rather have little 'hooks' on operating systems than tap the wires for metadata.

 Now would be a good time for the skilled devs who read these posts to bring fortuna back up to 3.x kernels so I would have an option to completely bypass intel's rdand when I update from iron lake... isn't the good thing about linux it giving you all the options?  ;)
http://jlcooke.ca/random/
 
Nomen - of course, I first tried to remember which signal SIGNUM was.
 
I thought it was a runtime configuration, not a compile time config that was being requested. A compile time configuration makes no sense. I haven't paid attention to the linux support thing since the last go round. Perhaps I should.
 
+David Gerard, look at how having the badge makes cops in U.S. feel like members of an entitled, separate caste. Read up on how SWAT teams now kill centenarian people for resistance..

Now if having security clearance can be perceived by one as a measure of social capital -- I guess in modern times it becomes as good as a Black Mark, indeed.
 
Ted, can you clear something up? Who was asking for a compile configuration option? Was it Intel like you said at the top, or RedHat as you said further down?
 
It was an Intel engineer in July 2011, then when I took it the random driver, I reverted the change in July 2012.

This past week, it was a Red Hat engineer who wanted to put in a run-time configuration parameter that would bypass the entropy pool.   When I asked why, he couldn't give me a cogent explanation, other than performance.  When I pointed out that all of the performance critical callers were already using a CRNG seeded from the random driver, and asked him to give me the specific place where performance would make a difference, he couldn't give me a straight answer.

I don't want to assume that either of these engineers were taking a position that was formally endorsed by their employer.  The most recent one was strange though, if for no other reason than he was completely unable to give me a justification that made any sense.
 
OK. It is a bit odd that he couldn't give a cogent explanation. There are two. #1 Customers want a SP800-90 source available through the OS interface. #2 Attack surface reduction.

Of course everyone has been speculating about #3 it's an NSA hack job. You know where I stand on that one.
 
AES-NI allows a higher performance CSPRNG algorithm because its local to the core and there is one per core thread. PRNG performance isn't an argument. The security model is.
 
Having /dev/random not block is a bonus too. People might choose to use it then.
 
The SP800-90 thing is a hard requirement for some suppliers. The default kernel can either support or not but its going in products either way.
 
+David Johnston /dev/urandom doesn't block and it's what most programs use. I don't consider the /dev/random behavior to be that important and so it's kept mostly for compatibility reasons. 
 
Further clarification - Ted's July 2012 revert stopped the internal "get_random_bytes()" from using direct RDRAND output. At no point did the kernel feed unfiltered RDRAND output to /dev/random, or /dev/urandom.
 
So /dev/random is left to die on the vine because the maintainer doesn't consider it important?
 
+David Johnston not sure that maintaining the same behavior /dev/random has always had should be considered dying on the vine.
 
There's a difference between a full entropy source and a prng seeded from a full entropy source and a non full entropy source and a peng seeded from a non full entropy source. The first two don't exist in this universe for example, but we can get close. The practical difference is the way multiple numbers can be combined and used in crypto systems making specific claims about their brute force attack resistance. The SP800-90 specs draw this distinction between DRBGs and ENRNGs. This is a useful distinction. Unlike the blocking/unblocking distinction of urandom vs random. The blocking behavior of Dev/random is there for a reason and though it is poorly stated or documented, it is that /dev/random is paying attention to entropy accounting so you are getting close to full entropy outputs. 
 
By not maintaining the distinction the utility of the Linux kernel RNG is diminished.
 
+David Johnston It's true that I haven't dealt with +H. Peter Anvin's patch series to improve the entropy counter calculations because I've been too busy, but also because most applications don't use it.  They use /dev/urandom instead.  So for the time I have to work on /dev/random (I don't get paid by Google to work on the random driver, and I'm also organizing things like the kernel summit), I'm more interested in worrying why get_cycle() is a no-op on the MIPS architecture, when it apparnetly has a cycle counter register --- since there are lots of home routers out there which use /dev/urandom, and use MIPS processors, and so this will make a much more immediate, practical difference.

The reality is that trying to estimate entropy given the timing sources available to the kernel is extremely difficult.   So in the absence of real hardware support (and that's what rngd is for), entropy estimation is always going to be problematic, and probably hugely subject to error.  So that's always going to be an issue with /dev/random.

Sure, I could imagine an option where the user specifies random.i_trust_the_intel_RDAND_hasnt_been_teampered_by_the_nsa=1 on the boot command line which routes RDRAND directly into /dev/random, where we blindly trust that RDRAND has full, completely trusted entropy.   That might be good for users who require SP 800-90 compliance, and those users will typically trust the NSA anyway (or have no choice but to trust the NSA).    But those users can also just use RDRAND directly.  I suppose if those users really want to use open source software, like OpenSSL, and still be SP 800-90 certified, maybe it might be nice if /dev/random  and /dev/urandom could have a SP 800-90 compliant mode.   But if that's the case, let's have people state that officially, as opposed to these half-baked patches where the claim is "performance".   I'm not even sure if his patch would have been sufficient for SP 800-90 certification, since the rules are a kind of strict about what is required by that.

One thing that we might do is to have the kernel periodically generate a random AES key from its random pool, and then encrypt the RDRAND output by that AES key before it is exported to user space.  If that's allowed by the SP 800-90 specification (and I haven't read it closely enough to determine whether that would be considered an acceptible post-processing operation), then maybe that would be a solution that would satisfy everyone.   I will say though, that, allowing federal contractors to make $$$ selling certified FIPS 140-2 implementations to the US government is not something that is a high priority claim on my volunteer time.   I'm much more interested in making https web serving, ssh connections, GPG to be practically secure against all enemies, including both foreign and domestic intelligence agencies.  
 
Once again: do not feed RDRAND raw to /dev/[u]random. If you trust the hardware you can do that with RDSEED once it is available. However, RDRAND is wrong for /dev/random, and unfortunately there are applications known to (seriously) misuse /dev/urandom in a way that would make RDRAND arguably unsafe.

In other words, technically incorrect.
 
+H. Peter Anvin OK, well, I'm glad we're all on the same page then.   Not that I was going to apply the patch from that Red Hat engineer....
 
I like how the option description in the patch is misleading.
 
Even if a/the chip maker hasn't put a back door in the RNG hardware currently, when/if it happens, the engineers involved will not be allowed to talk or admit anything about it in public, without going to jail (under us jurisdiction).
 
+Peter da Silva  I can give you root on my DNS servers and all you can do it shut them down. Lying won't work because of DNSSEC. private keys are not on the name servers
 
+Paul Wouters I'm not sure what point you're making to me. We're talking about the initial boot of a new virtual appliance in a datacenter, and whether it can depend on trusting an external server for its initial PRNG seeding on first boot through the point it generates whatever host certificates it uses. If your DNS is spoof proof, great, the objection I was responding to doesn't apply. How about your DHCP?
 
+Jim Gettys
actually you need about 1 hour accuracy of time or else big TLDs already start failing to resolve with DNSSEC
 
+H. Peter Anvin can you elaborate on why rdrand is bad for /dev/random? I'm not a cryptography expert but (suspicions about NSA tampering aside) it's difficult to imagine how rdrand could weaken it.

(Not disputing you, just trying to learn something.)
 
If you assume /dev/random to be fully entropic, then concatenating the outputs of a PRNG is not going to be valid for /dev/random because they are not fully entropic. There are algorithmic connections between the values. You certainly could use RdRand in the preparation of /dev/random output (an so preventing it from blocking) because RdRand has some entropy. You would need to extract it using an appropriate extraction function. It is certainly wrong to use RdRand directly for /dev/random output.
 
 
+Paul Wouters You are correct; time is needed to one hour for dnssec... I mis-spoke.  It's still a real problem: no hardware in home routers to maintain time across power cycles.
 
+Peter da Silva I was talking about home routers and other embedded devices at the edge of the network, not data center devices, FWIW.
 
Home routers have direct access to random inputs, they're plugged into a network, and can monitor human input from their configuration interface.
 
+Peter da Silva You can't presume a human actually does anything to do an installation.  In practice, these devices are/need to be "plug in and work".....  Depending on home users to be crypto aware is a guarantee to be insecure.

The most promising suggestion I've heard is from +Theodore Ts'o who suggests one grabs some packets on the network interfaces to use as random bits.  Still could be attacked in principle, but in practice, possibly good enough (for those devices, anyway).
 
You don't depend on users to be anything but human. I have never had a router that I didn't have to do some configuration for. That means I was sitting there clicking on stuff at unpredictable times, the low bits of those event time stamps are pretty random. Combine that with network response timing from the upstream and how many bits of entropy is that?
 
+David Johnston thanks for the clarification.  I thought rdrand had the entropic properties that evidently only rdseed is actually supposed to possess.
 
+Jim Gettys  "Providing entropy" is a long way down the technical competency slope from "being cryptographically aware".  Hell, you could through a game on the interface, or provide some other make-work task to gather/generate entropy and it would suffice.  They wouldn't even have to do anything particularly successfully, just do something.
 
The technical details: RDRAND is architecturally guaranteed to be 1/512 entropic (on actual silicon we are seeing much higher entropic factors) but for that reason we do a 512:1 data reduction in rngd to produce fully entropic seed data.  RDSEED is supposed to be 1/1 entropic but is of course slower -- but much less slow than a 512:1 data reduction.
 
The top of this thread gives me new appreciation for all the pain the CentOS guys endured in working out binary-identical builds.  At least the Redhat customers know that if their OS is buggered, it's not in the build process, but in the compile toolchain.
Back in the bad old days when we had to compile gcc ourselves, we used the system c to compile a small version of gcc, which bootstrapped itself through a couple more build phases.  I wonder if that's still the case and if llvm could be used to compile gcc phase 1.
 
+Edward Morbius You are asking the user to do something, when all they will do is "plug in", the device.  And with the future in the home being a network of routers (rather than a single router), expecting people to do anything at all is the wrong way to go.

These devices need to be "plug and play", with no other human intervention.  Because it's been shown that people don't think....
 
+Peter da Silva You don't even get many bits that way.  You are lucky to get the user to set a password (which I don't usually, for example, because I live in the woods and anyone who is nearby is welcome to use the public side of my network for Internet access).  You need quite a few bits of randomness to generate the certs you need... So almost certainly, you would have to ask the user to do 'do something' very explicitly to get the bits you need.  

Hell, it took me minutes to generate 4096 bit gpg keys on my x86 system the other day, working as hard as I could, moving windows around, typing, etc... (Ted thinks that Chrome likes to eat bits out of the pool; I need to confirm this theory....).   It was a royal PITA: we can't have royal PITA's in the way of decent security...

And the contribution to the entropy pool from network drivers was removed from Linux a number of years ago, which was, as I said before, the enemy of the good being the perfect...
 
+Jim Gettys - If your keygen program was reading keystrokes and mouse actions directly instead of depending on a low efficiency slopsucker process I suspect it would be easier.

Also, given a choice of generating the keys from completely predictable seeds like MAC address and time, and using those seeds plus adding some extra randomness, you're still better off with the extra randomness. 
 
+Jim Gettys We are now sampling the cycle counter (on those platforms that have it) on every single interrupt.   This is not optional, and it can't be disabled by the device driver mainatiners, so that problem has been solved since 3.2.27.   We are gathering entropy from network drivers (and anything else that triggers an interrupt).

There's a problem that some architectures don't implement get_cycles(), but that's a different problem, which we're working on, as you know.  Even though we aren't mixing in the cycle counter on certain platforms such as MIPS, we are mixing in the IP of the interrupt, which will be mixing in some uncertainty; not as much as if we could mix in something derived from the cycle counter, but the bottom line is that kernels post July 2012 are much better off than earlier kernels.
 
Thanks for the clarification.  Of course, we ran into this before 3.2.27.....  And then there is the installed base; but as the devices currently typically don't do certs anyway, it's not in practice a problem for them.
 
at least Kinux returns to /dev/random, and we avoid the disaster!, but attack Linux is very hard, if they cant use a generic attack for GCC, LVM and the rest of compilators, but we can use some traps for reduce the rish, get long the passwords for de GPG hashes and use SSH connections for encrypt the information and madden the national spy agency, increase the width of the GPG and SSl hashes and generate a strong SSH hashes, and increase the enctropy on /dev/random.
we know that the nsa has many control of 1 hardware manufacturer, maybe be Quantum, or Intel or AMD we don't kno, al least we avoid the "intel exploit" with the use of /dev/random, but the NSA never sleeps and we must "take weapons" and avoid it, the Linux Kernel has many oportunities to strenghten security and with 0 holes, and use this oportunities we could stop the NSA and Save GNU/Linux, this is the moment, in we can stop the nsa attack on Linux, for a huge Linux expansion
 
we avoid troubles,
at least we don't be as OpenBSD, becuse this system is very weak, and troyanized by NSA
"shut up and take my data"
only we are avoiding malwares, no repairing "99% of the time"
this is a razon more to use more time Free Software
and put the nsa to think and not attack us
 
You nerds. You're all over thinking this. Rubber hose cryptanalysis. Works every time and scales. 
 
+Paul Eubanks Rubber hose cryptanalysis doesn't scale to bulk surveillance; and this is the attack that we're looking to prevent here.   Why do you think the NSA has leaned on hardware manufacturers and standards bodies to introduce weaknesses?  It's because they couldn't do it in the open.   Rubber hose cryptanalysis is not subtle and it's not covert.  If they tried doing this on ordinary Americans, the EFF and the ACLU would be all over them.   (Of course, the US government feels like it can do whatever it wants to non-Citizens, including indefinite detention without a trial, but that's a different problem.)
 
Sure it is. Just depends who's getting the hose (upstream or end points) and how many hoses they have to use. Also, why do you assume these news stories about their capabilities are indeed accurate? EFF and ACLU? What have those guys done to advance an effective defense against the US govt? Nothing that's what. The rubber hose always wins in the end. 
 
I take the random noise of opinions about 'safety' as input! :-)
 
Ted, have you considered that distributions are sending you this kind of patches not because they are misguided or evil but as a symptom of your ideas being  detached from your user's real world needs ? btw, userspace trusts rdrand, these include all crypto libraries, libstdc among many other things.. ring any bells? (hint, hint .. people want something usable)
 
+Niklas Schnelle
I trust the NSA mostly. They ultimately report to President Obama. Do you trust any government more? Syria? Iran?
 
+Cristian Rodriguez But we are using RDRAND --- we're just not using it exclusively; in other words, we're not blindly trusting the entire security of the RNG to RDRAND, but mixing it with other entropy gathered from the system.

When I asked the engineer who submitted it what his rationale was, he couldn't give me a coherent answer.  He tried to handwave something around performance.  When I pointed out this was not a problem since we had engineered solutions to support all of the systems that didn't have RDRAND, and invited him to give me one example where we had a performance bottleneck, he never responded.
 
More clarifications - there have been engineers from both Intel and Red Hat referenced in this thread. I believe in the response above Ted is referring to the Red Hat one when he talks about not being given a rationale for a patch being submitted.

The lead sentence of the post that started this whole thread is rather misleading, and perhaps based on Ted mis-remembering the exact nature of the patch that he applied in July 2012.  At no point did any Intel engineer apply "pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction".  Peter pointed out above that RDRAND is not suited for this, given the ways that /dev/random and /dev/urandom are used - which is why his patch did not feed RDRAND straight to /dev/
 
Bruce Schneier just changed his PGP/OTR keys a few days back. Anyone wanna date the SSL keys on major sites (Facebook, banks, Google)? 
 
Until Edward Snowden went off the reservation, everything I say below would doubtlessly be considered simple paranoid delusion.  Now it's only 99.44% delusion, 0.56% plausible.

I respect David Johnston for defending himself here, even if he's been a little abrasive in how he's done it. HOWEVER, he's nowhere near paranoid enough when he says "I and a number of test engineers know full well that the design hasn't been subverted".
I wanted to get the following on the record as to the tip of the iceberg of the complexity of modern chip design.

The worst-case threat scenario RdRand faces isn't from bit players, it is from extremely knowledgeable, very well funded state actors.  From professionals who do this sort of thing full time, for a living. Ken Thompson's seminal paper "Reflections on Trusting Trust" certainly should be considered as a possibility.

The following is very very very long. But that's because modern chip design is quite complicated.

1) Was at least some of the RdRand circuitry designed in Verilog or VHDL? If so, then it needed to be synthesized to be converted to gates. That requires an external vendor's program, such as Synopsys Design Compiler. Can we guarantee there's no backdoor there? Not necessarily in the general binary shipped around the world, but in the particular binary used to synthesize this particular design.

2) There are tools to compare the synthesis result with the starting RTL. E.g. by using Synopsys Formality. Yet another complicated program from an external vendor. Can we trust the tool when it says the RTL is equivalent to the gates?

3) All of the synthesis and formal verification probably takes place over a LAN if not a WAN. Compilers, source files, and result files are stored in a SAN or NAS. Do we trust the NAS vendor? If the NAS uses an off-the-shelf x86 motherboard to control things, can we trust that motherboard 100%? Do we trust the firmware in all the hard disks in the NAS?  What about all the routers and switches between the workstation and the NAS. Do we trust them 100%? Are all the bits on the LAN moving unencrypted over NFS?  How secure is NFS?

4) The actual synthesis software is probably run on a Linux server in a big server farm. Can we fully trust each and every server in that farm?

5) Is there Windows software involved anywhere in any of this? Certainly Linux has bugs and exploits against it, but there are probably 10x as many exploits against Windows.  Having Windows machines hanging off the LAN probably means "game over" right there. Are we sure that none of those Windows machines aren't rootkitted or virus infected? Can compromised Windows machines be used to attack the Linux machines on the LAN?

6) There's a lot of actual layout involved between a synthesized netlist and a GDS file. I'm not familiar with Intel's actual design flow, but doubtlessly external vendor's layout tools are involved. Are those tools fully trusted? Also, in the past Intel has used contractors to do layout. Even if Intel employees can be 100% trusted, can we also trust that none of the contractors moonlight for the NSA?

7) There are tools such as LVS that are run to compare a netlist against a GDS file. That probably requires an external vendor's tool, such as Mentor Calibre. Do we know that tool hasn't been compromised? It might say "CORRECT" even though there has been some additional circuitry added to the GDS.

8) Forget all the above, the design probably hasn't been compromised using those techniques. It would require a lot of effort.  But when chip tapeout occurs, a GDS file is created.  Once upon a time the GDS was a relatively faithful representation of a chip. But now there are complicated steps that must be done starting with this GDS to create an MEBES file with individual layer masks for the chip.  At this point, additional transformations such as optical proximity correction may need to be done for deep submicron design. It would be relatively easy to add or delete a few wires at this stage.

9) Who manufactures the actual chip layer masks? Does Intel do it in house, or do they use an external mask vendor?  It wouldn't be all that hard for the mask vendor to introduce changes to the individual masks.  And yet that's done post-DRC, post-LVS. So as far as standard design flow is concerned, the design is clean and "taped out".  Do the design engineers compare the MEBES file against their GDS? Or do they trust their mask vendor to do that?  And do they simply compare the mask layer bits against the starting GDS file or do they optically extract the polygons from the physical masks themselves and use that for comparison?  If the comparison is done from files rather than physical masks, how can anyone be sure that the files match the masks?  Finally, once a design is in production, what's to stop a mask or masks from being surreptitiously substituted?  It's not like the masks are under armed guard 24 x 7.

10) Johnston says "I've examined my own RNG with electron microscopes and picoprobes". But did he verify that every single wire he saw using the electron microsope corresponded directly to his design? None extra, none omitted?  How many thousands if not millions of wires and gates are there in RdRand?  Even if all the wires are correct, what if some N-wells and P-wells were changed? How do you know you're really looking at an N-well when you think you are? Did you also check all the power connections? Do you know if an ion implant happened where you think it should have happened? That's harder to see than a metal wire or a piece of poly. Can you spot if the boron and arsenic atoms are there in the right concentrations?  Can you trust all the transistor thresholds are as they should be?

11) Finally, here's where the real fun begins: "I am putting my RNG into every new Intel chip, from server to desktop to laptop to phone chips". So that means there will be literally dozens of different implementations of this circuitry.  How can we guarantee that none of them will ever have a backdoor?

Okay, that was fun. Let me stress that I agree with Johnston that, with 99.44% probability, his circuitry does what he claims, and isn't backdoored. It's really quite difficult to do any of the above exploits and expect to get away with it forever and ever.  That still leaves all the other (probably much easier to achieve) compromises he's conceded such as microcode, cache timing, etc, etc, etc.

It's not paranoia if they're really out to get you. Edward Snowden coming out was a game changer, a real eye opener. To steal a quote from a cheezy cop movie: "shit just got real!".
 
If I try to think like nsa, then compromising PKI key-pair production through "Trojaned" /dev/random's (on some harware) seems really good ... Ts'o wrote that slower crypto-bit generation is sometimes safer, and I agree.
 
+Tony Luck That's fair, I should have said /dev/random driver.  However, note that get_random_bytes() does get used for key generation inside the kernel, so if RDRAND was comrpomised, we could get screwed that way.   The bigger threat though is actually openssl choosing to use RDRAND directly for session keys, without doing something like encrypting the RDRAND output with a secret key.  (And BTW, OpenSSL does have a RDRAND engine so that's just a configuration away....) 
 
nice attack on the hardware random number generator: """Our Trojan is capable of reducing
the security of the produced random number from 128 bits to n bits, where n
can be chosen. Despite these changes, the modi ed Trojan RNG passes not only
the Built-In-Self-Test (BIST) but also generates random numbers that pass the
NIST test suite for random numbers"""
http://people.umass.edu/gbecker/BeckerChes13.pdf
 
+Theodore Ts'o "without doing something like encrypting the RDRAND output with a secret key"
So the first step to generating a good key is to already have a good key.
Chicken meet egg, egg this is chicken. :-(
 
+Julius Volz I had not seen that paper. I'll read it with great interest. Thank you. Becker and co do good work. 
 
+Tony Luck Well, yes, it's all about bootstrapping, isn't it?   But just as people have talked about using LLVM to bootstrap gcc and vice versa to make it harder to carry out a "Reflections on Trusting Trust" style attack, this is why it's good to have multiple entropy sources and multiple random number generators. 
 
+Julius Volz My thoughts are - don't lend your chips to that guy. His proposed attack takes an average of 2147483648 Ivy Bridges to succeed. I think it's a hypothetical argument. The principle is sound though - if someone has physical access to your silicon and enough money, they can do evil things.
 
David: Not doubting your veracity. But what if the NSA comes to intel with a FISA court order, and a wad of cash, and asks them to backdoor rdrand. All your hard work no longer matters. We don't doubt YOU, its every other engineer/manager at Intel. The Snowden leaks have shown the NSA has worked with vendors to weaken or put exploitable holes in some security products. Who is to say someday, a microcode update is released that contains a subtle bug the NSA knows how to exploit. So mixing rdrand with other sources is the only solution.
 
+Theodore Ts'o I truly believe that not having a dependency on a single entropy source is very important! That is the main reason why I introduced a flexible and hookable entropy collector in PolarSSL. It's designed to be simple and easy to integrate in other projects ( https://polarssl.org/entropy-source-code) 
 
+Daniel Joyce I have not received a FISA order. Ask me in the future and if I say no-comment you know what has happened.
 
Fascinating thread.  I'm a former Intel engineer.  I worked in the lab with IVB silicon and the DRNG, though I won't claim any knowledge of it's internals.

Talking about a microcode attack vector is downright nuts.  A little less so than imagining a NAS driver could be so incredibly targeted as to corrupt a specific portion of a particular chip between RTL and layout in a way that doesn't make the entire thing nonfunctional.  Chips are hard enough to get right without assuming some unseen sabotage is possible.  But if you don't trust the microcode, just chuck the machine out and start wire wrapping your own. That's a more unstoppable threat than an attacker with physical access who can arbitrarily, undetectably read/write kernel memory. 

+David Johnston  It's not clear where you're getting the number 2147483648 chips from.  I'm assuming it's from the end of section 3, "Since the chance that two outputs have the same 32-bit CRC is 1/2**32, the attacker only needs 2**32/2 tries on average to fi nd values for c and K that result in the expected 32-bit CRC."  However, the very next sentence: "This can easily be done by simulation" implies the attacker doesn't have to burn through chips to check results.  Were you speaking to something else?  Or is the CRC unknown in advance and must be verified experimentally in the first place?
 
+John Vinyard There are reasons why the attack as written would not work. But the principle is sound and could be made to work. If you let someone pull the lid off your chip and edit it you can expect trouble. 2^31 simulations of full BIST would be noticed.
 
+John Vinyard I agree that, up until recently, most everything being discussed here would be "downright nuts". However, our understanding of the "game" has changed since Snowden went public.

Consider this: Let me spend a year watching RdRand development full time (covertly). Give me full access to Intel's LAN, full access to the design engineers' emails, full access to their internal IMs, full access to all their phone calls and conference calls and text messages. Give me the ability to call on the expertise of NSA's 30,000+ employees. Give me the money and resources I need from the $250 million NSA has allocated to this program.

If anybody here believes for one second that the NSA, if they wanted to, couldn't covertly access all the above at Intel, then they haven't been paying attention.

With all of that on my side, I feel somewhat confident that I could insert a hidden backdoor in RdRand. Consider this as an "advanced persistent threat". It is emphatically not the same as Randal Schwartz cracking a few Intel passwords for the lulz.
 
I think you'd touch one cell of the design and the automated tools that are necessary to get a chip out that's not DOA would set off a few hundred alarms requiring a human waiver.  Sure you can FISA warrant everyone involved, now we're dealing with ~100 engineers, many of whom are foreign nationals outside the borders of the US, who are all keeping their mouths shut.  You're fundamentally disrespecting the time and energy that goes into the high-end microprocessor design process and assuming a paltry $250mm could begin to cover the costs of acquiring the talent to make these types of changes stealthily is laughable.  It's a bad spend anyway, instead of throwing your whole budget at one RNG you'd get better ROI going for TLS.

Make all the baseless assertions you want about the "game" being changed.  It doesn't change the engineering realities about how difficult these projects are and how many people you'd have to pull in to make the kinds of changes you want.  It's ironic that your attempt to deflect criticism is precisely the nature of how you're wrong.
 
+John Vinyard If the final AES whitening step is controlled by the microcode (as opposed to having a dedicated AES unit just for RDRAND), it might not be that hard to compromise things via the microcode.

Yes, if someone can compromise the microcode, they could do something much more devious.  But doing this in a way that wouldn't be caught in testing would be quite difficult.  (Assuming that the regression tests are as good as they had better be.)
 
+Bohdan Tashchuk, yeah, those were the sorts of things I was thinking about, although not in such minute detail, when I supposed we would want to go into a chip fab to ensure that no back doors were being inserted into e.g. Core i5's implementation of RDRAND.  Physically verifying something as complex as a Core i5 does what we all think it should do is an asymptotic to impossible task given the sheer transistor count in one of those...not impossible, but highly infeasible, assuming they'd even let you in the door.  It's still a bit scarey to contemplate how potentially easy it is to exploit this complexity if it's done in a subtle enough way.  But as Mr. Vinyard points out, in a practical sense, it's not as easy as all that.
 
+Theodore Ts'o
 The "trust us" scenario you lay out in the latter part of your post reminds me of Clipper chip with "key escrow", where "trusted third party" had to be... trusted ...
 
+brent gregory white  I don't trust the wireless interface in wired/wireless routers, because spoofed wireless signals can be sent via satellite or truck. Once, I did a wireshark capture on my Linux box with the router's wireless antenna exposed, and I got lots of strange IGMP etc protocol messages. Now, my wireless/wired[ethernet] router is in a Faraday cage made of aluminum foil. Previously, the Faraday cage contraption had greatly diminished the volume of traffic in a wireshark capture, and Internet access was preserved due to ethernet staying-alive in the router (all-wired, no wireless); it's empirical, no proof of manufacturer malice or "incompetence".
 
I can imagine hardware-sabotage occuring at any of many points. But source code software-sabotage seems harder to pull-off for a long time. [in concerning: RdRAND CMOS vs. Yarrow; also, entropy-pool on servers is a concern, maybe RdRAND CMOS is better, yet I think hardware-sabotage could be done on some chips, on a later core, in secret,  etc. Cf.: "History of sabotage" ]. 
 
+Joe Philipps
It's not necessary to go to the chip fab if you have reconfigurable hardware such as FPGAs available. I suspect that roll-your-own-CPU is not too far away. But back in the day we used to use reverse biased diodes to generate random noise - can't see why chips don't use those for RNG.
 
Can't we just ask Intel for the final AES whitening stage key?
 
+Valentin Zagura There's no way to know whether or not any arbitrary key that anyone might give you is actually the key used for the whitening step.  If the entropy generator is really good, after you decrypt the output, you will get something that looks random.

Try an experiment.  Compute the series AES_ENCRYPT(i++, A).   Then create different random key, B, and look at the output of AES_DECRYPT(AES_ENCRYPT(i++, A), B).   It will look really good, but it will tell you nothing.
 
+Theodore Ts'o I was under the impression that the data before the whitening process should not look like white noise (otherwise I don't see a reason for the whitening stage). So if the data decrypted it's not white noise, then we have the good key :)
 
Any chance for the Linux /dev/random to become non-blocking like the one found in FreeBSD?  

"The FreeBSD operating system implements a 256-bit variant of the Yarrow algorithm, intended to provide a cryptographically secure pseudorandom stream—this replaced a previous Linux style random device. Unlike the Linux /dev/random, the FreeBSD /dev/random device never blocks. Its behavior is similar to the Linux /dev/urandom, and /dev/urandom on FreeBSD is linked to /dev/random.


Yarrow is based on the assumptions that modern PRNGs are very secure if their internal state is unknown to an attacker, and that they are better understood than the estimation of entropy. Whilst entropy pool based methods are completely secure if implemented correctly, if they overestimate their entropy they may become less secure than well-seeded PRNGs. In some cases an attacker may have a considerable amount of control over the entropy, for example a diskless server may get almost all of it from the network—rendering it potentially vulnerable to man-in-the-middle attacks. Yarrow places a lot of emphasis on avoiding any pool compromise and on recovering from it as quickly as possible. It is regularly reseeded; on a system with small amount of network and disk activity, this is done after a fraction of a second."
 
Someone else commented elsewhere on :
...
if (!arch_get_random_long(&v))
   break;
hash.l[i] ^= v;
...

If this is the only place where RDRAND is called, wouldn't a better microcode attack be to modify the behaviour of XOR instead of RDRAND
... when rdrand is called from kernel mode make the next xor just clear the data instead of doing an xor ...
 
+ronnie sahlberg Changing XOR would be discovered right away. It is too obvious and it will break the functionality.
It is more difficult to prove that a random number isn't random.
 
I'm very much a neophyte in these matters, but I imagine this paper would be relevant to this discussion, assuming it hasn't been mentioned already. Haven't read all the comments, coz I'm reading them slowly: people.umass.edu/gbecker/BeckerChes13.pdf
 
+Jeff Holmon /dev/random is intended for long-term keys and while the entropy estimator is not great, it does provide for a higher grade of security than using a simple CRNG.  /dev/urandom (and /dev/random) takes design inspirations from Yarrow such that if the attacker has knowledge (or partial knowledge) of the pool, over time, "catastrophic seeding" will allow you to recover from this state of affairs.   So in Linux we have three pools, the input pool, the /dev/random pool, and the /dev/urandom pool.   The two output pools, for /dev/random and /dev/urandom, are catastrophically seeding periodically form input, so it has the desirable features you described of Yarrow's.

Hence, I consider what we have in Linux to be a superset of what is in FreeBSD.
 
+David Johnston I think this question got missed: would your methods of examination have detected this form of attack?
 
+Örjan Ericsson no no, if we're assuming an attacker with full microcode access, it would be trivial to set up XOR to check if RDRAND's been run in the last few instructions and subtly modify the results or leave them untouched if that's not the case.  The natural conclusion ought to be "gosh what a crazy untenable threat model!!" but that hasn't stopped the crazy discussion so far.  Go hog wild!
 
Because of the same paper he's repeatedly addressed in this exact thread?  Oh wait, someone else linked to it!! Guess that changes everything!

What a terrible attempt at discourse.  Trolling of the lowest caliber.
 
Okay, sorry, this thread grew to be a long one, and my attention to the latter part of it was only spotty.
 
+David Johnston, now, could you please clarify why this attack does not work? Isn't the hardcoded CRC32 value the same for all chips -- because otherwise, the standard test sequence (as described in the paper) couldn't be the same for all chips.

And if the hardcoded CRC32 checksum is the same -- who prevents NSA from knowing it, and crafting the attack as described in the paper?
 
Well guess i have to thank you for making encryptionsoftware running on linux a littlebit more secure.
b.t.w. its a shame that most TLS-Implementations don´t use Perfect Forward Secrecy... Damn you Microsoft / IE!
 
+Alan Cox

hate to bring up old threads , but ... in your answer to jan wildeboer you fail to mention the tight connection Red Hat has with the NSA , trought SElinux . they're in bed already , it would be natural they whisper to each other under the blankets :)
 
Wow. I can't believe I spent nearly an hour reading this entire thread. Heh.

I don't have anything new to add that hasn't already been said, so I'll just say this: as an end user, I want to be able to choose my random source, and not have it forced on me. If I find one source less trustworthy than others, I want to have the ability to weed it out from the toolbox. And if I find a different source highly trustworthy, then I want to have the ability to use that source without much difficulty. Whether it be the Intel DRNG or Simtec's Entropy Keys, I don't care. Just give me the choice to make.

+Mirko Zlojić While it's true that the NSA started the SELinux project, it's full source code is in the open, and it has been rigorously scanned with fine toothed combs. If you suspect there is bad code in SElinux, feel free to bring it center stage. Otherwise, your claims that Red Hat and the NSA are already in bed with each other are FUD, and aren't adding anything to security.
 
I was not saying SELinux is a backdoor . What I said is , RH does a lot business with NSA and DoD , and from the leaks we leraned how the NSA bragged to british that they have foothold in big amerikan corporations . From what I understand , a simple FISA court-order would force RH to comply with NSA wishes , plus it would effectively gag RH to share the information about tampering with code with anyone .
RH is doing a lot business with DoD and the government in whole , and is an amerikan corporate entity , so that pretty much in today's world mean , it can't be trusted .
 
Actually, a backdoored RDRAND can completely control /dev/(u)random's output. At least up until 3.13-rc-something (and after that, a backdoored RDRAND can make it possible to reverse the state to an earlier time after a state compromise). I have already implemented this in Bochs and will be publishing it soon:

https://twitter.com/DefuseSec/status/408975222163795969

(IMPORTANT NOTE: This does NOT demonstrate that RDRAND is backdoored, it just demonstrates that IF IT WERE, then it could have complete control over /dev/(u)random output, and that the backdoor to do so would not be very complicated).
 
Yet Another Attack Assuming Total Compromise Of Microcode.  Color me unimpressed.  Again, if we're giving that ground, which the "RDRAND Backdoor" Becker et al described is explicitly not , then the only reasonable path forward is grinding everything back to sand.  

My only question is: Why bother with rdrand?  Assuming I've got that kind of access, why not just kick control over on some far more common mnemonic?
 
+Winston Smith If you were actually going to implement the sort of backdoor you are proposing in an actual Intel CPU, it wouldn't be enough to make changes to the RDRAND functional unit.  You would have to actually make change to the instruction decode pipeline, and the register renaming logic, and all of the other modern complexities that are in a real, modern CPU.    It could be done, of course, but it would require making changes in the heart of the CPU, and lots of people would have to be involved in such a conspiracy.   And only one of them would need to have the same sort of conscience as Snowden or Manning, and leak the knowledge to the rest of the world, and Intel's reputation would go down the tubes.     So I don't think it's particularly likely.   If you are worried about this sort of threat, then you should probably build your own CPU out of TTL logic chips.   I did it as a freshman at MIT; it's not that hard.   You might also want to take the graduate level computer architecture class, which is availble on MIT's Open Courseware site; it will give you  a much better understanding of why it's a lot more complicated to do what you did as a proof of concept in Boch in real life, in silicon, and why it would be much more likely that one of the hundreds of people that would be involved would have to know, and be likely to spill the beans.

Making a change to the RDRAND functional unit is much easier, especially since RDRAND is specified to use AES as the final step (as the whitener, which also conveniently means there is no way we can independently test the quality of their HWRNG; we have to take Intel's word that it is competently done).   There is at least one or two orders of magnitude fewer people involved on the RDRAND functional unit.   But if you are going to make changes in the core instruction decode and execution unit of the CPU, that's a much more difficult and non-subtle change.    And at if that is part of your threat model, you had better implement your own CPU, and implement your own compiler, and assembler, etc., from scratch.
 
+Theodore Tso Thanks for responding. I agree with all your points. Especially, thank you for the constructive version of the "if you can't trust the hardware, build it yourself" argument. I will take a look at that course, and maybe try to build my own CPU, since it sounds like fun.

You're absolutely right that it would be much harder to implement a backdoor like mine, and I am with you in thinking that such a backdoor probably doesn't exist in any of Intel's CPUs. However, we also have to consider Linux being used in VMs and emulators, which could possibly backdoor RDRAND like I did (although, again, if the host system is malicious, all bets are off).

In general, It's bad if one of the RNGs inputs can control the output, regardless of whether that source is thought to be malicious or not. It should be an easy fix, too, so why not do it? I could be missing some important point that would make it hard to fix, so I'll try to write a patch. If I can make a patch that works just as well, but doesn't expose the potential vulnerability, I think it should be accepted.

edit: re-arranged sentences so they make sense
 
+david johnston. Take a look at iPXE for a way how to collect sufficient entropy on the hypervisor level and then pass it to vm. Open source auditable code.
 
+Theodore Ts'o so , after this whole story , can I be confident that my linux box is safe ? are we using HWRNG or not ?
 
+Mirko Zlojić We are using RDRAND, but it is being mixed in with other entropy being gathered from the system.   That way, it can't do any harm, and if it is in fact an honest RNG, it will help.
 
thanks theodore , I was a little sleepy , so that was the reason for the silly question . I appreciate you still answering the question which you already answered :D
 
I still do not believe RSA compromised itself in such a manner ??
 
Same for AMD as Intel? Time for NXP / Lenovo Taiwan (via China mainland)  to come out with a new NSA proof IC set and take some market share in the USA!
Add a comment...