User: Password:
|
|
Subscribe / Log in / New account

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Ars Technica reports that effective in FreeBSD 10 (currently RC1 is available), processors from Intel and Via Technologies will no longer be trusted as the sole source of random numbers. "Specifically, "RDRAND" and "Padlock"—RNGs [Random Number Generators] provided by Intel and Via respectively—will no longer be the sources FreeBSD uses to directly feed random numbers into the /dev/random engine used to generate random data in Unix-based operating systems. Instead, it will be possible to use the pseudo random output of RDRAND and Padlock to seed /dev/random only after it has passed through a separate RNG algorithm known as "Yarrow." Yarrow, in turn, will add further entropy to the data to ensure intentional backdoors, or unpatched weaknesses, in the hardware generators can't be used by adversaries to predict their output."
(Log in to post comments)

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 10, 2013 23:17 UTC (Tue) by pr1268 (subscriber, #24648) [Link]

Having only read LWN's summary here, am I to assume that the BSD folks are taking a similar philosophical, if not technical, approach to Linux's use of RDRAND?

I kinda remember RDRAND raised a big stink with Linux users...

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 0:10 UTC (Wed) by rbrito (subscriber, #66188) [Link]

I posted this on Ars post on Facebook:

Everybody should read prof. Umesh Vazirani's paper from 1986 regarding "merging" multiple weak pseudo-random sources into a stronger pseudo-random generator.

The title of the paper is "Generating Quasi-Random Sequences from Slightly Random Sources".

The paper is at: http://www.cs.berkeley.edu/~vazirani/pubs/quasi.pdf

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 7:49 UTC (Wed) by ekj (guest, #1524) [Link]

It's trivially true that combining several weak pseudo-random sources can result in a randomness that is at least as strong as the strongest source;

If you simply XOR any number of weak pseudo-random sources, then the resulting stream of bits will be (genuinely) random at any point where at least one of the input-streams are random.

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 7:59 UTC (Wed) by dakas (guest, #88146) [Link]

While this is true on the surface, it isn't true for /dev/random which pauses until it can deliver appropriate entropy. Unless it does not count unreliably random sources towards its entropy, adding a non-random source will cause a correlated stream coming from /dev/random, in the extreme case turning it into /dev/urandom essentially.

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 8:45 UTC (Wed) by ekj (guest, #1524) [Link]

When you input entropy to /dev/random you can indicate the estimated amount of randomness in your data. RNDADDENTROPY ioctl on /dev/random for example takes a struct as argument:
struct rand_pool_info {
                  int    entropy_count;
                  int    buf_size;
                  __u32  buf[0];
              };
If you overestimate entropy_count, then all bets are off. But in that case you're not using the interface as intended and the bug is in your code.

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 22:20 UTC (Wed) by wahern (subscriber, #37304) [Link]

Entropy estimation like this is pure folly from a practical engineering perspective. The Yarrow algorithm was succeeded by Fortuna, and Fortuna doesn't care about entropy estimation. It focuses on maximizing whatever amount of entropy it receives.

/dev/random needs to disappear entirely, or become equivalent to /dev/urandom. Because otherwise the security of your system is predicated on some random engineer sticking his thumb into the wind and guesstimating how much entropy is coming from a device, based on a one-off experiment done by some other researcher 10 years ago on different hardware. It's patently ludicrous on its face.

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 9:13 UTC (Wed) by error27 (subscriber, #8346) [Link]

Yes.

In the linux kernel, we use the mix_pool_bytes() function to add data to the pool but there is a separate function credit_entropy_bits() which says how random and trusted the data is.

On embedded devices you don't have a random number generator, a keyboard, spinning disks, or any kind of timer randomness, or a random seed stored in the boot loader. You don't want the first few reads of /dev/random to be the same thing on all the thousands of devices. So we add things like MAC address or other device information to the random pool. We don't count it as entropy, but at least hopefully it makes the systems a little bit different from each other.

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 17:27 UTC (Wed) by FranTaylor (guest, #80190) [Link]

Most embedded devices DO INDEED have random number generation hardware.

http://www.st.com/web/en/catalog/tools/PF258754

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 20:37 UTC (Wed) by error27 (subscriber, #8346) [Link]

The point is that randomness on embedded devices has been an ongoing problem.

See this paper on the flaws in openWRT. http://eprint.iacr.org/2006/086.pdf

Here is another article that says 9.6% of SSH hosts have shared keys. http://lwn.net/Articles/507115/ Presumably their only source of randomness is network traffic and they configure their SSH key before configuring the network. It means that address space randomization fails as well. That paper is actually what prompted Linus to start adding MAC addresses to the random pool, just so we don't have this embarrassing thing.

As hardware becomes cheaper and people grow more concerned about security, then I think this situation will improve. But the hardware that exists out in the world now is pretty bad.

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 17:54 UTC (Wed) by rbrito (subscriber, #66188) [Link]

While the intuition of "just XOR the sources" is sound, a lot of things in cryptography are just "intuitive/trivial" and plainly wrong, unless you define your threat model and provide a theorem/proof that your strategy really works.

And that's not even talking about implementations, that may have lots of issues (side channel attacks etc.).

So, in the end, while the idea of simply "XOR'ing" is what the paper proposes, the real meat of the paper is the proof that this scheme works and has highly desired properties given the threat model.

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 18:33 UTC (Wed) by ekj (guest, #1524) [Link]

I know. I've actually got a reasonable background in crypto. Enough to know that there's a million ways of getting things subtly wrong.

Nevertheless, it's trivial math to demonstrate that xoring N values will result in a random result for any bit that is truly random for at least 1 of the values. This particular math truly *is* trivial.

I don't think that particular scheme of mixing several input-values to create a more random output-stream is a good one actully, because it has several undesirable properties. (for example if you XOR the precise timing of 4 independent events, then these may have best entropy in the last bits and for best-possible output-randomness you'd want to spread the randomness to as many bits as possible -- xor keeps the randomness only in the spot where it already exists.)

The main advantage is that it's easy to analyze, so that's why I choose that algorithm for my comment. (I wasn't even aware that the paper suggest the very same thing)

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 18:50 UTC (Wed) by janfrode (subscriber, #244) [Link]

If the last value you're xoring is coming from an instruction like rdrand, your trivial math doesn't work anymore. Ref: https://twitter.com/DefuseSec/status/408975222163795969

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 20:47 UTC (Wed) by ekj (guest, #1524) [Link]

Yes it does, unless you misunderstand me.

(((A xor B) xor C) xor D) will yield a random result if at least one of the 4 inputs is genuinely random. This is trivial math. It does assume that each of the inputs is generated independently, depending on your assumptions that may or may not be a problem.

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 21:22 UTC (Wed) by mathstuf (subscriber, #69389) [Link]

What if two of the sources are, individually, genuinely random, but together are correlated? As an example, stream A and stream ~A are both random if either one is, but their XOR is quite deterministic. I imagine this could happen if you have one source as the clock which heats up a hwrng and influences its values enough that clock XOR hwrng has less entropy.

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 21:51 UTC (Wed) by janfrode (subscriber, #244) [Link]

Did you read the twitter link? The D is generated by a "rdrand" that's observing your A,B,C xors, so it can trigger any results it wants to. And it's a real possibility for pre 3.12.3 /dev/random.

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 11, 2013 23:08 UTC (Wed) by foom (subscriber, #14868) [Link]

A real possibility? Well, the link showed that you can write an emulator which targets linux's particular instruction sequence around a particular call to rdrand.

The wonderful thing about compromising rdrand "honestly" (that is: simply compromising the entropy of the underlying generator), is that it works universally. Doing a trick like this seems quite fragile and unlikely, comparatively.

But if you're going to posit that your CPU knows about linux's rdrand instruction sequence, so as to break it, then I'm not sure why you would stop there. The CPU could have any number of other backdoors, maybe one that can trigger on the instruction sequence used to process a network packet in the linux network stack, so that the NSA can cause the CPU to run arbitrary instructions if you receive certain data.

"We cannot trust" Intel and Via’s chip-based crypto, FreeBSD developers say (ars technica)

Posted Dec 12, 2013 2:39 UTC (Thu) by gdt (subscriber, #6284) [Link]

With respect, the math ignores the typical attack vectors, particularly timing attacks. What you should do is to mix in the hardware generator last -- it is the most robust against timing and other covert channel attacks and using it last protects the result against timing attacks on the software entropy pool. This also implies that mixing RDRAND into the entropy pool isn't the most secure method, rather an application should make random number r by:

s = read(/dev/random) # Without entropy from /dev/hwrng
h = read(/dev/hwrng)
r = xor(s , h)


Copyright © 2013, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds