FreeBSD Developers Will Not Trust Chip-Based Encryption

New submitter srobert writes "An article at Ars Technica explains how, following stories of NSA leaks, FreeBSD developers will not rely solely on Intel's or Via's chip-based random number generators for /dev/random values. The values will first be seeded through another randomization algorithm known as 'Yarrow.' The changes are effective with the upcoming FreeBSD 10.0 (for which the first of three planned release candidates became available last week)."

Comments

Very Smart Move

[Anonymous Coward]

They have every reason NOT to trust the chips. Trust, but verify is always the correct way.

Re:Very Smart Move

[Billly Gates]

You know 6 months ago such a comment would be modded -1 and this story would have the foot icon for humor.

My have things changed. Microsoft was not that bad DRM monster we feared 12 years ago. First it turned out to be Apple in which we cheered them 10 years ago here on /.

But both companies fail far in comparison to the US government and this is something I would not have imagined in my wildest nightmares.

Re:Very Smart Move

[Anonymous Coward]

With a surname that's a homophone of "stallin'" I'm guessing this individual was a Java programmer

Re:Very Smart Move

[Anonymous Coward]

I take it you didn't even actually read what he said, then.

Linus Torvalds responds:

Where do I start a petition to raise the IQ and kernel knowledge of people?

Guys, go read drivers/char/random.c. Then, learn about cryptography. Finally, come back here and admit to the world that you were wrong.

Short answer: we actually know what we are doing. You don't.

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.

Really short answer: you're ignorant.

TL;DR: Linux was NOT trusting chips and doing a variant of what FreeBSD plans to do now since quite a bit before.

Makes sense ...

[MacTO]

One of the features of open source software is that the code, thus the algorithms, can be examined by a third party. In the case of chips, this is very difficult to do. Most people are stuck trusting that the designer implemented the algorithm they said they did, and that they implemented it properly (the former implying no malice and the latter implying competence). That is particularly true for something like random number generators, which are intended to be non-deterministic as far as the software is concerned so any testing the implementation can only be done statistically. Very few people have the ability to examine the physical design of the chip to check the actual implementation.

Is there any way to gain trust in a chip?

[Jeremi]

Just out of curiosity: Given a "black box" implementation of a random number generator, is it possible to test its output sufficiently to gain some faith in its proper randomness?

Seeing as such a piece of hardware need not (and hopefully would not) have any inputs, only an output, it's hard to imagine how someone might hide (and later trigger) a back-door mechanism that could change its behavior post-testing. (But I'm sure there is some way to do it that I'm not thinking of ;))

Re:Is there any way to gain trust in a chip?

[Anonymous Coward]

Black box? No. Even if testing proved it was absolutely random for the first N numbers, there is no way to be certain that N+1 is not the first of a string of non-random numbers.

But it's not necessary to make it a black box. Physical systems take well known phenomena and use them to to generate random numbers. http://en.wikipedia.org/wiki/Random_number_generation#Physical_methods Done this way, you can make a "transparent box" that performs great and is trustworthy.

Re:Is there any way to gain trust in a chip?

[Anonymous Coward]

Ok, I'll take a shot, here's two of them for you:

1: Chip outputs the digits of pi starting at some crazy number of decimal places out that only the NSA has had enough hours on the supercomputer to find. Your chip now puts out data that you cannot distinguish from random, but that the NSA can perfectly predict. They go to their giant database of all of your internet traffic ever, and can now read whatever they would like, as all of your keys are now utterly, hopelessly broken.

2: Chip internally stores the last n random numbers that it has output. Later, the NSA can confiscate your computer, subject the chip to some undocumented state that causes it to barf up its secrets, and again all your keys are now utterly, hopelessly broken.

Re:Is there any way to gain trust in a chip?

[tippe]

Really? I just did this:

$ cat /dev/random | xxd | head -n 10
0000000: 414c 4c59 4f55 5242 4153 4541 5245 4245 ALLYOURBASEAREBE
0000010: 4c4f 4e47 544f 5553 5448 414e 4b53 4652 LONGTOUSTHANKSFR
0000020: 4f4d 5448 454e 5341 414c 4c59 4f55 5242 OMTHENSAALLYOURB
0000030: 4153 4541 5245 4245 4c4f 4e47 544f 5553 ASEAREBELONGTOUS
0000040: 5448 414e 4b53 4652 4f4d 5448 454e 5341 THANKSFROMTHENSA
0000050: 414c 4c59 4f55 5242 4153 4541 5245 4245 ALLYOURBASEAREBE
0000060: 4c4f 4e47 544f 5553 5448 414e 4b53 4652 LONGTOUSTHANKSFR
0000070: 4f4d 5448 454e 5341 414c 4c59 4f55 5242 OMTHENSAALLYOURB
0000080: 4153 4541 5245 4245 4c4f 4e47 544f 5553 ASEAREBELONGTOUS
0000090: 5448 414e 4b53 4652 4f4d 5448 454e 5341 THANKSFROMTHENSA

Maybe there's a pattern there; I'm not sure. I guess that's the problem with randomness: you can never be sure.

Re:Is there any way to gain trust in a chip?

[Anonymous Coward]

All of this can be conveniently calculated by this tool, and neither of this will help you to distinguish actual randomness from a result of cryptographic algorithm working on extremely predictable input.

For example, here's what it says about 32M of random bytes:
Entropy = 7.999994 bits per byte.

Optimum compression would reduce the size
of this 33554432 byte file by 0 percent.

Chi square distribution for 33554432 samples is 257.80, and randomly
would exceed this value 43.91 percent of the times.

Arithmetic mean value of data bytes is 127.4968 (127.5 = random).
Monte Carlo value for Pi is 3.140698143 (error 0.03 percent).
Serial correlation coefficient is 0.000015 (totally uncorrelated = 0.0).

And here's what it says about 32 megabytes generated by SHA-256 hashing of 'Intel Intel Intel Intel Intel' concatenated with a 24 bit counter:
Entropy = 7.999994 bits per byte.

Optimum compression would reduce the size
of this 33554432 byte file by 0 percent.

Chi square distribution for 33554432 samples is 269.79, and randomly
would exceed this value 25.08 percent of the times.

Arithmetic mean value of data bytes is 127.4839 (127.5 = random).
Monte Carlo value for Pi is 3.141798922 (error 0.01 percent).
Serial correlation coefficient is 0.000266 (totally uncorrelated = 0.0).

See how different the results look?.. Oh, wait, they don't :(

For comparison, here's results for 32MB of simply ('Intel Intel Intel Intel Intel' concatenated with a 24 bit counter):
Entropy = 3.465109 bits per byte.

Optimum compression would reduce the size
of this 33554432 byte file by 56 percent.

Chi square distribution for 33554432 samples is 1153826816.00, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 91.5781 (127.5 = random).
Monte Carlo value for Pi is 3.948254105 (error 25.68 percent).
Serial correlation coefficient is 0.079051 (totally uncorrelated = 0.0).

Re:Wise

[Minwee]

Every time an OpenBSD system needs a random number, instead of trusting any hardware device, it phones home and asks Theo to provide one.

Re: what's that going to accomplish?

[Anonymous Coward]

https://www.schneier.com/yarrow-qa.html

your ignorance is unjustifiable

Re:what's that going to accomplish?

[houstonbofh]

Because true random in software is computationally expensive. Adding a layer of obfuscation on top of the untrusted hardware gives you a better random cheaply, and avoids potential back-doors in the hardware generator.

Re:Wise

[maxwell demon]

I think it phones to this place. However some developers don't trust that random number generator and instead opt for this implementation.

nine nine nine...

[jakedata]

http://dilbert.com/strips/comic/2001-10-25/

That's the problem with randomness, you can never be sure.

FYI, Linux did this 18 months ago

[swillden]

One of the first things Ted Ts'o did when he took back maintainership of /dev/random in Linux was to stop depending solely on the hardware RNG.

https://plus.google.com/117091380454742934025/posts/SDcoemc9V3J?e

TRNG using discrete components?

[QuasiSteve]

Given that it's stated that you can't trust a chip's encryption routines, which at the basis means that you don't trust its random number generator, and given that 'a chip' extends down from the latest Intel to a relatively lowly PIC, is anybody aware of an actually available TRNG (true/hardware random number generator) built out of discrete components?

Comments to a Bruce Schneier post titled "Surreptitiously Tampering with Computer Chips" once suggested this would be the only way to 1. be certain* of no tampering and 2. have reasonably sufficient output bandwidth to be used in practical applications.

However, I haven't seen any actual implementation. My Google-fu may be failing me, though.

* Barring some pretty sweet shenanigans like those pulled by Henryk Gasperowicz; [Spoiler video](https://www.youtube.com/watch?v=-KMLmpC7-Ls). I can't see manufacturers including any crypto-defeatery bits into a basic transistor thinking that it just might possibly be used in an actual crypto application, and eat the cost somehow.

Re:Wise

[Carnildo]

According to the OpenBSD link, OpenBSD uses the Intel and Via random-number generators, but not as the sole source of randomness. The nice thing about mixing random number generators is that if you do it right (like OpenBSD does), the result is at least as random as the most random source: a bad RNG does not reduce the overall quality of randomness.