Intel In Bed With NSA

                         INTEL IN BED WITH NSA



----- Forwarded message from Matt Mackall <mpm@selenic.com> -----

Date: Thu, 11 Jul 2013 17:34:48 -0500
From: Matt Mackall <mpm@selenic.com>
To: liberationtech <liberationtech@lists.stanford.edu>
Subject: Re: [liberationtech] Heml.is - "The Beautiful & Secure Messenger"

On Thu, 2013-07-11 at 13:47 -0700, Andy Isaacson wrote:

> > Linux now also uses a closed RdRand [2] RNG if available.
>
> There was a bunch of churn when this code went in, so I could be wrong,
> but I believe that RdRand is only used to stir the same entropy pool as
> all of the other inputs which are used to generate random data for
> /dev/random et al. It's hard to leverage control of one input to a
> random pool into anything useful.

It's worth noting that the maintainer of record (me) for the Linux RNG quit the project about two years ago precisely because Linus decided to include a patch from Intel to allow their unauditable RdRand to bypass the entropy pool over my strenuous objections.

From a quick skim of current sources, much of that has recently been rolled back (/dev/random, notably) but kernel-internal entropy users like sequence numbers and address-space randomization appear to still be exposed to raw RdRand output.

(And in the meantime, my distrust of Intel's crypto has moved from "standard professional paranoia" to "actual legitimate concern".)

--

Mathematics is the supreme nostalgia of our time.

--

Too many emails? Unsubscribe, change to digest, or change password by emailing moderator at companys@stanford.edu or changing your settings at https://mailman.stanford.edu/mailman/listinfo/liberationtech

----- End forwarded message -----

--

Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org

______________________________________________________________

On 2013-07-13 12:20 AM, Eugen Leitl [forwarding Matt Mackall <mpm@selenic.com>] wrote:

It's worth noting that the maintainer of record (me) for the Linux RNG quit the project about two years ago precisely because Linus decided to include a patch from Intel to allow their unauditable RdRand to bypass the entropy pool over my strenuous objections.
Is there a plausible rationale for bypassing the entropy pool?

How unauditable is RdRand?

Is RdRand unauditable because it uses magic instructions that do unknowable things? Is it designed to actively resist audit? Has Intel gone out of its way to prevent you from knowing how good their true random generation is?

On Fri, Jul 12, 2013 at 2:48 PM, James A. Donald <jamesd@echeque.com> wrote:

On 2013-07-13 12:20 AM, Eugen Leitl [forwarding Matt Mackall <mpm@selenic.com>] wrote:
It's worth noting that the maintainer of record (me) for the Linux RNG quit the project about two years ago precisely because Linus decided to include a patch from Intel to allow their unauditable RdRand to bypass the entropy pool over my strenuous objections.

Is there a plausible rationale for bypassing the entropy pool?

Throughput? Not bypassing means having to wait until enough randomness has been gathered from trusted sources.

Or maybe it's just trusting Intel and assuming that RDRAND provides better randomness.


On 12/07/13 21:54 PM, Patrick Mylund Nielsen wrote:

On Fri, Jul 12, 2013 at 2:48 PM, James A. Donald <jamesd@echeque.com> wrote:
On 2013-07-13 12:20 AM, Eugen Leitl [forwarding Matt Mackall <mpm@selenic.com>] wrote:
It's worth noting that the maintainer of record (me) for the
Linux RNG quit the project about two years ago precisely because
Linus decided to include a patch from Intel to allow their
unauditable RdRand to bypass the entropy pool over my strenuous
objections.

Is there a plausible rationale for bypassing the entropy pool?

Throughput? Not bypassing means having to wait until enough randomness has been gathered from trusted sources.

Typically, the entropy pool is used to feed a PRNG. Throughput isn't really an issue because modern PRNGs are fast, and there are very few applications that require psuedo-RNs at that sort of speed.

Or maybe it's just trusting Intel and assuming that RDRAND provides better randomness.

This thread has been seen before. On-chip RNGs are auditable but not verifiable by the general public. So the audit can be done then bypassed. Which in essence means the on-chip RNGs are mostly suitable for mixing into the entropy pool.

Not to mention, Intel have been in bed with the NSA for the longest time. Secret areas on the chip, pop instructions, microcode and all that ... A more interesting question is whether the non-USA competitors are also similarly friendly.

iang


[BTW, when responding to a message forwarded, do please fix the quote attribution.]

On Fri, Jul 12, 2013 at 2:29 PM, ianG <iang@iang.org> wrote:

> This thread has been seen before. On-chip RNGs are auditable but not
> verifiable by the general public. So the audit can be done then bypassed.
> Which in essence means the on-chip RNGs are mostly suitable for mixing
> into the entropy pool.
>
> Not to mention, Intel have been in bed with the NSA for the longest time.
> Secret areas on the chip, pop instructions, microcode and all that ... A
> more interesting question is whether the non-USA competitors are also
> similarly friendly.

I'd like to understand what attacks NSA and friends could mount, with Intel's witting or unwitting cooperation, particularly what attacks that *wouldn't* put civilian (and military!) infrastructure at risk should details of a backdoor leak to the public, or *worse*, be stolen by an antagonist. I would hope that talented folks at the NSA would be averse to embedding backdoors in hardware (and firmware, and software) that they could lose control of, especially in light of recent developments. I'm *not* saying that my wishing is an argument for trusting Intel's RNG -- I'm sincerely trying to understand what attacks could conceivably be mounted through a suitably modified RDRAND with low systemic risk.

For example, there might be a way to close a backdoor in a hurry, should it leak.

Understanding the attacks that sigint agencies might mount in this fashion might help us understand the likelihood of their attempting them.

I think it's important to highlight the systemic risk caused by embedding backdoors everywhere. See "Security Implications of Applying the Communications Assistance to Law Enforcement Act to Voice over IP", by Bellovin, Blaze, et. al. Systemic failures can be extremely severe. The 2008 financial crisis was a systemic failure, and, sadly, I can imagine far worse systemic failures. Minimizing systemic risk should be a key policy goal in general, but management of systemic risk is inherently not in the interests of any short-term political actors, therefore it's important to ensure institutional inertia for systemic risk minimization. The NSA that once worked to strengthen DES against differential cryptanalysis clearly thought so (or, rather, the people who made that happen did) -- is today's NSA no longer interested in the nation's civilian and military security?!

Nico
I think compromising microcode update signing keys would be the easiest path. Then you don't need backdoors baked in the hardware, don't need Intel's buy-in, and can target specific systems without impacting the public at large.

This is a pretty interesting analysis showing that these updates are 2048-bit RSA signed blobs:
http://inertiawar.com/microcode/

I'd like to understand what attacks NSA and friends could mount, with
Intel's witting or unwitting cooperation, particularly what attacks
that *wouldn't* put civilian (and military!) infrastructure at risk
should details of a backdoor leak to the public, or *worse*, be stolen
by an antagonist.

I would hope that talented folks at the NSA would be averse to embedding backdoors in hardware (and firmware, and software) that they could lose control of, especially in light of recent developments.

Unfortunately it appears that for security reasons at least some chips are being backdoored. For instance see "Breakthrough silicon scanning discovers backdoor in military chip". The chip designers have admitted in that case that the backdoor was designed as part of the security scheme. Actel inserted the backdoor, I would assume with NSA permission since backdooring sensitive chips without NSA permission would be extremely risky.

The NSA that once worked to strengthen DES against differential cryptanalysis clearly thought so (or, rather, the people who made that happen did) -- is today's NSA no longer interested in the nation's civilian and military security?!

But remember that the NSA weakened DES by reducing the key size from 128 bits to 54 bits. It appears that the preferred the ability to break DES to issues of civil security even back then.

On 2013-07-13 4:54 AM, Patrick Mylund Nielsen wrote:

On Fri, Jul 12, 2013 at 2:48 PM, James A. Donald <jamesd@echeque.com> wrote:
On 2013-07-13 12:20 AM, Eugen Leitl wrote:
It's worth noting that the maintainer of record (me) for the Linux RNG quit the project about two years ago precisely because Linus decided to include a patch from Intel to allow their unauditable RdRand to bypass the entropy pool over my strenuous objections.

Is there a plausible rationale for bypassing the entropy pool?

Throughput? Not bypassing means having to wait until enough randomness has been gathered from trusted sources.

Or maybe it's just trusting Intel and assuming that RDRAND provides better randomness.

Often, when the computer boots up, it needs to do things that require some true randomness. This is a potential disaster, therefore there should be a non blocking wait for randomness.


>I'd like to understand what attacks NSA and friends could mount, with Intel's
>witting or unwitting cooperation, particularly what attacks that *wouldn't*
>put civilian (and military!) infrastructure at risk should details of a
>backdoor leak to the public, or *worse*, be stolen by an antagonist.

Right. How exactly would you backdoor an RNG so (a) it could be effectively used by the NSA when they needed it (e.g. to recover Tor keys), (b) not affect the security of massive amounts of infrastructure, and (c) be so totally undetectable that there'd be no risk of it causing a s**tstorm that makes the $0.5B FDIV bug seem like small change (not to mention the legal issues, since this one would have been inserted deliberately, so we're probably talking bet-the-company amounts of liability there).

>I'm *not* saying that my wishing is an argument for trusting Intel's RNG --
>I'm sincerely trying to understand what attacks could conceivably be mounted
>through a suitably modified RDRAND with low systemic risk.

Being careful is one thing, being needlessly paranoid is quite another. There are vast numbers of issues that crypto/security software needs to worry about before getting down to "has Intel backdoored their RNG".

Peter.

There are plenty of ways to design an apparently random number generator so that you can predict the output (exactly or approximately) without causing any obvious flaws in the pseudorandom output stream. Even the smallest bias can significantly reduce security. This could be a critical failure, and we have no way to determine whether or not it is happening.

As for preventing potential security holes and making the backdoor deniable, that takes a little more thinking.

And for legal issues, there are any number of hand-wavy blame-shifting schemes that Intel and whoever would want to backdoor their RNG could use.

I contest the idea that we should ignore the fact that Intel's RNG could be backdoored. Just because other problems exist doesn't mean we should ignore this one. I agree that perhaps worrying about this constitutes being "too paranoid", but no cryptographer ever got hurt by being too paranoid, and not trusting your hardware is a great place to start.

[Peter Gutmann's preceding message omitted.]
On Sat, Jul 13, 2013 at 1:38 AM, William Yager <will.yager@gmail.com> wrote:

not trusting your hardware is a great place to start.
Heh, might as well just give up. http://cm.bell-labs.com/who/ken/trust.html

(I know what you meant, just couldn't resist.)

[Peter Gutmann's message 1 omitted.]

William Yager - will.yager@gmail.com writes

>no cryptographer ever got hurt by being too paranoid, and not trusting your
>hardware is a great place to start.

And while you're lying awake at night worrying whether the Men in Black have backdoored the CPU in your laptop, you're missing the fact that the software that's using the random numbers has 36 different buffer overflows, of which 27 are remote-exploitable, and the crypto uses an RSA exponent of 1 and AES-CTR with a fixed IV.

Peter.
It's nice that you can be so cavalier about this, but if your system's RNG is fundamentally broken, it doesn't really matter so much whether your other stuff is well-programmed or not. At least if my web browser is remotely exploitable, it doesn't break my disk encryption software, GPG, SSH, every other web browser I'm using, and pretty much every crypto appliance on my machine.

I'd rather have a rickety shed built on solid ground than a castle built on quicksand.

On Sat, Jul 13, 2013 at 4:32 PM, Peter Gutmann

[Peter Gutmann's preceding message 2 omitted.]

A good point, of course. So what should everyone do?

--

Noon Silk
[Messages omitted by Patrick Mylund Nielsen, William Yager, Peter Gutmann, Nico Williams.]

Arrange that a certain specific sequence of data operations, which can be triggered by processing an incoming packet, switches the random number generator from true random mode to pseudo random mode based on a key found in that data.

Noon Silk <noonslists@gmail.com> writes:

>A good point, of course. So what should everyone do?

Look for things, and fix things, in order of likelihood of occurrence and exploitability. (Strong) Crypto is bypassed, not penetrated, so address that first. Once you've addressed all of those issues, then you can start looking for the tape measure to determine how much tinfoil you'll need for the hat.

Peter.

William Yager <will.yager@gmail.com> writes:

>It's nice that you can be so cavalier about this, but if your system's RNG is
>fundamentally broken, it doesn't really matter so much whether your other
>stuff is well-programmed or not.

Well I'm not sure what thread you're coming in from, but the current one was about the issue of unnecessary paranoia about MIB's backdooring CPUs (and their RNGs). Good RNG design is an entirely different issue, see e.g.

https://www.usenix.org/legacy/publications/library/proceedings/sec98/gutmann.html.

>At least if my web browser is remotely exploitable, it doesn't break my disk
>encryption software, GPG, SSH, every other web browser I'm using, and pretty
>much every crypto appliance on my machine.

If your browser is remotely exploitable then it breaks everything on what used to be your machine.

Peter.
On 13 July 2013 03:20, Peter Gutmann <pgut001@cs.auckland.ac.nz> wrote:

[Gutmann message 2 omitted.]

But what's the argument for _not_ mixing their probably-not-backdoored RNG with other entropy?
Ben Laurie <ben@links.org> writes:

>But what's the argument for _not_ mixing their probably-not-backdoored RNG
>with other entropy?

Oh, no argument from me on that one, mix every entropy source you can get your hands on into your PRNG, including less-than-perfect ones, the more redundancy there is the less the chances of a single point of failure.

(Look at the Capstone design to see what the MIB are actually doing, they have a noise-based RNG, and ANSI X9.17 generator, and a straight counter, all fed into a SHA-1 PRNG, for redundancy).

And then run every static source code analysis tool you can find on your RNG, and implement dynamic analysis if you can, and perform entropy checks, and run a self-test with known-good test vectors on startup, and ... well, you get the picture.

This is just careful engineering. Worrying about what the MIB are up to is paranoia. If you apply your security engineering well, you don't need to worry about paranoia.

(Well, up to a certain extent anyway. Checked your keyboard firmware and wiring recently? Was that TSOP always there? It looks newer than the surrounding circuitry).

Peter.

On 13/07/13 09:32 AM, Peter Gutmann wrote:

[Gutmann message 2 omitted.]

;) has everyone had a read of this:

http://www.infoworld.com/d/security/in-his-own-words-confessions-of-cyber-warrior-222266

iang

ps, my comments here:

http://financialcryptography.com/mt/archives/001439.html

On 13 July 2013 10:11, Peter Gutmann <pgut001@cs.auckland.ac.nz> wrote:

> and run a self-test with known-good test vectors on startup, and ... well, you get the
> picture.

Amusing story: FIPS 140 requires self-tests on the PRNG. There was a bug in FIPS OpenSSL once where the self-test mode got stuck on and so no entropy was fed into the PRNG.

Also, back when I was doing FIPS 140 they made me remove some of the entropy feeds into the PRNG - particularly ones that protect against pool duplication over forks.
On 13/07/13 09:43 AM, Noon Silk wrote:

> So what should everyone do?

Risk analysis. Which starts with your business model.

What you do is go talk to your customers and figure out what happens to them. Formally, you would figure out the frequency of these events, and multiply them by the damages. Order them that way. Concentrate on the top one first, munch your way down the list.

If you do this, in ordinary business, you will find that the NSA isn't even on the list, unless for some reason you targetted some space that they also targetted [0].

<advert> E.g, in my current business I'm dealing with savings for v. poor women in Africa. The threats that are hitting them are shakedowns by police, government, scammers, banks, merchants, each other, family, and self, not necessarily in the order we westerners expect. Sometimes with violence. So those are the things I'm building the system to protect against, which of course takes some cryptography to preserve and lock down assets rather than hide them, mixed with a lot of other things... your classic old 1990s CIA models aren't going to help a lot here. </>

iang

[0] jihadist websites, CAs and chat systems for Americans spring to mind.