×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

FreeBSD Developers Will Not Trust Chip-Based Encryption

Soulskill posted about 4 months ago | from the fool-me-once,-shame-on-you dept.

Encryption 178

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)."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

178 comments

Very Smart Move (5, Insightful)

Anonymous Coward | about 4 months ago | (#45663917)

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

Re:Very Smart Move (1)

Anonymous Coward | about 4 months ago | (#45663991)

He who writes the code decides nothing.
He who executes the code decides everything.

-- aleph stalin

Re:Very Smart Move (3, Interesting)

Billly Gates (198444) | about 4 months ago | (#45664053)

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 (0)

Anonymous Coward | about 4 months ago | (#45664243)

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

Your imagination seems a bit limited, then. If it can be done, if there is a reason to do it, then it is done. Are there black helicopters flying over your bedroom collecting your thoughts? No. Are people using trying to record information on computer networks, like they did on radio waves for years? Yes. Is the US Government doing it? Sure. Are other governments? Sure. Are other non-governmental entities doing it? Probably on a smaller scale. Does it mean the end of the world? No.

Re:Very Smart Move (2)

PopeRatzo (965947) | about 4 months ago | (#45664583)

Are there black helicopters flying over your bedroom collecting your thoughts?

Why would they need black helicopters to fly over your bedroom when they can just get them directly from your email?

Is the US Government doing it?

You know they are.

Are other governments?

Not the free ones.

Re:Very Smart Move (2)

Em Adespoton (792954) | about 4 months ago | (#45665175)

Are there black helicopters flying over your bedroom collecting your thoughts?

Why would they need black helicopters to fly over your bedroom when they can just get them directly from your email?

Is the US Government doing it?

You know they are.

Are other governments?

Not the free ones.

True governance comes at a price. Always.

Re:Very Smart Move (1)

AHuxley (892839) | about 4 months ago | (#45664703)

AC you seem to have forgotten the "parallel construction" aspect for use in US domestic courts and the massive domestic surveillance network that supports such efforts:)
So thanks to Snowden many more people can understand that the US legal structure has changed.
Encryption will slowly have to be corrected so that non-governmental entities and former government staff cannot just sell gov methods to anyone for cash.
The "radio waves" aspect was always sold to countries and staff as watching the Soviet Union. Now we know it was all for internal, domestic use too.

Re:Very Smart Move (2)

lgw (121541) | about 4 months ago | (#45664389)

The RNG threat is particularly bad, because it looks like only one person would need to be in the know to sabotage the RNG on silicon, and it would bypass any review process, and it would be very hard to detect by observation of the RNG (assuming it still had, say, 32 bits of entropy).

Re:Very Smart Move (0)

Anonymous Coward | about 4 months ago | (#45664175)

What? Don't be silly, these chips are all so perfectly safe and perfectly usable for things like encrypting communications for us... *ahem* your customers! You're such a worrywart!

Signed,
um...
Mr. Norman Samuel Ayers

(/me starts a tally of wooshes)

Re:Very Smart Move (2, Funny)

Anonymous Coward | about 4 months ago | (#45664365)

What? Don't be silly, these chips are all so perfectly safe and perfectly usable for things like encrypting communications

.oO(wait, that was too subtle, nobody will get my funny joke)

for us... *ahem* your customers!

.oO(wow, i'm really funny and sarcastic. just add a little more so nobody can't possibly miss it)

You're such a worrywart!

Signed, um...

.oO(ba-dumm tsss - i guess i will need to explain my next awesome joke too, by using boldface - otherwise nobody might get the subtle NSA reference)

Mr. Norman Samuel Ayers

.oO(well, i guess my humor is just too sophisticated, people will probaly miss it despite me repeatedly explaining my jokes. so let me just inb4 this)

(/me starts a tally of wooshes)

Re:Very Smart Move (0)

Anonymous Coward | about 4 months ago | (#45665125)

What an insightful analysis...

NSA Honeypot (0)

Anonymous Coward | about 4 months ago | (#45664329)

The NSA has an innocent-looking honeypot right here [random.org] for all you wise-guys.

If you want proper random numbers, get yourself a radioactive source [wikipedia.org] .

Entropy source (1)

tchuladdiass (174342) | about 4 months ago | (#45665153)

Why not just hook a microphone on the inside of the computer to pick up the fan noise, and use that as a random source? I'm sure there's some entropy in there.

Re:Very Smart Move (1)

mlts (1038732) | about 4 months ago | (#45665379)

Trust but verify is important, but chips are incredibly hard to know if a random source is truly random, as opposed to, say the output of a clock AES encrypted, so that it appears random.

Best thing to do is have the chip be part of the RNG, but not the only part, so another random source will provide enough unpredictability to keep thing secure.

Wise (1)

Anonymous Coward | about 4 months ago | (#45663925)

It's always wise to get entropy from as many places as you can; in light of the NSA revelations, it's time relying on just one becomes something people don't even consider anymore.

Is OpenBSD, the 'security first' BSD, ahead of, or behind the curve with this?

Re:Wise (4, Funny)

Minwee (522556) | about 4 months ago | (#45664021)

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:Wise (5, Funny)

maxwell demon (590494) | about 4 months ago | (#45664089)

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

Re:Wise (0)

Anonymous Coward | about 4 months ago | (#45665151)

Really paranoid developers don't trust that one either. We use good-old fashioned dead trees [amazon.com] for our random numbers!

Re:Wise (0)

Anonymous Coward | about 4 months ago | (#45664043)

I would assume ahead or on par. The benefit of the BSD license and the BSD projects being similar is that the various projects are always looking at the others' code trees for ideas and software to use. They all do it and it's encouraged.

Re:Wise (1)

aliquis (678370) | about 4 months ago | (#45664063)

I googled it:

http://www.openbsd.org/crypto.html#hardware [openbsd.org]
https://lobste.rs/s/gbe1zl/we_cannot_trust_intel_and_via_s_chip-based_crypto_freebsd_developers_say [lobste.rs]

I don't know whatever that actually mean, how it is or how reliable anything else is. Maybe someone with some actual knowledge can provide the answers :) (My thought was that one could likely use different randomizers.)

Re:Wise (4, Interesting)

Carnildo (712617) | about 4 months ago | (#45664789)

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.

Re:Wise (0)

Anonymous Coward | about 4 months ago | (#45665217)

Depends on how bad that RNG really is (how can an RNG done right be bad?). Try this one on for size: f(x): x XOR x.

Re:Wise (1)

Anonymous Coward | about 4 months ago | (#45665767)

It's assumed in proofs that two different RNGs are _independent_. If they're independent, and you use the correct constructs, then you're guaranteed to be no worse off than the best RNGs.

Re:Wise (1)

thesupraman (179040) | about 4 months ago | (#45664355)

You mean just like Linux has for quite some time?

After all, these hardware random sources feed the entropy pool, however are certainly not its only source.
Hell, applications can even contribute to the pool as they wish, and that is not considered an issue no matter how non-random their contribution is.

FreeBSD and its reliance on the Yarrow approach is much more 'sensitive' to its PRNG source(s), so its about time they caught up..

http://en.wikipedia.org/wiki//dev/random

Then again, random numbers tend to be treated almost as a religious argument rather than a technical one.

Re:Wise (2)

Thud457 (234763) | about 4 months ago | (#45664701)

random numbers tend to be treated almost as a religious argument rather than a technical one.

Hail Eris!

Re:Wise (0)

Anonymous Coward | about 4 months ago | (#45665423)

Then again, random numbers tend to be treated almost as a religious argument rather than a technical one.

Because random numbers are only random to those who believe. Nothing is random in the deterministic universe. We haven't backdoored the RNG we call "existence", but just like the hardware RNG, it's not actually random! More accurately, a hardware RNG cannot be random in a deterministic universe.

Re:Wise (0)

Anonymous Coward | about 4 months ago | (#45665909)

Fortunately, we don't live in a deterministic universe!

Also, you're just wrong. Even _if_ we lived in a deterministic universe, you can still have unpredictable random numbers. This is sometimes called "mechanical randomness", because it doesn't fundamentally rely on quantum indeterminism. You can construct an unpredictable RNG in a deterministic universe if the processing power needed to compute the next sequence is greater than your adversary has available.

Because the _mechanical_ cause+effect of even the most simplest of processes around us can result in chain reactions that very quickly result in an unfathomably large number of free variables, it's actually trivial to build RNG's that no computer in the universe could crack. Think of it this way: if the universe is one big computer, and in order to predict the next event you need to simulate that universe from the very first instant, and to simulate it you need a bigger computer, where are you going to find that computer? Nowhere.

Many hardware RNGs can be described as either quantum RNGs or mechanical RNGs. For example, thermal noise based RNGs can be described either way, and so they can be proven secure whether quantum mechanics is real or not. You can prove they're secure by proving that no human being could possibly build a computer capable of computing the next sequence. To do that you just need to establish the limitations in how far back they can record the inputs (a few missed atomic collisions anywhere in the prior chain of events could be enough to fatally screw up the simulation), and the limitations of their processing ability.

what's that going to accomplish? (1)

Anonymous Coward | about 4 months ago | (#45663955)

if the idea is not to trust the hardware implementation then why use it alongside "Yarrow" in the first place? This just seems like the glorious Foundation using recent news about the NASA as a self-promotion tactic and even to a layman it's a poor one. "Trust FreeBSD, we still use rdrand et. al., but we filter it through some vague algorithm called Yarrow that makes it safe!"

You'll forgive me for not being entirely convinced, particularly when even the latest release of 10 still refuses to boot and install properly on my UEFI-based system.

Re:what's that going to accomplish? (0)

Anonymous Coward | about 4 months ago | (#45664033)

if the idea is not to trust the hardware implementation then why use it alongside "Yarrow" in the first place? This just seems like the glorious Foundation using recent news about the NASA as a self-promotion tactic and even to a layman it's a poor one. "Trust FreeBSD, we still use rdrand et. al., but we filter it through some vague algorithm called Yarrow that makes it safe!"

You'll forgive me for not being entirely convinced, particularly when even the latest release of 10 still refuses to boot and install properly on my UEFI-based system.

Yeah, I was wondering the same thing -- if you don't trust it, don't use it, since it just gives you a false sense of security - if Yarrow is cryptographically secure, why combine it with the hardware RNG? "Well, the on-chip RNG might be compromised, but at least I'm combining it with Yarrow..... Yarrow might not be secure, but at least I'm combining it with the on-chip RNG."

That seems a little like saying "I think the burglar knows the combination on my padlock, so I'm going to add this other keyed lock just in case. I think the burglar has a key to my keyed lock, but at least I have the combination lock too". Having 2 locks might make it a little harder for a thief to break in, but if you are certain that one of the locks is secure, why do you need the second one? And if you're not sure that either one is secure, are you really gaining anything by using two - maybe you should spend some time finding a lock that you *do* trust.

Re:what's that going to accomplish? (0)

Anonymous Coward | about 4 months ago | (#45664209)

It's called redundancy. Let's say I hack Yarrow or the NSA builds in a back door to Intels hardware? It's not a false sense of security, it's redundancy.

Re:what's that going to accomplish? (1)

aardvarkjoe (156801) | about 4 months ago | (#45664267)

And if you're not sure that either one is secure, are you really gaining anything by using two - maybe you should spend some time finding a lock that you *do* trust.

There is no PRNG, Yarrow included, that we can say with 100% certainty that is not (or will not be) broken. The point of using multiple PRNGs is so that even if one or more of the components is compromised, it doesn't compromise the entire system. To use your metaphor: if your options are a padlock and a keyed lock, and there's a 25% chance each that a burglar could bypass them -- wouldn't you use both locks to reduce the probability of being robbed to 1/16 instead of 1/4?

Re:what's that going to accomplish? (1)

Em Adespoton (792954) | about 4 months ago | (#45665427)

And if you're not sure that either one is secure, are you really gaining anything by using two - maybe you should spend some time finding a lock that you *do* trust.

There is no PRNG, Yarrow included, that we can say with 100% certainty that is not (or will not be) broken. The point of using multiple PRNGs is so that even if one or more of the components is compromised, it doesn't compromise the entire system. To use your metaphor: if your options are a padlock and a keyed lock, and there's a 25% chance each that a burglar could bypass them -- wouldn't you use both locks to reduce the probability of being robbed to 1/16 instead of 1/4?

That's not quite it, as we're not dealing with locks here, but patterns. And as you know, humans are pretty good at spotting patterns in the randomness.

The end result is that if you choose the wrong combination of PRNGs, you can end up with a result that has a decidedly non-random pattern embedded in it that can be exploited to do predictive analysis of the crypto. Layering more PRNGs on can actually help to isolate the pseudoness instead of the randomness. At some point, you need to use some algorithm to randomly select from the PRNGs, and do so in a way that eliminates the pseudo-generative effects of those sources while failing to introduce its own. The best way to do this is to use something very contextual, where it is highly unlikely an attacker would have access to all the variables.

Re: what's that going to accomplish? (5, Informative)

Anonymous Coward | about 4 months ago | (#45664045)

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

your ignorance is unjustifiable

Re: what's that going to accomplish? (0)

Anonymous Coward | about 4 months ago | (#45664649)

Well... no.

Taking the output of a "compromised" RNG and using that as a seed of a PRNG offers exactly 0 security.

If the chip RNG is in fact compromised as the authors state, then the compromiser can simply get the "random" number that the chip would have provided, and then run that through Yarrow themselves, resulting in the actual number just as easily had they not run it through Yarrow in the first place.

This is Security 101 stuff here. If you start with a compromised algorithm, running it through any number of other algorithms is only going to increase the amount of time to break the system by a constant factor and does absolutely nothing to provide any true security. "Security though obfuscation" and all that.

Re: what's that going to accomplish? (0)

Anonymous Coward | about 4 months ago | (#45664803)

... And that's why they're also adding other entropy sources instead of relying on just possibly compromised RNG.

That's basically the Pascal's wager - if on-chip RNG's working, they win and get better random stream, if it's broken - they lose nothing (as long as they don't count it towards available entropy estimate).

Re: what's that going to accomplish? (0)

Anonymous Coward | about 4 months ago | (#45665233)

A good PRNG should take a string of 0s in the state and produce a (pseudo)random distribution. This is the main yardstick, and also why many ciphers (stream ciphers especially) are used as the core of PRNGs.

Re: what's that going to accomplish? (2)

mlts (1038732) | about 4 months ago | (#45665495)

What is needed is are seed inputs. When a key is hit, get a super-accurate clock sample of it, hash it with MD5 [1], and toss it in the pool. Mouse movements, similar. If the computer is idle, this won't help much, but while it is in use, it should help provide enough unpredictable data to be up to par for security purposes. I'm sure there are other inputs that can be hashed over time and the hashed bits tossed in. Of course, the RNG from the chip can be easily tossed in as well. The good thing is that the most random factor "wins" in this case.

[1]: MD5 has its issues, but it is being used in this case as a bit blender, so hash collisions can happen, and not really matter. It would be wise to move to a newer algorithm like SHA-1024 or SHA-3, for more bits though.

Re:what's that going to accomplish? (4, Insightful)

houstonbofh (602064) | about 4 months ago | (#45664049)

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:what's that going to accomplish? (2)

Billly Gates (198444) | about 4 months ago | (#45664155)

Not to mention insecure too.

There are only so many milliseconds on the clock to use on the seed. Even if you use the mic statistically silence or a clicking sound will be heard for 90% of the users so that makes that seed bad too. Network? At home there is little traffic and even at work there are the same patterns from Cisco and HP for 80% of the packets.

SGI had some interesting encryption methods that dealt with quantam mechanics on their servers and workstations. Man I miss them.

Re:what's that going to accomplish? (0)

Anonymous Coward | about 4 months ago | (#45664417)

Ground noise feedback in the PSU coming from the power company, transmission lines, and any random squirrels warming their nuts in a transformer somewhere (usually to their detriment).

That should be random enough. Not 60 Hz, but the variations on it. (Substitute "50 Hz" for Europe.)

Unfortunately, a good PSU smooths out garbage power and also has no way of providing it as a data point for the CPU. Also, UPS systems get in the way.

Re:what's that going to accomplish? (1)

dAzED1 (33635) | about 4 months ago | (#45664593)

you just...answered why it wouldn't work. If that much garbage is actually coming into the conditioned power, it will kill the system in very little time.

Re:what's that going to accomplish? (2)

Billly Gates (198444) | about 4 months ago | (#45664783)

you just...answered why it wouldn't work. If that much garbage is actually coming into the conditioned power, it will kill the system in very little time.

You know I had a problem with BSOD occuring frequently in a large call center.

Turns out hte problem was the big UPS for the whole floor spiked things and the power strips always tried to smooth things. Over a period of time the soldier would crack and burst due to the UPS doing hard rectangular patterns rather than waves when it alternated back and forth.

Real power from the wall was cleaner than the UPS for the power strips.

Re:what's that going to accomplish? (1)

Em Adespoton (792954) | about 4 months ago | (#45665645)

you just...answered why it wouldn't work. If that much garbage is actually coming into the conditioned power, it will kill the system in very little time.

Why? Is there something I need to know about electromagnetics and primary transformer coils being unable to handle variance in the amperage and voltage?

The DC provided by the PSU is by definition conditioned to some degree -- the transformer does this by using induced current to step down the voltage, then passes it through the rectifier (diode-cathode ring) which should smooth things out even further.

Unless you're saying that if there's enough garbage (read: degree of variance in amperage and voltage, vs frequency of change) to get through the transformer, you're going to kill your PSU, which is true.

Re:what's that going to accomplish? (1)

mlts (1038732) | about 4 months ago | (#45665537)

I've wondered about using a very high speed flip-flops, or on a simpler thing, a SR latch with both inputs on, and sampling the output. I remember some cryptographically secure RNGs doing this in lieu of a radium-painted chip.

Re:what's that going to accomplish? (0)

Anonymous Coward | about 4 months ago | (#45665271)

True random doesn't exist in software-only form, because virtually any software you or I touch is going to be executed deterministically wrt the underlying machine. That's why a real RNG uses something like a radiation source and software stuff is referred to as a PRNG.

Re:what's that going to accomplish? (0)

Anonymous Coward | about 4 months ago | (#45664257)

Hi,

Maybe you should try filing a PR or actually engaging the developers? They're hunting down the handful of models that won't boot. If you cooperate they'll gladly fix it for you.

Stop being a bad open source whiner and spend 15 minutes contributing for once.

Makes sense ... (4, Insightful)

MacTO (1161105) | about 4 months ago | (#45664011)

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.

Re:Makes sense ... (1)

Anonymous Coward | about 4 months ago | (#45664791)

Once you are talking about encryption or the algorithms around encryption the people that actually have any hope in hell of making an intelligent review of the code are as rare as hens teeth. closed or open their is very little difference in the level of reviews that happen in this area. Having said that you should never rely on one source of truth for randomisation anyway.

Re:Makes sense ... (0)

Anonymous Coward | about 4 months ago | (#45665319)

If it really matters (and by really matters, I mean, existing legal protections are insufficient to satisfy your risk tolerance), you really ought to engage an expert cryptographer, physicist, electrical engineer, and software developer. It won't be cheap, but for most people, it doesn't really matter. Either that or you can spend a decade or two trying to catch up yourself.

Re:Makes sense ... (0)

Anonymous Coward | about 4 months ago | (#45665873)

"there". you should have used "there"

Is there any way to gain trust in a chip? (4, Interesting)

Jeremi (14640) | about 4 months ago | (#45664019)

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? (1)

Billly Gates (198444) | about 4 months ago | (#45664103)

What kind of world do we live in when we can't even trust our own damn hardware! Seriously ...

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

Anonymous Coward | about 4 months ago | (#45664337)

I'm not sure why anyone's trusted "hardware" since at least the time System Management Mode was introduced with the 386.

The 386 also happens to be Intel's first processor not designed entirely by hand. This is not a coincidence. WAKE UP SHEEPLE!

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

Anonymous Coward | about 4 months ago | (#45664689)

Intel processors are shit. x86 is a turd.

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

K. S. Kyosuke (729550) | about 4 months ago | (#45664655)

Except that it's not your own damn hardware. It's mostly Intel's hardware. Most people don't make their own chips nowadays. ;-)

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

Anonymous Coward | about 4 months ago | (#45664115)

You would have to sample a large size of CPU's on a regular basis using an expensive and probably impossible process.

Re:Is there any way to gain trust in a chip? (5, Funny)

tippe (1136385) | about 4 months ago | (#45664359)

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 [dilbert.com] .

Re:Is there any way to gain trust in a chip? (3, Informative)

Anonymous Coward | about 4 months ago | (#45664191)

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? (1)

OzPeter (195038) | about 4 months ago | (#45664207)

Just out of curiosity: Given a "black box" implementation of any device, is it possible to test its output sufficiently to gain some faith in its proper operation?

Why do you stop at randomness? You are trusting a lot more hardware than just that when you use a computer.

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

Anonymous Coward | about 4 months ago | (#45664215)

You are so wrong. They don't have to have a back door to alter the results. If there is a way to determine the next number that random number generator based on previous results, then the numbers are no longer random to that observer. It is like you came from the future and you know the results of every lottery.

Re:Is there any way to gain trust in a chip? (3, Interesting)

Anonymous Coward | about 4 months ago | (#45664219)

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.

So the NSA can predict your video game ... (1)

perpenso (1613749) | about 4 months ago | (#45664625)

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.

More likely its just going to get the random numbers generated for a video game.

Re:So the NSA can predict your video game ... (1)

X0563511 (793323) | about 4 months ago | (#45665017)

If you're using /dev/random (or the Windows equivalent) instead of /dev/urandom for that, you're an idiot and probably have lots of open bugs related to your game hanging.

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

jasax (1728312) | about 4 months ago | (#45664231)

You could initialize the hardware RNG and a software (open code, verified by whoever is interested) implementation of the same algorithm with the same seed and compare if the first millions or billions of generated numbers were the same. Reseed and redo this a certain number of times and you statistically can reduce the probability of evil-non-randomness to (near) zero.

Of course, the existence of a programmed or delayed-opening backdoor of any sort in the chip would break this procedure...

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

X0563511 (793323) | about 4 months ago | (#45665027)

If you can feed in a seed and get the same output reliably, it's not a RNG, but a PRNG.

Re:Is there any way to gain trust in a chip? (1, Insightful)

SuperKendall (25149) | about 4 months ago | (#45664253)

The output can be completely random, but it doesn't matter if someone else has a mechanism to reproduce exactly the same random stream. Or the ability to toggle on the semi-random mode...

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

LordLimecat (1103839) | about 4 months ago | (#45664549)

AFAIK the term "random" refers to "non-deterministic"; that is, if you know you have a box here which you know will provide the same output as the box over there, neither one is "random".

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

SuperKendall (25149) | about 4 months ago | (#45664671)

Yes, but the point is you can still have something that is random until it is not.

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

Anonymous Coward | about 4 months ago | (#45664283)

Every electrical device has an input: Power. Without inspecting the silicon, there's no way to tell if a device is backdoored or not.

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

Anonymous Coward | about 4 months ago | (#45664287)

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?

Yes. But it takes a very long time to test it on the level that you need these days.

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

Anonymous Coward | about 4 months ago | (#45664335)

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?

You measure its the mean [wikipedia.org] and the auto-correlation [wikipedia.org] of produced numbers. A perfectly random system will have a mean half way between the min and max number and the auto-correlation should be a delta function (i.e.. completely uncorrelated).

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

bug1 (96678) | about 4 months ago | (#45664505)

You can also test to see how compressible it is, compression algorthithms recognising and removing patterns, so "good random" data should not be very compressible.

Re:Is there any way to gain trust in a chip? (3, Interesting)

Anonymous Coward | about 4 months ago | (#45665229)

All of this can be conveniently calculated by this tool [fourmilab.ch] , 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:Is there any way to gain trust in a chip? (2)

AHuxley (892839) | about 4 months ago | (#45665055)

Re 'output sufficiently to gain some faith in its proper randomness".
Back when cypher machines where unique physical devices sold to gov for embassy use the US and UK had two options:
Set their own device standard with Tempest to leak the plain text. Such a unit would pass all "proper" crypto testing as it was a real crypto unit. The plain text was leaking out as entered or printed and could be collected.
The great aspect was "trust" form the end user and the message was "safe" for sending.
The other option was to get to staff or set up a front company to sell junk weakened encryption at a low price or via a trusted brand in a 'neutral' country.
The low price would make any real commercial crypto efforts fail and set international standards to what junk brands where 'trusted' 'safe' and been used.
When countries started the read leaked fragments of their encypted communications in the press - that was the time never to trust 'hardware'.
After Snowden users can think back - you can have all the crypto post-testing you want as the US branded OS or tame telco or junk hardware/software is set for collecting all your keystrokes...
The same tricks seem like crypto magic to every generation of academics. The problem is anyone could have followed the methods via the press in the ~1960-70-80-90's.

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

VortexCortex (1117377) | about 4 months ago | (#45665067)

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?

Yes and No. One can statistically analyze output of the (pseudo) RNG and compare it to pure randomness, like atmospheric noise. However, you can't be sure there is no message in the stream. For example: Strong crypto produces enciphered data that looks exactly like pure randomness. It's one way we test for cryptographic strength. Indeed, BSD will now pipe RNG output through Yarrow (a pRNG based on hash functions) to produce randomness. Considering that knowing the initial state of a PRNG reveals its full exact stream of bits, and that hashes produce the same output for a given input: I'm not satisfied with this result either, unless the input is sufficiently salted with device IO timing and other such quasi-random states as in Linux's /dev/random entropy pool.

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 ;))

Strong crypto needs strong randomness for initialization vectors.

While it's true the Ken Thompson Microcode Hack [bell-labs.com] could exist in silicon (Chips could have full featured back-doors in them) it would be far less obvious and simpler to attack a single point of failure: The (hardware | pseudo) random number generator.

It's possible to build a (pseudo) Random Number Generator that is biased in a way that's not noticeably different from pure atmospheric noise in practice, and even passes all the NIST / Diehard tests for randomness. I built one such high entropy pseudo random number generator using a pool of 517 integers and a mixing system. I had arranged the mixing system such that based on a small sample of randomness (50 or so integers, ~1500 bits) one could deduce a weak signal inherent in the pool which then slowly revealed the entire random number generator state in a cascade effect via an Error correction coding present in the bit-stream.

Looking at the source code for my PRNG one wouldn't realize the thing had a back door in it via the selection of primes, constants, and the XOR, shift, AND, etc. mixing strategy itself. The implementation of error correction code akin to Reed Solomon Codes was hiding in plain sight. I sort of turned the weak signal bits on ear and presented them in the stream in "parallel" instead of "serial". The NIST tests chi-square, etc. against my PRNG proved indistinguishable from true random sources such as atmospheric noise, even with gigabytes of data to analyze thanks to the prime number sequence's weak enciphering of the bias pattern.

To make matters worse, I built the system around constants taken from a run of digits in Pi. When apparently any random values will do as inputs for an equation, a known source of digits like this is meant to put cryptographer's minds at ease in that the values aren't just 'magic numbers', pulled from thin air -- Constant numbers selected with possible nefarious purposes. For examples of such 'un-magic selections', see the initial constant states of nearly any hash function, such as MD5, SHA-1, or SHA-2, etc...

......!

According to RFC1925 - Rule 6(a), [ietf.org] it's always possible to add another layer of indirection. So, I put my "careful number selection" to create the backdoor one level higher than the values themselves. I went looking for sources of workable constant values in the supposed accepted places. Of course anyone can supply their own pool sizes and init values to defeat my random attack, but in practice folks will use the default values -- Esp. because I selected reasonable looking pool sizes, etc. which performed well. Even if you have a poorly performing PRNG, if it's a default RNG folks will still use it, as the RSA security toolkit's insane default selection of the probably backdoored Elliptic Curve PRNG proved.

If a lone crypto nut like me can do something devious like this in their spare time, then the NSA likely employs at least one such individual themselves.

Good hardware RNGs utilize quantum effects to produce lots of random bits fast. One can make a cheap quantum RNG with two IR-LEDs soldered to an old fashioned serial port -- Supply voltage and detect timing of the photon's arrival. The trick is determining and correcting the bit bias the system adds to the signal via clocks cycles, etc, on the fly; Simply perform a statistical test and correction periodically. However, the indication that the hardware RNG may not be simply quantum, but be implemented in microcode give rise to distrust.

Without a layer-by-layer tear-down of the individual chip and its microcode one wouldn't know if there were an algorithm leaking its state on purpose -- hiding a PRNG back door signal in the noise. Spot tests on the production line don't help, select chips could still be compromised. Finally, examining the silicon may not reveal the back door method: You can't trust the random number stream is random just by testing it or looking at the algorithm / implementation. The output looks the same as any random output or encrypted data, You'd need the key bit of insight to detect and decode the signal from the stream if it exists.

To reiterate: Just like bias can leak initial pseudo random number generator state in software; In hardware it's possible to hide the same stuff in plain sight too. Not only can you not trust the hardware random number generator, you may not be able to trust the the software random number generator either.

In my cross platform applications I take Linux's approach and use the user's input and timing, ect. to fill an entropy pool -- Even still it's important to look at the software in use and ensure it's no more complex than it need be. See: RFC1925, 8 and 12.

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

gnasher719 (869701) | about 4 months ago | (#45665227)

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?

Short answer: No.

Long answer: There is "statistical randomness" and "cryptographical randomness". "Statistical randomness" tells you whether a random number generator can be used reasonably to simulate random physical phenomena. "Cryptographical randomness" means that it is impossible to predict the next random number if you know the mechanism that produces the random numbers, and the previous sequence of random numbers. Statistical randomness can be tested. For example, if you calculate three random numbers a, b and c, there are six possible ways how they could be ordered, and each possible ordering should be equally likely. Cryptographical randomness cannot be tested.

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

melikamp (631205) | about 4 months ago | (#45665897)

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?

gnasher719 gave a nice answer, and I just want to add more. For statistical purposes, a true and fair RNG printing a string of zeroes and ones would at the very least print a normal number [wikipedia.org] , and to test for that, one would have to count the frequencies of substrings of every length, in every base, which of course can be done, but may get expensive if one wants a lot of confidence [wikipedia.org] .

What gnasher719 calls cryptographical randomness cannot be tested in practice, but in theory, one can run the countable set [wikipedia.org] of all computer programs in parallel, and see whether they can predict the digits of the RNG sequence with probability better than 1/2. Of course, this is completely intractable in the foreseeable future, with or without functional quantum computers.

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

cOldhandle (1555485) | about 4 months ago | (#45665583)

Even though it only has an output and no inputs, one trivial way of providing input would be to request random numbers in an irregular, timed pattern to trigger a state change in the obscured chip.

With alll we know about hardware backdoors (1)

ganjadude (952775) | about 4 months ago | (#45664073)

We have known for some time it is not impossible to hardcode a backdoor into a chip. I thought we already decided a while back that we cannot trust chip protection, in the past it was china chips but with the information given by snowden it only makes sense not to trust a chip from intel

They will be tried in secret in a secret court.. (1)

Anonymous Coward | about 4 months ago | (#45664119)

for violating secret orders they never even heard of :-)

Hipster Judges (0)

Anonymous Coward | about 4 months ago | (#45664717)

That order is too obscure, you probably never heard of it.

nine nine nine... (5, Funny)

jakedata (585566) | about 4 months ago | (#45664125)

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

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

FYI, Linux did this 18 months ago (4, Informative)

swillden (191260) | about 4 months ago | (#45664333)

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

Dumb headline (0)

Anonymous Coward | about 4 months ago | (#45664499)

The summary itself says it's just the RNG that they're not trusting; it doesn't say anything at all about not trusting the encryption. (Probably because the question of whether or not the encryption works correctly, is actually verifiable, unlike the RNG.) So why the dumb headline, which contradicts its own summary?

Me neither (0)

Anonymous Coward | about 4 months ago | (#45664569)

I wouldn't trust chip based encryption either, and I wouldn't trust anybody else that did.

TRNG using discrete components? (4, Interesting)

QuasiSteve (2042606) | about 4 months ago | (#45664711)

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" [schneier.com] 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:TRNG using discrete components? (0)

Anonymous Coward | about 4 months ago | (#45665409)

How about floating differential inputs to an ADC powered by a battery with the MSBs stripped off?

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...