Surreptitiously Tampering with Computer Chips

This is really interesting research: "Stealthy Dopant-Level Hardware Trojans." Basically, you can tamper with a logic gate to be either stuck-on or stuck-off by changing the doping of one transistor. This sort of sabotage is undetectable by functional testing or optical inspection. And it can be done at mask generation -- very late in the design process -- since it does not require adding circuits, changing the circuit layout, or anything else. All this makes it really hard to detect.

The paper talks about several uses for this type of sabotage, but the most interesting -- and devastating -- is to modify a chip's random number generator. This technique could, for example, reduce the amount of entropy in Intel's hardware random number generator from 128 bits to 32 bits. This could be done without triggering any of the built-in self-tests, without disabling any of the built-in self-tests, and without failing any randomness tests.

I have no idea if the NSA convinced Intel to do this with the hardware random number generator it embedded into its CPU chips, but I do know that it could. And I was always leery of Intel strongly pushing for applications to use the output of its hardware RNG directly and not putting it through some strong software PRNG like Fortuna. And now Theodore Ts'o writes this about Linux: "I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction."

Yes, this is a conspiracy theory. But I'm not willing to discount such things anymore. That's the worst thing about the NSA's actions. We have no idea whom we can trust.

Tags: , , , , , ,

Posted on September 16, 2013 at 1:25 PM • 242 Comments

Comments

Nicholas Weaver • September 16, 2013 1:48 PM

One bit of subtleness is the effect of the design decision by Intel to not to include the tRNG in the JTAG chain (a test feature that allows reading/setting portions of the chip), but only use a Built In Self Test (BIST) based on a 32b CRC.

The BIST is "replace tRNG with LFSR (Linear Feedback Shift Register) known pRNG on the input, cycle the output, and do a 32b CRC checksum on the results". Thus one brute-forces the constants so that it passes the BIST CRC test(s), since the test input is known, and with only 32b of CRC, brute force will find an answer.

Intel did this BIST-only because:

If there is a BIST failure during startup, the DRNG will refuse to issue random numbers and will issue a BIST failure notification to the on-chip test circuitry. This BIST logic avoids the need for conventional on-chip test mechanisms (e.g., scan and JTAG) that could undermine the security of the DRNG.

http://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide

On one hand, that makes sense-ish: JTAG on the INPUT (the ability to tie into the more general test chip framework rather than just a known initiated LFSR) to the hardware RNG would be questionable, as it would be easy to hijack. (Although given the microcode design on modern microprocesors, you could also possibly hijack RDRAND with alternate microcode).

But at the same time, there is no way to read the whole output with JTAG (which would prevent these 'stuck-bit' attacks from working), yet such a connection would prevent this attack from working.

Three months ago, my attitude would be 'yeah, makes sense as a tradeoff to do this BIST design, pity you can trojan it.'.

Today? Paranoia is infectious: its a great example of the corrosive damage that the NSA has done to US cyber-security.

Gareth Owen • September 16, 2013 1:52 PM

We need to examine intel's RNG more closely. Maybe we need more effective ways of evaluating RNGs in a black-box implementation - although my feeling is this has been explored without great success.

Intel's RNG is clearly suspect now - but until we can test it then what can we do?

Nicholas Weaver • September 16, 2013 1:55 PM

I suspect that the chip reverse-engineers are frantically adding techinques to determine the doping on transistors. But its a very hard problem, because in addition to being a late-bound attack, this can be done with just TWO different masks that are corrupted, so it would be quite reasonable for an attacker in the fab to produce a small batch of trojaned chips.

smc • September 16, 2013 2:01 PM

Is this open to test? I don't have the maths, but can you generate a whole pile of random numbers out of the stock intel method and measure the entropy in some way?

Steven • September 16, 2013 2:36 PM

Back when the NSA was pushing the Clipper chip, they were getting pushback, and one of the objections was that the whole design was secret. So at one point they briefed someone on the design, who was then allowed to report some details to the rest of the community.

One thing I remember is that the design included an RNG, and it was not a hardware RNG. It was a software RNG, the NSA explained, "because software can be audited."

Alyssa • September 16, 2013 2:48 PM

can't trust software.
can't trust firmware.
can't trust hardware.
argh.

p.s. kudos for spelling "Surreptitiously" !

nobodyspecial • September 16, 2013 3:05 PM

@smc - not on a single chip.
I can produce a perfectly randomly distributed stream of numbers - but I know what they are, so I know the next one in the sequence.

Presumably you could do an analysis of a sufficiently large number of chips and see if they are correlated. But you don't know if the RNG's NSA mode only turns on in those chips sold to China, or to the CIA, or on MacBooks or only when running specific encryption packages or versions of a specific OS.
And since these chips have downloadable microcode updates the feature could be enabled/disabled at any time.

Nicholas Weaver • September 16, 2013 3:34 PM

The chip wouldn't fail the NIST testing because things go through AES first, so it looks random until you collect greater than the # of bits of actual entropy.

gonzo • September 16, 2013 3:35 PM

I find this discussion fascinating in the context of hopes, expressed by some in earlier threads, of ditching 8086 legacy devices in favor of CPUs that operate on a much higher level of abstraction.

There seems to be an inherent tension there.

We can write a program that operates on "DOS" using 386 era hardware that can generate VERY GOOD random streams for CRYPTO purposes using Yarrow or Fortuna. We can add kludges of various kinds to sprinkle true "physical world" entropy into the mix, yes, even using that old hardware. (We did a project in college where we made one of those "drop the ball down through a series of pegs" gadgets to create entropic information -- it used a magnetic ball, plastic pegs and substrate, and a series of magnetic switches and logic gates, if memory serves).

We can alternatively rely on a hardware RNG built right into a modern era Intel processor. But it seems no one trusts the implementation, so in reality, best practices strongly militate toward avoiding reliance on the raw hardware RNG outputs, and washing the products somehow with additional software routines.

If you have to rely on a software routine to achieve confidence from the hardware RNG, you then have to ask what you REALLY gain from that implementation over, say, simply going back to 8 bit computer era liner congruential generators, or a counter-based block cipher implementation and putzing around with software to clean the result.

In my gut, I'd almost rather have a kludged up software solution based on a much older processor but with transparency of the implementation than to have to post-process a result from an untrusted implementation in hardware.

Its a fascinating discussion, and as someone mentioned, a measure of the true CORROSIVE effects of the policy implemented by the NSA and permitted by the political class.


gonzo • September 16, 2013 3:54 PM

@curious

I'm very much _not_ a techie, and make no bones about it. Over the years I've learned a lot about this stuff by trying to read and absorb things that those smarter than me can offer. If anything I post is foolish or simply wrong, I am not abashed -- the only dumb question is that not asked as they say. If I have misconceptions, they are probably common to those with my (in)experience and, so, having them out there, refuted, corrected, etc., cannot but help the overall level of understanding.

Stanislav Datskovskiy • September 16, 2013 4:03 PM

The ugly but inevitable solution: use TRNGs made of discrete components, which can be verified with an oscilloscope. And replaced, if need be, with vintage (perhaps Soviet, via eBay) versions.

Skeptical • September 16, 2013 4:08 PM

My real concern about the Project Bullrun disclosure is that the NSA may have weakened security features in programs and systems in a way that left them vulnerable to intrusion by other actors (criminals and other governments).

However, the NSA is of course also responsible for helping to safeguard such programs and systems. As far as I can tell, they take that responsibility seriously - on the same level with which they take their offensive mission.

It seems likely to me therefore that the NSA would be unlikely to introduce a vulnerability exploitable by others. Acquiring keys from a company is one thing - that doesn't necessarily render the lock more vulnerable to others. But weakening hardware features in the manner you described certainly would.

My question is:

Is there any evidence that the NSA has weakened protections in a way that would leave systems or programs vulnerable to intrusion by parties OTHER THAN the NSA or the US Government?

If not... this may all be much ado about nothing. The police can acquire keys to apartments from building supervisors and owners under certain circumstances (exigent circumstances or a warrant). That police ability does not mean the lock is more susceptible to being picked by criminals.

If I want to restrict police ability to search my residence, then I must rely on legal mechanisms, not perfect physical security features. And by and large, those legal mechanisms work. Nor have we seen evidence that those mechanisms have failed in the case of the NSA - instead we've seen examples where the NSA has made mistakes, then voluntarily disclosed them to the supervising FISC, and then complied with procedures and redesign to prevent such mistakes from occurring again.

Curious • September 16, 2013 4:10 PM

@NobodySpecial

Except that is not how the trojan actually works. It works by reducing the overall entropy in the system, not by allowing the attacker to predict what the next in a series of "random" data would be. The type of hack you describe is quite limited because it requires the attacker to actually be doing a side-channel in real time.

Nicolas Weaver. GIGO. If the entropy of the data is reduced before AES is implemented AES can't magically increase the entropy again. So a post-hoc analysis of the entropy after AES would reveal the hack.

Muddy Road • September 16, 2013 4:25 PM

Re: "....leery of Intel strongly pushing for applications to use the output of its hardware RNG directly and not putting it through some strong software PRNG like Fortuna."

I think you may have answered your own question.

However, certainly INTEL should like to respond and emphatically deny as well as show proof the NSA or other entity has not corrupted their chip architecture.

Frankly, my position would be guilty until proven innocent beyond all doubt at this point.

A sad thing if you think about it too long.

Greg • September 16, 2013 4:27 PM

Off topic...

Curious: I disable RC4 ciphers for SSL in Firefox. No ill-effects at all. Except for my ISP's website: VirginMedia...
Fishy!

Bauke Jan Douma • September 16, 2013 4:27 PM

Let's face it -- we'll always run behind on the tech.

What's needed is a mentality shift. There's apparently no operational concept
these days in the US of 'public morale', the ethics and loyalties of a public servant,
within a so called democratic soceity, the responsibility towards joe and jane citizen.

Here's an interesting short talk by Chomsky, on "Legal Vs Moral":
http://www.youtube.com/watch?v=lcJLsompHJU&feature=c4-overview-vl&list=PLUPB_KWeZWccRU-kZNddE73srvUGCbvTN

bjd

ac • September 16, 2013 4:27 PM

@Skeptical

Is there any evidence that the NSA has weakened protections in a way that would leave systems or programs vulnerable to intrusion by parties OTHER THAN the NSA or the US Government?

Yes. Weakening protections necessarily implies the latter.

The police can acquire keys to apartments from building supervisors and owners under certain circumstances (exigent circumstances or a warrant). That police ability does not mean the lock is more susceptible to being picked by criminals.

Is that because building supervisors never have their apartments robbed, because building supervisors are never criminals, or because the police are never criminals? Having extra keys out there does in fact reduce security.

papppfaffe • September 16, 2013 4:33 PM

There is another subtlety specifically about the Linux /dev/random implementation, which also borders on conspiracy theory: According to the audit on http://pastebin.com/A07q3nL3, the output of the hardware random generator, if one is present, is added *as an afterthought*, after all other sources of randomness have been mixed and hashed.

In other words, the function get_random_bytes returns the value hash(some_other_random_stuff) XOR rdrand_output.

Now, still according to the link I gave above, if you assume a malicious CPU, it can most probably access the value v=hash(some_other_random_stuff) in a register, then set its rdrand_output=v XOR tampered_value, et voilĂ , the last XOR before the function returning will result in setting the return value to tampered_value, effectively eliminating all other sources of randomness and giving a perfectly predictable tampered "random number".

Scary, that.

Steve • September 16, 2013 5:05 PM

@gonzo: it's not truly an alternative, you can do both. Have a good-quality entropy collector, feed it entropy from device drivers *and* entropy from your on-chip TRNG. Then by the definition of "good-quality entropy collector", if either of those sources of entropy is good then the output is good. The TRNG protects you against side-channel attacks on your devices, and the devices protect you against Intel-sabotaged reduced entropy in the TRNG. Only if the attacker can do both at once do they win.

A key feature of any entropy collector is that when you put data in you give it a (lower-bound) estimate of the entropy contained in that data. As long as the actual total entropy exceeds the total of your estimate, your output is solid. Furthermore, part of the definition of "good quality" is that you can feed in completely untrustworthy data with an estimate of 0, and it still won't make your output any more predictable than it would be without that input. So a kernel entropy collector can accept untrusted "randomness" from user-land without any risk that one process subverts another process's use of random data. Even if something goes wrong and you are over-estimating the entropy, your output might not be critically weakened. Fortuna is *designed* to mitigate against attackers having partial knowledge of its internal state and its inputs.

The temptation offered by a TRNG is that because it's fast and inexhaustible, you might choose to rely on it when other sources of entropy are (for the time being) used up. Intel engineers unaware of any NSA exploit might in good faith (albeit perhaps too naively impressed with their own creations) recommend that people do this when implementing /dev/random or CryptGenRandom().

But if it's your only source of entropy, and it's compromised, that's when you could be in trouble. So implementers of /dev/random shouldn't give in to temptation (and by the sounds of it Ts'o didn't) -- they can for example block until multiple sources of entropy are available so as never to have to rely on just one. And crucially, as long as they're able to pick a number smaller than the true entropy of the device, it is still a perfectly useful source of randomness.

All this is of course assuming that the chip your code is running on isn't also grossly compromised in other ways. At the absurd (technically infeasible) extreme, if Intel somehow managed to sneak a radio transmitter into a chip that reports every value it handles straight to the NSA, then your output will never be solid no matter what code you run.

Clive Robinson • September 16, 2013 5:08 PM

@ Curious,

    GIGO. If the entropy of the data is reduced before AES is implemented AES can't magically increase the entropy again. So a post-hoc analysis of the entropy after AES would reveal the hack

Would you care to explain how you do this "post-hoc analysis of the entropy after AES"?

Please remember how CS-PRNGs work like AES-CTR...

I think you are having the problem many people have with the notion of entropy with respect to testing for non-determanistic behaviour when you only have the output to measure. There are very many algorithms that whilst fully determanistic can not be shown to be such from just observing their output even when the algorithm is well known to those carrying out the tests. These algorithms include but are not limited to crypto-hash, block ciphers, stream ciphers, one way hash functions and key expansion functions.

@ gonzo,

    I find this discussion fascinating in the context of hopes, expressed by some in earlier threads, of ditching 8086 legacy devices in favor of CPUs that operate on a much higher level of abstraction.

Actually I'm the possible exception to that. I would like the hardware to be as simple as possible, but the programing interface for jobbing code cutters to be as high as possible.

As I explained the design proceadur is generaly get a core that meets minimal specifications (in terms of complexity etc) and then put a wrapper around it to give the required level of abstraction. So a striped down RISC core gets a microcode wrapper, or some form of byte code or executable code and shell scripts etc. In all cases the wrapper is an interrpreta thus in most cases it realy does not matter at what level of abstraction the wrapper is provided it's BELOW the standard programing layer.

I could give the full reasoning behind it but it would chew up a large amount of thread space, and be a bit pointless as I've given the reasoning before.

MarkH • September 16, 2013 5:33 PM

@Brian M.

This reflects a very common misunderstanding. Tests like Diehard can only reveal statistical properties, but in general can never demonstrate unpredictability.

An absolutely insecure generator (from which billions or trillions of past and future output bits can be readily computed from a small sample of consecutive output bits collected at any point in the sequence) can have perfect statistical properties, up to its period.

And the period can be made so long that no feasible amount of sampling is likely to detect it.

A crypto PRBG must have good statistical properties -- those properties are a necessary condition for security, but not a sufficient condition.

If a clever agent who wants to violate your confidentiality fiddles your PRBG, you can bet that he will make sure that its output is statistically perfect. And in fact, the Intel design, by using its AES post-processing, does exactly that: no matter how predictable the internal source bits may be, the output will look perfect under statistical analysis.

Clive Robinson • September 16, 2013 5:35 PM

@ Bruce,

    That's is the worst thing about the NSA's actions. We have no idea whom we can trust.

You forgot to add,

    including ourselves.

No I'm not talking about mental illness just the age old failings of "over confidence", "lack of knowledge" and plain old "errors and ommissions". As has frequently been observed "To err is human".

P.S. Speaking of "errors" you've obviously typed this quickly and commited one of the grevious sins I frequently commit ;-) In "That's is" the "is" should not be there.

Clive Robinson • September 16, 2013 5:48 PM

@ Stanislav Datskovskiy,

    The ugly but inevitable solution: use TRNGs made of discrete components which can be verified with an oscilloscope.

Actually it's the prefered way to do it to be quite honest, but these days the test gear is a bit more complex than an oscilloscope.

@ All,

If you are thinking of getting a TRNG from some place, it's very important to have direct access to the output of the buffer immediatly after the "physical source" of randomness prior to any debiasing or hashing, and you should monitor it continuosly.

If you don't then how do you tell if the "physical source" has gone wrong or is suffering from external influance?

gonzo • September 16, 2013 5:55 PM

@Brian M

I agree with Mark.

You can generate a 20 megabyte file of binary data using the old DOS DELPHI's "random" command and have it appear to perform well in the DIEHARD battery. The stream will have distribution and other characteristics that look fairly random on almost all of the tests.

But its an illusion.

"Random" under that particular version of Delphi is a LCG that generates the same series of 2^32 numbers every time its run. When you seed it with the randomize command, it simply drops you into that formulaic sequence at a point determined by the system clock. So while the data looks random in its outward characteristics, its trivial to exploit the stream if used directly for functions where true random numbers would be crucial.

I believe some "online Texas Holdem poker" companies found this out to their great dismay some time ago. They used the 2^32 limited PRNG I mentioned to shuffle the deck of cards. Hackers had developed a tool where by a player knowing his own two cards and the three in the "flop" (visible after no more than 2 rounds of betting) would be able to determine every single other players' hand and the final two cards that would fall -- thereby knowing "when to hold em and when to fold em" as the saying goes.

It was an object lesson about deterministic RNGs and their risks.

Dave Walker • September 16, 2013 5:56 PM

Having misspent my youth doing more solid state Physics than was strictly good for me, I did kinda wonder whether something like this would be feasible.

I'm also reminded of the old LANCE Ethernet controller, which had a design flaw the result of which was the early demise of the vast majority of these units with a stuck transistor. Apparently, the problem was down to proximity between a group of transistors, and an inadequate electron sink between some of them. Over time, electrons would bleed into one of this group of transistors, and this would eventually wedge it.

So, not only is it possible - if you know what you're doing - to under- or over-dope a gate to make it stick, but other conditions (involving electron sinks) could be set such that transistors operate as normal at time of shipping, but wedge some short-ish (a year, maybe 18 months) time later.

Robert Thau • September 16, 2013 7:12 PM

There's another way for NSA to arrange to selectively hack RDRAND behavior --- distribute a "microcode update" to selected targets which cuts bits off the hardware random source, or cuts it out entirely, and gives the victim, say, an AES-whitened version of the real-time clock. (Or something a little less crude.) This would require separate access to the entropy source and whitener at the "microcode" level, but that may exist. It would also require NSA to have the Intel-internal documentation and signing keys required to produce a microcode update, but they most likely have those, one way or another.

This has the advantage that the processors Intel ships, including anything likely to wind up in a test lab, really do behave exactly as advertised; the NSA can confine the weakness to selected targets in the field. The flip side is that they have to be able to execute privileged code on selected targets in the field, but they seem to be good at that.

Stanislav Datskovskiy • September 16, 2013 7:33 PM

At the risk of repeating myself: at this point, anyone who relies on a TRNG made of anything other than discrete components - for anything more important than playing games - is a fool.

If your application is actually important (Bad Things will happen to you or your loved ones in the event of compromise) - these discrete components should be ones which you purchased and soldered personally.

And I dare say: the junkyard (or eBay) is a more trustworthy source of such components than a Western electronics vendor. Expect to see a climb in the prices of well-preserved Soviet, East German, Czech, etc. clones of 1980s and early 1990s-era CPUs.

Of course, a perfectly-honest TRNG does you little good if the whole rest of the system is thoroughly pwned. RNGs remain interesting, however, because a diddled unit can result in weak keys, leading to the compromise of countless physically-distant systems which would otherwise function perfectly.

Vilmos • September 16, 2013 7:49 PM

Heh, the US successfully "infected" the Soviet technological leviathan to a level that the Soviets had no idea what was safe (hint: they stole everything). Now it looks like the US successfully infected its own computer industry. I am not sure the people who came up with these things and approved them really thought it through. They accomplished two things:

1. short term, they will get access to a lot of data.
2. long term, they killed their computer (and all hight tech) industry competitiveness (and 1. too).

An article about how the US screwed the Soviets.

http://fcw.com/articles/2004/04/26/tech-sabotage-during-the-cold-war.aspx

Vilmos

Dirk Praet • September 16, 2013 7:57 PM

Since this is not entirely my area of expertise, my simple question is: if there is any doubt about Intel's hardware random number generator, why then not throw it out completely and replace it by, say, Fortuna ? Performance reasons ?

Berecz Ferko • September 16, 2013 8:09 PM

@Clive:

Have you used C64 or equivalent hardware for Internet usage? I don't recall hearing about modern firmware and other modern exploit vectors for these older systems.

Another Kevin • September 16, 2013 8:30 PM

I'm also more than a bit concerned that the NSA has influenced outfits like Intel, Phoenix, American Megatrends, and Insyde to place spyware in the firmware level. I strongly suspect that every computer manufactured in the last few years can be commanded by the NSA to disgorge at least a key log. Which means that passwords are secure only if they have never been typed on the keyboard. We have no idea how deep this particular rabbit hole goes.

Stanislav Datskovskiy • September 16, 2013 8:52 PM

Vilmos, the pipeline sabotage incident is well-known.

However, vintage Soviet CPUs are probably safe. Simply because the logic density of that time left very little room to hide hardware-level nasties. I would even venture to guess that all silicon created before the era of ubiquitous networking is probably "clean."

Curious • September 16, 2013 8:54 PM

@Gonzo

I think you misunderstand me. There are two different people calling themselves 'Curious' here. I was simply referring to that other guy to sort of point that out. :) Wish he would write with some other handle to be honest.

Entropy- Bad Religion • September 16, 2013 9:11 PM

RdRand was implemented mainly because plenty of VPS servers have no human operator providing entropy and /dev/[u]random has no idea there isn't sufficient entropy and provides PRNG anyways even if it's completely feeble.

RHEL is apparently exclusively using RdRand for all their PRNG so beware. RHEL is definitely an O/S the NSA would love to backdoor, it's running banks, stock exchanges, air traffic control in some countries...

Most devs are using /dev/urandom on Linux nowadays, so that's what is mostly maintained. Apparently they don't have time to maintain /dev/random which is for legacy systems.

OpenBSD PRNG now has only one random device, /dev/random and it's safe to use on an embedded device with barely any interactive entropy since it's completely different from linux /dev/random and doesn't blindly trust itself to always have sufficient entropy for PRNG

What total clownshoes the global security industry has become. Between exponential complexity, sloppy code, hardware backdoors, toolchain/compiler backdoors, broken crypto like RC4/TLS 1.0/1.1, and rogue spy agencies ballooning into totalitarianism this has all effectively gone to hell.

I used to be critical of Stallman but now appears he was right all along. A machine that interprets the code instead of having to compiling it with backdoors, where you can press halt and find out exactly what is going on that is built on trusted open hardware is probably our only hope of maintaining security because this NSA/CSIS/GCHQ/MSS/FSS/MI6/NZSIS/ASIO/DGSE rogue agency nightmare isn't going away anytime soon. Time to dust off my SICP book and order up some FPGAs for the sole purpose of messaging and encrypting files.

Nick P • September 16, 2013 9:13 PM

@ Dirk Praet

Question is "did they subvert the RNG and *only* the RNG?" Or did they embed an "errata" that gives them total access?

If it's just RNG, using a different source would be good enough. Using Fortuna would also be good and their bad TRNG could even be used in it b/c the enemy would need the other seed material. If subverted thoroughly, then we have bigger problems that basically come down to trusted features can't be on an Intel chip. And maybe not an American one. And that means no x86 unless you're cloning or emulating it, far as I know.

(VIA is another alternative to Intel for x86 that also has crypto acceleration, however they also have strong US ties. So who knows...)

Larry • September 16, 2013 9:32 PM

OK so there is a new attack on PRNGs. Sounds like opportunity. There has to be a way to create a verifiable RNG hardware source. Doesn't have to be on a chip. Time something radioactive. Look at the timing of photons in a photomultiplier. I never liked the psudo part of random number generators anyway. Random random numbers, and don't be greedy about the number of bits at a time so that it stays testable. Deal with the whiteness issues some other way.

Joe in Australia • September 16, 2013 9:55 PM

This Forbes story gives a conservative data storage estimate of 3 exabytes (2^60 bytes) for the NSA's Utah facility. If you stored 1024-bit keys plus their factors in a totally naive way you could fit about 2^53 keys-plus-factors in that amount of storage. Realistically you wouldn't do that: you wouldn't need to store both factors; you wouldn't need to have the keys always online; and you could afford to use a lengthy search to find the right one. Anyway.

Suppose the NSA have subverted popular RNGs so that they actually only produce a small subset of possible number sequences. The number of possible keys you could generate would be large enough that there would be no tell-tale collisions, but small enough for the NSA to store all the possible keys. In other words, suppose that the number of possible sequences is merely 2^53. Nobody without a data facility comparable in size to the NSA would be able to exploit this, but as far as the NSA is concerned, every key produced would already have been broken.

Dan • September 16, 2013 10:03 PM

You know, Bruce, with your renowned presence in the media, you could actually ask Intel for a formal comment on this blog post and they would probably give one.

Figureitout • September 16, 2013 10:06 PM

Steve
At the absurd (technically infeasible) extreme, if Intel somehow managed to sneak a radio transmitter into a chip that reports every value it handles straight to the NSA, then your output will never be solid no matter what code you run.
--Well, there is a peripheral...and I generally don't see a lot of cables besides power transformers coming off most laptops.

Larry • September 16, 2013 10:09 PM

We have single point of failure systems now. How do we make it so that this isn't the case? What if we trade cheap for secure and multiply source the hardware? Make it run with some kind of voting protocol, and multiply source the hardware running that.

Gweihir • September 16, 2013 10:41 PM

@Entropy- Bad Religion: The first design is on your reference is actually badly broken: I tried it and it failed. My guess is that 74ALS is implemented quite differently these days (e.g. extra stages) and not anymore usable as analog amplifier.

The second design using two transistors works well and is quite tolerant to voltage and resistor variations. Use any standard small-signal NPN transistors, but avoid extra slow ones. Normal ones have something like 0.2W maximum load and >= 100MHz F_t. 12V is quite enough, BTW, E-B reverse breakdown comes out to something in the 5...6V range. And use a coupling capacitor!

What you get is a mixture of about half thermal noise (not strictly random) and half quantum-tunneling (physics thinks this is the only real random thing in the world), which is pretty good. One problem is that amplifying the signal dramatically reduces noise bandwidth, unless you are careful. The original signal has > 10M zero-crossings/second (best my equipment can do), after just one transistor amplification stage, that is down to about 1M zero-crossings/second in my experiments. (That was the original motivation for the ALS gates, I think, as they are really fast.) Still, if you sample conservatively, or with something slow like a sound-card or standard A/D converter on a microcontroller, you should get something like 1bit/sample. Be careful, assume something like 0.1bit/sample, hash together, whiten and you get pretty solid randomness for a few bucks (assuming that sound-card is present).

Gweihir • September 16, 2013 10:50 PM

@oops: That design is highly problematic. I tried it and you get less than 1mV usable signal. This needs very careful shielding, filtering of power, amplification, etc. to be useful at all. To make matters worse, the original signal is small enough that you cannot really measure it with amateur-level equipment. Most people will just end up sampling the mains signal and/or its harmonics coupled in somewhere.

A 2-transistor avalanche source is much more tolerant to environmental influences, a lot easier to use and the original signal is already strong enough that a cheap digital oscilloscope can give you reasonable measurements and FFT, so you can verify that it actually works.

Gweihir • September 16, 2013 10:54 PM

@Nick Weaver: Indeed. Not having the outputs in JTAG is either very sloppy design from a security POV, or intentional to prevent detection of a compromised CPRNG. In any case it is a strong reason all by itself to not trust the generator exclusively.

Nick P • September 16, 2013 10:56 PM

@ Entropy Bad Religion

I'd prefer a design along those lines. Reason is it can be simple, can use components that aren't say microscopic, and whose parts can be foreign sources. Favorite quote in the article, though:

"Looking at the latest Linux sources is generally the best way of getting the very latest random code."

Lol. Of course, I designed a way to use shuffled decks of cards or 8-sided die to get bias free data. I just type the numbers into a program till it reaches entropy point, then it whitens it. The cards give 5-bits each and die 3-bits each. Hadn't had to use it.

I like the LavaRnd concept. A days meteor burst data might be nice too. Or just intercepting background cell phone activity to feed into a Fortuna style generator using other private inputs too.

So many ways. Random numbers is a truly easy problem compared to the endpoint security that matters most.

RC • September 16, 2013 11:37 PM

@Vilmos
Heh, the US successfully "infected" the Soviet technological leviathan to a level that the Soviets had no idea what was safe

yup and heh, now NSA is likely allied with most western countries (and who knows, maybe even Russia) and "the regular people" has become their enemy, their Soviet Union.

Mike the goat • September 17, 2013 12:07 AM

@stanislav - you preempted exactly what I was about to say. If the TRNG is not miniaturized then it can be verified with relative ease. The most logical choice is to use zener diodes as a noise source. I guess you could also easily embed a tiny radiation source (legislation already allows americum-241 in domestic ionization smoke detectors so given that I doubt there would be an issue re export and transport of completed PCs) and a cheap GM tube in a shielded enclosure. You could probably make it quite small too. The problem is - like everything else we have spoken of in the past few days - you have to trust the entire system as a collective. It doesn't matter if the TRNG module is feeding perfectly random data when, for example UART on the other end is covertly altering what's seen.

Mike the goat • September 17, 2013 12:42 AM

@Vilmas - I have heard Putin's office is so concerned about this that they have gone back to using a typewriter for sensitive documents (of course there are meatspace attacks against that too - ribbon reading, etc.)

@Joe - you know, I was considering something today. Given we know the approximate floor area of the facility we could probably make some assumptions about equipment density (e.g. space between rack units, etc) and use either budget or square footage of area to assume what brute force capability they have.

e.g. if we assume they are using COTS hardware (say x86 machines with, say 4 graphics cards each) and a standard rack will hold 42RU or 20 2U boxes (single RU boxes won't accommodate that many cards) plus 2U left over for their switching hardware, then we can get a rough idea based on floor area. If we assume an average rack occupies about 24x42" of floor space and a decent graphics card like a 5970 can do 1103658/sec brute forcing AES. So, assuming work can be divided evenly and it scales linearly (which it won't but this is just a rough estimate) we can assume 88292640/sec per equipment rack. When you think about the size of the facility then the idea that they can break certain web encryption standards certainly gains some credence.

Now, if they were using custom cracking hardware like ASICs then we start getting downright scary.

That said this would have to be carefully targeted and carte blanche surveillance would still not be feasible. Perhaps the most plausible idea is that they use their cracking cluster to obtain the private keys of SSLized sites that are of widespread use and import (and where merely asking for the key has failed)

Just thinking . . .

Just-a-lawyer • September 17, 2013 1:15 AM

@Bruce:

Someone told me - may be in August of 2011 - most CPUs (esp. those from Intel) do inherit stack-(or cache?)areas which can be accessed and loaded with code. Shall be some sneaky "only-for-us-developers" backdoor-like gadget.

Might that 1) be true and 2) a problem in this context?

Best regards from

a lawyer in Germany.

a lawyer in ToonTown • September 17, 2013 1:31 AM

Re: Microcode

TAILS Linux updates the Microcode with each boot.

For a privacy/security conscious distribution, I wonder what's really being updated and why?

RobertT • September 17, 2013 1:35 AM

The truth is imagination is the only limit to the ways that a modern chip could be Trojan'ed.

This referenced paper tries to use the implant masks so that the chip can pass even detailed optical inspection. Personally I think this is a waste of time for deep sub micron designs, what they are using (with implants levels) is a trick we used to use back in the old days of 1um structures (early 90's) to create logic gates that would be difficult to reverse engineering. Today there are much more interesting effects that can be generated by intentionally fiddling with the OPC algorithms.
Let me explain:
ANY chip made in a technology below 130nm (late 1990's technology) has used special fudge algorithms (called optical proximity correction), modern chips at being made at 20nm gate lengths so the OPC is VERY advanced.
http://en.wikipedia.org/wiki/Optical_proximity_correction
OPC is intended to correct for process abnormalities so that your layout design database contains what you actually want, rather than what is necessary for this to print properly, you see adjacent cells that are completely unrelated in the design database effect the chip processing due to etch rates and sub-wavelength lithography effects. These "errors" need to be fixed before the masks are made so the "layout" database gets lots of correction information added JUST before the masks are made. The whole field of OPC algorithms is a kept VERY secret and the exact structures vary form one manufacturer to the next so nobody (on the design team) really knows what to expect (and would probably never understand the exact purpose of the added structures even if they looked at the post OPC database). Now IF you appropriately fiddled with the "fill and OPC correction polygons" you could easily build or alter gates, if your introduced "error" was ever discovered everyone would assume it was "just another OPC F-up"

BTW: There are other Masking stage added structures called "Fill" and Phase Shift masks that could also be used to hide information.


Ben • September 17, 2013 2:03 AM

If not... this may all be much ado about nothing. The police can acquire keys to apartments from building supervisors and owners under certain circumstances (exigent circumstances or a warrant). That police ability does not mean the lock is more susceptible to being picked by criminals.

This wins "worst analogy in the thread", as having locks with master keys (as is common in big buildings) does make them more susceptible to picking.

RobertT • September 17, 2013 2:35 AM

Another issue to consider is "Fake chips"
You would be surprised at the range of fake chips I've seen, they range from simple amplifiers where a cheap, usually Asian "compatible" part, gets re-stamped with some high dollar logo like Maxim or LinearTech. But this is also happening for digital and mixed signal VLSI parts making something like a discrete TRNG an obvious target for faking.

Since almost all PCB's are assembled in Asia it is fairly easy to substitute these fake chips into the production line especially if they are cheaper. A discrete TRNG might only cost $1 but I guarantee you I can build a functional equivalent (especially if I make it a PRNG) for say $0.25 so the PCB (stuffers) can make an extra $0.75 per PCB. The whole electronics assembly process is VERY competitive so their total profit for a laptop PCB might be less than $1 however if they use a fake TRNG chip they make $1.75, this is why its so difficult to keep fakes out of the supply chain.

Of course if say the Russians (or the NSA) wanted to seed the supply chain with fake Trojaned TRNG chips than they might even pay the PBC assemblers $1 to use their chip.

Once the whole system is assembled it is almost impossible to tell if its a fake or not. I've seen cases where everything was a perfect copy, right down to the chip layout itself.....but it just wasn't one of our chips, it was a fake and had some subtle flaws.

Boško Brajković • September 17, 2013 2:58 AM

yeah man and what of firmware downloads for a bunch of the hardware like bios, game cards, cdrom drives and stuff how many times man have you seen a gpg signature how many times man have you seen checksums to go along with it tell me man how we arent fucked on a daily basis by all of this proprietary hardware and software?

the bullshit on windows systems never ceases to fascinate me:

INSTALL this bullshit program with no available source code and we promise it will work as advertised.

(goodfellas voice over) you want more options? fuck you - pay me. you want faster updates? fuck you - pay me.

Peter • September 17, 2013 3:31 AM

@Mike the goat, the thing about typewriters was misreporting. They never stopped using typewriters; an order of ribbons got blown up into a "story" because of the silly season.

unimportant • September 17, 2013 4:18 AM

@Boško Brajković: "how many times man have you seen a gpg signature"

Some manufacturers embed the uploadable authenticated and encrypted firmware code within an authenticated application (e.g. by using Authenticode). A separate PGP signature would be better for the educated consumer, but it also only confuses normal users.

Clive Robinson • September 17, 2013 5:02 AM

@ Gweihir,

    This needs very careful shielding, filtering of power, amplification, etc to be useful at all. To make matters worse, the original signal is small enough that you cannot really measure it with amateur-level equipment. Most people will just end up sampling the mains signal and/or its harmonics coupled in somewhere.

This is true of all random sources...

For home constructors of TRNGs you are going to have to make your own PCBs --they don't need to be through hole plated though-- using good RF and analog design rules (see an Amature Radio guide from the likes of the ARRL).

One big thing to note is that you need to take the signal from both sides of the noise source with suitable ac coupling. That is as follows,

(+V)--[RES]--(A)--[Noise Diode]--(B)--[RES]--(-V)

And you suitibly small values of capacitor from points A and B into the following circuit.

In practice you would make the footprint of the noise source on the PCB as small as possible and put an AC-Ground gaurd ring around it on both sides of the PCB. You would also not use just single resisters from either DC power supply, as a minimum you would use a Tee Filter. That is use two resistors in series with capacitors from the junction between them to the AC-Ground guard rings. You would also use power supply line filtering across the whole circuit but grounded to DC-ground. The cutoff frequency of the low pass power supply filtering should be as low as is reasonably possible. Likewise that of the tee filters which must be atleast a decade below the cut off frequency of the effective high pass fillter of the ac coupling going to the following amplifier stage which must be biased for minimum noise not maximum gain and very wide bandwidth. One type of amplifier suited to this is grounded base or grounded gate.

As for sheilding you need to issolate the noise source from the amplifier and dc filtering and in turn shield all three from other parts of the circuit. There are shielding materials and shielding materials silver plated mu-metal has been used in the past but is impractical for most home constructors. One trick you can use is strips of double sided PCB, however it generates a lot of heat so it needs to be done before you fit components. You design your layout PCB with ground planes on the top and bottom layers. You then cut strips of unetched PCB material to form the side walls, these strips are about 1cm wide and file the edges carfully so the copper comes right down to the edge. You solder in place support wires on the layout PCB at the corners of where the shield box is to go. Using these "tack solder" the strips of PCB at right angles to the layout PCB, then "seam solder" the PCB strips all along the bottom edge to the layout PCB do this on both sides of the PCB strips. However... how do you get signals etc in and out :-) there are two basic ways use PCB tracks and remember to file a notch in the edge of the side wall PCB strip so it does not short. Alternativly before soldering the side walls on drill holes through sufficient to take the component legs remembering to use a larger drill to clear back the copper from the hole on both sides. Better if you have them are small "feed-through capacitor" filter components which you solder in place, however they are not likely to be at your local Radio Shack (but the likes of Digi-Key sell them "mail order "http://www.digikey.co.uk/product-search/en/filters/feed-through-capacitors ).

Berecz Ferko • September 17, 2013 5:40 AM

@Clive (I feel you missed this above):

Have you used C64 or equivalent hardware for Internet usage? I don't recall hearing about modern firmware and other modern exploit vectors for these older systems.

Mike the goat • September 17, 2013 6:20 AM

@berecz - A device like the C64 would likely be able to support a very basic TCP/IP stack but you would be limited to text only web and even then only small pages would render. Actually the only use I could think of would be as a dumb terminal, in which case it solves nothing as you are just shifting trust to another machine. modern crypto would be unusable. 64k of RAM is not enough.

An Amiga or an 80386 would be a much more suitable machine. There are TCP stacks for DOS and even a basic browser (google arachne). An early Motorola based Mac would also be another option.

Personally I would go for a pre UEFI era Pentium 4. When things started to get "dirty" is anyone's guess though. Stanislav's suggestion of a soviet PC clone is a good one.

But we are all just guessing.

Dirk Praet • September 17, 2013 6:31 AM

@ a lawyer in ToonTown

TAILS Linux updates the Microcode with each boot.

Could you elaborate on that and tell us where you got that from ?

out of memory • September 17, 2013 7:00 AM

If the RNG is compromised I don't think they implemented it in a way to detect it by measuring entropy. I think they would use a kind of strong pattern within the generated numbers generated.

Thinking in solutions we could use RNG to get the numbers very quick and disorder them by using some local based informations (think of generating a unique key out of hardware serial numbers, time, fan rpm, ..., maybe informations of browser cache, too or the last few mails received and sent).

I was just thinking loud so feel free to put fingers in your ears, if that were stupid thoughts.

Gweihir • September 17, 2013 7:08 AM

@Clive Robinson: Actually, no. For example, the two-transistor avalanche generator works quite well with 330R pull-up resistor which leads to a low-impedance output signal with enough amplitude that you can just amplify without any additional shielding or special filtering.

Taking a differential signal form a noise diode does not help. In fact, it is a pretty stupid approach, as it limits you to use a differential amplifier in the next stage, with corresponding worse bandwidth. From you other "tips", I have to deduce that you actually have no clue what you are talking about for this application and have not done any of this yourself in an experimental fashion as what you say is mostly complete nonsense. Sorry, but this is not RF design or high-quality audio. As long as the signal that you get is mostly noise, you are fine. No need for custom PCBs or bizarre shielding arrangements at all.

Clive Robinson • September 17, 2013 8:20 AM

@ Berecz Ferko,

    Have you used C64 or equivalent hardware for Internet usage?

No.

Though I have used other 8bit micros for SLIP connections they were a lot faster.

unimportant • September 17, 2013 8:30 AM

A quick-n-dirty approach is to sample otherwise unused floating A/D channels of a micro-controller. This kind of an entropy source must then be fed combined with other entropy sources into a PRNG.

microcode • September 17, 2013 8:31 AM

Tails is based off Debian and if you look at dmesg you will sometimes see "failed to update microcode" which could just be a regular kernel function. I have no idea but wondered myself what that is doing. I'm sure its in their design document though or we could ask them

Personally I don't use it because its full of junk/bloatware. I use a base openbsd install with softraid crypto as since 5.3 openbsd can boot cryptodisks eliminating an unencrypted boot loader that you have to carry around on USB or hide.

Clive Robinson • September 17, 2013 8:50 AM

@ Gweihir,

    Taking a differential signal form a noise diode does not help. In fact, it is a pretty stupid approach, as it limits you to use a differential amplifier in the next stage, with corresponding worse bandwidth.

I did not say "take a differential signal" but "take the signal from both sides" ie two signals. Nor did I say "use a differenntial amplifier in the next stage" I actualy sugested using a ground base or grounded gate amplifier which is not a differential amplifier is it?

Also do you know what the input impedence for a grounded base or grounded gate stage is and it's coresponding bandwidth even when biased for minimum noise?

Oh and why all the sheilding and filtering... have you put a mobile phone or WiFi card near your "prototype" I suspect not. GSM mobile phones and un sheilded amplifiers be the audio or RF don't play nicely. The GSM phone produces a pulsed output that gets picked up on most conductors including cheap design PCBs and the first diode junction they hit generaly acts as a diode detector and demodulates what is in effect an AM signal. Thus the amplifier output has a nice pulse train sitting on it as you would see on you oscilloscope screen if you turned the time base down to an appropriate rate or if you want a simple demonstration involving no tools or test equipment tune a radio to a radio station call somebody on A GSM phone and just bring it within about a foot or so of the radio.

Oh and the reason for a signal from either side of the noise diode I'll let you think about for a while.

Nick P • September 17, 2013 9:41 AM

@ Mike the Goat

"Personally I would go for a pre UEFI era Pentium 4. "

That's my preference too. Remember, too, that there's plenty of UNIX RISC workstations with varying processors/hardware: Compaq Alphas, HP PA-RISC, Sun SPARC's, SGI MIPS and so on. Back when they were high end, the majority of my power user activities were done on a Pentium 2 (233MHz) PC w/ 64MB of RAM and 28K dialup. Seeing how much I got done, I'm pretty sure modern revolutionaries could turn one of the other machines into something useful. ;)

Btw, one must worry about one other thing: processor errata can lead to subversion. The errata are basically hardware bugs whereby the processor doesn't act in accordance with its specification. Vendors of processors often produce errata lists with their processors. They can make for interesting reading, esp. when the error is in security-enforcing functionality like MMU or control flow. Kris Kaspersky has a great presentation on it.

Don't forget the Chinese processor and OS

The Chinese have been making their own processors based on MIPS (Loongson) b/c they're worried about subversion. One machine is open down to the firmware I think, which is why Stallman uses it. They also have an OS, Kylin?, that's a modified FreeBSD. They might have subverted these things for their benefit but I doubt NSA has.

So, if you have something you must keep from NSA, but China is no worry, then maybe use Chinese gear. It's really just remix of my old maxim of "use the other side's equipment if you don't trust your side."

loongson • September 17, 2013 11:00 AM

Problem with using Chinese hardware like Lenovo is they are still backdoored, and every other country knows this and has probably figured them out. We need hw with no backdoors or RNG tampering so looks like only solution is a FPGA though Lemote/loongson laptops running BSD look pretty enticing, and BSD doesn't rely on hw crypto for random memory address at boot, or for RNG.

There's always a beagle board too and wishful thinking that ARM hasn't been tampered with yet.

WD • September 17, 2013 11:12 AM

Is it out of the question for industry to come up with analog discrete random number generator devices which *can* be audited? Aren't we tired of everyone's BS?

Tony • September 17, 2013 12:07 PM

Ted did write "I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction." ... but he later admitted that it was misleading. Nobody from Intel ever tried to have /dev/random depend solely on the RDRAND instruction. The Intel engineer contributing the patches to the Linux kernel stated that RDRAND is not suitable for that given the ways that exisitng applications and libraries use /dev/random.

Dig through the Linux kernel mailing list archives to see the discussions and proposed patches - it is all public.

Anyone what to build some chips? • September 17, 2013 12:29 PM

I think it is about time we do to hardware what the GPL did to software, open it up. You can't trust what you can't verify.

Also, there is enough entropy in the universe. All that is required is mechanism to collect it, encode it, and use it.

That being said, the average user will continued to get screwed while we put trust in companies and governments to get it right. Even in the best of situations they often get it wrong. Chalk it up to indifference or malice.

paul • September 17, 2013 12:41 PM

I think RobertT's argument about OPC needs to be made slightly more complicated. If you have visual access to the chips, you can still check whether the visible structures make the things you called for in your layout -- the OPC just changes the masking to get the structures you want out of light whose wavelength isn't short enough to do th job simply. You would have to use an OPC trojan to affect a non-visible layer.

There are, however, more invasive and expensive methods, e.g. focused ion beams, that could verify that the gates were actually what you wanted, but it's not clear you'd have a working chip afterward. So you'd have to rely on statistical methods and manufacturing surveillance.

gonzo • September 17, 2013 12:44 PM

Hey guys....

I was discussing this with my dear other last night and she had an interesting perspective from her position in the medical field: "If you can't fix it, embrace it, once you embrace it, you can deal with it using the tools you have. Use ALL the tools you have."

This got me thinking about the fact that the NSA and other "adversaries" (including hackers with their Playstation 3 devices and video card brute force farms) have leveraged the exponential increase in computing power, memory, and storage FAR FAR beyond what folks in the user space have done in terms of their work protecting secrets.

What fallows is partially comedic absurdity (call it my quest for levity), and I got a chuckle writing it.

But burried somewhere in here is also a thought on overall technological arms race. The NSA has huge, but not unlimited, resources for processing and memory. How about we take that disparity out of the equation or at least reduce its impact.

Here is where the tongue gets planted in cheek... ahem:

As far as random numbers go, why not "embrace" determinism, but make the haystack so big and the process so convoluted (exponential branching with cascading points of divergence for the stream) that the cryptographic goal is accomplished. Stop calling (or EXPECTING) it to be a random number generator. What you really need for cryptographic purposes is a "totally unpredictable nonce engine"

Example: Fill a directory on a 2 gigabyte ram drive with 500 t0 700 megabytes of junk: MP3s, video files, 100 days of the Huffington Post Comments section, weeks and weeks of Slashdot.com articles and comments, the previous hour's twitter feeds for 3000 or so super active + moderately active users, blocks of data from stock tickers and investing "wire" reports, the AP photo feed, a bunch of arbitrarily selected LINUX repository files, whatever. Add another 500 to 700 megabytes of PRNG gunk. I don't care what from, linear congruential, XOR shift, Intel's processor instruction, an ARC4 stream, or a little of everything.

Set up a process to "stir" this pot. That means arbitrarily discarding items in the pot, replacing items, XOR scrambling of parts of the pot, whatever. Really use the system processing power and memory so that every 30 seconds a large percentage of the pot will have changed.

Separately, set up a process that then traces an outrageously convoluted path through the muck. Maybe while you have the stirring process working at a file level, the convoluted path through the entire mess operates at the sector level? It will be completely deterministic, of course, but set it up so that every byte of "output" at least 33% of the pool of muck will have affected it. The path through the pool should be different for, for example, for every possibility that could come up as the next number in a PRNG with 2^32 possibilities. But not only that, the pool should be changing so fast that even two identical paths starting through the muck will land in hugely different places. A simple, flawed, whatever PRNG can pick which files (or sectors) in the muck to dip into, it can determine which bytes to start with, it will determine how much of each file/sector to grab, it will determine what order to combine these samples, it will determine which out of several thousand operations will be performed on these samples (XOR with each other, encode with various ciphers using either other samples or counter based keys, flipping various bits, application of compression, processing through a stream cipher, arithmetic operations, truncation, XOR against frame grabs from a VM running a texture intensive video game in demo mode, whatever). Keep adding possibilities, keep adding branches, and dump some of the output of this step back into the original constantly evolving pool... and at the tail end add whatever whitening process may be desired.... if it is even necessary

Do all this ... such that every X time slices, the above process will have Y bytes of nonse material available for sampling by whatever applications need it. This should flow through a particular memory location like a ticker tape. Hell, maybe make the window for this output the debug registers on the processor itself.

The idea here is that although the process to come up with these little bits of nonce material is completely determinable, the pool of data that generates and is manipulated to get the output is (a) so large as to be infeasible to capture remotely; and (b) changing so quickly, and from so many sources of new bytes, that even physical access of the "state" of the mess at any particular point simply will not be of any value at N+ time slices later. Make the process to generate the nonce material require memory pools and processor power of a magnitude that make it infeasible to set up any kind of video card farm. Have the process that accesses web materials to throw in the pool go out and "access/download" ten times the amount of stuff that actually goes into the pool, such that an adversary monitoring these access attempts cannot duplicate the part of the pool that is mucked up with daily internet detritus of other (more locally) generated not really random garbage.

It probably will take some tweaking of the path through the muck and all the transformations to have the statistics one desires in the output, but in the end, you ought to have a stream that passes the tests for random characteristics. It won't be random, not per se, but it ought to be totally infeasible to hack and compromise.

In a similar frame of thought, for block ciphers, imagine a cipher that runs 10,000 rounds based on a preliminary key schedule, and then uses the results of rounds 10,001 through 10,032 to generate the key schedule (and perhaps tweak lookup tables and portions of the cipher etc) for the actual encryption operation which is performed using another 100 rounds. Is there a delay to the user? Sure. But a properly designed system like this would add mountains to the computational infeasibility of breaking the codes.

Its an outrageously inefficient approach, and THAT is the idea. LOL. If the government minders want a technological arms race, give them one.

Bonus points if you sprayed coffee on your USB compromised keyboard while reading this.

wasn't me • September 17, 2013 1:28 PM

Or just suppose if a fabless US-based SoC designer like Cavium could be pressured into weakening the encryption in their Nitrox chips. These are so incredibly powerful for offloading SSL and VPN encryption, up to several Gbit/sec, which would be very difficult to do any other way. These may end up in all sorts of appliance and shipped off all over the world. And then you would have backdoored huge volumes of sensitive Internet traffic for many years to come.

name.withheld.for.obvious.reasons • September 17, 2013 2:12 PM

Thanks Gonzo--how'd you know I would spill my coffee? Sounds a little too deterministic to me.
Off to get a CF (compact flash) keyboard, comes with a write lock.


greg • September 17, 2013 3:58 PM

> you can tamper with a logic gate to be either stuck-on or stuck-off by changing the doping of one transistor. This sort of sabotage is undetectable by functional testing

Well, sure, you won't catch it in simulation pre-silicon, but the whole point of ATE is to run test vectors at the factory to detect bad flops, bad combinatorial gates, and shorted/open wires, that are a result of manufacturing errors and bin out the bad parts.

As long as the RNG is hooked up to flops, and those flops are hooked up to jtag and test logic that eventually connects to a pin, then flops stuck to 1 or 0 can be detected by ATE.

they'd have to fiddle the doping and then they'd have to fiddle the ATE to ignore any failure from that flop for the part ot get out of the factory. But even then, once you have the part, you could put the part on your own tester, run the test vectors, and detect that the bit is stuck.

Clive Robinson • September 17, 2013 4:42 PM

@ Greg,

My take away from what was said, is that you can cause it to stick not initialy but after a short time of operation, so it would get through initial ATE butbe a juvinial failure in a non obvious way.

name.withheld.for.obvious.reasons • September 17, 2013 5:11 PM

@Greg, Clive

Also, milspec, EIA, and a half dozen other standards requirements mean destructive testing in addition to ATE tests. SPC might miss a deliberate valance layer as destructive runs tend to be based on smaller sample sets. So it could be possible to get it past a consumer or industrial QA process but less likely for non-counterfeit milspec parts.

Gweihir • September 17, 2013 7:00 PM

@Clive Robinson: Sorry, but no game. The "buzzword overload" strategy does not work against me.

I still think you have no clue. Your design is overly complex, it use the worst noise source possible, it is non-transparent and now you want to play games with the supply lines? And, no, there is zero need for a base-to-ground amplifier, the source is already low impedance and decoupling the signal is not a concern here, IT IS NOISE! If it gets distorted, that does not matter for the intended application at all.

Are you actively trying to discourage people by selecting the most complex solution that has a chance of delivering the intended result and using a lot of complex and hard to master RF engineering stuff that is completely misplaced in this discussion? That would either be stupid or plain malicious!

And while shielding (a plain, cut up can of tomatoes is quite enough, no need for any 'magic' pass-through capacitors, these you only need if you need a very stable signal line-to-ground impedance, because you have some calibrated filter or oscillator in there) is nice, it is not necessary with the 2-transistor avalanche construction. Even a mobile phone next to it does not matter as long as you use sound entropy gathering practices (entropy pool) and a conservative entropy per sample estimation.

This is not magic or difficult, no matter how much you try to make it sound like it is.

RobertT • September 17, 2013 7:20 PM

@Paul
You're kinda right that you can still inspect the chip and see what you get and compare to what you want but on 20nm designs this inspection will need to be done with a SEM because the structures are way to small for visible light. Remember the OPC does not need to do much to change the function. A NOR gate can become a funny sort of dynamic memory if one of the parallel fets has a via missing on the source or drain side. Naturally I'll make sure the test vector set can never discover this. So all I needed to do was introduce an error into the OPC function that would result in the miss processing o ONE well chosen via in the TRNG.

I dont know if you've ever worked on 20nm Failure analysis but I can assure you it is a major project to find this sort of problem, we're talking maybe $1M in expense using tools like FIB and SIM's machines. Before you even start down this road you need to have an idea about what you are looking for a "smoking gun". Most design guys move onto the next project as soon as they possibly can, they verify the function of their block and their gone. Monitoring the chip in production is a "production engineers" job and they're usually so green that they dont even know what the are looking for, especially with a block as critical as the TRNG, or anything security for that matter.

As I've said before, but not in this post, make the OPC mask changes after the first silicon is verified, you'll get most of the production volume with little or no top level engineering oversight. Masks changes are made during production for a variety of reasons., maybe to fix bugs in another section or enable so called "risk functions" (functional blocks that were added but not originally enabled) there are plenty of opportunities to make these changes during the life of the project.


Jimmy the Geek • September 17, 2013 8:50 PM

Bruce, thanks for doing what you do. You're always an education.

Re: paranoia...:

"Next in importance to personal freedom is immunity from suspicions, and jealous observation. Men may be without restraints upon their liberty: they may pass to and fro at pleasure: but if their steps are tracked by spies and informers, their words noted down for crimination, their associates watched as conspirators, who shall say that they are free? Nothing is more revolting to Englishmen than the espionage which forms part of the administrative system of continental despotisms. It haunts men like an evil genius, chills their gaiety, restrains their wit, casts a shadow over their friendships, and blights their domestic hearth.

The freedom of a country may be measured by its immunity from this baleful agency. Rulers who distrust their own people, must govern in a spirit of absolutism; and suspected subjects will be ever sensible of their bondage."

-The Constitutional History Of England

- by T. E. May

RobertT • September 17, 2013 10:18 PM

@Gweihir

your solution sounds interesting, do you have schematics so that I can run some simulations. Also do you have wideband FFT's of the output zoomed in around the 900Mhz and 2400Mhz bands, because this ubiquitous RF does leak into all manner of poorly designed /constructed equipment.

If I understood correctly your noise source is the Avalanche breakdown of an NPN junction. This should be OK for vertical NPN structures But I'll need to give a little thought to the long term stability of Lateral Bipolar structures under these bias condition.

BTW Clive's shielding paranoia is not without reason, because these days it is very easy to build a powerful RF transmitter and hide it near critical equipment.
There are three secrets to avoid accidentally demodulating injected signals.
- keep the source impedance low (which can introduce its own supply rejection problems) because supply's can be a major source of unintended signal ingress, they tend to have long total wiring lengths (equals large antenna effects)
- Keep the active / wiring areas small (minimize unintentional antenna's)
- Shield it.

Wakko Warner • September 17, 2013 11:22 PM

@Tony
I agree with you. The whole RDRAND issue is baseless.
There is no reason to suspect that the workings of RDRAND are in some way subverted. And yes, it is all in the open since LKML is public.

@Bruce
Please do read the answers of the Intel engineers in the thread you posted and also the LKML. Also, it would be a real, big, mistake to scare the people away from something that is actually working as advertised. When we do this we should have solid grounds under our feet or else we are only going to play in favor of NSA.

Mike the goat • September 18, 2013 12:29 AM

@Wakko - you may state that the TRNG is working as advertised but we all know it is impossible to validate. For this reason Tso's solution of using RdRAND as just one source of entropy rather than having /dev/random pump out RdRAND derived data directly. Surely this is a good compromise? If people need high throughput random data and don't have an issue with Intel's implementation then perhaps we can have a /dev/rdrandom

Wakko Warner • September 18, 2013 1:54 AM

@Mike
I perfectly agree with you. Linux's RNG should keep working as it is now. What i was simply saying is that the statement of Ts'o is simply exaggerated and that there is no real reason to even suspect any wrongdoing from Intel.

My point is that one thing is being paranoid, and i can assure you that i am, another thing is pushing people away from technologies that have a real chance to make security stronger just because of "voices" or "suspects".

If we let panic get at us, then the NSA will become stronger as we will walk away from hardware-based RNGs because "it's a black box".
I have already read many comments about scared people wanting to disable RDRNG from their OSes just because of what are IMO baseless statements... this is bad... this is going to really damage security not improve it.

After all, if you think about it, the whole CPU is a black-box. As is a black-box the chipset, the RAM and any IC inside your machine. From what we know the CPU could easily detect specific sequences of commands and subvert them, it could even wait for an external command to enable this behaviour and there is just no way to tell it.
And why worry about the hardware when the same OS used by 90% of people and governments worldwide _is_ a black-box? What are the chances that Windows does have a backdoor from NSA inside it? I believe there is a very good chance... much higher than the subverted RDRAND hypothesis.

Let me tell you, this whole NSA thing really hurt my trust in anything ever made in USA. NSA did a very bad job as "protecting USA" as i believe (and i won't hide that i do hope) many of us will walk away from any technological business in USA (when we will have a chance to do it).
As an european i really feel betrayed. What's worse is that no one in politics here is really giving "a shit" about all this.
They don't even seem to understand the implications of this all. They don't even seem to realize that the USA government betrayed us all... their supposed f*cking allies!

Lets for one moment think that the EU did this to the USA... what would have happened? So why isn't there any real reaction from my own country (Italy and Europe)? The only thing they seem to care is keep Berlusconi out of jail!

At this point what we (europeans) should do is drop any hardware and software coming from USA (and Russia, and China, etc.), it is clear we cannot trust anyone anymore. We should invest in our own chip-industries, in our own hardware-industries, in our own software developers... instead we letting every other country develop their (and our) technology and always trusted whoever sold us our chips, our software and so on. As anyone can easily understand, especially now, this is extremely dangerous for the security of any country. The same USA is buying chips from China/Taiwan/etc. without worrying that they _might_ be compromised.

So as you see it is not that i have any interest in "defending" Intel... but, at the moment, i have no reason to think that Intel is any worse than AMD, or VIA or any other big american or chinese company.

Sometimes i really think that i should get back from the attic my old MSX and use that... at least it is all made from the good old TTL family of ICs and the good old Z80 which are very unlikely to be broken by NSA.

Mike the goat • September 18, 2013 2:26 AM

@wakko - I agree with you. Given the concern perhaps Ts'o can have his code look on boot for a specific flag so those who do not wish to use RdRAND as even a source of entropy can simply edit their grub/lilo config and tack on a "rdrand=0". I think having something like a sysctl that you can write to while multiuser to disable/enable using RdRAND would be too difficult to implement given how it is currently designed but I may be wrong. Ideally though at a minimum even if a kernel boot argument is out of the question they should add a simple entry to the kernel .config so you can choose to force it off at compile time (I haven't looked at kernel source since 2.6 so it may already be there). This would be trivial to implement as the "old" behavior is the default where a modern Intel hwrng equipped chip is not detected.

I think given the way the kernel handles it there is no risk and only potential benefit from using RdRAND in addition to all the other sources of entropy the kernel uses. That said it is important to give users an option to easily disable a feature that some consider controversial.

On an unrelated note I am going to make a hardware RNG in the next few weeks just as a purely academic exercise and teaching tool. My plan of attack is to either use a tiny source coupled to either a Geiger-Muller tube or a CCD. The former would be slightly more expensive but would mean that I could use a very simple microcontroller to detect and time the milliseconds between "hits" and then send this stream through a hash to whiten the output. Seeing as one of the boards I was looking at has an integrated temperature and barometric pressure I guess I can use this data too. A simple daemon can read the data from the serial port and pump it straight into /dev/random. The latter idea of using a CCD I don't like as much. You could pump the output of each frame from the camera into a bit of code that reports the location of any "lit up" pixels which can be expressed as an integer (if we give, say each pixel from the top left corner onwards a number) and add to that the number of dark frames in between hits and the delay in ms between each lit frame. It seems like this would create non trivial overhead on the PC (although it need only be used periodically to seed the PRNG) which is why I like the microcontroller idea much better.

Wakko • September 18, 2013 2:42 AM

@Mike
Oh btw... if you want to increase the speed of the "hits" in your geiger tube you might add close to it a source of alpha-particles (assuming that your geiger tube can detect them) such as the one you can find in old smoke detectors (americium-241). Make sure you don't pulverize/eat/inhale it or you are in deep trouble.
Another good alternative is to buy on eBay one of those "glow in the dark" uranium-glass balls who emit gamma-rays.

Mike the goat • September 18, 2013 3:26 AM

Wakko: I am sure we have a 1 microcurie reference source of cobalt 60 somewhere. Might be perfect.

MarkH • September 18, 2013 3:44 AM

@Wakko: (nice handle, BTW)

I do recommend preserving the mechanical integrity of a smoke detector radiation source. (Don't cut or file, or scratch or abrade with tools, the tiny piece of metal which may be mounted at the center of a metal disc or other structure.)

Believe it or not, such a source _if intact_ is not really dangerous to swallow -- but of course, this is NOT recommended! The tiny quantity of Am-241 is plated with metals intended to keep the Americium atoms INSIDE the source, and the radiation emitted during the time it takes to pass through the digestive tract is not large.

These sources typically emit between 15000 and 25000 α particles / second. α particles are actually the nuclei of helium atoms, and because of their (relatively) giant size have very low penetrating power. A radiation detector (such as a G-M tube) for these particles must have a very thin window at one end: this window needs to be near the Am-241 source.

If you put a piece of ordinary Scotch tape over the source, the α flux drops essentially to zero: give it a try! If you touch the source with your finger, almost all of the α particles stop in the outer layers of your skin (again, not the best safety practice to have the source in skin contact).

Smoke alarms use these sources, because they are about as benign a radiation source as one can find (and because the Americium is a byproduct of nuclear reactor operation). The plastic structure of the smoke alarm fully contains the α radiation, and the only gas emission is a minute quantity of harmless helium.

FabQ • September 18, 2013 5:31 AM

Based on what I learned in class, it seems that controlling doping at the level required by this paper is really hard, expensive and error-prone. It seems easy to detect this with mask set inspection... any fabrication experts here?

Dirk Praet • September 18, 2013 5:34 AM

@ Wakko Warner

What I was simply saying is that the statement of Ts'o is simply exaggerated and that there is no real reason to even suspect any wrongdoing from Intel.

Hanlon's razor may apply. @Clive has previously made a couple of good points about their engineers' competence in that particular field. I very much like @Mike the goat's suggestion of an "rdrand=0" boot argument so the user/admin can choose whether or not to use it. IMHO simple to implement and everybody happy.

Wakko Warner • September 18, 2013 9:48 AM

@MarkH
Thank you for your recommendations and informations.

@Dirk Praet
Yes. I have now read the guide here http://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide

Of course it is still a black-box... but i think they put a lot of work and expertize into this hardware random number generator it would be very strange if they would let anyone sabotage it.

If i have well-understood this document then their RNG is incredibly fast... it tops over 500MByte/s of high-quality random data... this is well enough to wipe a whole 1TByte HD in a matter of 30 minutes or so... i still find it hard to believe it... this is the clear advantage of having something built straight inside the CPU (another advantage is that there is pretty much no way to mess with it).

Since the RDRAND is available at all privilege levels there is not even need to ask for the OS approval before using it... a couple of assembly lines will do the job and you will know that no one has messed with it. Since it doesn't do I/O it doesn't require any kernel-level driver. Any user-land software can use it without special privileges.

I am no expert but the architecture includes several self-tests who, i believe, make it particularly hard for an attacker to control it by any external (or internal) means. By reading this document it is quite clear that who made it wanted to make a good, secure RNG... i would be quite surprised to learn that after all this work they broke it on purpose.

greg • September 18, 2013 12:37 PM

Clive: you can cause it to stick not initialy but after a short time of operation, so it would get through initial ATE

From the paper: Since the n-dopant is applied to the entire active area
of the p-MOS transistor, including the metal contacts, a direct connection from
these contacts to the n-well is created.

It sounds like they're talking about doping a transistor so the output is always high or always low. This should be detectable by ATE.

Brian M. • September 18, 2013 1:10 PM

@gonzo, @MarkH:

"It is impossible to prove definitively whether a given sequence of numbers (and the generator that produced it) is random." -- Random.org

Nothing is a predictor of future entropy when your machine can be rooted. "Gee, my white noise generator is giving me a sine wave. What happened?"

However, a chip can be tested. Want to test a big sample? Get a big sample.

The hack under discussion is that the mask is modified (not a minor thing in semiconductor production) to change the bit range. If the test suite is any good, a reduction in entropy would be shown. The Dieharder test result I linked was run for 45 minutes, with a rate of "~6.374 billion bits per second." That seems to be a sufficiently large sample for analysis.

Random.org states that it samples atmospheric noise for its randomness. But how do you know that? It could be another cleverly designed NSA front. Who can you trust? Math that you do yourself. So look at the source code for the test suite, and run it.

At some point, you take your chances with what you have.

Coyne Tibbets • September 18, 2013 1:21 PM

The solution should be the similar to the "sock drawer problem". Use the chip to generate, say, 5 billion random numbers and see if there are more than 232 unique results.

MarkH • September 18, 2013 1:52 PM

Well Clive, you've got me stumped. You prescribe taking two signals -- one from either side of the diode. Unless charge is being created or destroyed inside the diode, the voltage waveforms ought to be accurately complementary - ne c'est pas?

Is the idea to XOR them as an integrity check against interfering signals?

Maybe was me • September 18, 2013 3:03 PM

@ wasn't me

"Or just suppose if a fabless US-based SoC designer like Cavium could be pressured into weakening the encryption in their Nitrox chips. These are so incredibly powerful for offloading SSL and VPN encryption, up to several Gbit/sec, which would be very difficult to do any other way. These may end up in all sorts of appliance and shipped off all over the world. And then you would have backdoored huge volumes of sensitive Internet traffic for many years to come."

This is precisely what the Snowden documents claim. From the excerpts of the budget requests the Guardian released, the NSA specifically claims that they are "working" to make various VPN encryption chips "exploitable." There is no mention as to whether this is through sabotage or cooperation from said manufacturer(s). Indeed, it is likely NSA has means and methods to do both.

The Guardian for some weird reason redacted the precise name and/or manufacturer of the specific chips the NSA was after (perhaps they were foreign companies and the Guardian felt that those were "operational details" that didn't need to be exposed). Or perhaps they were American companies that would be embarrassed if it were disclosed they were working with NSA to essentially make their product useless. Either way, I found it odd that Guardian used redaction.

Also, as an aside, John Gilmore (of IETF) posted an interesting story on the IETF maling list the other day detailing some of his experiences with NSA meddling in the IPsec protocol that was supposed to be a part of IPv6 (this was back in the late 90's I believe). He essentially said the NSA people were making things for more complex and confusing than need be and appeared to be trying to stop IPsec from being a viably secure protocol all together.

Gweihir • September 18, 2013 3:51 PM

@RobertT: I just did some experiments last year when I was bored. Also, as I said above, I do not have equipment to go above 25MHz or so, but that is not an issue here, you are not going to sample the signal much faster than at 100kHz or so anyways in a practical set-up. You want to run it though an A/D for minimal digitization loss and resilience. Personally, I don't trust the designs that amplify it until it is square and then sample it digitally. Too much risk of seeing only a dominant signal, and then shielding, supply filtering, etc. all become a potentially serious issue. With an A/D, you get the noise even if it is being just 10% of the final signal or less. As you need to hash it down anyways (say at an estimated 0.1bit of entropy per A/D sample), that is quite enough.

Use a large entropy pool, mix this in conservatively and you are fine.That is a fundamental difference to "normal" signal processing here: You are not concerned about keeping other signals out, you just want to make sure your original signal is still in there strong enough so that it influences final sampling.

So any 2.4GHz or 900Mhz signals do not really matter. (You do not really need to worry about these signals in audio either, do you? You also can also run all sorts of statistical tests and an FFT in addition to detect such a problem on the software side. And if an attacker can place something really close to your hardware, you are screwed anyways, as they then likely can directly manipulate that hardware.)

As to circuits, I did use the classical 2-transistor design from http://web.jfet.org/hw-rng.html, but with a 330R pullup, 12V supply and a pair of BC550C I had lying around. 330R pullup is the smallest not causing thermal overload to the transistors. I found little difference in the signal compared to 10k pullup, but of course less sensitivity to environmental signals. That gives about 50mVss of noise, with a flat spectrum that begins to level off at about 50MHz (could be my equipment though). I tried a number of different setups, and I was going to try a darlington as second transistor, but I got side-tracked and seem to have misplaced my notes. Experiments with single-transistor amplifiers were pretty unsatisfactory, as strongly dependent on the transistor. I will try the HCU idea that alo suggested (@alo: Thanks, should have had the idea to use an explicitly unbuffered one myself!) at some time, but have not yet gotten around to it. OTOH, 50mV is already strong enough for an 16bit audio input and certainly for a microphone input and may be strong enough for other 16bit A/D converters. And depending on the actual sample rate, you can just say screw bandwidth and use an OpAmp as amplifier. (Just don't forget the S&H if you do this yourself. A sound-card should already have all this and be fine. OTOH, a soundcard fill have some low-pass filters as well, so make sure not to sample too fast.)

Bottom line is that you do not need that many random bits, and they do not need to be that good individually, as long as you can be sure some quantifiable fraction is actually truly random.

Side note: I did a different generator a long time ago, based on OpAmp input noise. It used a 741 with shortened inputs and came out at something like 400k zero-crosses/sec. And it was sensitive to environment noise like hell. Needed complete encapsulation and a voltage regulator inside that to produce anything useful at all.

Gweihir • September 18, 2013 4:15 PM

@alo: Just saw that NPX actually gives an example for using the 74HCU04 as analog amplifier in their datasheet. Nice! Only 5Mhz unity-gain bandwidth product, but quite enough and no way to get this cheaper and simpler.

Clive Robinson • September 18, 2013 5:41 PM

@ Mark H,

    Is the idea to XOR them as an integrity check against interfering signal?

You could do that but you'ld get spikes due to phase delay and having differing "mid-points" on the logic that converted analog to digital in a simple circuit.

So not XOR ;-)

But your idea is on target. If you read back I was talking about both AC and DC grounds which might have given you the clue ,-)

Due to the AC coupling on the amplifiers inputs and outputs you lose the "mid-point" voltage. For various reasons limiters etc are bad news so a zero crossing detector is the better way to go. Also "noise" is almost by definition asymetric and simply integrating the signal unless done over a long period will not give you the mid-point back, but simple two resistors and take from their junction will give you a mid point for a zero crossing detector.

But also if you integrate this mid-point signal over various time intervals in various ways it will give you an indication of if there are things amiss in the analog section.

In some very broadband systems in the past they have mixed the two noise signals with a phase quadriture oscillator and then fed the two phase quadriture signals into a balanced mixer with DC connected IF. This is in effect a "direct conversion" receiver the output of which shows many evils relativly easily.

Whilst Gweihir's design will work, running transistors in avalanche mode unless they are specificaly designed for it is not usually a good idea due to the failure modes. And even if you verify one particular transistor from one particular manufacture unless the data sheet specificaly mentions the avalanche charecteristics they are very likely to change for various manufacturing reasons. The big problem with the design is although it's simple it's not robust and from a security perspective that's a major issue. The unoficial CIA moto is "trust but verify" for TRNGs thats the wrong way around it's "verify as you trust" which is the complaint I have with the Intel on chip TRNG, you can not verify it and thats a no no. The other issue as I've mentioned previously on this blog is the difference between real-entropy and faux-entropy there are a number of issues but the big one with entropy-pool systems is the entropy estimator. This should stop values being read from the pool if the real-entropy drops below a certain point. If you get the estimator wrong then you could end up with a pool that is little more than a simple card shuffling algorithm in one direction or loosing most of the usefull entropy by compleatly under reading.

Whilst I have no problem with people experimenting, specifications are there for a reason. You would not want to trust your life on a specification less TRNG any more than you would trust your life in a car built for fun without it being tested against the relavant standards. And from that point of view several dice in a beer glass might be a safer option.

Gweihir • September 18, 2013 5:44 PM

Come to think of it, the problem with RDRAND is not that it is easy to backdoor. The problem is that it has been made extremely hard to detect a back-doored instance in the field. No JTAG reading before whitening. No possibility to switch whitening off. Both are stupid and unnecessary and do not increase security, no matter what is claimed.

My conclusion is that while there may be no backdoored instances yet, there certainly has been significant malicious influence on the design to prepare for the future deployment of malicious instances. This may not even be the lead designer (David Johnston), but he either has no clue how to design a TRNG that is verifiable in the field or he deliberately allowed or was coerced to allow a design where that is not possible. It is really incompetence or maliciousness (not necessarily his, but some people think differently: http://blog.jim.com/crypto/rdrand.html) here, there is no 3rd option.

And a TRNG that cannot be verified in the field is just dead hardware that eats power and should never be used in any critical function anyways. A pity, this could have been a nifty hardware function.

Nick P • September 18, 2013 6:33 PM

@ Gweihir, Clive Robinson, RobertT

Yes the main problem with many cool ideas you guys have been discussing is verifying it isnt subverted and keeps its randomness over time. Im not sure thats doable. Also, amount of numbers generated might need to be high. So, I maintain that it's best to use CRNGs with seed generated low tech & hand entered via a trusted path during install or startup.

Manual methods of mine: deck of cards with many removed so only eight ranks exist. (Combine two such for 16). Learn to shuffle "too well." Shuffle it for a min or two. Then, with 8 ranks (2^3) and 4 suites (2^2), we have 5 bits of entropy. 80 bits is considered safe minimum by many that requires 16 cards to produce. Around another 10 give 128 bits. Use a few more to choose the CRNG or any layering of them or iterations before use for each. Then use its output for random numbers.

speedup: Dedicated airgapped cheap machine for making keys and RN's decent idea anyway. Use low tech method to get strong CRNG going, then use it to seed other machines. Encrypt its state with strong password and it can be backed up for if you think the CRNG machine was subverted.

Low tech 2: another near zero bias method I came up with was when I noticed 8-sided D&D die correlate to 3 bits perfectly. Divide no of bits you need by 3, round answer up, and do that many 8sided die rolls. Shoebox helps. Testing die for bias is easier than detecting subversion of electric stuff. And cards cant be subverted meaningfully that I know.

Gweihir • September 18, 2013 7:01 PM

@Clive Robinson: Stop the FUD already!

This is a _robust_ design and it is _not_ my design, but something that has been known for a very long time and if your fuzzily claimed "failure modes" where a significant concern, they would be known. It does work and work well with a wide variety of generic small-signal NPN transistors. It works well with a wide variation of emitter current. Still, running statistical test to detect hardware failure is of course part of any sane TRNG design, as components do fail, and it may not even be the noise source.

However, your FUD about "midpoint" is just complete BS, it does not matter here, unless you do a simplistic zero-cross detector design, which I have argued against. Your mentioning of a "phase quadriture oscillator" (and that is "quadrature", btw.) is completely irrelevant and only serves to confuse. What have you done, Googled HF design? You certainly do not understand what is being discussed.

You know, I had a lecture once that taught tactics for confusing "opponents", and I detect quite a few of the relevant techniques in what you are posting in this thread. In order to keep the tone civil, I leave the possible conclusions to the other readers, but ....

I am going to stop now pointing out that what you say is tangential, irrelevant, plain wrong and indicates you do not understand the problem. Be it hereby said for the future things you are doubtlessly going to post.

Muddy Road • September 18, 2013 7:15 PM

A NO TRUST model of future development is essential.

But, let me make it clear, it's government and corporate leaders that cannot be trusted.

There are many wonderfully talented and intelligent people creating and maintaining the internet who are also honest, ethical and responsible. Most of them certainly work for government or corporations. We can work with those who have not openly or secretly sided with corruption and lawlessness. Are they loyal to Americans or the bosses?

Start small, build out and build up that's the way.

As an aside, I agree laws need to be written and the politics of internet communication, privacy, security need work, a great deal of work.

However, as it stands right now we have a dysfunctional government that even at this moment is contemplating shutting itself down based on some flaky fantasy.

Rockford • September 18, 2013 9:20 PM

@Clive:
The unoficial CIA moto is "trust but verify" for TRNGs thats the wrong way around it's "verify as you trust" which is the complaint I have with the Intel on chip TRNG, you can not verify it and thats a no no

A question:
Is it possible to verify or even reverse engineer an on chip TRNG using an optican microscope and either 1) endless amount of patience or 2) some pattern recognition software that reads the input from the microscope?

Nick P • September 18, 2013 10:14 PM

@ Wakko and Mike the Goat

Re Smoke Detectors

http://www.cs.berkeley.edu/~daw/rnd/smoke-alarm

"Dr. Mike" was apparently working on that a while back. Several people thinking about an idea is usually a good sign. Publish your design if you can make one out of cheap smoke detectors that's also cheap and easy to build. Alpha particles aren't that dangerous so there might be some take up of *that* radiation-based design. ;)

martinr • September 18, 2013 10:37 PM

what puzzles me most about Intels RDRAND: Why the hell do they artificially thin out the randomness from 1.5Gbit/s into 6Gbit/s? this will amplify the bias of the collector. The AES-CBC-MAC conditioner will make the bias invisible to the statistical tests, but not make it go away.

For robustness, it would have been better to compress the output from the collector by a factor (1:4 or more) e.g. using a secure hash function. This would have taken care of most bias and weak/bad sample related issues already. With the DRNG forced between the entropy source and the RDRAND output a software-based compression of several consecutive RDRAND outputs seems necessary, maybe something like 17:1 or 23:1


Jon DuBois • September 18, 2013 11:38 PM

Wouldn't reducing the entropy by a factor of 2^96 show up in many statistics tests? Couldn't you just compare it to several software generators?

RobertT • September 19, 2013 12:45 AM

@Gweihir
I'd suggest you study the effects of high power RF ingress into unprotected circuits before concluding that everything Clive says is FUD.

With sufficient field strength EVERY bit of wire in the system becomes an antenna every diode a rectifying (down-modulating) junction. With high field strength 2.5Ghz of power supply lines become small resonant antennas, look at the "self resonant frequencies" for even the best decoupling surface mount capacitors, you'll see that most ceramic caps have SRF's well below 1Ghz. Wire lengths of just a few cm's can will have a few nano henrys of inductance. Look at what this means for single ended reference signals (say the bandgap reference use by your ADC)

Now you might say this is all so far out of the signal band BUT once you sample it you effectively down convert the RF signal and its modulation. The Beat pattern from this down conversion might still fall out of band, or it might not, to know which you'll need to do some good old fashioned RF signal planning.

High field strength RF ingress might not be of concern for the average home PC owner but it is definitely something to consider IF you are trying to keep state level adversaries out of your high value commercial server systems.

MarkH • September 19, 2013 3:17 AM

@Gweihir:

This is almost completely redundant with RobertT's comment, but maybe I can put it a little differently:

1) Clive's info is (as far as I can tell, and I've been following this blog for a long time) predominantly based on real-world experience. Sometimes I disagree with his take on things (and yes, sometimes I get impatient with the way he presents things, though he's gotten a lot better at it), but when he says "X can get you into trouble," I consider it prudent to take a damn good critical look at X before making use of it. In my opinion, attributing unworthy motives to somebody who's trying to help means it's time to sit down and take some long deep breaths.

2) It doesn't matter at all that radio frequencies are outside the band of signals for your circuit. What matters is whether the modulation frequencies* applied to those RF carriers are in your circuit's band. Because the circuit's signal band corresponds (very roughly) to audio frequencies, the likelihood of modulation in that range is very high indeed. So in fact, RF signals in the 100s of MHz can very badly bias an RNG that operates only in the kHz range.

*As RobertT notes, in practice there can be situations that are more complex than this. I refer to the simplest (and most benign) case.
___________________________________________

Anyone not already aware of point 2 has BIG knowledge gaps concerning electronic engineering. I learned about the dangers of unintended RF detection to signal processing circuits before I learned to drive a car -- and I'm reminded of this problem every time I'm listening to music and a truck driver passes my house with his AM transmitter keyed :)
___________________________________________

I wouldn't bother to make a hardware RNG unless I took confidentiality very, very seriously. And because I take confidentiality very, very seriously, I want to educate myself about real-world failure modes. If an RNG is inadequately protected from RF interference, it could make long bursts of nastily biased output, even while passing 100 tests a day.
___________________________________________

Bruce has tried to explain the "security mindset." Plain Old Regular Engineers focus the majority of their attention on How Things Work. Security Engineers don't worry much about that (that's what Plain Old Regular Engineers are for). Security Engineers are constantly exploring, "how can this fail?" and "how can it be INDUCED to fail in a way that breaks security?"

Clive seems to have a near-encyclopedic knowledge of security-compromising failure modes. Sometimes I wonder whether he soldered triode valve circuits for A. M. Turing.
___________________________________________

Before I finish my sermon, two anecdotes I found instructive:

A. (read in a magazine) A man who had worked as a telegrapher (this was a job category once!) when he was very young had ajdusted the pivot screws nice and snugly on his telegraph key. An old-timer told him, "you've got to leave some play on that key, or you'll get glass elbow." The youngster ignored this advice, and learned to his considerable pain what glass elbow is.

B. (told by a gentleman I met some years ago) As a youngster, he worked in shop making furniture. For cutting very large pieces, they had special cutting room with a giant circular saw that was suspended from a rig on the ceiling that enabled it to be moved about anywhere in the room; the operator would walk the saw about to make the cut. He was preparing to cut a large piece of maple to size, and an old-timer said, "you've got to watch that maple: it's hard, and then it's soft." He only understood what that meant when he suddenly found himself with the whirring saw blade a finger's breadth from his chest.

I think of Clive as an "old-timer" who has collected a lot of lore about how things can go wrong, and is generous enough to take his time to educate people on this blog.

Clive Robinson • September 19, 2013 5:00 AM

@ Rockford,

    Is it possible to verify or even reverse engineer an on chip TRNG using an optican microscope and either 1) endless amount of patience or 2) some pattern recognition software that reads the input from the microscope?

I'm not the best person to answer this but I'll say what I understand the problems are.

Firstly visable light optical methods won't work due to the wavelength -v- transistor size. So you have to think in terms of optical methods that use much shorter wavelength (there is an old rule of thumb that indicates 16:1, that is the wavelength should be atleast 16 times shorter than the dimension you are trying to measure). But that aspect is just the start of the problem so we will ignore it for now.

Semi-conductors are often thought of as two dimensional not three dimensional objects and without being destructive you can not look inside a box that is not transparent to the frequency you are using.

So you have to ask an important question,

If I destructivly examine the contents of the box is it possible to have hidden features that get destroyed as part of the process of the destructive part of the examination?

And as far as I can tell the answer to that is likely to remain yes, which if true would mean the answer to your question is unfortunatly no.

However, the US DoD is putting a very large pile of money on making the answer to the question yes. If not 100% yes atleast some significant percentage of yes.

Is this a usefull thing to do? I actually think so.

The reason for this is one of dividends. If they find methods to find a significant fraction of such subvertion then it makes it ever increasingly expensive for those trying to subvert the system. And yes it becomes a game of cat-n-mouse with ever increasing cost which would appear endless, which on it's own simply becomes a game of who can outspend their opponets perceived or actual.

But there is another aspect to consider which is plurality of supply lines. At some cost point it becomes less expensive to switch to a mitigation methodology. With out going into the ins and outs of it you can as NASA did with their "voting systems" half a century ago find ways to see changes in behaviour that would otherwise be difficult to detect.

In this way you accept the fact that systems "may" be untrustworthy but design it out of the system to the point it can be mitigated to the required level of confidence.

Ultimately it becomes security by obscurity where by the oponent has to guess what measures the deffenders use to detect them, and they have to get each and every one right or lose the game. The defender on the other hand does not, thus the attackers costs rise at some power law above that of the defender (this is the opposit way around to what is considered the normal defencive problem with attackers where you hear "the terrorists only have to get lucky once"). In effect it becomes "probabalistic security" with the high cost going to the attacker not the defender.

RobertT • September 19, 2013 6:14 AM

@ Rockford,
"Is it possible to verify or even reverse engineer an on chip TRNG using an optican microscope and either 1) endless amount of patience or 2) some pattern recognition software that reads the input from the microscope?"

Up until about 10 years ago it was easy to reverse engineer almost any chip with just a microscope a camera an XY moveable stage and a diamond polisher . Basically you take photos and move the stage by so and so many mm on one axis, take another photo and repeat.

Once you have photographed the top layer you take the diamond polisher and polish back the surface to remove the top layer and repeat the photo process on the next layer. A chip might have 7 levels of metal and one level of Poly typically the rest of the layers are uninteresting because you can guess them.

With a little work you can identify the logic gate function for each of the patterns, this gives you all the logic primitives used on the chip you than only need to figure out how they connect to one another. The interconnect information is like a of wiring list for a PCB.

With all of this information you can now simulate the circuit and see exactly what it does.

With something like a TRNG the real secret sauce will be in the ways in which the "random" events are generated.


Most on chip TRNG's uses multiple jittery ring oscillators that are sampled at a rate significantly below the cycle jitter accumulation rate. (if say a 10Mhz oscillator is used than it might accumulate 2 nsec of jitter per cycle so we want more than 100nsec of unknown meaning you sample this jittery ring oscillator with a fixed frequency source (at less then once every 50 cycles = 50*100nsec = 5usec.
This gives you one bit of random data every 5usec repeat for extra bits.


Just because MOST Trgn's are done this way it does not mean that ALL Trng's do this. Today it is becoming common to use higher order Sigma Delta modulators as the noise source (these operate as chaotic circuits where small errors get accumulated and multiplied by the loop gain) To analysis this circuit you'll need to understand how to simulate Sigma Delta modulators and use tools like Spice to simulate. The exact way this noise shaping loop works will depend on the interaction of the on chip capacitors and maybe resistors in the loop. You need to have a fair idea what you are looking at before you know how to simulate it.

OK so this was what happened 10 years ago, today thing can be done the same way but the process is made more difficult because the structures are below 1/10 of the wavelength of viable light. You can compensate by using deep UV optics with a 130nm illumination laser. With this process you'll be just about able to extract a 45nm chip, remember the cell dimensions will still be several 100nm so you can still figure out what cells are used and still kinda trace the interconnect. At sub 20nm I'm not sure how to reverse engineer a chip.

Part of the problem is that there is no pointer saying LOOK HERE TRGN, so you must figure the location of the cell by other means (It helps if you can find an ISSCC presentation with a chip photo)


BTW" if you dont want to do this yourself there are specialty companies that will do the whole reverse engineering for you. for something like a 20nm TRGN you would probably need to pay them somewhere between $10K and $100K.


Z.Lozinski • September 19, 2013 6:53 AM

@Clive, @Rockford,

There is a nice article on the "The State-of-the-Art in IC Reverse Engineering" (from 2009) written by two engineers from Chipworks, and hosted by the International Association for Cryptologic Research. Chipworks is a reverse engineering company.

http://www.iacr.org/archive/ches2009/57470361/57470361.pdf

Clive has already mentioned the problem of using an optical microscope. The Chipworks paper has a case study of the reverse engineering of a Sony camera chip, and there is a scanning electron micrograph (SEM) showing the planar structure of the 3 transistors that form the circuit behind an individual pixel sensor. You can also use SEM to give the profiles through the chip and see the 3D structure, which shows you the interconnects and metal layers.

The authors also make the point that you can use scanning capacitance microscopy to determine positive and negative doping. SCM was invented in IBM Yorktown in the late 1980s, and the original application was semiconductor dopant profiling.

The legal aspects of this are are covered by the American Bar Association:

http://www.americanbar.org/newsletter/publications/gp_solo_magazine_home/gp_solo_magazine_index/intellectprop_judicialsupport.html

So, if you don't have someone who is actively trying to make a chip (or a part of a chip) that cannot be reverse engineered, you should be able to analyse it. For current chip technology, assume a lab with (I'm guessing) upwards if $100K of equipment. A university physics lab would have what you need. Then you need staff to do the actual analysis (or graduate students).

If you have an organization actively trying to make the chip hard to reverse engineer, then as Clive says, you are in an arms race. Don't bet against FIPS 140-2 "Level 4 attackers" (ie state-funded actors). There is a lot of interesting history in the evolution of the protection of banking hardware security modules (HSMs) which shows this sort of arms race in action.

Z.Lozinski • September 19, 2013 8:21 AM

Some fun reading. Sergei Skorobogatov, from the Computer Lab in Cambridge, has written up all the techniques he knows for reverse engineering hardware.

There are some nice pictures of just what sort of information you can extract from a chip with various technologies from fuming Nitric Acid to lasers and infra-red cameras.

http://www.cl.cam.ac.uk/~sps32/PartII_040213.pdf


Mike the goat • September 19, 2013 10:08 AM

Hmm, off topic but just doing a bit of rough mass based on the 90000sqft data center area of the new MD facility of the NSA. Scary but using COTS hardware I described earlier they would have the ability to try 1,986,584,000,000 tries a sec at an AES key when brute forcing. Now if that space was filled with /custom/ ASICs then the figure would be astronomically scary. Which is why I use 4096 bit RSA when I have to use asymmetric.

Clive Robinson • September 19, 2013 11:36 AM

@ Jon DeBois,

    Wouldn't reducing the entropy by a factor of 2^96 show up in many statistics tests? Couldn't you just compare it to several software generators?

Simple answers not always, not realy.

The longer answer goes back something like 150 years ago to a man who probably more than any other put the nail in the coffin of "pre-ordained" and "all-knowing" which prior to the 20th century had led mathematicians to belive that all questions were answerable even when dealing with "God's Domain" of infinity.

Georg Cantor was not a happy bunny about the then almost universal mathmatical view of the world and some time prior to 1874 he had come up with a simple and very elegant argument as to why it was wrong. However for reasons unknown he chose to publish a much more almost impenitrable argument that in many ways was ignored (as I shall now do ;)

Although published much later his simple --Cantor's diagonal-- argument can be seen as the death knell of the old order and both Kurt Godel and Alan Turing used it for their to seminal works that have defined the limitations of logical systems and computer long before the first computer was built (neither Pascal or Babbage count for differing reasons).

The diagonal argument deals with infinite sequencies and shows that no matter how many you know there will be many times more.

The most fundemental difference between a TRNG and a PRNG is the former --is in theory-- infinite and non determanistic and the latter finite and determanistic.

Thus a TRNG could push out any sequence at any time whilst a PRNG will only push out a predetermined sequence. But there is a problem there is the issue of what the observer sees at the output of the black box RNG. For each bit out there can be two choices as the sequence continues as you would expect there is 2^N possible sequences but... how many generators are there?

The answer is you don't know and you can't know you can only say that in human terms there is adefinately one for each sequence seen (actualy it's rather more than infinity if you look at Cantor's other work). Further it's actually not possible to say if the sequence you have observed is the product of a PRNG or a TRNG that by chance has generated that sequence.

Thus all sequences are in effect equiprobable and all those you can observe are by definition finite which is a very small fraction of what sequences are possible. So for what ever statistical test you devise to try to measure a finite sequence you cannot do any more than say "there is a generator that has produced this sequence and it has passed the tests that stand witness to it's lack of statistical anomalies tested for". It's why a CS-PRNG can stand in for a TRNG over a short length of it's output, and if it's state size is large enough then from any normal measure it can not produce sufficient output for you to be able to tell if it is a TRNG or CS-PRNG.

Wael • September 19, 2013 12:02 PM

@ RobertT

Up until about 10 years ago it was...
Great info...
20nm TRGN you would probably need to pay them somewhere between $10K and $100K.

I am surprised this is a lot cheaper than I thought it would be.

MarkH • September 19, 2013 1:24 PM

@Mike the goat:

There's plenty to be scared about ... but probably not their ability to crack encryption. That's why backdoors (such as the topic of this thread) are so important.

To find a 128-bit key by exhaustive search needs (on average) about 170,000,000,000,000,000,000,000,000,000,000,000,000 tries. The best known attack on a single AES-128 key reduces that only by half. Bearing this in mind, the ability to test 2,000,000,000,000 keys per second is utterly useless (unless NSA has broken your PRBG, see topic of this thread).
___________________________________________

As to RSA: all public key systems depend on "computational security," which means that any key can be cracked by executing algorithms that are much, much faster than exhaustive search, but whose cost is high enough to render cracking impractical.

Usually, cryptographers speak of cost rather abstractly, by quantifying the "order" of operations required to complete the algorithm.

However, it can be amusing to make the cost estimate more concrete. Elsewhere on Bruce's blog, I estimated that factoring a 1024-bit RSA modulus (the best known attack) using GNFS (the best known algorithm) would consume at least $200,000 of electricity. Allowing for improvements in technology, and perhaps better electric rates, let's take this to be $100,000 today. The way GNFS factoring scales, the number-crunching to factor a 2048-bit RSA modulus would be at least a million times greater (actually, a lot more than a million). But as a baseline figure, let's say $100,000,000,000 of electricity.

Leaving cost to one side (NSA would need several years of their whole budget, to buy the electricity of factor ONE MODULUS), to perform this factoring in one year would require continuous 24-hour-per-day consumption of more than one quarter of the entire electrical generation capacity in the United States. This is to say nothing about the quantity of hardware required, and how much that would cost. Also, you might enjoy sparing a moment to ask "how do I cool my data center at a rate of 200 gigawatts?" (if I don't, temperatures will rise problematically -- and given the poor efficiency of typical cooling systems, cooling can increase energy total cost by a substantial margin).

For 4096 bit RSA, the cost becomes much, much worse.

Now, this analysis assumes:

(a) NSA didn't break the random generator used to create the key (per topic of this thread)

(b) nobody has discovered a better attack on RSA than factoring the modulus

(c) nobody has discovered a factoring algorithm better than GNFS

(d) most efficient available off-the-shelf computer hardware doing the computation

Note that with respect to (d), although NSA obviously can afford to do custom silicon development, what really matters isn't speed: it's the number of joules per arithmetic operation. The optimum for this probably won't be the latest super-duper CPUs (or GPUs), but rather fairly generic medium-speed processors. It seems unlikely to me that the energy per computation could be improved over the commercial state-of-the-art by better than a factor of 10 -- most of the world's computing capacity is now (or at least, will shortly be) in people's pockets, powered by lightweight batteries, so a LOT of R&D goes into efficiency.

Let's give NSA the benefit of hyper-optimized (factor of 10) hardware. If the hardware is free (say, found in a dumpster), and they are willing to devote almost all of their budget to paying for electricity (thereby, firing most of their employees and contractors), they could factor one 2048-bit modulus per year. Still, the computer cluster's power consumption would likely exceed the output of the world's largest generating station (the Three Gorges Dam in China).

Mike the goat • September 19, 2013 3:31 PM

Mark: of course my estimate doesn't get them nearly close enough to breaking, say an AES128 key. That said, it is a frightening amount of computational capacity when you take into account what else they may have up their sleeve to reduce their workload. My fear is that they have a viable cryptanalytic attack on AES. It is my opinion that a government doesn't push a technology unless it has the technology somewhere to break it (eg DES). If this is the case, even if moderately computationally expensive then all bets are off. I have similar concerns about the RSA problem. It is admittedly unlikely but they may have a breakthrough on factorization.

That said if I was the NSA I would not even bother with this route and would instead pursue ways to leak keys, weaken crypto hardware etc.

Something to consider - let's pretend they did subvert a popular VPN concentrator as reported and they didn't have it leak its key in some crafty manner. Pretend that the keys generated are made correctly but with a very low entropy (deliberately) RNG, ala a deliberate Debian SSL bug (but not quite as weak and overt). Your big cluster would now be necessary for breaking these weak keys.

Even better have the RNG doing something that looks random but isn't, like encrypting the output of the RTC with AES. They know the key, they know the time (and the device is likely NTP enabled so there is a fair amount of accuracy there) so they should be able to work from there.

My thoughts on RSA are to trust it but increase the safety margin to 4096, which should be well above any technology we could anticipate them to have (unless they have fundamentally broken it by a new means of factoring). I don't think it is unreasonable and ads minimal overhead.

Nick P • September 19, 2013 4:49 PM

@ people worrying over RSA

There was a method that was resistant to classical and quantum attacks on signature schemes. Impractical esp due to size of data. Today, we have tons of bandwidth/storage and a bunch of solid hash functions. So... Merkle signatures to the rescue?

http://www.emc.com/emc-plus/rsa-labs/historical/recent-improvements-efficient-use-merkle-trees.htm

Simpler alternative: sign with multiple signatures each using a different hard problem (RSA, NTRUsign, etc.). Can combine them HMAC style to prevent transferring several KB of signatures on every transfer. And remember that we only need asymmetric for secret exchange if non-repudiation isn't an issue. From that point, our symmetric algorithms can do all the work.

Gweihir • September 19, 2013 5:52 PM

@RobertT: It is really not a concern here. First, you have a very low source impedance and a pretty strong signal. Second, and I guess this is something all the folks here that understand RF engineering have real trouble coping with, as long as you have enough of the noise signal left (and you do not need a lot), all the interference in the world does not make it circuit fail. I know where well that shielding is a major concern in RF design as most circuits become unusable even with a little interference. Not so here.

That said, my impression is that Clive has really no clue about RF engineering, but googeled a few things. Requiring mu-Metal for RF shielding is just stupid, as it pretending lead-in capacitors are somehow special (or needed here). His non-understanding that doing zero-cross detection only results in a very non-resilient design is telling. And his claim that the avalanche-construction is a severe risk and on amateur level is just plain wrong.

What really annoys me though is that he tries to sabotage the discussion for a little self-aggrandizement. That is just plain repulsive and immoral.

@Mark H: The modulation frequency does only matter unless it is a modulation the circuit can actually decode and the base carrier does not get dampened out. Just to be sure, I have placed my cellphone next to a sample circuit and made a call. No change in the output spectrum at all. That tells me that the argument about interference and "modulation" is nonsense for _this_ circuit, just as I expected. What you seem to forget, is that this is a very low impedance source and that coupling something there requires massively more RF energy and that the components are far too slow to be able to demodulate the frequency ranges in question.

And no, Clive's comments in this discussion are laced with nonsense, blustering and wrong information. Sorry, but he just has no clue here and seems to be desperate to hide it and thereby hurts everybody looking for information. He is spreading FUD, nothing more.

gonzo • September 19, 2013 7:36 PM

All.... I don't think we're well served by bickering with each other or getting into e(ngineering) dick measuring contests.

Frankly, none of us here likely will use a hardware RNG based on a home built circuit. None of us have that sort of problem. A RNG in hardware we can trust on a system that is not compromised is the goal. Lets keep our eyes on it and avoid the circular firing squad.

MarkH • September 19, 2013 8:57 PM

gonzo,

I concur that the place we'd like to reach, is to have trustworthy components and systems generally available.

To the extent that this can be accomplished, it is likely to take a decade.

Today, tomorrow, and for years to come, there are and will be people and organizations with critical security requirements, who need trustworthy solutions before our hoped-for nirvana is attained.

And some of them "likely will use a hardware RNG based on a home built circuit." This is not an academic exercise.

In governments we have dangerous* adversaries who not are only extremely powerful in resources, but also actually using the compulsion of law and police power to force substantial organizations to become secret accomplices. How many integrated circuit foundries are beyond the reach of such compulsion?

The security community is in a situation analogous to an intelligence organization just learning that a "sleeper" agent was imbedded in it for years. It's unlikely that EVERYTHING is compromised ... but every technique, every file, every device, every operation, MAY have been compromised in some way. In order to restore security, everything must be assumed to be contaminated until its soundness has been carefully evaluated.

It has become reasonable to assume that any factory-produced TRNG has a non-negligible probability of having been intentionally compromised. As has been discussed here, when the (supposedly) random bit source is inaccessibly enclosed in a black box, it is impossible by inspection of outputs to verify that they are actually unpredictable. The availability of unpredictable numbers is the root foundation of all cryptographic symbol-manipulation techniques -- so an anti-confidentiality organization like NSA (or, almost certainly, the government of PRC) must consider the compromise of RNG hardware an extremely high value target.

Personally, I find paranoia and conspiracy theories to be exceedingly irritating, and almost always brainlessly stupid. I don't like being railroaded into a situation where paranoia is the cautious default posture. Unfortunately, it is what it is.

*empowered to imprison and (in the countries containing most of humanity) kill, openly and legally

Nick P • September 19, 2013 10:07 PM

@ MarkH

Well said! The comparison to an organization learning of a sleeper is excellent.

The analogy implies the correct response ;)

Of course, knowing that we're being hit with that kind of panic we should remember our own advice to lay people after 9/11: don't panic. We have to remain calm. We must rationally address the situation and not let our paranoia feed into the analysis too much. We must identify risk areas, then make mitigating decisions where possible.

One thing that helps me is that they don't have full access to everything. Their leaks don't indicate that. If anything, their leaks indicate they tried to unnoticeably *weaken* many important things for *future* attacks. And what they weakened was mostly made by American companies. This should relax INFOSEC pro's in that it tells us:

1. We might be safe[r] if we just augment the security-critical functions of COTS gear that they likely targeted.

2. We can probably rely on foreign made chips to not have NSA backdoors, although we should assume host govt might have one & test for counterfeits.

3. The countries identified in leaks to be targets of NSA activities will become safer for both data and security-critical products in near future as they try to resist US subversion (or US anything).

4. That NSA's adversaries know they have strong focus on traffic analysis can be used against them by smart adversaries.

5. That NSA prefers subversion might boost the use of both open-source and subversion resistant development processes.

So, far from extreme paranoia, people concerned for their privacy have much to be grateful for and happy about. I mean, imagine if our country had the SS with NSA's tech: none of us would be openly talking about this and any counter move would be *very* hard to pull off. We're all speaking, breathing, having public conversations, private one's too albeit anxiously, and have strategies for handling parts of the situation near-term. We remember this, then maybe we all stay sane and come up with ways of reducing our risk until a real solution emerges. If it does.

Mike the goat • September 19, 2013 11:29 PM

@Mark: I know someone else mentioned this elsewhere but Linus the other day was asked at a conference whether the NSA had attempted to subvert the Linux kernel. He answered in the negative while nodding in the affirmative. Whether he was joking or was trying to hint at just thst , perhaps without overtly violating an NSL or gag order is anyone's guess.

The problem we all face as system administrators and security oriented IT professionals is that our employers pay us to ensure their machines are secure. We can no longer even testify to the fact that we believe them to be safe (although really we never could warrant them bug or remotely exploitable flaw free) and this might be an issue for the eagles in the legal dept as they ponder compliance with infosec legislature and for those organizations who handle financial data Sarbanes-Oxley &c.

MarkH • September 20, 2013 3:16 AM

@Nick:

Personally, I don't think it particularly likely that the Intel RNG has been subverted. Regrettably, I don't know any way to confirm this, and it doesn't seem plausible that anyone will be able to give assurances on which we can rely.

Though NSA and the FBI certainly don't have access to everything, giant US companies like Intel are (ironically) the most vulnerable to their hammers of persuasion. It would seem completely sensible to me, for an NSA infosec boffin working on the problem of increasing world-wide traffic visibility to advise "go for the Intel RNG -- it will pay us back more than any other measure we can possibly take, and at very modest expense."

Those of us with engineering ability can concretely make some little steps to advance the situation, even though there will be many problems that remain difficult to remedy.

Starting from the premise that if your random source is broken, then EVERYTHING is broken, I think it should be entirely practical to publish "open source" build-it-yourself TRNG designs -- and also to provide certain materials for them, in such a way that everything is 100% auditable. In other words, to set up a trust-worthy source whose message is "don't trust us concerning ANYTHING -- you can and should verify the security case yourself." This would be the diametric opposite of Intel.

Ordinary consumers will never go that route, nor commercial operations. But there will be individuals and organizations around the world needing to take high precautions, with life, limb and liberty at hazard. It's possible to provide options for these cases, and I think there are enough geeks who "support the cause" to provide the necessary technical backup (mainly, in the form of painstaking security design review).

Gweihir • September 20, 2013 4:34 AM

@gonzo: Actually, I am in the process of deploying a TRNG in an experimental fashion. That is why I have looked at these things for a while.

Clive Robinson • September 20, 2013 5:33 AM

@ Gweihir,

I realy don't know what your issue is and what you are saying is not helping you, as the comments of others are indicating.

Especialy when some of your statements are just wrong and apear to be based on what you would like to think I am saying, not on what I am actualy saying.

In your latest posting you say,

    Requiring mu-Metal for RF shielding is just stupid, as is pretending lead-in capacitors are somehow special (or needed here). His non-understanding that doing zero-cross detection only results in a very non-resilient design is telling. And his claim that the avalanche-construction is a severe risk and on amateur level is just plain wrong.

I've only refered to mu-metal once and I said,

    As for sheilding you need to issolate the noise source from the amplifier and dc filtering and in turn shield all three from other parts of the circuit. There are shielding materials and shielding materials silver plated mu-metal has been used in the past but is impractical for most home constructors.

      I have quite clearly said "silver plated mu-metal has been used in the past" which is a verifiable fact, I also went on to say "but is impractical". So I'm not sure how you think I am saying it's required... Perhaps you would care to state how you arived at that idea, especialy when I explained another method in some detail immediatly after my statment about it being impractical?

      Further contrary to what you say I did not say "mu-metal for RF shielding" I said "silver plated mu-metal" with respect to shielding --not "RF"-- that issolated the noise source from the dc filtering of the supply and the following amplifier sections. The "silver plated" asspect is what provides the RF shiielding the mu-metal is for magnetic shielding. As any audio design engineer over fourty will tell you circuitry dealing with low level signals often needed to be magneticaly shielded from laminated iron E-Core transformers used in the power supply and other places. Low power mains power supply transformers these days come as two basic types laminated iron E-Core which could be problematic in a small enclosure or ferite toroidal transformers that are generaly not problematic unless the core gets damaged.

      As for your comments about feed through capacitors if you go back and re-read what I wrote I gave three ways for required connections to ingress and egress from the sheilded areas. I indicated that the feed throughs were the best option. Now feel free to take acception to that but don't give as a reason any competant EMC or EmSec design engineer would say is possibly the least important reason for using them. You will find them used in many many forms of secure equipment especialy those that have broadband signals and also test equipment ranging from oscilloscopes through much RF test gear as well as anttena amplifiers for communal dwellings and cabe televison head end amps. Whilst not as ubiquitus as other components they are fairly standard, which is why DigiKey has so many types available.

      With regards your "his claim that the avalanche-construction is a severe risk" is again very far from what I have said. I have noted that many transistors are not designed with avalanche mode operation in mind and some designs will be changed without the avalanche charecteristics taken into account. Without using a part specificaly designed for avalanche mode you run the risk of damaging the device or making it fail long before it's MTTF. I once heard a design representative from Motorola refer to using ordinary signal transistors this way as like "trying to drive your car in reverse down a motorway and trying to keep up, you get a lot of noise but lousey milage and repair bills".

      You should have noted from the fact I say "noise source" I am being agnostic to the type. And for longevity noise diodes have been specifficaly designed for the job thus it is part of their normal specifications and can be relied on over time. You could also use voltage regulator diodes or some LEDs but whilst they are being used in their normal mode of operation the noise charecteristics are generaly not given as part of their data sheets thus may well change as manufacturing processes improve or the devices age.

      As for your comments about detection / conversion you have not said what issue you have in particular with a zero crossing detector. As you should appreciate all designs are compramises for various reasons some of which change with time and technological improvments. Further you have not said what your chosen method is, you have just made comments about sound cards. Which is at variance to your other comments about bandwidth of amplifiers. Further you appear to think 74 family logic is the way to go but appear not to have been aware of the differences between 74ALS and 74HCU parts both in operation and output configuration, which is usually given in quite some detail in the data books section that charecterise the family types. Which also tends to suggest you are not familier with their input configurations and the issues arising from their out of specification usage.

      Any way I will as this is getting well of topic leave it for now befor either Bruce or the Moderator showes either of us the yellow card.

      However when this thread has quitend down in a week or so and if Bruce allows it I will be quite happy to continue the technical aspects of this discussion with you.

      []

Nick P • September 20, 2013 11:35 AM

@ Mike the goat

"We can no longer even testify to the fact that we believe them to be safe (although really we never could warrant them bug or remotely exploitable flaw free) and this might be an issue for the eagles in the legal dept as they ponder compliance with infosec legislature and for those organizations who handle financial data Sarbanes-Oxley &c."

name.withheld said something similar. I cannot overemphasize how misleading (and impractical) such statements are. The revelations show us the systems are vulnerable to *The All-knowing, All-powerful NSA*, not *every blackhat companies worry about.* If NSA is in such companies' threat profile, then... then I don't know what they're thinking. If they're worried about the threats that *actually damage them*, then there's plenty of tech that can we can have confidence in and NSA's actions have almost zero effect on that.

Also, what legal compliance requirements force anyone to be secure against a domestic TLA with legal authorization to hack them? Has anyone been prosecuted for not being NSA proof? This is an imaginary concern. NSA & INFOSEC compliance are two different issues in 99+% of cases. On other hand, I can think of a few companies and individuals that suffered greatly for doing the opposite: resisting the NSA.

Of course, recent events would worry in the exceptional case where the NSA is actually in your threat profile and you're operating stateside in a public way. Good luck with that, all I can say.

Nick P • September 20, 2013 11:41 AM

@ MarkH

"Those of us with engineering ability can concretely make some little steps to advance the situation, even though there will be many problems that remain difficult to remedy.

Starting from the premise that if your random source is broken, then EVERYTHING is broken, I think it should be entirely practical to publish "open source" build-it-yourself TRNG designs -- and also to provide certain materials for them, in such a way that everything is 100% auditable. In other words, to set up a trust-worthy source whose message is "don't trust us concerning ANYTHING -- you can and should verify the security case yourself." This would be the diametric opposite of Intel.

Ordinary consumers will never go that route, nor commercial operations. But there will be individuals and organizations around the world needing to take high precautions, with life, limb and liberty at hazard. It's possible to provide options for these cases, and I think there are enough geeks who "support the cause" to provide the necessary technical backup (mainly, in the form of painstaking security design review)."

All sounds good. Particularly, pushing solutions that are open to hard review and require less trust. It's why I like high assurance or subversion resistant methodologies for critical stuff. Most dev's and reviewers don't understand them, though, and such processes are as exciting (sarcasm) as SOX audits. Hopefully the fact that they're seeing subversion everywhere might inspire them to bite the bullet and build working solutions despite them not being the coolest, prettiest, fastest, etc.

And if you get a verifiable TRNG, certainly publish it. We could always use more of them, esp verifiable ones. I'm sure i'll get tired of rolling dice and shuffling cards eventually. ;)

MarkH • September 20, 2013 1:38 PM

@Paul:

US intelligence agencies, chartered to operate against foreign adversaries for purposes of national security, have already provided so much data to DEA -- for use in prosecuting domestic cases -- that DEA has a special protocol for its attorneys to create fictitious "cover stories." These prosecutorial lies are intended to explain where all that info came from, while shielding its secret, likely unlawful, and certainly unconstitutional sources. See http://www.reuters.com/article/2013/08/05/us-dea-sod-idUSBRE97409R20130805

We are still very far from the condition of East Germany.

We are moving in the East German direction, not only in terms of universal domestic surveillance, but also the post-2001 government assertion of authority to deny due process to US citizens by:

• Detention in Guantanamo, see http://en.wikipedia.org/wiki/American_detainees_at_Guantanamo_Bay

• Imprisonment for years without charges in violation of habeas corpus, see http://en.wikipedia.org/wiki/Jos%C3%A9_Padilla_(prisoner)#Habeas_corpus

• Murder, see http://www.cbsnews.com/8301-202_162-57585798/who-were-the-4-u.s-citizens-killed-in-drone-strikes/

Men with guns CAN break down the door of your house in consequence of NSA spying on YOU. And if you pick up that .308 in self defense because you hear a break-in during the dark of night, they may kill you. See http://abcnews.go.com/US/tucson-swat-team-defends-shooting-iraq-marine-veteran/story?id=13640112 -- or the writings of Radley Balko.

I agree with you, that it's foolish and unhelpful to say "it's East Germany!" At the same time, it is dangerous to say "it's no big deal." The assault on privacy and liberty is not academic -- this is real.

Curious • September 20, 2013 3:03 PM

It should be obvious that Paul here isn't really referring to anyone actually owning firearms. :| Except perhaps referring to himself. :)

name.withheld.for.obvious.reasons • September 20, 2013 4:02 PM

For the "Bruce Schneier Bloggers"...

First, let me state that I do not see myself as a Bruce Schneier's Bloggers (BSB'ers)--yet. But, I have participated in blogging on several topics--for the last 12 months--and I see an obstacle and an opportunity.

1.) We, at least those that have a moderate level of computational, cryptographic, mathematical, and/or engineering background would be well served to organize. NOTE:This can be impractical as most persons on this blog are highly independent, organizing as a group is predicted to be improbable.

2.) The ad-hock nature of the blog does not lend itself, for several reasons, readily to address the issues expressed by the SB'ers in an effective and timely manner.

3.) As there is a significant amount of anonymity within the community, it is unlikely that this forum is appropriate for even discussing this issue.

4.) If a "known" coordinator could be identified, and persons that have an interest in the issues brought to the attention of the community, can produce a "blind" cooperative to start developing some of the ideas and concepts that have been expressed here.

5.) This is only a series of suggestions, it is not difficult to make suggestions given the current circumstances.

If anyone has an idea that could allow for a plausible answer to the day's problems besides more tinfoil--that'd be great.

Wael • September 20, 2013 4:44 PM

@ Bruce,

This technique could, for example, reduce the amount of entropy in Intel's hardware random number generator from 128 bits to 32 bits. This could be done without triggering any of the built-in self-tests, without disabling any of the built-in self-tests, and without failing any randomness tests.

I see this as a strange claim.
1- Why wouldn't it fail randomness tests if the entropy was reduced from 128 to 32 bits? Can't statistical tests show the reduction of entropy effect?
2- If the above is true, then reduction of entropy has no effect on the RND from a security standpoint ;)

Figureitout • September 20, 2013 7:34 PM

I don't think we're well served by bickering with each other or getting into e(ngineering) dick measuring contests.
gonzo
--Wait til you talk about antennas..."mine's bigger, no mine is.."

name.withheld.for.obvious.reasons
--It's a great idea, but I'm busy w/ school and most others probably w/ work. And we're scattered all over the place. However, I do think we all can start by building tiny trusted devices for various purposes, and giving/selling to our circles. If someone has access to a nice lab, can we work out some inspections. The math assistance center at my school is a perfect environment (walls are painted w/ dry-erase paint) to cover the walls in math; someone could mod a room in their house. It's actually a lot of fun to write on the walls again lol.

We need to break this awkwardness of security and try yet again this extremely challenging problem of trust (maybe that's why it's so attractive b/c it's hard).

I'd love to see some kinetic action and try some secure builds and not just bits zipping around the net. My observations are there's generally a couple people who are the "glue" to a group and get things done.

Figureitout • September 20, 2013 7:40 PM

name.withheld.for.obvious.reasons
--And I need to stop my outbursts, sorry all. Never again.

MarkH • September 20, 2013 7:54 PM

@Wael:

This question probably confuses more people than anything else related to cryptography. Though I lack a secondary school diploma, but I'll do my best to explain.

"Entropy" as used here means unpredictability, and is very closely related to "randomness". These are notions we understand intuitively, but are not simple to define formally.

One big contributor to the confusion is the term "randomness test." No test performed on a finite sample of data can prove randomness, but it can disprove randomness, so it would be more accurate to call these tests "non-randomness oracles."

Any useful function of a random variable (that is, of an input that is at least partly unpredictable) has a distribution (that is, likelihoods of various outputs) that can be calculated. Though (by definition) we can't predict any particular output of such a function, we know how often certain outputs should be found in relation to other outputs, when averaged over a quite large sample (that is, a sequence of successive outputs of the function). These are statistical properties of the function.

The misleadingly named "randomness tests" measure statistical properties, and compare those properties to the properties expected of a function of a true random variable.

The problem is, a partially predictable -- or even completely predictable -- sequence can perfectly match the statistical properties of a random sequence.

The LFSR is a simple logical construction capable of producing long sequences of "random-looking" bits.

For example, a 64-bit LFSR can be constructed to generate seemingly random bits at a rate of 1 gigabit per second for more than 500 years before it repeats itself (it actually creates the same astronomically long sequence over and over again). If you collected a day, a month, a year or even a century of output from this generator, that output would pass any randomness test. However, if you collect any 128 output bits in a row, you can by analysis predict any future output (for example, whether the 9,477,213,482nd bit following the captured 128 bits will be a 1 or a 0) -- and similarly, "predict" all previous outputs as well. The entropy is practically zero.
____________________________________________

For the record, there are many ways to generate "random looking" bits. There's a whole science of this, they're call pseudo-random bit generators (PRBGs, or PRNGs for those who say 'number' instead of 'bit'). The LFSR is by far the easiest to "crack" in the sense of predicting outputs from a sample of output. But even the hardest to crack is fully predictable to anyone knowing the internal state of the generator.

IF somebody who wants to violate your confidentiality has tampered with your PRBG, he can preserve its statistical properties (so it passes all the randomness tests), while retaining his ability to predict outputs. And it's not necessary to have perfect prediction: even if the generator is partly random, by reducing the entropy the attacker can cut the number of trials necessary to guess his way past your encryption, sufficiently that it's practical for him to do so.

Wael • September 20, 2013 8:33 PM

@ MarkH,

Thank you for the explanation. I think there are several things to talk about here. I'll need to think how to put it. I understand what you are saying and I think we maybe talking about two different and related things (not sure yet). I was Hoping to have a break this weekend, but.. This is also fun, and may be a long discussion...

I'm not going to fall in the trap of "secondary degree thing" you maybe a stochastic processes and statistics professor somewhere pulling my leg and trying to make me to look uneducated ;)

Clive Robinson • September 21, 2013 12:13 AM

@ Wael,

One way of looking at information entropy is it defines "the number of possabilities", anything that is predictable reduces the possabilities.

My son intuativly understands this from playing with lego bricks. If you have a pile of lego bricks it is not a model. As you start to build a model you start reducing the outcome of what it is going to be to an observer. Each brick added fixes it's relationship to the model and in the process has gone from it's maximum entropy as a free brick to a much reduced entropy as a brick connected to one or more others. As more bricks get added and the model gets closer to compleation the entropy of not just the model but each brick inside it falls. To the observer the unknown model reduces in possabilities untill the information about what it is, is in part then whole is conveyed to the observer. At some point sufficient information is conveyed such that the observer can start to predict where other bricks will be placed and thus be able to compleate the model in their mind. If you think about it the number of ways the model can be built is maximum whilst all the bricks are disconected and at a minimum when all connected but... there are many ways to build the model one is you build the model by adding free bricks to the model individualy. Another is to build recognisable parts and then put the parts together. Another is to go through just putting two bricks together over and over, then putting two block parts together to make four brick parts, then eight etc etc, this conveys information about the final model more slowly. Finaly you could just randomly put parts together to make odd sized sub parts that are to the observer just random clumps of bricks untill the form of the model finally appears.

But consider the last method, sometimes those odd clumps will look like part made sub parts to the observer but are they? What if the maker has no model in mind and is aimlessly puting parts together at what point can you tell purposful from aimless brick assembly?

Further consider the difference between an observer who can see the brick pile and one who can not. As you see the first recognisable part being constructed you might correctly or inccorectly decide that is the model or a sub part of the model. You only know when the maker stops. But likewise consider if they make two identicle sub parts in succession does knowing the size of the brick pile convey any information? Is the maker just going to carry on making identicle parts or stop after say the fifth or start making different parts. You don't know from just observation but by being able to examine the brick pile you may be able to make more valid deductions than by just observing the model makers output.

Hopefully thats given you a bit more feel for the idea of information entropy, and what you can and can not do as the observer of the output of an unknown process.

Gweihir • September 21, 2013 2:57 AM

@Clive Robinson: Sorry, there is nothing to discuss. You have nothing to contribute on the electronics side. That is not to mean you generally do not understand electronics, I have no opinion about that. But I am convinced you do not understand this thing we are talking about here.

Just some comments:

1. HCU is so rarely used that I just did not think of it. It is quite exotic as it is a digital circuit basically unsuitable for digital use. Your nebulous references to "datasheets" is fascinating though, and I deduce you have no clue what HCU is or why it does not have the problem the ALS gates have as that can be described with a single sentence: No buffer stages on HCU. Now the implications of that are a bit more complicated to understand.

2. mu-Metal is for shielding against magnetic (B) fields that are static or changing with low frequency (less than 1kHz). What we are talking about here is shielding against Electro-Magnetic radiation, and that is a completely different beast. Requires some high-school level of physics to know that though. Seems though that you have read up on what mu-Metal actually is by now, although the implications seem to not quite have sunk in yet.

3. The avalanche construction is using a diode in reverse breakdown. While a Z-Diode is optimized for that (and for low noise in addition, which makes it mostly unsuitable for this application), a NPN E-B diode is not. Still, it is a normal semi-conductor, the voltages are low and no thermal problems are to be expected. You seem to have some kind of irrational fear of using a device for something not in its data-sheet. There really is not need for that as long as the principle of operation is understood. It is also not a risk here, as of course failure will be detected in any sane design.

Side note: I think I understand that alleged statement by the alleged Motorola representative a lot better than you: What he said rather strongly indicates this was for a completely different scenario, likely using a transistor with E and C swapped. It still works to some degree if the voltages are low enough, but it can indeed result in a quick wreck and the properties of the transistor are really, really bad used this way.

Gweihir • September 21, 2013 3:09 AM

@Wael: The thing is that these randomness tests are statistical and you have (in the sense of Colmogorov complexity) not only those 32 bits in the output, but also a minimal description of AES, its mode and the key used, and that will be a few 1000 bits. That sabotages the tests. An attacker that knows the key and AES can remove the AES and key and ends up with just the 32 bit which can then be brute-forced.

Now, why not make statistical tests that removes the AES? Quite simple: The problem is the AES key. While AES could be removed from the Colmogorov complexity of the output, the AES key can only be removed when it is known. And as long as it is unknown, you have still 128+32 bit of entropy in there, and no statistical test can go that far, it requires too much data. You would have one expected collision in 2^80 full length samples by the "birthday paradox", i.e. need something like 16Byte * 2^80 output samples for the statistical test to have a real chance of finding something. That is about 10'000'000'000 metric tons of 4TB disks in storage ;-)

(Lots of detail omitted and lots of fuzziness, but the idea is sound.)

Johannes • September 21, 2013 3:26 AM

@Dirk Praet - September 17, 2013 6:31 AM
@ a lawyer in ToonTown

TAILS Linux updates the Microcode with each boot.

"Could you elaborate on that and tell us where you got that from ?"

https://tails.boum.org/contribute/design/

"3.9 Hardware support

Tails generally ships the latest kernel from Debian unstable or Debian Backports as a compromise between stability and recent hardware support. Recent Intel and AMD microcode are included as well.

The x86 hardware architecture is the main supported one."

Wael • September 21, 2013 5:16 AM

@ Clive Robonson, Gweihir

The randomness test only tests the RND generator and is independent of consumers of its functionality, like AES. So AES details are not a factor influencing our characterization of the RNG. This is supposed to be a surgical test of one component of the chip. My brain is not working very well this early in the morning (3:12 AM) but I'll think about it more and continue...

Nick P • September 21, 2013 6:51 AM

Johannes is right. Here's a Debian page on the microcode update. TAILS uses Debian Live.

http://packages.debian.org/wheezy/intel-microcode

So, yes, even TAILS could be subverted if the microcode updates include subversion. I've always been a fan of using non-x86 hardware to throw off sophisticated, fire-and-forget attacks. Just got some more motivation along a different angle. ;)

Nick P • September 21, 2013 7:08 AM

@ Wael

Way I think of it is that a cipher (e.g. AES) is designed to turn an input into something that looks random. The key and the plaintext could both be all zeros, a very non random thing, but after AES is done with them they'll look just as random as something run through with a 128-bit key. It's the nature of ciphers: they scramble and randomize data to hide patterns in it.

Most (or all?) statistical tests test a given set of data to see if it looks random. Raw sources of entropy whose data looks random consistently in these tests might actually be random. The problem is that ciphers make everything look random so anything you pass through will automatically pass a statistical test for randomness. So, one must test the original source for its randomness properties before it passes through a cipher.

The Risk: If enemy can predict your input numbers (bad TRNG/low entropy) & knows how the CRNG is constructed, then the post-processing steps like AES will provide you no benefit. The real security is in unpredictableness of the numbers fed into AES, a whitener, or whatever. The more predictable the raw source is, the more risk of attack on it.

And NSA can probably brute force certain CRNG constructions if the seeds are weak.

Wael • September 21, 2013 9:01 AM

@ Nick P,

Why is everyone talking about AES and ciphers. I know what these compression algorithms do (lol). Just look at the simplest part of the question. If you have a source of randomness, can a test quantify its entropy? Please don't talk about ciphers (or Legos :)) now. We'll tackle the other parts later.

Wael • September 21, 2013 9:10 AM

@ Nick P, again...

The key and the plaintext could both be all zeros, a very non random thing

Says who? They may very well be random, although highly unlikely

name.withheld.for.obvious.reasons • September 21, 2013 10:33 AM

The microcode updates that source a blob, converting the hex to bin yields a small stub--but it is the comments in microcode.c (Intel CPU Firmware Update Driver) has some interesting source modification notes--including removing the BIOS image from the kernel and eliminating the IOC read() of the in-proc blob.

MarkH • September 21, 2013 11:05 AM

@Wael:

pseudo-random ≠ random

AES was mentioned in a couple of posts above, because a block cipher (like AES) is one of many ways to construct a PRBG (pseudo-random bit generator). The output of a decent PRBG looks random, and has all of the statistical properties of a true RNG: it will pass any "randomness test."

The key concept isn't AES, but the difference between pseudo-randomness and randomness. So, two ways to think about the difference:

Determinism

Imagine that we can monitor perfectly (missing nothing) a fixed population of atoms of some unstable isotope. From any chosen starting instant, there will be some finite time interval before the next atom spontaneously decays. That time interval has well-defined statistical properties: we can say calculate a time by which the probability of next decay is 0.1, 0.5 or 0.9 with precision. But no person -- anywhere, using any conceivable technique, even with the most complete knowledge of those atoms that is physically possible to learn -- can dependably predict when the next decay will occur.

That time interval is non-deterministic, even though its statistical properties of a large sample of such intervals is well known.

By contrast, the output of a typical PRBG is fully deterministic1. A person knowing the construction and seed of the PRBG can predict all future outputs with 100% accuracy.

1 A PRBG can be made partly deterministic by progressively "mixing in" random bits, but that doesn't affect the distinction between deterministic and non-deterministic.

Minimal Encoding

A way to think of "entropy" that is pretty close to its rigorous definition in information theory, is that it answers the question, "what is the most compact possible encoding of the data set?"

For example, consider the 64-bit LFSR example I cited last night. One way to encode its output is to note that it is strictly periodic, playing the same 2^64 output bits over and over. So we could "write down" all 2^64 bits, along with some bits2 to express "repeat these ad infinitum." This would fully encode the bit sequence, consuming 2^64 bits. If there were no smaller encoding, we could say "this generator has 2^64 bits of entropy".

However, we can make a much more compact encoding by noting the LFSR algorithm, plus the 64-bit feedback pattern, plus the 64 bits of current state (or "seed"). Suddenly, the encoding has shrunk from from the order of 10^38 to 10^2. Presumably, this is the most compact encoding possible, so we can say that our LFSR has roughly 100 bits of entropy.

By contrast, consider a sequence of 2^64 bits generated by "tosses of a fair coin," or by suitable processing of measured time intervals between spontaneous radioactive decays. There is no predictability to those bits: there is no underlying pattern. No compression algorithm could shrink such data even by a few percent. The most compact possible encoding of this sequence would be about 2^64 bits in size: its entropy is 2^64.

If someone (let's call him Oscar) makes a PRBG using AES 128 in CTR mode, the bits needed to encode the algorithm, plus 128 bits of key and 128 bits of seed fully encode the resulting bit sequence. That generator can easily make 2^64 bits of "random-looking" output, but the entropy is only 256 bits.

Hope this helps!

2 There are different ways of encoding the PRBG algorithms: for example, as source code! How this is done would affect the encoded size, but it boils down to a (somewhat) constant offset. Compared to the entropy needed for crypto purposes, algorithm encoding is so tiny that it can be neglected for comparison purposes.

MarkH • September 21, 2013 12:11 PM

@Wael:

Probably ;)

"If you have a source of randomness, can a test quantify its entropy?"

A function of any finite sample of the source's outputs can estimate an upper bound for its entropy, but cannot give the lower bound.

In other words, if the sequence is an endless repetition of "010101", a function -- PKZIP, for example :) -- can demonstrate the tiny quantity of entropy. But I believe that it is impossible to devise an effective procedure able to reliably detect the very low entropy in the outputs of PRBGs.

name.withheld.for.obvious.reasons • September 21, 2013 3:40 PM

@figureitout

Yes, life is rarely convenient but neither is the subversion of network computing technologies AND our data (meta or otherwise). I appreciate your enthusiasm and your situation. In my opinion is we "have" to make the time. Industry and academic professionals, the print and digital press, and LEA's and are representatives are all but silent on this issues surrounding a rogue government and government agency. In a way you can say it falls to (the figurative) us. I can see that this is the direction Bruce is headed. It would be useful if as a group (the BSB'ers) engage the various communities. Academia (Cambrigde--the brit ond, CMU, Berkeley, MIT, Stanford, etc.), businesses (small and medium size companies that are outside the soon to be drawn circle. organizations (FAS, CDT, EFF, EPIC, IEEE, Union of Concerned Scientists, and other civic minded) and other stand groups or individual. The idea is to develop "buzz" about this kinda thing.

Oh, and I have a small clean room. Started last year when I realized that the landscape was changing rapidly. But I originally began the operation planning to do a small light manufacturing and hiring four dozen "collaborators", but this situation has upset the apple cart. Spent six months restructuring the company. Required me to rethink the whole managent and operations theory to form an efficient and scalable framework that is antithetical to the way the development is compartmentalized and served by small enclaves (similar to the way LEA's do business but without the requirement of classification systems used by the likes of the NSA or their contractors. This cultural of secrecy is beyond the breach, I suggest a way to achieve a more respectful society is to make honesty a cornerstone--not something that is to be feared. I've worked in some environments and classified systems are inherently flawed as classification creates a "shielded" bias. A satellite system, Air Force/Navy, that recently need redeployment (original had a short service life) was to be replaced, I was asked to review/critique the new system. My honest appraisal was not well recieved by the program manager and thus the classification saved the system. It also affects contracts and government services that are wrapped in the "national security blanket".

RobertT • September 21, 2013 5:15 PM

@gweihir
" It is really not a concern here. First, you have a very low source impedance and a pretty strong signal. Second, and I guess....."

U da man
/sarc

Evdokim Ulyanov • September 21, 2013 5:32 PM

@Nick P:

"So, yes, even TAILS could be subverted if the microcode updates include subversion."

I wonder why they feel they need to load it at all - and I thought this was a FOSS project - the microcode is proprietary, correct?

"I've always been a fan of using non-x86 hardware to throw off sophisticated, fire-and-forget attacks."

Where may I purchase it?

Gweihir • September 21, 2013 5:54 PM

@Wael: The "AES" is the AES in the whitener in RdRand, and it is not consumer-side at all, it sits between the hardware generator and the RdRand instruction and you cannot get at the hardware generator past it. If you could get at the hardware generator directly, it would be (relatively) easy to find sabotage or to bypass it.

For example, if you have a structurally simple hardware noise generator (e.g. avalanche construction, whether Zener or 2-transistor or something else does not matter), a statistical test can tell you how much true randomness is in the observed output signal, if all error sources are also simple (mains noise for example). One thing where that fails is if somebody beams, e.g., strong RF modulated with a noise-like but predictable signal at it. If that is a concern, better put some thick copper shielding in there and make sure said RF does not get in via supply or signal lines. Supply lines you just filter. Signal lines are a bit more tricky and depend on the specifics of your circuit, but low impedance, high signal levels and short wires are king, as the RF power needed to "get into the circuit" will approach something that makes the shielding glow pretty fast and become impractical or obvious.

Nick P • September 21, 2013 7:20 PM

@ Evdokim Ulyanov

"I wonder why they feel they need to load it at all - and I thought this was a FOSS project - the microcode is proprietary, correct?"

They can include whatever they want. Binaries for proprietary hardware are common in Linux use these days. As for microcode, those updates are often to fix problems ("errata"). So I could see them wanting a working processor before their security tech loads.

"Where may I purchase it?"

Replacing Intel or x86 chips for subversion resistance. Options.

Instruction Sets

Alternative ISA's include POWER/PPC, SPARC, Alpha, PA-RISC, ARM (naturally), and MIPS. Many old workstation computers were quite functional and used these. So, for these, I suggest Googling (to review pro's/cons) and buying old machines from eBay. Especially look for hardware supported by OpenBSD, NetBSD, or Linux so you have up-to-date, patched software rather than proprietary UNIX. Or, if you dare, you can virtualize or security-enhance the UNIX/OS they're built on to keep its applications/toolset.

Prebuilt, very usable

Hardware vendors to eBay include VIA x86's, Apple PPC Mac's, Genesi Efika, or Freescale for PPC; IBM servers for POWER; Sun SPARC servers or Sunblade SPARC workstations; Compaq Alpha servers/workstations; HP PA-RISC servers/workstations; SGI's Octane/Origin MIPS; homebrew PS2 (MIPS) or PS3 (Cell). These are all built to run desktop, workstation or server loads. Also, Loongson is China's chip and they have both BSD- and Linux-based stacks built on it. Top contender for anti-NSA chip.

Note: Super old, slow and obsolete ones like VAX, Pyramid, Motorola's, and so on if you want that.

Embedded, simple and/or special-purpose

The systems above are old and/or complex. Past few years, I advised people wanting modern non-Intel (and non-server) stuff to look at embedded companies. Freescale, Curtis-Wright, AMCC, etc come to mind. There's *plenty* of embedded boards for ARM, MIPS, PPC, and even x86. They're usually pretty simple compared to a desktop or server board. You can get as much or as little functionality as you want. And there's more foreign suppliers available. Just get an embedded board with a high end processor, plenty of RAM and ability to integrate with peripherals. You can build a simplified desktop out of that, esp if it runs Linux. (Many do.)

Note: that was all 32- and 64-bit stuff. I've known of people willing to do stuff on 8-bit and 16-bit machines. You can actually do quite a bit on those machines. You're just going to take a [huge] hit in avail software, usability, and performance. Maybe security too without memory protection.

Processor cores on FPGA's

This route is rougher but you might find online guides. Who knows. The concept is you get a core and you put it on an FPGA. Might have to add other stuff to make it work. The core might be x86 compatible, one of other ISA's I mentioned, or an open ISA such as OpenRISC. Or even the rigorously analysed VAMP verified processor. You can build your system ground up. If it proves out and there's demand, maybe you can turn it into a dedicated ASIC and have a foreign fab build it. Who knows.

High level processors

We've discussed this recently on this blog. I've brought it up in previous discussions about language-based security. If language was securable and runtime safety was hardware supported/accelerated, then building a complicated system w/out common issues like code injection might be easier, right? And a high level language or architecture could help detect subversions if it promoted layering, information hiding, etc. So, the idea here is to outright buy or put on an FPGA a core supporting a higher level language. Examples I've seen are LISP machine's (LISP processors), Forth machines, JOP-style Java processors (think server type is called Vega), HISC instruction set, and crash-safe.org's recent tagged design. If not build a desktop, you might use one of these for purpose-built devices or a trusted front end to many less truthworthy devices.

Just remember

Remember that you must define your threat model for this stuff. I don't like x86 because *everyone* attacks them. I prefer an obscurity benefit on top of a hardened system. However, people worried about black hats and foreign TLA's would do well to use a recent Intel processor b/c they have lower errata than previous chips and features that benefit security (e.g. IOMMU). I'd say the same about certain embedded PPC and ARM systems made by Freescale. Problem with these? NSA might have backdoored them. If you're worried about NSA, you're going for foreign made equipment from China (Loongson) or something. But then you won't have the local features and experience. And *they* might have backdoored it.

So, as you can see, worrying about nation state subversion of hardware you depend on is like working through a maze. My solution has been to separate such concerns on *different physical hardware*. If NSA is the threat, do it on a machine dedicated to that stuff. If it's China and malware, do it on a machine safe against that. Unless you're specifically at risk to NSA (few are), the other threats should be top priority. You can always get a dedicated embedded system for your battle with US TLA's. And I'd recommend you don't operate it in America on the public internet. Air gaps with simple, non-executable transfer mechnisms are your friend. ;)

EDIT TO ADD

Edit to add more foreign and embedded chips to look into: Fujitsu FR-V; RISE MP-6 (x86 compatible); Transmeta Crusoe (x86 compatible); NEC RISC chips such as VR and a 2005 one supporting auto-parallelism; Toshiba TX MIPS-based processors; higher end SuperH (one was in Dreamcast).

MarkH • September 21, 2013 8:13 PM

As a supplement to Nick's valuable information on non-Intel processors:

In my opinion, the boot firmware in all "PC-compatible" x86 systems (BIOS or EFI/UEFI) is a worrisome security hazard. This x86 boot firmware is (with very rare exceptions):

• complex
• bloated
• proprietary
• closed source

Efforts toward open-source BIOS have been hampered in part by the prevalence of proprietary hardware on PC-compatible mainboards.

Such boot firmware is an excellent locus for attack vectors, and (coming almost always from a very small number of vendors) readily subject to subversion by powerful agencies.

It's a relief to transition to computing platforms without that particular nastiness.

Clive Robinson • September 21, 2013 9:28 PM

Also of interest to add to Nick P's list,

Have a look at the high end Microchip PIC chips you can do a surprising amount with the (the real prob with PIC24 and down is no software interupt or MMU but with a little thought it's not much of an issue). Oh and they are almost dirt cheap in very small quantities (some are sub $2) and loaded down with usefull I/O components.

With regards Forth many many moons ago it's inventor Charles Moore striped it down to 27 basic instructions and then got it running on a TMS DSP chip in 4K of ROM. There are considerably more powerfull DSP chips knocking around these days for just a dollar or two. It's unlikely. That DSP chips have been backdoored in anyway becausse in many ways they are Sub-RISC and theres not realy anywhere to hide one, even time based side channels would tend to show up due to DSP normal usage would be compromised and thus discovered very quickly.

Clive Robinson • September 21, 2013 10:23 PM

@ RobertT,

You mentioned using ring oscillators for TRNG's as well as Sigma Delta loops. Of the two I prefer the "look" of RO's using metastability as the randomnes source.

I've been looking around for "non analog" ways to exploit the inherant metastability. However finding non-pay wall documentation is proving a little hard. The best I've found so far is,

http://www.iacr.org/archive/ches2008/51540162/51540162.pdf

And this gives an interesting model of behaviour,

http://eprint.iacr.org/2011/637.pdf

Do you have any others that are worth looking at?

Clive Robinson • September 21, 2013 10:32 PM

@ Evdokim Ulyanov,

    What else can I say but thank you

Well in the fullness of time you could come back and tell us which method you selected and why. That way it will encorage others and we will all be that bit more secure because of it :-)

RobertT • September 21, 2013 11:38 PM

@Clive R
Sorry but I'm not really up to date on the TRNG literature, I had a list of all of these RNG circuits about a year ago. but that was life time and several countries back.

Personally I'd never even try to do this sort of thing with "digital" cells because their output is not very random, its typically just unbelievably complex, which is not quite the same thing as random.


As for other approaches 4th order Sigma Delta loops are very good sources for Chaotic outputs. I'm still not certain if I should consider Chaotic to be "random" or simple indeterminable. But this is not a circuit that can be created without the help of an Analog IC design team.

Personally I'd always use a Fully Differential SD design style with as perfect symmetry as was possible for the actual layout. The problem with Single ended is usually at the sampler stage where Power Supply noise can feed through with very little rejection. In the fully differential design the cross-over of the Output_sigN and Output_SigP is what generates a changing bit. Since both signals see the same power Supply and common mode noise you get about 30dB to 40dB better rejection of injected disturbance signals.

Many papers use lower order SD loops but I'd be VERY careful about using these as part of a TRNG design. the problem is that the parts are designed mainly for Audio applications and Hearing is very sensitive to "tones" so practically all commercial SD's add Dither. Dither is Noise added to the loop to dominate and scramble any tonality of the loop. Unfortunately the Dither is generated by a long sequence LFSR (good luck finding out the details) This is practically the same circuit that was used for early DSSS comms systems, SO guess what the Dither adds "Processing Gain" to the TRNG output, which is not exactly something that you ever want in a TRNG.

Higher order SD (3rd and 4th order) loops are inherently unstable (similar to Lorenz chaotic circuits) so dither is unnecessary Interestingly the Loop characteristic itself shapes the noise and this loop characteristic is often discernible in the SD output but I'm not convinced that this knowledge is of any use at all.

MarkH • September 22, 2013 2:09 AM

Re oscillator jitter as an entropy source:

I'm getting way out of my depth here, but to my limited understanding, ring oscillators are used not because they have any particular virtues to recommend them -- but because they are the most practical to synthesize from the MOSFET building blocks of modern CPUs.

I remember (almost exactly 20 years ago ... wow the years go by quick) working at a semiconductor shop, where a young engineer was tasked to design the PLL oscillator for the programmable-frequency clock on a CPU (as I recall, that was a fairly novel feature back then). He gave me a quick explanation of his voltage-controlled ring oscillator, and how it's a rather poor-quality oscillator ... but good enough for a PLL.

The company had their own fab on-site, enabling them to test design changes quickly.

@Евдоким: не за что

Gweihir • September 22, 2013 2:52 AM

@RobertT: Just be careful in your entropy estimation and dither noise is not an issue. You need to make sure your statistical tests are prepared to subtract it though, or you may end up with an undetected non-working generator. Unless you signal is very weak with regard to maximum input range, you should be fine. And for cross-verification, you can always put in a sine-wave instead of your noise source and look at what the spectrum does.

Incidentally, even long-sequence LFSRs are not that hard to break. If the dither is strong enough to be cleanly recognizable, reconstructing the LFSR is easy. Hmm. Would they put the noise just into the lowest-order bit only? Anyways, the data-sheet should allow establishing an upper bound, as it _is_ noise after all (just not the type we want).

@MarkH: I would not trust oscillator jitter as randomness source, unless the oscillator set was specifically designed and evaluated for this use (like in the Via C3). Its primary advantage is that it is mostly all digital. But my intuition is that separating chaotic behavior (complex, but deterministic) and random behavior (non-deterministic) is really tricky and can easily go wrong, leaving you with much less entropy in the output than you thought.

Mike the goat • September 22, 2013 3:26 AM

It is funny how many people suggest that diehard/etc. test can somehow detect a subverted RNG. If the intel RNG was just taking, say the current time and pumping it through a block cipher we would really be done the wiser (provided it is whitened adequately, of course).

You could prove this yourself by making a for loop that shoots the output of date +%s into, say openssl in AES-128-CBC mode, then pump the output into ent or diehard.

You can imagine with a little more creativity you could make the output even more pseudorandom.

Gweihir • September 22, 2013 5:58 AM

@Mike the goat: It can if you have access to the raw bits generated by the "analog" generator. But you have a point: A generator as you describe, pretending to be a raw ("analog") bit generator would be hard/impossible to detect if done right. You would need to have things like a bias that has some thermal drift, maybe some non-random components, etc. for a convincing fake. It would be dead-obvious on the chip though.

Clive Robinson • September 22, 2013 6:56 AM

@ Mike the goat,

    It is funny how many people suggest that diehard/etc. test can somehow detect a subverted RNG.

Yes, but I've been waiting for someone to notice two things and put them together,

1, NIST point people via theirs standards at these and similar tests.

2, NIST takes it's technical advice in this area from the NSA, and it's rumourd the NSA have "baked in" weakness in an EC RNG...

And put them together as something along the lines of "The easiest way to hide the RNG weakness is to fix the tests" or something similar.

Thankfull so far nobody has, as trying to disprove that would be niegh on impossible with the fact that there can be,

    No one RNG to rule them all, No one RNG test to find them, No one RNG test to bind them all, Into the darkess to hide them".

[With appologies to J.R.R.Tolkien]

Clive Robinson • September 22, 2013 8:49 AM

@ MarkH,

    I'm getting way out of my depth here, but to my limited understanding, ring oscillators are used not because they have any particular virtues to recommend them -- but because they are the most practical to synthesize from the MOSFET building blocks of modern CPUs

Yes, in my "dead tree cave" I've a number of books and technical papers on using CMOS inverters as both amplifiers and oscillators, the oldest (and here I might be leaking a "bit" on my age ;-) is a Motrola "McMOS Handbook" from Oct 1973 which claims on it's title pace to be a "First Edition". Chaptor 8 (Anolog) and 12 (timepiece) give quite a bit of info sadly though of metastability and jitter there is a paucity of information other than the equivalant of 4uV broad band noise at each gate input...

Likewise nearly all other information I've got in the cave is about reducing both metastability and jitter, not enhancing it for entropy extraction. So much so I feal like a 17th century navigator whose charts all have "here be dragons" on them.

A little over a decade and a half ago I designed a quick and dirty noise generator based on using a Schmitt nand gate as a chaotic VCO by adjusting the input bias point from a Zener noise source amplified by other gates. This was put on the Clk input of D type with the Data input being driven by an14pin DIP TTL compatable Xtal Osc. The output of this "roulet wheel" generator going into a hand full of logic on an ISA bus card. It was fine for Monte Carlo simulations but it was by no means crypto grade. This was because it was faiirly clear the Zener noise source was only responsible for around 80% of the noise voltage driving the Schmitt nand gate input and that from the "analog amp" gates was both temprature and powersupply noise sensitive.

Oh one thing of note you can use a 74LS Schmitt gate as a 30MHz. Oscillator with an AT cut crystal, if you take the output of a miniture electret mic it makes a fun little FM transmitter / Bug you can tune into with an ordinary FM radio.

Clive Robinson • September 22, 2013 9:14 AM

@ RobertT,

    Sorry but I'm not really up to date on the TRNG literature, I had a list of all of these RNG circuits about a year ago. but had a list of all of these RNG circuits about a year ago. but that was life time and several countries back.

Ouch...

    Personally I'd never even try to do this sort of thing with"digital" cells because their output is not very random, its typically just unbelievably complex, which is not quite the same thing as random.

Which is kind of the conclusion I'd come to a decade or so ago. It's just that in the past decade papers keep turning up claiming fantastic figures for output rate etc and I wanted to see "what all the noise is about". In all the papers I've seen the authors appear to take it as read that the AGWN from metastability / jitter is "random" not "chaotic" or "determanistic" caused by other effects such as on chip activity noise.

It just buggs my "curiosity gland" in a similar way that PUFs did with you some time back.

Figureitout • September 22, 2013 10:01 AM

name.withheld.for.obvious.reasons
--Likewise, organizing a secure build w/o the ways of middlemanagement in Dilbert or a locked-down military environment will be tricky.

Nick P • September 22, 2013 10:48 AM

@ name.withheld and figureitout

The fab security issue. Options.

Fabs for semiconductor chips are ridiculously complicated and expensive. I've tried to work out how to have several countries running a fab for the low nm processes only because they're already so expensive to build that my mere tens of millions (!) in security might be justifiable.

So, what does a person without $1+ billion do who worries about chip subversion and stubbornly continues to use electronics? ;)

1. Stick to old models of stuff I posted above and wall them off.

2. Use simple or open models of chip built at foreign fabs in countries that spy on US.

3. Partner with a fab operator to cover the security expense of operating a run with extra security.

4. Partner with a fab operator to maintain continual security.

5. Buy an existing fab off the list. The best one you can afford.

6. Pay a fab company to build you a working fab.

1 will be easiest. Problem is old stuff is in finite supply and old problems might not be easy to fix. 2 lends itself to people using simpler, text-based computers that run on the cheapest and most easily source foreign computers. Time to break out the DOS and CP/M apps.

3 is about stopping the subversion of a given project. The idea is that, between your design and them manufacturing it, there are steps they can take to subvert it. The activities of 3 are focused on those. 4 is worried about the whole fab being subverted long-term to work against you. Efforts here will need to focus on physical, personnel, manufacturing, and communications security. 3 was expensive. 4 is getting into ridiculously expensive category.

5 might be more practical. In 5, you work against the economic motives by arranging to buy a fab. You might give them time to build their next one. Buy it in a country that doesn't worry you too much. The advantage here is that it's established with efficient operation and staff who understand the issues. Security can be incrementally implemented into the workflow.

6 is the ideal setup. With 6, one can bake security into every aspect of fab operation by using a risk assessment methodology (and a bit of security mindset). There's going to no doubt be plenty of methods or setups in fabs that would've been much easier to secure if done differently. A design starting from scratch can make different choices.

If 5 or 6 are chosen, one can always make most of the chips for commercial and military market. The *fab* might exist to produce the few chips you need to trust, but most of the *chips* can be for others and pay back the cost a bit. A bit of the market might be willing to pay a premium for chips with low subversion risk.

If 3, 4, 5, or 6 are chosen, one of the best projects might be to create building block chips. Lets say we have a limited investment allowing only a few runs. Single-purpose, throw-away hardware doesn't cut it here. It would be best to make a few useful chips (CPU/MCU/DSP/FPGA) that could cover a huge number of applications and even be retargetted to them. So, if you had only a few runs, you'd at least have a pool of trustworthy chips you could keep using or reusing in different projects. If you get more runs later, then you have a few proven and mostly paid for designs ready to go.

Disclaimer: I'm neither an electronic engineer nor a fab operator. None of this is gospel.

Previous discussion with RobertT and Clive on technical details here.

https://www.schneier.com/blog/archives/2011/07/research_in_sec.html

name.withheld.for.obviuos.reasons • September 22, 2013 1:27 PM

@Nick P

Very thoughtful treatment on the topic Nick, you inspired me to come up with an additional option...let me make a comment first. Yes sub 200nm fab is exceedingly expensive and since the off shoring of fabs to Taiwan I've always seen the domestic sourcing of all types of components as suspect. SEMTech was supposed to be a fab consortisium to keep fab capabilities with the domestic purview. We seem to, here in the US, forgotten the value of domestic production. The DoD has taken a dangerous approach to procurement for the sole purpose of "selling" weapon systems. What does that have to do with National Security? Eisenhower was the last President to oversee the War Department before it became its own department. I could cover this topic but I digress.

7. Petition fab OEM's to embrace a community (worldwide) to adopt a secure fab platform source chain. Everyone benefits from a reliable fab process, no one wants to see for example Airbus 380's falling out of the sky because they cannot acquire reliable components.

On a side note I am very concerned about the toolchain integrity of RTL and synthesis tools for fabless production. I see it as the choke point

name.withheld.for.obvious.reasons • September 22, 2013 1:54 PM

@Clive


Yes, in my "dead tree cave" I've a number of books and technical papers on using CMOS inverters as both amplifiers and oscillators, the oldest (and here I might be leaking a "bit" on my age ;-) is a Motrola "McMOS Handbook" from Oct 1973 which claims on it's title pace to be a "First Edition". Chaptor 8 (Anolog) and 12 (timepiece) give quite a bit of info sadly though of metastability and jitter there is a paucity of information other than the equivalant of 4uV broad band noise at each gate input...

Glad to know I am not the only one holding on to data books but I don't have any that predate the 1980's. In fact in 2000 I became so concerned with what I term "information integrity". Just yesterday I was stating a dir to audit time stamps and 2 lines in the standard output showed the same file name (not consecutively, sorted by mod times). Went to scrap the output to the console but I erred by issuing a few commands and scrolled back the console buffer and the duplicated entry was no longer there. And I knew I should have caught it before doing anything else.

My favorite source data books are from National Semi, was tragic to lose Jim Williams last year. The timing of his death and its impact on NS is a story in and of itself.

Keep your copies Clive, please identify a suitable home for them in the event you are taken. We may need them more than we know.

Figureitout • September 22, 2013 2:15 PM

Nick P
--The wave really repeated in that link, I've been sidetracked in reading the archives, wanted my PIR be read by my arduino.

Something seems not right, reverting to ebay for secure sourcing, I've had my mail packages tampered w/ before, really didn't appreciate that; trust gone there.

Seems pretty impractical; saving up for a few runs seems best where I and maybe others can sleep at the facility and monitor the entire process. Would need to interview some engineers. I really want to visit a fab lab.

Clive Robinson • September 22, 2013 2:26 PM

@ Nick P,

You might find this interesting, especialy when you look at the date,

http://theinvisiblethings.blogspot.co.uk/2009/06/more-thoughts-on-cpu-backdoors.html

@ Name.witheld...,

Yes I have some very old and now impossible to replace books in the cave, but weighing in around 7000Kg it's become a bit of a problem in terms of "caring for the beast" and like the rest of us I'm not as young as I was yesterday.

But rest assured I've no intention of going out the Viking way, but have not yet made my mind up who would best benifit by the collection.

You have to be carefull... In South East London "Croydon Council" have decided to flog of some very rare artifacts they were bequested. And it looks like not only are they selling at the wrong time and thus willl lose a considerable. Amount off the value they will also be lost not just to those in London but to the whole Nation as they will in all probability go abroad into private collections...

Nick P • September 22, 2013 4:03 PM

@ name.withheld

"We seem to, here in the US, forgotten the value of domestic production."

I agree. We're too dependent on other countries, especially competitors, for critical things. Plus, putting semiconductor manufacturing in control of people who might backdoor you just seems... stupid. It's why the old discussion I had here involved US funding a state-of-the-art fab they control for chips that *have* to be trustworthy. Of course, now I'm working on how to get chips that *aren't* American so *Americans* can trust them. Life's 180's are certainly amusing.

"On a side note I am very concerned about the toolchain integrity of RTL and synthesis tools for fabless production. I see it as the choke point "

Absolutely. Goes all the way back to Reflections on Trusting Trust. Many people cite that to worry about compilers. They're missing the bigger picture of it. The old work on security told us how to architect, specify and to a degree implement secure systems. The aforementioned paper pointed out that we must also trust the tools that turn those abstractions into something concrete. So, as you said, the RTL & synthesis tools will be an issue. I think we'll need something similar to Leroy's CompCert verifying compiler but for hardware designs. Fortunately, there's been a ton of work on hardware verification of all kinds. Verisoft's VAMP and total verified stack being my favorite. Look up the papers on how they architected that to verify each layer and interaction. Great stuff. Any complex subversion resistant design will be using similar techniques.

I think it shouldn't be hard to create a verifiable translation system from lower levels to chip structures. I'm pretty sure existing tools already do that to a degree, albeit as a proprietary black box. Might be a matter of licensing the technology from a larger vendor, breaking it into verifiable pieces, building/vetting each one, vet the combo, and use trusted distribution techniques from there to get it to end users. The software should also be *very* easy to port to arbitrary hardware so it can all be bootstrapped and also hardware remains vendor/ISA neutral. Forth or LISP are almost an ideal target for the verified translator, as their core is easy to port. (There are also Forth/Lips processors, established open implementations, & VLISP was rigorously verified.) Even if it doesn't *fully* verify the hardware, it verifies so much of it that it leaves only the most low-level steps of the production process to worry about. Less worry is always better.

Note: My usual method for high assurance translators is to use a typical (fast) translator for development, then do the final run with the provably correct (often ridiculously slow) translator. I mean, what if the only trustworthy bootstrap a person has is a 100MHz machine with 32MB RAM and they're running bare metal LISP (w/ no unsafe optimizations) on it? And memory is constantly swapped to disk? The conversion could take... a while. So, to make up for it, I've always advocated combining trusted and untrusted systems for software lifecycle management where critical steps happen on trusted system before signature or release. Seems like a decent compromise?

@ figureitout

"Something seems not right, reverting to ebay for secure sourcing, I've had my mail packages tampered w/ before, really didn't appreciate that; trust gone there.

And the irony is that, if your PC is using modern Intel or AMD, a stealthy subversion is *much* easier for attacker in question (NSA). ;) Interception and modification of something you buy on eBay is tricky. It must be targeted, it requires knowledge of the product, it can't interfere with shipping time too much, etc. So, if you're worried about that, browse what to buy with an anonymous browsing solution, have someone else buy/receive it for you, pay extra for overnight shipping (shorten attack window), and pay the person aiding you via cash. Many black hats use this strategy (minus overnight shipping) to acquire laptops for their online activities.

"seems pretty impractical"

COTS has proven to be the most practical. It also proved to be easy to subvert. So, anything we make that is hard to subvert is going to be impactical. And impractical aspect may be directly proportional to subversion resistance. Security is anything but convenient in this category.

"saving up for a few runs seems best where I and maybe others can sleep at the facility and monitor the entire process. Would need to interview some engineers. I really want to visit a fab lab."

Sounds like a decent idea. For recruits, maybe look into those CCC parties thrown supporting Wikileaks. There were plenty of hackers and anti-government types there. They have the security mindset (maybe), are usually ideological, and could learn enough tech.

I'd also like to visit one some time for the heck of it. I'd particularly be interested in wrapping my mind around all the technology there. I mean, in high end fabs, individual machines can go up to $50 million. Mind-boggling. It would suck to spill a can of soda on *that*.

MarkH • September 22, 2013 4:31 PM

@Nick P:

"It would suck to spill a can of soda on *that*."

Possibly, one wouldn't be invited to visit again.

RobertT • September 22, 2013 7:10 PM

@Clive R

"ouch"

I miss for the old days when the who and why were obvious but the what-to-do was an unknown, these days the what-to-do is second nature but the who and why questions remain, sure makes for a world of shadows.


@Gweihir
You need to understand the concept of "processing gain" as it applies to any spread spectrum comms system. Unfortunately the inclusion of an LFSR creates a long sequence locking mechanism which reveals the true nature of the source noise. What is important here is ensuring that the "noise input" is an order of magnitude greater than the dither added.

As for using the digital baseband byte wise/word-wise outputs of the SD-ADC, frankly I'd much rather access directly the bit-wise outputs of the modulator elements (pre-decimation) the algorithmic nature of FIR and IIR digital filters is a big unknown I'd rather not deal with. All SD ADC's are noise shaping loops, so maintaining this extra noise and complexity makes your adversaries problems that much more difficult. BTW you will need to add a couple of Zero's to the transfer function to flatten the frequency response of the noise.


Re: NIST random number tests.
I agree with what Nick P and others have said about all TRNG output looking perfect after algorithmic processing. It is well known that modern crypto algorithms are indeed that good. So instead of GIGO you get still have the GI but the next stage looks perfect, it makes this just too easy a solution.

I've had this argument many times in design reviews where these difficult to achieve NIST spec's (diehard etc) become the rational for resorting to algorithmic digital processing complexity because NO raw True Random can actually pass all the tests.
For low level signals (like noise) getting more than about 40dB signal to distortion ratios is very difficult. This lowish SNDR means that there are obvious spurs in the FFT of most raw TRNG data. Fortunately a little bit of digital post processing and all the spurs completely disappear. Indirectly the NIST is rewarding the "dishonest" TRNG maker because the tests are practically impossible to pass if you dont "cheat". Additionally any competent adversary will make it their business to understand how you cheated, so they alone can unscramble the scrambled mess that you are claiming is "raw trng" data.

Frankly I'd much rather a situation where the real world limitations of the TRNG problem were reflected in the spec because then the security community can than deal with the reality of biased rng streams.


Gweihir • September 22, 2013 10:13 PM

@RobertT: What does that have to do with Spread-Spectrum? I was asking about the dither amplitude and whether it was strong enough to be recognized directly. Maybe you are just using big words to say "no"? Also don't forget that the LFSR has a base clock frequency and in is putting out pulses very often in that raster. A real spread-spectrum design uses a cryptographically strong sequence and far longer spacing and there you have no chance to find the signal. Not so for an LFSR.

As for your second paragraph, I guess you are talking about an oscillator-jitter generator (no bit-wise output otherwise), and of course you would never put that through an ADC, that is just for an avalanche generator.

For the tests, I completely agree. They would do far better having statistical tests applicable before whitening, as after whitening these tests become meaningless. But we may see the hand of the NSA here: If you do raw-generator tests before whitening, you can very likely detect generators that have tampered with (well, maybe with an additional check of the chip, but some attack-targets of the NSA must have that capability) _and_ you have to make these raw outputs available! With making the tests strong enough to fail on almost all non-whitened output, but weak enough to succeed easily in whitened output (as they cannot made strong enough to detect bad cryptographically whitened output), they have removed the need to make the raw signal available. I think that is highly suspicious.

Contrast that with the VIA C3 generator, where you get the raw output if you want it. There you can see all the non-random things and it allows you to find out whether the generator really displays all the faults in behaving randomly its design indicates. The VIA C3 generator also shows how damn easy it is to give access to the raw noise, just a shift register and one switch is enough.

Figureitout • September 22, 2013 10:30 PM

Nick P
--It was just textbooks thankfully, but it affected my education; people need to factor in all these hidden costs of their pathetic ops. I've known of people shipping drugs to their school mailbox; so they need to get their head out of their rear.

You don't need to tell me about stealthy subversion, I've seen plenty of ridiculous hacks that still puzzle me.

I think there would be shots fired if you spilled soda on such a machine; I mean I would probably shed a tear.

RobertT • September 23, 2013 12:38 AM

The point with understanding the LSFR's dither is that it adds pseudo noise to the SD loop. If the SD input were locked at zero signal (normally mid point), then the pseudo random nature of the LSFR output still whitens the SD's raw bit output sequence making an output that appears "white" while it is actually highly deterministic. Anyone that knows the type of LSFR that is used can perform a simple correlation operation on the bit serial output and remove the effect of the dither.

In a way this is exactly the same problem as the algorithmic cryptographic whitening of TRNG's but just applied one stage earlier. I've referenced to spectrum spreading because the all the Receiver techniques/tricks for DSSS type systems operating 20dB or more below the channel AWGN limit, can be used to analyze the effect of LFSR's on RNG sequences.

Maybe you need to study and simulate some lower order ADC Sigma Delta modulators. With first and second order loops the output of the first integrator stage is basically tracking the input signal. This means that the comparator is always just looking at small differences (Deltas) except when input signals are slewing very quickly.
Meaning you must add dither or the "error" into the loop because it might not naturally accumulate quickly enough to keep all the frequency components of the SD loop noise shaping function out of the baseband region.

Re second paragraph.
Internally nearly all Sigma Delta's output a serial bit sequence at the input clock "Over Sampled signal rate" So for an OSR of say 128. A 10Khz ADC bandwidth requires a clock rate of 1.28Mhz, this is the raw bit stream. This bit stream is digitally filtered (typically FIR or IIR filters) to produce the baseband data. I'm saying I'd rather use the OSR data (for TRNG) than the baseband post filtered data. this is nothing to do with loop jitter.

Anyway I'm done with this discussion, I'm happy to acknowledge that I know practically nothing about this topic, so I'm probably just writing complete FUD.


Gweihir • September 23, 2013 2:54 AM

@RobertT: Thanks, I did not realize you were talking about Sigma-Delta converters. I am still firmly stuck at the successive-approximation stage for faster A/Ds. Should have realized that SD is probably cheaper to do for 16 bit audio by now and also fast enough. My interest in audio electronics is small, so I do not really follow the development there.

Just one thing about LFSRs: You actually do not need to know what type it is, you can synthesize an equivalent one from the bit-stream using the Berlekamp-Massey algorithm. Did this a long time ago in a cryptography lab.

Nick P • September 23, 2013 11:29 AM

"Possibly one wouldn't be invited to visit again" (MarkH)

"I think there would be shots fired if you spilled soda on such a machine; I mean I would probably shed a tear." (figureitout)

Probably true on both counts. lol

Wael • September 23, 2013 1:35 PM

@ Clive Robinson,

German not English BSI standard AIS-31 ...
Thank you Sir[1]! Maybe one of the things I was looking for. Problem is, unfortunately, Mein Deutsch ist sehr schlecht :(, and I could not find the german version either.

This will take sometime, but may help answer some of the questions I have.

[1] I had a British colleague, that I called him Sir once. He said I am not "Sir", I was not knighted.

MarkH • September 23, 2013 2:04 PM

Please remember, an automatic entropy estimator can tell you that the entropy is not greater than X (i.e., can estimate an upper bound).

But the actual entropy may be smaller than X by an astronomically large factor, and there is no way to make the estimator "smart" enough to prevent such an outcome.

Cointelpro • September 23, 2013 4:09 PM

204 comments on that subject: this thread is obviously trolled, in the interest of NSA.

Trolling ways: fights, poems, moquing, damage control: all elements of the Cointelpro techniques as detailed in http://cryptome.org/2012/07/gent-forum-spies.htm ; these began, one or two months ago, to surface in threads of schneier.com.

Next time you feel that you are answering to a Cointelpro agent, do not forget to state also that:
"I have the feeling that you was payed to deploy technique #24 of Cointelpro in your comment, as defined by http://cryptome.org/2012/07/gent-forum-spies.htm ..."
Do not forget to replace 24 by the right number.

Clive Robinson • September 23, 2013 4:40 PM

@ Wael,

    I had a British colleague, that I called him Sir once. He said I am not"Sir", I was not knighted

Yup it can be confusing :-)

The simple rule is "sir" on it's own is an honerific not a title, it becomes a title when it's with the name such as "Sir Clive" or "Sir Clive Sinclair" but don't say "Sir Sinclair" it's bad form

So the honourific use is if you don't know someones name or you've not been introduced then it would be "goodevening sir" you also use it on it's own when acknowledging an officer in the armed forces as a mark of respect to the monarch. It used to be that school children would call their teachers Sir or Miss or Mam / Madam respectivly.

Also watch out for the use of Mr, Miss or Mrs, it would be Mr Robinson or Mr Clive Robinson. Not Mr Clive, this is known in my and older generations as "Slave Talk" and it's considered to be very wrong and way beyond being Un-PC.

The use of Mr/Miss/Mrs/Ms is going out of fashion so I would probably be introduced to you as "Wael meet Clive, Clive meet Wael" or "Wael this is Clive Robinson".

Other things that are going out of fashion are the realy old things. As I am "a person of property and title" (briefly Lord of the Manor) this ment I was considered to be a step above a gentelman so instead of Mr. C.Robinson I could sign letters etc as C.Robinson Esq. for esquire, which I beleive is reserved in the US for the legal profession

Dirk Praet • September 23, 2013 7:31 PM

@ Cointelpro

Interesting link, but you obviously haven't been here long enough to know that the bulk of these posts have been made by long-time commentors in good standing like @ Clive Robinson, @ Nick P, @ RobertT, @ Gweihir, @ name.withheld.for.obvious.reasons , @ Wael and several others.

Instead of venting baseless accusations, you would probably have served yourself better by trying to understand the ongoing discussions, in the process getting a valuable free course on several subject matters. That's what I did. And yes, we regularly disagree on stuff.

Wael • September 23, 2013 11:01 PM

@ Gweihir,

The "AES" is the AES in the whitener in RdRand, and it is not consumer-side at all, it sits between the hardware generator and the RdRand instruction and you cannot get at the hardware generator past it. If you could get at the hardware generator directly, it would be (relatively) easy to find sabotage or to bypass it.

That is what I was thinking needs to be done as part of the test. If the RNG with its building blocks are a black box, then statistical tests would fail to show sabotage (unless the papers @ Clive Robinson pointed to show otherwise)... Chips are very complex, and functional tests may not be sufficient to detect subversion. Part of the tests that I suppose are not available to the public are verification tests, which would have better chance finding subversion.

Wael • September 23, 2013 11:53 PM

@ Clive Robinson,

One way of looking at information entropy is it defines "the number of possabilities", anything that is predictable reduces the possabilities.

I think about it differently. I believe there is nothing random in this universe. Everything has order. If we cannot detect a pattern or predict the future of a sequence, we call it random. "Randomness" is a defect in our understanding or a side effect of an incomplete or erroneous model of some phenomena.

MarkH • September 24, 2013 2:26 AM

@Wael:

"If the RNG with its building blocks are a black box, then statistical tests would fail to show sabotage..."

Yes. I've been doing my best to explain why such tests can never prove that an RNG is cryptographically secure.

"Chips are very complex, and functional tests may not be sufficient to detect subversion."

I think that is the consensus among those who have considered the question. I would strengthen the conclusion: functional testing not only may fail to detect subversion; such testing cannot give a high degree of assurance that subversion did not occur.

Clive Robinson • September 24, 2013 6:38 AM

@ Wael,

I know this. Is going to sound like the first line of a joke but it's neither a joke or funny,

"When is a chip not a chip?"

The answer is to all intents and purposes you don't know. It falls to those two well known saws,

"If it walks like a duck and quacks like a duck..."

"The contents are what it says on the tin."

And for the majority of chips used in the electronics industry the supply side goes with the "what it says on the tin" and just a few go through the "duck test" as part of the QA process.

As I'm sure you realise from software testing once you get above a certain degree of complexity full functional testing is not actually possible let alone full state testing by the chip manufacturer. So what chance has the end user got?

Once you get out of the certainties of logic you find those gates are realy all analog circuits and suffer the attendant problems and hidden cludges (how you turn a SR Latch into a D type register being one). You thus get such problems as metastability where every once in a while (about one time in a billion or better) the logic will go to the wrong state, go to the wrong state and flip back, take an age to go to the right state or just latch up untill the power is recycled all of which does not usually play nicely with down stream functionality. Now you can not stop this behaviour only mitigate it in some way usually by adding aditional logic.

When production chips are tested they are tested to see at what clock speed they will run at by some measure of reliability. And in times past a manufacture would put a speed rating on the device and price accordingly. However there is a lot of profit in premium product but the main turn over is in non premium parts, so the chip manufactures mark down a lot of what would be premium parts into lower speed ratings, which is where "over clockers" get some of their fun.

Unfortunately this gives rise to some low moral individuals buying the low cost parts and relabeling them as premium parts and putting them back in the supply chain. Various techniques have been tried to stop the practice but such parts make it onto the market and into products regardless.

The problem is that once a chip is encapsulated you cannot perform some qualifing tests so the only way to be sure a chip is what it is is by destructive testing, which kind of makes them difficult to use as production parts. Which is why "goods inward test" is at best a partial procedure.

There are also those who know this and use it to actually make "Chinese Knock Offs" whereby they make their own copies of the chips only by using cheaper production techniques.

One side effect is the metastability issue raises it's ugly little head, in making copies the mitigation logic in problem areas may well get left out as it's not directly "functional". This brings the soft MTBF figures way way down on the knock off parts... Testing for this in "goods inwards" is a compleat non starter due to time constraints and the stress testing that would show it up would do a bit more than "burn the part in".

But... all these Digital TRNGs work on metastability, such as connecting the output of an inverter back to it's inputto make it oscillate and then changing it's input bias point or supply voltage to change the frequency in some supposadly unpredictable way. Two or more of these are then gated to gether and fed into the clock input of a following circuit that acts like either a frequency counter or mixer, in either case thecounter LSBs or mixer output is assumed to have the addative metastabillity jitter on it's output.

There are two main issues with this,

Firstly the metastability is in effect the byproduct of the analog bias points of the inverter being used as a high gain amplifier with a total of 360 degree feedback making it an oscillator. There is an old saying in the RF electronics design world "Oscillators don't, Amplifiers do" which gives rise to another saying "If you want to design an oscillator design an amplifier". Basicaly both are highly sensitive to design parameters and this includes the bias points. Now this brings up an issue, of is metastability random or chaotic? Chaos is complex but still determanistic, random is not determanistic. Thus is the gain in the chaotic system sufficient to amplify the non determanistic quantum/thermal effects at the bias points to make them predominant or even present at the output? The simple answer appears to be "we hide behind the duck test" which is a "cop out". As has been noted by RobertT when it comes to looking like AGWN there are many quite simple circuits (LFSRs, LFGs/Lfibs, CAs and add/mul/squ mod n) that all produce what looks like AGWN but are without doubt fully determanistic. Some of these can be found in the likes of Sigma Delta (SD) DTRNGs. So are we kidding ourselves about the supposed randomnes of DTRNGs?

Secondly these DTRNGs are usually buried deep within the chip and as I've indicated sensitive to temprature voltage and the activities of circuits around them, testing them reliably is impossible in any meaningfull time frame and impossible once their output has been de-biased and then put through a crypto function.

Can these DTRNGs by nobbled, yes, can it be reliably detected after being put through a crypto function, yes if you know the method and key no otherwise. What about keyless crypto functions such as hashes... well we know how to find collisons in one kind of hash and we are aware that the NSA knowes atleast one other. Also we know that some hash functions are "brittle" in that small changes in their design makes them very weak, but you only see this if you can see both the inputs and outputs to run tests on.

Now getting back to the simple DTRNG of two oscillators and a D type, if you look at the output on an oscilloscope with the time base turned down you can see what looks like regularly spaced bunchin of the waveform. If you measure the frequency difference of the two oscillators you will see it nicely correlates in period and phase to the bunching. This means that without doubt the output is serialy correlated and the bits are not independent of each other. Von Neuman debiasing only works when the bits are fully independant otherwise it simply has the effect of dividing the bit ouput rate by four. You can see this on the oscilloscope screen but to a lesser extent. So with two high stability oscillators or oscillators locked to a refrence the entropy of this DTRNG is very close to or ZERO... This is quite clear in the output if you run the right statistical tests in the right way, thus run the wrong tests or in the wrong way and this DTRNG of zero entropy and easy predictability will pass...

Is it easy to lock these oscillators up? yes and in effect invisably if you examine the chip layout with a "digital eye" not an "analog eye". To see how, go and look up "injection lockinng" and how it's used in your colour TV "chroma burst" system as used in both NTSC and PAL (PAL gets it's name from correcting a problem in NTSC which alows phase drift and thus chroma problems).

Now as has been mentioned GIGO does not work with encryption primatives unless you either know the key or the method the output is "golden".

Now as I've repeatedly stated you need access to the raw TRNG output to check the system functionality. This alows you to check both the TRNG and the crypto function. Not providing it is such bad practice it raises suspicion in it's own right. As I've said "verify and trust" is the only trustworthy path so I consider Intels DTRNG untrustworthy by definition.

So getting back to the argument. Locking the oscillators up is fairly trivial, thus the result from the D type is a highly predictable digitised sine wave. If you likewise fritz the crypto function if it's a hash or know the key if it's AES etc then you know or can fairly quickly find the DTRNG output.

As I noted above the output will be fine for Monte Carlo and other similar activities but very dangerous for Crypto work.

Similar arguments can be made for all DTRNGs so you need to be able to "verify" and/or mitigate with other sources of entropy in some kind of entropy pool where the mixing function is especialy good at dealing with long sequence serial corelation. One such involves the use of "Chinese Remainder" maths on primes to get maximal sequence sampaling/shuffeling.

Jack Gatrost • September 24, 2013 9:39 AM

A question for any mathematicians out here:

If the byte streams from two different random number generators are bitwise XOR'ed, ...

1) Can the result end up any less "random"?

2) Is there any reason to expect a more random value from this action?

For example, mixing with bitwise XOR the output from a hardware RNG with a software PRNG output.

Clive Robinson • September 24, 2013 10:42 AM

@ Jack Gatrost,

    A question for any mathematicians out here If the byte streams from two different random number generators are bitwise XOR'ed

As you don't say if the two byt streams are independent or not there are several answers.

If the streams are not interdependant and fully random, over a long period the output is assumed to still be random and the effective entropy the normalisation of the addition of the entropy of the two streams.

However of short distances there is the probability that the two streams will match and produce all zero's, all one's or a very regular pattern the probability of this is fairly easily found with a truth table by hand or simple mathmatics.

If however they are not fully independent then the situation is different and depending on how dependent they are and any offset involved defines how much entropy there is.

The simple case is when the streams are the same or one is the inverse of the other the output is going to be zero or one so the outp is fully determanistic so no entropy at all.

Lesss well known is that form many sequencies that have been linearly generated adding them together is the equivalent of simply adding them together (think of adding two sine waves together with a phase differance and you end up with another sine wave but phase shifted). So the entropy remains the same.

Even non linear sequencies exhibit this shift behaviour. To see why you need to do a Walsh Analysis (equivalent of a Fourier Analysis but using digital sequencies not frequencies) on the non linear sequence to remove the basic sequencies and identify the correlations which either cancel or sum to one when shifted in time (ie as linear components).

I hope that provides you with sufficient information to dig further if you wish.

Wael • September 24, 2013 11:46 AM

@ Jack Gatrost, @ Clive Robinson

A question for any mathematicians out here If the byte streams from two different random number generators are bitwise XOR'ed

The output will still be random (as long as A and B are two independent sources, as @ Clive Robinson mentioned), with a different distribution. If the two streams A and B have a uniform distribution (Probability Distribution Function, pdf), and we XOR them (approximate that with an addition operation), then the output will be random with a Gaussian pdf, or normal distribution (the bell curve). This results from convolution.

MarkH • September 24, 2013 6:27 PM

@ Jack Gatrost:

Disclaimer: I'm no mathematician. The following is my non-expert understanding.

If a bit sequence has "perfect" entropy (1 bit of entropy per bit of data: for example, the results of "fair coin tosses"), then it can be XORed with any other independent bit sequence, and the data will be just as entropic (disordered). This is the cornerstone of the Vernam (one-time pad) cipher.

As a practical matter, if the entropy of an RNG is satisfactory, there's nothing to be gained by XORing it with a PRNG.

On the other hand, if the RNG output is imperfect (not perfectly entropic), a usual way to enhance the output entropy is using a hash function. For ordinary hashes, the digest (output) is of fixed size, based on inputs of varying and potentially large size.

For example, suppose a careful evaluation of an RNG concludes that the entropy per output bit is at least 0.25. One could then collect RNG output into "batches" of 1024 bits, applying SHA-256 to each batch. The 256 bit digest (output) from the hash operation should then have 1 bit of entropy per bit of output: the hashing process destroys any "patterned-ness" (predictability) in the raw RNG output.

To improve the quality of RNG output for crypto purposes, hashing (I believe) is a much safer procedure than simply XORing with output from a PRNG (whose entropy is limited to its seed).

RobertT • September 24, 2013 8:27 PM

Slightly off Topic: Re XORing multiple RNG sequences

Many Forensic Accounting tools rely on the data set Order created by adding groups of Random numbers. Benfords law is just such an effect.

http://en.wikipedia.org/wiki/Benford's_law

My point is that the data order created in large random data sets can often be simply the result of the way we process/view the data. Leading Digit theory is a direct consequence of using Base10 arithmetic and it is not an effect that most people (even security professionals) are watching out for when they create / manipulate RNG data sets. This means that a bit wise XOR of RNG sequences is safe but an actual ADD of two or more Random Number sets not safe. Small difference in the arithmetic operator but a huge difference in the result.

Wael • September 24, 2013 8:51 PM

@ RobertT

Bitwise XOR operation is identical to bitwise ADD operation (ADD with no carry). Would you care to explain the unsaftey of the ADD operation?

0+0 = 0
0+1 = 1
1+0 = 1
1+1 = 0 (ADD, not ADC)

XOR has an identical "truth table".

In fact you can use the add operation instead of the XOR operation to exchange the values of two variables in place in three steps, just like you can with an XOR.

RobertT • September 24, 2013 9:24 PM

@Wael,
It is precisely this minor difference between a simple bitwise Add and an Add-with-Carry that can create problems. Unless you are looking for exactly this type of issue the two Arithmetic operators look very similar, so it comes as a surprise to many that one reduces randomness whereas the other preserves it.

You might say that no security professional would be dumb enough to make this mistake......my only retort would be.....I have no shortage of experience with security professionals making far more fundamental mistakes than this subtle arithmetic operator difference.

Wael • September 24, 2013 10:19 PM

@ RobertT,

At the risk of looking stupid, I am not convinced that adding two random numbers reduces randomness. Add with carry or otherwise. As far as I know, adding two random variables changes the distribution, but not the randomness per se. The addition of two uniform distribution, independent random variables results in a random variable with normal distribution. Perhaps you believe that a Gaussian PDF is less random than a uniform PDF?

Wael • September 24, 2013 10:33 PM

@ RobertT,

Hmm after Googling a bit, it seems that I forgot to mention the limit - the central limit theorem... Oh well. getting off topic now...

Soothsayer • September 24, 2013 11:19 PM

I didn't spend a lot of time on the paper -- but it appears the technique works ONLY because the BIST on the intel implementation uses a 32 BIT PRBS .. probably NIST check is equally flawed.

Otherwise this paper makes absolutely no sense -- you can force one gate to be stuck at a level and no test can detect it .. good luck to all the logic on this planet.

Clive Robinson • September 25, 2013 12:22 AM

@ Wael,

Whilst I remember (insomnia is a harsh mistres)? I think you were looking for a determanistic sequence that passed all the Diehard test witnesses. Also more stringent tests for determanistic tests such as the TestU01 [1] suite of Crush [2] tests,

Whell if you look at the work of Makoto Matsumoto you will find two examples,

1, The Mersenne Prime Twister
2, WELL -Well Equidistributed Long-period Linear

It appears MT19937 passes Diehard and is used as an argument for the adoption of more stringent tests [3].

TestU01 has three sets of tests and other usefull code, it is written in C and runs on Linux. It is both more extensive and easier to use than Diehard (originaly from 1997). It is recognised that with it's fixed sample size and sample. Format that even the Diehard tests are generaly not used to best advantage even in non cryptographic fields such as Econometrics. There are other collections of tests that are more effective [4] that have been made available in software for by others.

[1] http://www.iro.umontreal.ca/~simardr/testu01/tu01.html

[2] http://www.iro.umontreal.ca/~simardr/testu01/guideshorttestu01.pdf

[3] http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf

[4] See volume 2 of Donald Knuths Semi-numerical Algorithms second edition.

RobertT • September 25, 2013 12:56 AM

@Wael,
Re: XOR Vs ADC (add with carry)
I really dont have the math skills needed to formally answer this sort of issue, maybe Bruce or some other Math/Cyrpto experts can help.

I can however assure you that I have fallen victim to this exact sort of issue before. For me it is also counter-intuitive that a linear operator like ADC (Add with carry) can in ANY way reduce random-ness. But it is hard to argue with the facts when the leading digit (or four MSB's ) depending on which way you want to view the problem can be predicted with 30% accuracy (rather than 1 in 10 or 1 in 15 as would hopefully be the case for Decimal or Hex RNG numbers)

Clive Robinson • September 25, 2013 1:13 AM

@ RobertT, Wael,

Talking of "Benford's Law" not only have a use in forensics, it's had a use in cryptography going back to the 1930's.

Basicaly many people used "book codes" and would use common or busines related almanacs for the pad. The fact that they contained tables of numeric data that followed Benford's law aided cryptanalysis.

As some people might know adding indipendent and uniformly distributed numbers togther changes the distribution from flat to succeessivly normal distribution, which is useful for doing many types of simulation. The general advice being add four to six random numbers together.

However there is an easy trap to fall into which if you by mistake do it modulo a number with common factors to the size of the uniformly distributed set you go back from a normal distribution to a uniform distribution.

You see this happen in C programs where people don't understand the implicit case rules for converting unsigned ints from the RNG function to either signed or floats used in their program and the consiquences of adding two or more full range unsigned ints into another equaly sized unsigned int.

Wael • September 25, 2013 1:47 AM

@ RobertT

But it is hard to argue with the facts when the leading digit (or four MSB's ) depending on which way you want to view the problem can be predicted with 30% accuracy (rather than 1 in 10 or 1 in 15 as would hopefully be the case for Decimal or Hex RNG numbers)
I believe you, you don't need to assure me. Sometimes I refuse to let math answer some questions.

@ Clive Robinson,

Thanks for correcting me, the keyword is "successively".

Wael • September 25, 2013 2:01 AM

@ Clive Robinson,

Whilst I remember (insomnia is a harsh mistres)?...
Insomnia is my sweetheart ;) sometimes I stay up two nights in a row. My record was four. Thanks for the links, I'll check them out. One thing that puzzles me is the links you, @ Nick P, and @ Dirk Praet find and share with us. And that is especially true for the link @ Dirk Praet posted:
AFAIK there is no such law. What you are citing is Opinion 820 from the New York State Bar Association Committee on Professional Ethics (NYSBA)

That just... Kills me! How in the world did you get that @ Dirk Praet?

name.withheld.for.obvious.reasons • September 25, 2013 11:06 AM

@figureitout

I'd be more specific about hardware, but, as Bruce's generous support of this forum makes giving details problematic. As you are probably aware there are lible laws that have time to time cropped up and I would be doing a disservice to Bruce--as I am speaking about a commerical product using a pseudo anonymous ID (though the ip_addr leads "somewhere").
What I feel comfortable in saying is that the platform was not very robust (programmatically) but it is a good piece of hardware. AD's analog components are well designed and their competence in the design and fab is of a high caliber. I am not trying to give AD any cover, it is the errant attack that could be launched against Bruce that gives me the most concern. I should probaly write a white paper for the IEEE describing the engineering process that produced a whole series of "Doh" moments. And, I did have one on my part, committig to a development strategy that I knew was risky and going against my better judgement...

@Nick P

Whilst I was consulting on a "project", the work performed in tempest rated environment, the attenttion to detail that could cause anomolies in the development process. More than once I was witness to processes and procedures that were not treated in a manner that would even merit a ISO15408 qualification. On area I've had the chance to (for a six month trail period) oversea a QA program at a major systems manufacturer, one of our efforts was to achieve a Baldridge award. If you have spent any time with senior management, you know that driving development that can answer "all" the constraints of robust architectures and products. As a member of a committee I remember pleading the case for taking deliberate steps, not statements of desired outcomes, but committments to make the destination reachable. I've yet to see an org achieve this--Richard Feynman is the name used to refer to me, and I see that as a compliment.

A few monts ago I engaged you in a conversation about engineering security, we both made the same observations...and I can guess that is why Bruce's thinking appeals to both of us. An honest assesment of what is possible can differ greatly from what is possible, in both the positive and negative terms.
If we are serious, I'd draft a white paper that is both detailed in critism but is complete in its resolution/solution. One thing I've been successful with is always having a solution to present, after I describe what is so wrong with whatever project/product/system.

Didn't proof this--have a business affair that requires my attention...excuse the misspellings...gotta go.

Nick P • September 26, 2013 12:41 PM

This talk on PS3 hacking has a nice list of useful features to consider for tamper-resistant systems starting around 12:50 into video.

https://www.youtube.com/watch?v=PR9tFXz4Quc

Earlier in the vid they also show how long each system lasted before being hacked and how it was hacked. Many smart, motivated people tried to hack these consoles. So, I think this gives you a useful measure of what protection period to expect from these types of features when the attackers aren't thought to have a whole lab of equipment for chip hacking.

someone • October 7, 2013 12:55 AM

"Efforts toward open-source BIOS have been hampered in part by the prevalence of proprietary hardware on PC-compatible mainboards.

Such boot firmware is an excellent locus for attack vectors, and (coming almost always from a very small number of vendors) readily subject to subversion by powerful agencies."

I could see how something like coreboot could pretty much eliminate cold boot attacks. Say, if the computer starts up, it only will boot from say a USB stick with /boot (which you then hide/destroy), fishy UUIDs just make it wipe the DRAM.

I mean, if they have physical access you your hardware, that's bad to begin with.

I think this was from another thread:

"> The forensics magazine I occasionally get had an advertisement for an interesting device - basically a briefcase like UPS... allowing you to take a FDE enabled PC back to your office where you can do a cold boot attack at your leisure.

There are some fairly simple defenses against this kind of trick. One could, for instance, embed a GPS receiver into the machine. Better still, a 3-axis accelerometer. Any appreciable motion and the keys get zeroed and repeatedly bit-walked over."

You could also get an internal battery, inside the chassis, have a daemon wipe any keys in the event of tampering. It all depends how much effort they will put in. There are a lot of attacks that could work in principle. This thread is about tampering with chips, and everyone has been talking about RNG. But I wonder (I don't know this) how does AES-NI actually work? It seems like it could be that the chip could be made to store keys in SRAM, in some special area, that could be accessed later. I don't know anything about that. That's only a worry if they can access your hardware. Maybe epoxy the CPU to the motherboard so it breaks if removal is attempted? That would probably be unreliable.

Clive Robinson • October 7, 2013 2:52 AM

@ Someone,

If you have read this blog for some time you will know that I've investigated building computers into thermite lined safes which are built into "firebrick" supporting structures.

What I did not go into was the other aspects of physical security which is the sensors both electrical and mechanical that trigger the firing circuits of the thermite and other chemical based protection methods.

Whilst it would not be impossible to "bomb disposal" your way in the probability of doing so is very small, things like "explosive disruption" and "saline cutters" all have disadvantages that can be used against attempts to use them. After all they are designed to stop a bomb exploding not stop information being lost in the process of their use.

Semi Industry Eng • October 17, 2013 5:04 PM

I am a H/W engineer at a major Si company and would just like to point out that the idea of altering the masks in the layout stage is basically insane, for a variety of reasons.

First of all, the production masks are maintained in a versioned repo - all changes (and who made them) are tracked. The keys are held by specific individuals (gatekeepers). Of course, this in itself doesn't prove that you couldn't have a mole.

But, secondly, this mole would have to have an amazingly broad knowledge of computer technology - all the way from the RTL and circuit design, right down to the gate-level physics in the transistor. The hypothesized mole would have to a) have worked out what the circuit does and how it can be subverted (requires full access to the RTL, as well as to the standard cells), b) worked out where to attack the circuit in order to subvert it, c) know how to manually "hack" the mask set.

Masks today are at such small dimensions that they have to be mathematically deformed to counteract the refractory effects of light because the dimensions of the features being fabricated are beginning to approach the wavelengths of light being used to activate the photoresist (see http://videoprocessing.ucsd.edu/~stanleychan/research/Lithography.html for example). There are dozens of masks applied in a specific sequence and exactly the right masks must be altered in exactly the right way to produce the desired "trojan".

In short, the mask set isn't something you can just manually "hack". It is generated algorithmically from the RTL and must follow a large number of "design rule checks", the violation of any of which is likely to result in bad parts. The hypothesized hacker/mole in this paper's scenario would be, by construction, avoiding the automated tool-chain so he would have to manually work out the optical deformations of the mask required to get the correct doping pattern. He would also have to ensure he altered all and only the correct masks. And when he was done making his alterations, he would have to somehow check these into the versioned repository without detection. Finally, when the production masks are re-generated with each new spin of the parts through the fab facility (in early stages of the design, this could be occurring every few weeks), he would have to repeat this hacking of the masks.

Nothing is impossible but I would argue that this is a very low ROI attack vector, especially for any kind of cutting-edge silicon where you are dealing with a set of design-rules so large that no "manual" process could be implemented in reasonable time/cost to avoid going through the official tool-chain.

I will refrain from speculating here about other, more cost-effective hardware attacks.

RobertT • October 17, 2013 6:45 PM

@Semi Industry Eng

First off lets be clear on a couple of points:
1) No chip mask flow can be hacked by some outsider and certainly not some script-kiddy....its an inside job
2) The ideal person to do this is the team leader for a design critical and security critical block, it is also possible (even probable) that this individual does not understand the crytograpihic importance of the minor changes they are making, they have simple been instructed / paid to get this information off chip somehow.

OK with that said...

I've never said that hacking a chip mask set would be easy, just that it is possible. I agree with most of what you are saying although specific aspects of the final chip flow vary from company to company, so accordingly so should the exact attack method vary to leverage the security weaknesses in the mask creation flow.

For most of my mask hacking cases I've assumed the hack happens at the actual mask creation stage, with some support for the final hack being inserted at the layout stage.

Let me give you an example:
Lets say the only information you want to get off chip is the state of the ALU Carry flag. Nothing more just this single bit.

Now imagine the ALU hardware designer told the layout person that this signal is critical and should be hand routed first. From my experience it is common for critical signals to be hand routed and nobody would question the head of the ALU team. OK so what we have is a signal that is fixed in the design, Lets say this signal gets a shield layer so say an M2 routed signal has an M3 shield to minimize signal cross coupling and capacitive loading. In reality this shield has no function EXCEPT to introduce some dedicated routing / signal coupling that will be utilized later.

OK so we have a design database that will pass all our LVS and formal verification flows. it is logically correct. Now lets connect the shield to say AGND (AVSS) and make that AVSS route ALSO go to an opamp input. This shared routing has just ONE via actually connecting it to AVSS, so by eliminating this Via we have a floating input to an opamp that conveniently routes right along side the ALU bit that we want to take off chip.

Now we are left with the problem: How to make that one via disappear. Personally I'd make this happen at the OPC (optical proximity correction) stage, I've never seen a real closed loop flow implemented at this point, so whatever correction pattern the tool spits out goes on the masks no questions asked nobody even looks at it, (if you have ever had to dig through a Mebes database looking at hammerheads and trying to figure out how a real OPC error occurred you'll know what I'm talking about). So we want an OPC change that opens the VIA, remember this via has no function in the normal sense that the chip functions exactly the same with or without the via, however without the via it leaks information on the state of the Carry flag and it leaks it into the Analog domain where all routing is normally hand done.

Since it has no function no test can ever discover that the Via is missing we just have "noise" on an analog output. The normal function of this Analog output might be to measure local onchip temperature so it will normally be time integrated, probably in the firmware. Basically nobody knows it is noisy nor cares it is noisy EXCEPT the person that knows this noise is actually the ALU carry state.

The whole flow could be completed with only two or maybe three people needing to know, probably the most critical person is the guy at the mask shop that knows which VIA to messup the OPC on.

John Langman • October 24, 2013 11:00 AM

Surreptitiously Tampering with Computer Chips

Whilst the theory of tampering with chips is great for the theorists, reality is much harder, Most Microcircuits are not designed from the transistor level up-it just takes too long-.
Whilst tampering with devices at the transistor level is possible many devices are simply designed to ignore stuck at zero or stuck at one scenarios, I feel the white paper mentioned is idealogically correct but not rooted in the real chip design world. The authors assume that a 100 million plus chip design is flawless, which is simply not true, chips are designed to be robust in functionality and to provide data sheet compliance not perfect design.


Major Microcircuits are designed using libraries of 'Macros'. Therefore to 'tamper' with a design requires tampering with the Macro, and its test vectors and its physical layout, because after a design is 'assembled' it is simulated including physical layout, and this simulation must comply with the spec, so tampering means changing the simulation outcome as well. and the JTAG test pin placements and a whole host of things designed to assure that it is right first time. So if ALL of the above are tampered then it clearly and logically WILL pass internals start up self tests-but why wouldn't it-. If any part of the tool chain is individually subverted then the device will likely fail simulation and self test. Again I feel the extreme and un detailed nature of this paper is foisting an untested and unrealistic scenario on users. The authors assume that self test checks the whole chip which it does not,


Similarly devices can have multiple vendors with self design (see ARM implementations) each vendors devices will therefore be unique in implementation whilst being data sheet functional compliant and interchangeable with other vendors ( see 8051 Micro controllers vendor lists-some 40 plus vendors and 40 plus implementations and processes-)


The Right First Time scenario is vitally important. Each mask step requires a UV and or Deep UV special mask ( possibly at veery fine geometries a phase Mask that only passes half wavelengths of UV) which are super expensive Like millions of dollars each and a major design (see core i7 intel at circa 1 Billion+ individual transistors) may require 12 or more masks all at the same price. In the scenario of tampering with the design a significant number of process steps have to be subverted and there will be a huge price to pay, and even Intel will balk ( read refuse) at mask change costs running into circa 25 to 100 million dollars to satisfy an NSA or any other subversion agency. These kind of costs show up in the financial accounts available to the public and investors. So whilst theory is great practice is much much more difficult. As for the detection requirement the user base finds this stuff out super quick,Intel and AMD have found their co-processor implementations subject to oops moments -see history of Maths co-processor implementations and the effects on Spreadsheets-


The user base is so large today and so diverse that the community of users numbering 100s of millions will for sure find the non compliance, and they will publish that the device does not meet the published specification. So modifying the Random Number Generator design ( carefully chosen item in the paper:- an rng and judgmental words 'devastating' to raise maximum interest and worry ) is theoretically possible, however the authors ignore the huge user base that actually really needs a rng and then tests for it. I would argue that the statement that a dumbed down rng is undetectable is not true


Its is not difficult to plot a rng output on a schmoo diagram or to plot a test algorithm and see a devices capability, incapacity or inaccuracy, 'cos the results will be bunched up in one place on the graph, a sure give away of non compliance as a rng. So no its is not difficult to detect tampering -even assuming anyone can get a chip company to comply with a government agency demand for changes! Just because Intel pushes one aspect does not make a subversion an actaulity. Untested assumptions are just that untested, have the authors done a real world rng check on an Intel, AMD, et al 386/486/686/Pentium/Core duo/i Core device to support their case with real world test plots and comparisons?


And yes the Open Source world will take a negative view of requests from any 'outside' source and I hope they continue to do so, we need the capability and robustness of their attitude for our competitive landscape but reflective comments justifying a previous action are intellectually dishonest, just say Intel pissed you off with the attitude in the email/phone call or whatever I am happy with that.

John Langman • October 24, 2013 6:27 PM

Reverse Engineering or Design Analysis sometimes notated 'Tear Down' of microcircuits is not new and has been an activity pursued across the chip world for 30 years or more. Reverse Engineering can extract circuitry; although an en-mass RE of an Intel i7 core would be economically dubious, partials are quite common. Why? well patent infringement is the usual quoted reason but also just to identify and copy specific functionality. Material use, and Dopant levels can be measured at the device level especially as most of the processes are published documents so its not necessary to identify all the materials. Papers research, allied with FIB, EM. SEM, et al in microscopy can RE a device only depending how much time and money you have to thro' at the device

Note that the RNG quoted in the Theoretical Tampering is not a RNG but a pseudo random number generator. There are multiple research papers from across the world on the behavior and implementation of PRNG, none of them particularly flattering to the efficacy of the 'random' output. One author pointing out that PRNGs have a certain level of determinism....... and that the output is a function of the seed.

If you want a genuine RNG prepare to work hard, and check well, implementation is non trivial, will be classified as armaments and require end user certificates prior to shipping, and all before acceptance of an output.

Built in Self Test test vectors whether implemented or not, or vectored into JTAG are not proof of subversion that is just paranoia, RNG and PRNG are non trivial to accurately test at the output, however if the design topology can be tested for design compliance including stuck at zero or stuck at one the logic will appear to be non functioning, and whether it is a transistor or a logic gate, the resultant will be non functioning logic as far as the JTAG/BIST or Chip Probe test is concerned and the device will be in the reject bin. If the JTAG/BIST or probe test passes the test vector it is reasonable to assume correct functionality, if the supposed tampering has taken place then a whole mess of stuff has too have been changed -that way madness lies

RobertT • October 24, 2013 10:02 PM

@ John Langman

Sensible comments.

Not sure if the Intel dig was aimed at me, for the record I've never worked for Intel or any of their affiliates. I've worked on one product that was designed / fabed exclusively for Intel, both parties were very happy with the project, so there's no bad blood there at all. From memory the only slightly derogatory comment that I've ever made about Intel wrt chip design was that they are generally not very skilled at analog or RF IC design...I think my position is well supported by their lack of success with past efforts in the Analog/RF space, my opinion is based mainly on private discussions with other Analog IC designers.

Wrt TRNG's are you sure embedded TRNG's are considered Armaments, I know I've put simple TRNG circuits on everything from RFID tags to Cell phone chip sets but I've never heard of a requirement for registration or export licenses. btw very simple TRNG circuits can give very good quality output results (even the cheapest RFID tag TRNG passed all Die-Hard tests)

WRT Jtag / Bist for RNG's, there is a catch22 that ideally the core TRNG circuit should have as little external controllability as possible. This is done so that the start-up / load state cannot be influenced even if the TEST / JTAG mode is somehow operationally selected. direct Observability of the TRNG output can also be potentially problematic, especially if the real secret sauce is in the algorithmic "entropy" stage.

johnlangman@consultant.com • October 27, 2013 3:39 PM

Any true rng is listed as armaments and will be subject to export controls, in the uk I purchased ATT rngs and had to supply end user cetificates and comply with export regulations. If your system provides pseudo rng then it will not be a controlled device. However there is a large body of work showing that prng are deterministic and that output 'is' a function of the seed. Note that the seed source itself is not without determinism. That is not to belittle prngs just saying that the 'theoretical' paper choose rng as a deliberatly provacative implementation and I challenge some of their assumptions. With 40 years in microelectronics and some 10 in RE I would like more robustness,, less paranoia,, and more clarity.


Whiskers in Menlo • November 16, 2013 11:03 PM

Bruce said it -- the issue is a lack of trust.

If you do not trust some hardware or software function
the obvious solution is to replace the parts you do
not trust.

Today I would look hard at external USB hardware...
Consider password safe living on a USB stick but
a smart device. Invest $50 in a Beaglebone black to
see what I mean. Memory, CPU, ability to load any
OS you select, ability to load any SW you care to load.
Disconnect it or set it to replace /dev/random. In a
year or so there will be USB3 devices although network
devices may still be quicker.

In defense of Intel, a number of benchmark programs depend
on random numbers and their (Intel) hardware is going to be faster
than a quality software solution. Winning benchmarks is the
job of a lot of folk and in a random selection of Intel folk will find
someone that will make this type of statement.

For those that have serious needs for unique impossible to guess
random numbers they should promptly find multiple options unique
to their site.

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

← Tom Tomorrow from 1994 The Limitations of Intelligence →

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of IBM Resilient.