16 ms·
“We cannot trust” Intel and Via’s chip-based crypto, FreeBSD developers say
- gnu8 13y agoIf I recall correctly, Linus refused to make this change in Linux, denouncing it as paranoia. My fear is that the extra complexity adds additional opportunity for a back door to be inserted. However, software can be audited, the hardware cannot be.
- sjwright 13y agoWhat Linus correctly points out is that when multiple sources of entropy are combined, no single source can act to diminish the sum total of entropy. Even if rdrand was comprehensively backdoored and entirely predictable by the US government, it's still going to improve the quality of randomness. At worst it's a wash, but it will never reduce it. Here's the direct link to Linus Torvalds' entertaining observation: http://www.change.org/en-GB/petitions/linus-torvalds-remove-rdrand-from-dev-random-4/responses/9066 http://www.change.org/en-GB/petitions/linus-torvalds-remove-...
- masklinn 13y ago> You recall correctly indeed No, the situations and concerns are very different.
- sjwright 13y agoThe situations are indeed different because it's FreeBSD and not Linux. And there's different history behind their /dev/random implementations. But the underling concern is the same: a lack of trust for rdrand -- and the solution should be the same: to only ever use rdrand as an "improver" and never as an actual source of entropy.
- mnw21cam 13y agoIt's not true that it will never reduce it. It wouldn't be too hard for a CPU to notice when the result of RDRAND is XORed with something, and do evils to deliberately control the eventual result.
- riquito 13y agofake_random = 5 result = secret ^ real_random result = result ^ fake_random You know the value of fake_random, but the randomness isn't reduced at all (sorry, I can't produce a real mathematical explanation)
- mnw21cam 13y agocurrent_random = <something unpredictable> fake_random = RDRAND() new_random = current_random XOR fake_random Surprise! new_random is predictable, because the malicious CPU peeked ahead at the XOR operation and adjusted the RDRAND operation accordingly.
- hershel 13y agoCan't you wrap the RDRAND call with some long complicated code , so that tracking what fake_random will be hard to in hardware , thus preventing this attack?
- mnw21cam 13y agoYes, but then it's an arms race between the hardware manufacturer and the random number software writer. The fact is that the Linux/BSD random number generators were actually rather good before all this RDRAND stuff.
- deleted 13y ago[deleted]
- kerkeslager 13y agoTry this again, but instead of: fake_random = 5 Try: fake_random = secret ^ real_random ^ 5 No matter what secret or real_random are, result is now 5. You can't hide secret or real_random from the processor. In a larger sense, there's no way to stop the processor from simply setting result to whatever it wants before returning it to the place where it's used. My point is, there's no real way to trust hardware that can't be verified.
- salient 13y ago> However, software can be audited, the hardware cannot be Exactly. So work on solid security/privacy principles, rather than take the easy way out and hope for the best.
- masklinn 13y agoNo, Linus has refused to make a different change in Linux (the complete removal of RDRAND) because linux does not directly use RDRAND output, and it already uses RDRAND as an other source of entropy[-1], which is what FreeBSD is moving towards. According to Theodore Ts'o, there was pressure from Intel engineers to rely solely on RDRAND but they were rejected[0], it looks like the FreeBSD devs did do it and have /dev/random using RDRAND/Padlock directly[1] [-1] although — and I don't know why — the linux rng XORs pool output with RDRAND output instead of feeding RDRAND into the entropy pool itself[3] [0] https://plus.google.com/+TheodoreTso/posts/SDcoemc9V3J#+TheodoreTso/posts/SDcoemc9V3J https://plus.google.com/+TheodoreTso/posts/SDcoemc9V3J#+Theo... [1] That's the only way I can interpret "for 10, we are going to backtrack and remove RDRAND and Padlock backends and feed them into Yarrow instead of delivering their output directly to /dev/random"[2] anyway [2] http://www.freebsd.org/news/status/report-2013-09-devsummit.html#Security http://www.freebsd.org/news/status/report-2013-09-devsummit.... [3] I'll try to stop now but[4] provides a rationale for it: a history of unnoticed bugs in the random pool making the risk of a trivial xor lower as far as kernel devs are concerned: if you xor a known A and an unknown B, you can't know anything about the output (it won't be any more known than B is), whereas if you know of bugs in the random pool you might be able to take advantage of them and skew the output. Make of that what you will. [4] http://thread.gmane.org/gmane.linux.kernel/1323386/focus=1332780 http://thread.gmane.org/gmane.linux.kernel/1323386/focus=133...
- acqq 13y agoThe last time I've followed, RDRAND was not "just another source" in Linux, as it was xored after another sources were "fully" mixed.
- masklinn 13y agoYes, I had modified my comment to make note of that. Although I tuned the language a bit more (removed the "just" of "just an other source")
- bluecalm 13y agoAny info on why Intel engineers applied the pressure ?
- phaemon 13y agoI think you're mistaken. It looks more like FreeBSD is moving to using these devices the same way Linux already does.
- a1a 13y agoYour comment implies that Linus trusts Intel. This is not true, since the change is unnecessary even if they were infiltrated: "Long answer: we use rdrand as _one_ of many inputs into the random pool, and we use it as a way to _improve_ that random pool. So even if rdrand were to be back-doored by the NSA, our use of rdrand actually improves the quality of the random numbers you get from /dev/random." http://www.change.org/en-GB/petitions/linus-torvalds-remove-rdrand-from-dev-random-4/responses/9066 http://www.change.org/en-GB/petitions/linus-torvalds-remove-...
- lvh 13y agoThe conclusion is arguably correct, but the premise not so much. RDRAND isn't used as an input to the random.c pool: http://blog.lvh.io/blog/2013/10/19/thoughts-on-rdrand-in-linux/ http://blog.lvh.io/blog/2013/10/19/thoughts-on-rdrand-in-lin...
- andrewaylett 13y agoNo, as I understand that's a different change. The current state of FreeBSD, if I understand correctly, is that it has the option of returning the hardware-generated random sequence directly. They're changing it so it feeds entropy into the pool. Linux does neither, instead it xors the output of the entropy pool with the output from the hardware random number generator. This is strictly no less secure than the entropy pool on its own. Note that the implementation of the systems' entropy pools is also quite different -- my understanding is that FreeBSD uses Yarrow, a pRNG, to feed /dev/random, while Linux mixes bits of 'real' random data together, without the extra pRNG stage. Which of these schemes is better is irrelevant to this particular discussion. No links, I'm afraid, as EE apparently thinks Stack Exchange isn't suitable for under 18s and I can't turn content lock off at the moment.
- masklinn 13y ago> This is strictly no less secure than the entropy pool on its own. I'm not quite certain, it should be possible (though possibly overly complex) to use RDRAND (or calls to the crypto routines) as a trigger for a XOR backdoor working in concert with a RDRAND backdoor, and thus control the final output.
- mnw21cam 13y agoIt wouldn't actually be that hard for a CPU to notice which register the result of RDRAND was being XORed with and just set that register to something generated instead. Because, you know, that doesn't actually break any contracts. The effect is still that of XORing with a number we didn't know beforehand.
- sjwright 13y agoThat assumes we can't read the result of rdrand after the XOR is performed. I don't know the specifics of how the chip RNG is implemented in hardware, but surely its values have to hit some sort of readable memory before the kernel's code performs the XOR?
- salient 13y agoSounds like a good move to me. Intel has been awfully quiet about this.
- jrockway 13y agoNot to accuse Intel, because I have no idea whether or not they have backdoors, but do you want them to say: "Yes, we intentionally sold faulty products that put all your customer data at risk, and you at risk of a lawsuit for not protecting your customers' data." Not so good for the share price, methinks.
- kabdib 13y agoEspecially when Snowden outs them :-)
- numbsafari 13y agoMakes me wonder, though... if the government forces intel to sell everyone defective products does that violate our 4th amendment rights? Do I, as an individual, have standing to sue the federal government because they intentionally weakened a product I purchased, potentially exposing me to other kinds of threats? What about someone who has actually been victimized by an exploit of a backdoor that was ordered installed by the government? Would they have standing to sue for damages that resulted? I only ask because I know "standing" has been an important issue in many of the cases related to these abuses. Most of the suits have failed because the plaintiffs were found to lack standing for one reason or another.
- jrockway 13y agoNo. In general, you may only sue the federal government when the federal government gives you permission to sue them. http://en.wikipedia.org/wiki/Sovereign_immunity_in_the_United_States#Federal_sovereign_immunity http://en.wikipedia.org/wiki/Sovereign_immunity_in_the_Unite...
- protomyth 13y ago
- deleted 13y ago[deleted]
- acqq 13y agoYou wouldn't prove anything by analyzing the results, for anybody who knows a bit of cryptography it's trivial to produce the stream that "doesn't have the patterns" but that can contain "master" key.
- Donald 13y agoWhat do you mean?
- simias 13y agoThe output of any good cipher in "counter" mode should be very close to random noise while still being perfectly predictable. Basically any stream cipher worth its salt would pass the parent's test.
- caf 13y agoThat's not entirely true for counter mode. For random noise, if you see 2^(n/2) n-bit blocks then there's a ~50% probability of two of those blocks being identical, but if you have that many n-bit blocks from an n-bit block cipher in counter mode the probability of two identical blocks is zero. This doesn't apply to stream ciphers.
- simias 13y agoInteresting but I don't understand why the probability of two identical blocks in this situation would be 0 for CTR mode. As far as I know theoretically there could be a collision and the cipher could output the same value for two different counter values, unless the block cipher guarantees that such a collision can never occur? I was not aware of such a guarantee.
- 13y ago
- ape4 13y agoWhere are the Intel and Via random instructions supposed to be getting their entropy? Edit: thanks for the interesting replies!
- jbri 13y agoIn theory? Quantum and thermal effects inside an unstable configuration of transistors. The simple example is a basic SR latch (two NOR gates, where the output of one gate feeds one of the inputs of the other, and vice versa), where you start things off by applying a signal to both S and R. When you remove the signals, the latch will eventually fall back into one of the two stable states - but which state it ends up in is random. So you can easily produce a stream of bits from a potentially-biased random source, and then do some deterministic massaging of that stream to produced an unbiased stream of random bits.
- rst 13y agoIntel is at least supposed to be using something like a "coin-flip" circuit, which has two stable states and can be forced one way or the other based on thermal noise: http://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator http://spectrum.ieee.org/computing/hardware/behind-intels-ne... That output stream may be biased, so it subsequently goes through a "whitening" stage based on AES. (One question I haven't seen an answer to: presuming all the hardware functions as described, would it be possible for a microcode update to change the output --- e.g., by whitening the output of the real-time clock instead of what I'm calling the coin-flip circuit?)
- sspiff 13y agoUsually, electric components with unpredictable timing or behaviour are used to generate randomness. Sometimes they intentionally use noisy or unshielded components to use the noise for randomness. For some physical phenomena that can be exploited for getting entropy from a chip or other hardware, have a look at http://en.wikipedia.org/wiki/Hardware_random_number_generator http://en.wikipedia.org/wiki/Hardware_random_number_generato...
- polarix 13y agoHave people talked about using sensor device input as prng seeds? onboard microphone, fan speed jitter, etc?
- Keyframe 13y agoI wonder if it's practical considering bandwidth. Is it enough for most practical purposes?
- BCM43 13y agoYes, Linux already does it iirc.
- XorNot 13y agoYou have to install a utility to do it, but yeah. The problem is ambient noise isn't that random in say, a data centre - it works better in a noisy environment like an office where you have people doing fairly random things rather then a whole bunch of oscillating fans.
- zurn 13y agoI'd wager machine room fan noise has at last as much entropy, since office sounds are pretty structured and usually mostly quiet. In any case there's a significant amount of noise from the a/d conversion even when recording a predictable sound.
- ingenium 13y agoWhat utility is it?
- XorNot 13y agoOn Ubuntu you can install the 'randomsound' package. There used to be a different one I used but I can't remember the name.
- kstrauser 13y agoWhite noise is an enormous source of entropy, by definition. For example, take a stream of samples and record whether the least significant bit is 0 or 1. That'd be almost impossible to predict or influence from outside the system.
- ctz 13y agoIt was always the right answer to feed all available entropy sources (irrespective of previous laundering -- eg. Intel RDRAND gets laundered through the SP800-90 AES-CTR_DRBG internally) into a decent CSPRNG. Feeding multiple entropy sources of different qualities, speeds or backdooredness cannot (by construction) decrease the entropy of the output (it can, obviously, fail to increase it -- say if your ring oscillator got stuck in a fixed bit pattern like the Taiwanese smartcards). Yarrow and Fortuna are examples of decent CSPRNGs, so I'd say this is a pretty good move by FreeBSD.
- Peaker 13y agoIf the RNG instructions are malicious, they can reduce entropy, by for example XOR'ing into the result previous register values that held the previous entropy source values.
- nightcracker 13y agoI warned against this in July: http://crypto.stackexchange.com/questions/9210/technical-feasibility-of-decrypting-https-by-replacing-the-computers-prng/9212#9212 http://crypto.stackexchange.com/questions/9210/technical-fea...
- RamiK 13y agoThere is a(n expensive) solution: https://en.wikipedia.org/wiki/Hardware_random_number_generator https://en.wikipedia.org/wiki/Hardware_random_number_generat... https://en.wikipedia.org/wiki/Comparison_of_hardware_random_number_generators https://en.wikipedia.org/wiki/Comparison_of_hardware_random_...
- simias 13y agoNot a solution to the particular issue of trusting HW PRNG unless you can audit the innards of this particular hardware. Maybe an opensource FPGA-based solution might do the trick if you really need high-quality highly-secure fast random number generation. Personally when I've needed good and fast sources of entropy I've just picked a good (but slow) random number source and used it as a key for a strong stream cipher (that I would renew every megabit or so). Assuming there are no weaknesses in the cipher and you have hardware acceleration you can get a very fast PRNG source. And unlike RDRAND you can actually audit the hardware cipher implementation because it behaves deterministically.
- DanBC 13y agoSome of the older devices (1997) had obvious flaws, and were lousy for crypto. Here's a list: https://news.ycombinator.com/item?id=6060636 https://news.ycombinator.com/item?id=6060636
- ris 13y agoThis coming from a BSD distribution that ships binary blob device drivers.
- tachion 13y agoYes, and?
- opendomain 13y agoI think he is saying, that FreeBSD ships binary device drivers - how can we trust that those do not compromise the system? If FreeBSD is open source - why are not the device drivers? If we can not trust FreeBSD for these device drivers, then why should we trust their opinion on using intel for a crypto source?
- matthewmacleod 13y agoThe point was obviously that it's surprising to see that they are happy to ship binary drivers (which could contain arbitrary compromises from a user's point of view) but are not willing to trust the HWRNG (to which the same caveat applies). Of course, I don't agree with this comparison; running the output of the HWRNG through Yarrow is good practice in any case.
- AnthonyMouse 13y agoWhat's the problem with the comparison? The only real advantage of the binary blob over the hardware is that you can theoretically verify what it's doing more easily. But actually doing that verification has a difficulty on the same order as reverse engineering the driver to release an open source version, so all the existence of the binary driver does is to imply that such verification hasn't occurred -- because if it had then those doing the verification would have been in a good position to release source code (or at least complete hardware documentation) for an open source driver. Binary blob software also has the distinct disadvantage that even if you were to verify it, you would have to verify each release again whenever there is an update.
- noir_lord 13y agoI think which Linux distro you use should be like religion and politics should be a personal matter ;). That said I am a Mint XFCE user and have been back to 13 (before that Gnome 2) every release has been brilliant I run it on everything from an ancient ThinkPad to a thoroughly modern development machine and it has worked well. It's also the only WM/DE that handles multiple screens (3 on both desktops and 2 on Dell/External) without any show stopping/tremendously irritating bugs couple that with the huge amount of software available via Debian/Ubuntu and PPA's and it's a cracking developer OS.
- kkielhofner 13y agoI've been working with this project for some time: https://github.com/pwarren/rtl-entropy https://github.com/pwarren/rtl-entropy Quite a bit of entropy using radio noise and a $15 RTL-SDR USB dongle. Still could use some work and review but seems like the start to an almost ideal solution.
- IgorPartola 13y agoI wonder how hard it is to build something like that using the mic input. Or perhaps measuring the noise on a spare 802.11 card. I know in general it is not easy to add a kernel facility that will be widely available, but how hard is it to build a physical RNG if your specific case demands high entropy and you do not want/need a commercial product?
- hdevalence 13y agoThere is already a project whose name sadly escapes me that does this, using information theory to derive lower bounds on the number of bits of entropy in data read from a line-in jack. EDIT: I'm thinking of Turbid: http://www.av8n.com/turbid/paper/turbid.htm http://www.av8n.com/turbid/paper/turbid.htm EDIT2: There's also a wealth of information in this thread from the metzdowd cryptography mailing list: http://www.metzdowd.com/pipermail/cryptography/2013-September/017572.html http://www.metzdowd.com/pipermail/cryptography/2013-Septembe...
- BuildTheRobots 13y agois it VanHeusden's audio_entropyd? [1] They also provide a timer and video based entropy daemons too. [1] http://www.vanheusden.com/aed/ http://www.vanheusden.com/aed/
- dangero 13y agoHmm I've been having similar concerns about the Windows rand_s function. Every Windows application including every modern browser relies on rand_s for secure random number generation but obviously the function is completely closed source. Seems like a perfect target for the NSA.
- stinos 13y agoIt sure is, but how would they do that practically? I'm not saying it's impossible, but I really wonder how they would approach this. Call Ballmer and tell him to slip in a new CRT with the next Windows update providing a targetted version seems like a long shot. And even it works they would only target a (possibly small) subset of all machines since there's enough of them that aren't updated and there's enough software out there that ships with it's own copy of msvcrxx.dll
- tptacek 13y agoClosed source isn't a significant obstacle to understanding code, and Microsoft's code is the most comprehensively reverse-engineered in the industry. It would be extremely stupid to hide a backdoor in binaries that Microsoft ships.
- nly 13y agoUnless the backdoor was so incredibly subtle and hard to spot that it could be hand-waved away as a bug should it turn up.
- timbro 13y ago> the NSA and its British counterpart defeat encryption technologies by working with chipmakers to insert backdoors, or cryptographic weaknesses, in their products. I had already started to forget about that... From that other report (september): > They reveal a highly classified program codenamed Bullrun, which according to the reports relied on a combination of "supercomputers, technical trickery, court orders, and behind-the-scenes persuasion" to undermine basic staples of Internet privacy, including virtual private networks (VPNs) and the widely used secure sockets layer (SSL) and transport layer security (TLS) protocols.
- pja 13y agomhoye points to the notes from the FreeBSD summit on his Twitter feed. The notes from the security sessions are here: https://wiki.freebsd.org/201309DevSummit/Security https://wiki.freebsd.org/201309DevSummit/Security Key quote: "rdrand in ivbridge not implemented by Intel."
- tedunangst 13y agoYou're referring to errata BV54?
- pja 13y agoNo, that's just a failure to set the relevant property bit in the CPU at startup, so despite the RDRAND instruction being present it won't actually run on those CPUs. It's well known that the Intel RDRAND implementation uses a hardware entropy source to seed a software RNG implemented directly in the CPU. The suspicion is that said CSRNG could be using an elliptic curve CSRNG to carry out the final mixing where the NSA has chosen both the curve and the points on the curve. It's impossible to tell from the outside whether this is the case or not - such an implementation would still pass all known randomness tests. However, if the curve points have been carefully chosen then you can derive the internal state of the RNG from the output and thus both predict future values (until the hardware entropy source re-seeds the generator, if it actually does that at all) and derive past ones (up to the last re-seed). It's been said elsewhere that using an elliptic curve CSRNG where the NSA has chosen the curve points is effectively equivalent to doing the second half of a Diffie-Hellman exchange with the NSA to securely communicate your RNG state to them. For cryptographic algorithms that depend upon a secure RNG source this is devastating. All communications that use such are source are transparent to the NSA. (The NSA crypto geeks must have thought this was a fantastic trick: the communication would remain completely secure against all other third parties because deriving the magic numbers that let you decrypt the output from the public curve points is next to impossible - it's the discrete logarithm problem in action.)
- tedunangst 13y agoI don't understand how what you just wrote relates to your key quote: "rdrand in ivbridge not implemented by Intel."
- lifeisstillgood 13y agoI used to work for an online gaming company (legal in the UK) - and they basically used the on server chips (as opposed to quantum RNG) - and was not unusual in the industry. which may lead to weaker randomness and so an exploit for scamming. It's just that the validation tests were to simulate a few million rolls of the dice and see if the graph came out right.
- Flenser 13y agoIs that a good validation test though? I'd have thought that if I programmed it to have a 50/50 chance that it would repeat the previous roll the graph would look about the same. i.e. half a million rolls look about the same as a million. Edit: which is to say that I thought the issue wasn't that the Intel/via chip's random number generators wouldn't look random in aggregate over lots of uses, but that people are concerned that there could be exploitable patterns in short sequences.
- deleted 13y ago[deleted]
- UNIXgod 13y agoThis on AMD chips as well? Since it's BSD we can just have an option to turn it off.
- zxcdw 13y agoAs far as I am aware there are no instructions for AMD CPUs to generate random numbers thus far, although Wikipedia mentions that their upcoming Excavator(scheduled for a 2015 release) architecture includes support for Intel's RDRAND.
- codex 13y agoEven if you could trust these RNGs, it is possible that they will malfunction at any time through a manufacturing defect or thermal issue. Blindly trusting hardware is naive. Linux never did, and decisions like this make me less likely to ever use BSD again. The critical mass of talent is just not there.
- astrange 13y agoIt seems unlikely that a manufacturing issue could affect the RDRAND instruction and not any other part of the CPU.