“We cannot trust” Intel and Via’s chip-based crypto, FreeBSD developers say

http://arstechnica.com/security/2013/12/we-cannot-trust-intel-and-vias-chip-based-crypto-freebsd-developers-say/

by robin_reala • 13 years ago

348 167 13 years ago

gnu8• 13 years ago

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

sjwright5• 13 years ago

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

masklinn6• 13 years ago

You recall correctly indeed

No, the situations and concerns are very different.

mnw21cam8• 13 years ago

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

salient3• 13 years 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.

masklinn6• 13 years ago

No, 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#+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....

[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=133...

acqq• 13 years ago

The last time I've followed, RDRAND was not "just another source" in Linux, as it was xored after another sources were "fully" mixed.

bluecalm• 13 years ago

Any info on why Intel engineers applied the pressure ?

phaemon• 13 years ago

I think you're mistaken. It looks more like FreeBSD is moving to using these devices the same way Linux already does.

a1a• 13 years ago

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

lvh• 13 years ago

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

andrewaylett• 13 years ago

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

masklinn6• 13 years 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.

salient3• 13 years ago

Sounds like a good move to me. Intel has been awfully quiet about this.

jrockway2• 13 years ago

Not 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• 13 years ago

Especially when Snowden outs them :-)

numbsafari• 13 years ago

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

drzaiusapelord3• 13 years ago

In theory, Intel could be under some kind of directive or warrant to do this and it would be illegal for them to even disclose its existence, let alone protest against it.

kps• 13 years ago

I don't know whether Intel the corporation has said anything, but the responsible hardware engineer has personally stated there is no backdoor. http://lists.randombit.net/pipermail/cryptography/2013-Septe...

If I had an application where it mattered, I would pick RDRAND over a software system that was not reviewed, built, verified, and continuously monitored by someone I trust. It's implausible that RDRAND on my hardware is implemented differently from the hundreds of thousands of other copies of the core, or differently from the way it was yesterday. I have no such confidence in /dev/random. That doesn't mean there's anything wrong with FreeBSD's RNG; it only means that it's harder to be sure I'm actually using it.

ape4• 13 years ago

Where are the Intel and Via random instructions supposed to be getting their entropy?

Edit: thanks for the interesting replies!

jbri• 13 years ago

In 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• 13 years ago

Intel 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-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• 13 years ago

Usually, 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_generato...

polarix• 13 years ago

Have people talked about using sensor device input as prng seeds? onboard microphone, fan speed jitter, etc?

BCM43• 13 years ago

Yes, Linux already does it iirc.

XorNot2• 13 years ago

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

ds9• 13 years ago

That seems to me the right kind of solution.

Hardware devices from big companies are categorically untrustworthy, because of these companies' history of cooperating with surveillance, their incentives to sell out users, and the inability of users to verify what's going on in the devices.

The answer is something that's verifiable - and that means precisely a no-code, low-tech source of entropy, plus a means of translating fluctuations into bits, the latter being "open" enough to enable users to confirm exactly what it does.

And thanks, it's funny to think of putting a microphone in a colo server and using the roar of all the nearby fans and occasional voices as a source of random bits.

drzaiusapelord3• 13 years ago

I don't want Linux sampling my microphone randomly. Other things are fair game.

logfromblammo4• 13 years ago

I don't recall who did it, but someone once pointed a webcam at a row of several lava lamps as a source of entropy. As long as at least 75% of them were on at any given time, the image-hashing function produced unpredictably random numbers. The low quality of the camera produced some random noise all by itself.

I imagine you could do something similar with a feed of traffic on a nearby highway or blobs of cornstarch suspension on a subwoofer.

Keyframe• 13 years ago

I wonder if it's practical considering bandwidth. Is it enough for most practical purposes?

__alexs2• 13 years ago

Yes. People have even experimented with using CPU specific instabilities in certain operations to extract entropy.

http://www.irisa.fr/caps/projects/hipsor/misc.php#exectime

The problem with such systems is that is generally quite difficult to have confidence that they are not subject to attacks that may starve the system of entropy or trick the entropy estimator into thinking it has any when it has none.

Low-level hardware RNGs can be constructed in ways that make them quite difficult to attack externally, but are also basically impossible for us to verify.

Really it seems that the best approach is to take a wide range of flexible entropy sources and to learn to trust our mixing pools and trapdoor functions.

wtbob• 13 years ago

The problem with such systems is that is generally quite difficult to have confidence that they are not subject to attacks that may starve the system of entropy or trick the entropy estimator into thinking it has any when it has none.

That's why you give up on estimating entropy. It's just not possible in the general case.

Mix multiple sources of potential entropy in a secure fashion (e.g. with a crypographically-secure hashing function). Recover over time from a compromise.

Really it seems that the best approach is to take a wide range of flexible entropy sources and to learn to trust our mixing pools and trapdoor functions.

Yup, you're exactly right. Now we just need to convince Ted T'so to replace Linux's hacky /dev/random with a Fortuna-based one.

ctz• 13 years ago

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

Peaker3• 13 years ago

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

klodolph2• 13 years ago

That doesn't reduce entropy, it just fails to increase it.

ars_technician8• 13 years ago

Sorry, that's not how entropy works with XOR.

If you do not know one of the inputs to an XOR, you know nothing about the output.

XORing random sources is great because it acts as a minimum function for entropy of all of the sources. As long as you have just one good source, the output is good.

Perseids2• 13 years ago

Aren't you talking about the Linux kernel? There the very last step is XOR'ing the random output with the hardware RNG. The article explicitly mentions Yarrow as a mixing and CSRNG function for FreeBSD though.

michaelt• 13 years ago

As I understand it when you read from /dev/random it checks a measure of entropy and blocks if there isn't sufficient entropy available.

Do we trust hardware RNGs enough to allow their output to increase that measure of entropy?

X-Istence3• 13 years ago

/dev/random is not blocking on FreeBSD.

spacehome• 13 years ago

Unfortunately, this statement is only true if your entropy sources are uncorrelated. If your new entropy source is correlated in precisely the right way to cancel with a previous entropy source, you reduce entropy of the result.

Perseids2• 13 years ago

With a cryptographic primitive like Yarrow finding this precisely right way should be infeasible, in the same way that finding a collision for a cryptographic hash function should be infeasible.

midas007• 13 years ago

Fortuna supersedes Yarrow FAIAP.

Fortuna has the advantage of making it harder to game entropy pools. [1]

[1] http://th.informatik.uni-mannheim.de/people/lucks/papers/Fer...

nightcracker• 13 years ago

I warned against this in July: http://crypto.stackexchange.com/questions/9210/technical-fea...

RamiK• 13 years ago

There is a(n expensive) solution:

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

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

simias• 13 years ago

Not 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• 13 years ago

Some of the older devices (1997) had obvious flaws, and were lousy for crypto.

Here's a list:

https://news.ycombinator.com/item?id=6060636

ris3• 13 years ago

This coming from a BSD distribution that ships binary blob device drivers.

tachion2• 13 years ago

Yes, and?

matthewmacleod2• 13 years ago

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

acdha2• 13 years ago

You seem surprised that they acted where they had the ability to do so but don't where the only option involves losing users.

This is the difference between engineering and idealism.

ris3• 13 years ago

Ah so all of a sudden running a verifiable system is considered idealism.

noir_lord2• 13 years ago

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

leokun• 13 years ago

The original post is neither about Linux nor bragging about what you use. It's about the RNG in FreeBSD which is not a Linux distro

noir_lord2• 13 years ago

Heh, Posted the comment in the wrong thread, downvotes are fair enough.

kkielhofner• 13 years ago

I've been working with this project for some time:

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• 13 years ago

I 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• 13 years ago

There 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

EDIT2: There's also a wealth of information in this thread from the metzdowd cryptography mailing list: http://www.metzdowd.com/pipermail/cryptography/2013-Septembe...

dangero2• 13 years ago

Hmm 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• 13 years ago

It 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

tptacek10• 13 years ago

Closed 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• 13 years ago

Unless the backdoor was so incredibly subtle and hard to spot that it could be hand-waved away as a bug should it turn up.

pnathan• 13 years ago

Calling attention to this: disassembly is a thing. It is entirely possible to reconstruct a program's design and logic from the disassembled code. This is what software crackers and antivirus writers do on a regular basis. For an enlightening write-up, see the Symantec paper(s) on Stuxnet.

dangero2• 13 years ago

I'm aware that programs can be disassembled and I have written x86 assembly myself. If closed source is not a significant barrier to completely understanding s_rand then I ask for one reference to someone who has completely audited the Windows 7/Windows 8 version of s_rand, and CryptGenRandom that s_rand calls.

If you look on the related Wikipedia page what you find that there was an audit done of the Windows 2000 version of CryptGenRandom (which s_rand uses), and it was discovered to be flawed in a number of ways. The follow up is that Microsoft said that the issues were fixed in Vista. It's more than a theory that s_rand vulnerabilities will be called "bugs". It already happened once.

http://en.wikipedia.org/wiki/CryptGenRandom

salient3• 13 years ago

Microsoft shares all vulnerabilities with NSA as soon as they find out about them, and long before they fix them, anyway, which is like giving them access to a lot of backdoors into Windows. Adding one more from rand_s doesn't change the situation that much. Then there's TPM and all that other fun stuff. Until Microsoft overhauls their Windows security policies, you can never really trust Windows to keep you safe, even with the latest updates.

drzaiusapelord3• 13 years ago

MS shares information with intelligence agencies and usually before MS has even delivered a patch.

On top of it, when we analyze government malware, we don't see some weird calls to rand_s. We just see a few zero-days, exploits for known issues, or just plain-jane trojans.

Why compromise rand_s, which could help our enemies and cause a public outcry, when you're sitting on a mountain of zero days?

Also, windows is not closed source. MS shares source with governments, universities, etc. I think functions like rand_s are well understood and there has never been an MS backdoor for the government.

timbro• 13 years 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.

pja4• 13 years ago

mhoye 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

Key quote: "rdrand in ivbridge not implemented by Intel."

tedunangst7• 13 years ago

You're referring to errata BV54?

pja4• 13 years ago

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

lifeisstillgood• 13 years ago

I 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• 13 years ago

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

UNIXgod• 13 years ago

This on AMD chips as well? Since it's BSD we can just have an option to turn it off.

zxcdw• 13 years ago

As 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• 13 years ago

Even 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• 13 years ago

It seems unlikely that a manufacturing issue could affect the RDRAND instruction and not any other part of the CPU.

“We cannot trust” Intel and Via’s chip-based crypto, FreeBSD developers say

Related Stories