Insecurities in the Linux /dev/random

New paper: “Security Analysis of Pseudo-Random Number Generators with Input: /dev/random is not Robust, by Yevgeniy Dodis, David Pointcheval, Sylvain Ruhault, Damien Vergnaud, and Daniel Wichs.

Abstract: A pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform. A formal security model for PRNGs with input was proposed in 2005 by Barak and Halevi (BH). This model involves an internal state that is refreshed with a (potentially biased) external random source, and a cryptographic function that outputs random numbers from the continually internal state. In this work we extend the BH model to also include a new security property capturing how it should accumulate the entropy of the input data into the internal state after state compromise. This property states that a good PRNG should be able to eventually recover from compromise even if the entropy is injected into the system at a very slow pace, and expresses the real-life expected behavior of existing PRNG designs. Unfortunately, we show that neither the model nor the specific PRNG construction proposed by Barak and Halevi meet this new property, despite meeting a weaker robustness notion introduced by BH. From a practical side, we also give a precise assessment of the security of the two Linux PRNGs, /dev/random and /dev/urandom. In particular, we show several attacks proving that these PRNGs are not robust according to our definition, and do not accumulate entropy properly. These attacks are due to the vulnerabilities of the entropy estimator and the internal mixing function of the Linux PRNGs. These attacks against the Linux PRNG show that it does not satisfy the “robustness” notion of security, but it remains unclear if these attacks lead to actual exploitable vulnerabilities in practice. Finally, we propose a simple and very efficient PRNG construction that is provably robust in our new and stronger adversarial model. We present benchmarks between this construction and the Linux PRNG that show that this construction is on average more efficient when recovering from a compromised internal state and when generating cryptographic keys. We therefore recommend to use this construction whenever a PRNG with input is used for cryptography.

Tags: , , ,

Posted on October 14, 2013 at 1:06 PM • 121 Comments

Comments

Adrian Ratnapala • October 14, 2013 1:47 PM

If there is a vulnerability (especially an academic sounding one like this) then I am not surprised it comes via the entropy estimation. Ted Tso claims (and I believe) that it’s just a *cking hard thing to do.

So the question is, how can we do better? Since I doubt entropy estimation is going to get much less unreliable.

Samuel Alexik • October 14, 2013 1:52 PM

It is good that someone do an analysis.
What if this new construction of PRNG will insert an hidden insecurities into GNU Linux kernel PRNG ?
The current situation plays with us but also plays against. We might be now more open, to fast fixing insecurities than ever. Same claim can be applied to this post, because new construction is better than actual one:-) , etc……

Jarrod Frates • October 14, 2013 2:12 PM

Adrian: Implementing a solution that provides true randomness would be the best way to handle it. VIA’s C7 processors had this by measuring electrical noise in the CPU, but they’re increasingly hard to find. Given that a complete CPU/motherboard combo could be had for less than the cost of an Intel CPU, I don’t think it would cost much to add it to new CPU architectures, even if VIA got patent royalties.

Brian M. • October 14, 2013 2:27 PM

If you are concerned about random numbers in your computer, then you need a hardware random number generator. Do a Google search for hardware random number generators. Some are on USB, some are PCI, and there’s one that plugs into a serial port. If you are cheap, then you could point a camera at a lava lamp or a plasma globe. Maybe the scene outside of your window is enough for random number seeds.

Take a look at Behind Intel’s New Random-Number Generator to see what Intel did for their processors.

The point of the paper is that /dev/random can be attacked, and done so successfully. Intel has been putting a random number generator in chips since at least 2004 (Intel random number generator-based true random number generator, Intel 815 chipset & ISD) with no detectable problems. I’ve found references to AMD HRNG back to 2002.

Honestly, I have no idea why anybody’s kernel would ignore any available hardware random number generator. It’s a complete no-brainer to use it.

Jockular • October 14, 2013 2:37 PM

Translation? that the random number generator in Linux has been weakened? does not perform robust encryption? – thnx in advance!

Bystander • October 14, 2013 2:37 PM

@Jarrod

Electrical noise within the CPU is partially deterministic. It depends on the code executed and the quality of the supply and changes with the age of e.g. electrolytic capacitors, so and the random generator would not pass the NIST test.

Thermal noise, radioactive decay are considered safe.
If you design a hardware random generator on a motherboard, you must be extremely careful supply-wise.

Chris • October 14, 2013 2:42 PM

@Brian M:
How do we know we can rely on Intel’s HRNG? How do we know they don’t reduce entropy or do some other fancy things? With open source software (Linux Kernel) we know what we do, even if it is not perfect.

Brian M. • October 14, 2013 2:52 PM

Rant:

It bugs me to see headlines like, “Researchers can backdoor hardware chips,” etc. It’s like reading, “Researchers can cause Boeing 747 crash by replacing jet engines with engines from a 1971 Ford Pinto in mid-flight!” No, really???

While the paper looks like a good paper, there’s some things that really point to a “well, duh, people!” response. “If I rootkit your machine, I can screw with your random number generator.” Well, duh! “There’s a bug in OpenSSL!” Well, duh! “We ignored the available HRNG in favor of our cool algorithm, and there’s a problem with the entropy.” Well, duh!

Installations are supposed to optimize themselves for the available resources. So why is it that the HRNG on the motherboard is ignored when it’s available? That is the question that should be asked!!

Michael Moser • October 14, 2013 2:59 PM

If I understand correctly then /dev/urandom is only pseudo random; Using /dev/random directly is impractical, because you usually do not have enough entropy at a given moment in time; reading from /dev/random can block for some time;

I guess the right way is using /dev/random in order to seed something like SHA1PRNG (repeatedly computing SHA1 of the seed)

Alex S • October 14, 2013 3:18 PM

This seemed like a great hardware answer, but they don’t seem to be able to ship them:

http://www.entropykey.co.uk/

It’s hard to justify something expensive if you don’t have a specific use case, but I’d definitely buy a cheap hardware RNG if it were available.

Brian M. • October 14, 2013 3:21 PM

@Chris:
How do we know we can rely on Intel’s HRNG?

How many tests over the years have shown that Intel’s HRNG chips are good? The hits for that are on the first page of a Google search, going back to 2004. Nine years of tests! Also, read up on what Intel and AMD have done to produce good HRNG chips for your use. If you have, or anybody else has, a link to a paper that shows an AMD or Intel HRNG being faulty, please post it!

Let me put it another way: if you don’t have the math to test the numbers, and you don’t trust anybody, what are you going to do?? You are screwed.

AFAIK, none of the HRNG manufacturers list the conditioning code for their systems, so all of them are closed source. That means that the only thing that can be done is statistical analysis, like Diehard and DieHarder. Check the Wikipedia page for pointers to get started.

Really, some of this stuff starts sounding like, “The NSA has sabotaged quantum physics!” Sheesh.

@adf:
Random numbers are testable. Point me to a paper that says, “This [Intel | AMD | Via | blah blah] HRNG is worse than my kid sister’s 8-bit cyclic XOR.” A backdoor is like the one on the DLink routers. That is a real backdoor!

Tim • October 14, 2013 3:26 PM

@ maxCohen

That cartoon confuses two different theories of value. Intrinsic values would be Plato, not Ayn Rand.

InsecuritanT • October 14, 2013 3:28 PM

If I remember correctly, /dev/urandom doesn’t know if it has sufficient entropy to hand out pseudo random numbers but if called it hands out what it has anyways. So if you were running a server install with no physical interaction and were to use it as a source you could have serious RN problems.

The cloudflare blog recently talked about the problems they found with /dev/random and how they are mitigating it with hardware TRNG.

I don’t understand why Linux just doesn’t copy the *BSD yarrow model. The paper says they are not sure of a practical attack but they aren’t the NSA, who probably figured out /dev/[u]random was crippled long ago.

Nick P • October 14, 2013 4:07 PM

@ Brian M

“How many tests over the years have shown that Intel’s HRNG chips are good? The hits for that are on the first page of a Google search, going back to 2004. Nine years of tests! Also, read up on what Intel and AMD have done to produce good HRNG chips for your use. If you have, or anybody else has, a link to a paper that shows an AMD or Intel HRNG being faulty, please post it!”

I could come up with a way to subvert that where black box tests think it’s random and I’m neither a cryptographer nor a hardware expert. Seeing as NSA has been subverting US entropy sources, then they could quite easily do something to the processing where they could break it and others couldn’t. A black box test wouldn’t prove anything in that case.

“Let me put it another way: if you don’t have the math to test the numbers, and you don’t trust anybody, what are you going to do?? You are screwed.”

That’s not the situation. We don’t trust companies with a high likelihood of working with the NSA or who are using unjustifiably poor crypto. Intel seems to be in one boat, Linux /dev/random apparently in the other. That leaves plenty of sources for hardware and software to generate good random numbers. Just can’t use these few.

Jack Bates • October 14, 2013 4:19 PM

@Jarrod :

I’ve use the VIA C7 before.

It is not well-known, but the Raspberry Pi has a 1Mb/s HWRNG on-board.

The circuitry is not open-source, however.

CHEERS

Jack Bates • October 14, 2013 4:22 PM

@Brian :

The noise on an unsaturated ICCD (web chip) is generally a pretty good source of entropy. Compressing this noise with a cryptographic hash function yields very good entropy with several $5 webcams that I’ve tried this with.

CHEERS

Jakub Narebski • October 14, 2013 4:46 PM

Errr… doesn’t Linux kernel use hardware random generator (the RAND instruction in Intel chips, though supposedly NSA-weakened) as one of sources of entropy?

Clive Robinson • October 14, 2013 5:11 PM

@ Adrian Ratnapala,

    If there is a vulnerability (especially an academic sounding one like this) then I am not surprised it comes via the entropy estimation. Ted Tso claims(and I believe) that it’s just a *cking hard thing to do

Actualy it’s a bit more than “*cking hard thing to do” it can easily be shown to be in effect impossible to do by any resource limited entity, irrespective of what statistical tests you come up with (both diehard and dieharder are a bit of a joke these days as many fully determanistic systems pass them with little difficulty).

Basicaly if you take any old garbage generator such as say a plain integer counter, you can then “whiten it” with a basic crypto function such as a block cipher or hash algorithm. The result will pass any of the “usual suspect” “not random” witness tests and thus appear to be sufficiently random for “crypto use”.

And as has been mentioned on this blog before hardware engineers that fail to meet “Diehard” with their basic TRNG source can make it meet diehard by simply whitening it with AES etc which may also be built into the chip (as is the case with Intel).

Unless the chip manufacture provides you with access to the output of the raw source generator so you can test it, then to be honest I would not trust it as I would not be able to verify it functioning correctly. Intel have consistantly failed to provide access to the raw source therefore I for one am not going to bet my life on their generator nor would I bet the lives of my loved ones or others I know.

The reason why “entropy estimation” is so hard is in part due to the definition of “random” and in part because we know no way to measure what qualifies as a “random sequence”. Thus you could say the output of any entropy generator is the sum (or in some cases the product) of,

1, Real Entropy.
2, Faux Entropy.
3, Detectable determanism.
4, Detectable bias.

What you are after is (1) the real entropy in your physical source left after you have removed (3) the determanism and (4) bias that you have been able to detect and remove. Unfortunatly that leaves a lot of (2) faux entropy which you cannot detect and remove for a very large number of reasons.

Faux entropy consists of many things including the outputs of complex processes and chaotic processes inherant as side effects of the design process. One example of which is to have two free running oscillators one running at high speed into the D input of a D-type latch and the slower one going into the clock input of the D-type. Close in observation of the Q output of the latch shows both metastability and what appeares as random behaviour. However observation at a slower time base shows “bunching” patterns that corespond on the timebase to the lowest frequency difference of the two oscilators. And in fact if driven into a suitable counter circuit will produce a sinusoudal output count… Taking what is in effect an FFT of the random source output will show up this determanistic wave, only if it is within the FFT Window range…

Thus great care should be practiced on estimating what part of such a signal is real or faux entropy.

Which brings me onto your question of,

    So the question is, how can we do better? Since I doubt entropy estimation is going to get much less unreliable

The simple answere is “nothing” unless we are prepared to use increasing levels of computation to run more “witness to non randomnes tests”.

What we can do on the practical side is run more “faux generators” against our “entropy pool” in a way that would make any determanistic process hidden by an adversary next to impossible to see. One such way is to take the output of the OS RNG through what is in effect a blind encryption algorithm.

Flup • October 14, 2013 5:27 PM

If you have a laptop (not sure about desktops) that has TPM, you can make use of the pRNG in it. See http://domsch.com/blog/?p=107

You could probably also use those SDR dongles you can get on Ebay for 10 bucks or so as another source of entropy. Use a GNUradio program to look at the entire radio spectrum from 100MHz to 850MHz or so. That should be random enough for anybody.

FreeBSD user • October 14, 2013 5:42 PM

Linux /dev/random has came up a few times here, but I haven’t seen much discusstion of the *BSD model. Does it seem that *BSD /dev/random is “robust”?

Toni • October 14, 2013 5:48 PM

@Jack Bates ~

“It is not well-known, but the Raspberry Pi has a 1Mb/s HWRNG on-board.”

Well thank you for that, sir. Hmm – 1Mb/sec is quite a bit faster than the Simtec Entropy Key, and a whole RPi is actually cheaper than the Simtec (which you can’t get anyway right now), too.

I have an RPi on my network – I’m going to have a whack at installing the tools and trying to use the RPi HWRNG across my network for my other Linux boxes. Fun little project. Oughtta work…

Toni

Theodore Ts'o • October 14, 2013 6:08 PM

So I’m the maintainer for Linux’s /dev/random driver. I’ve only had a chance to look at the paper very quickly, and I will at it more closely when I have more time, but what the authors of this paper seem to be worried about is not even close to the top of my list in terms of things I’m worried about.

First of all, the paper is incorrect in some minor details; the most significant error is its (untrue) claim that we stop gathering entropy when the entropy estimate for a given entropy pool is “full”. Before July 2012, we went into a trickle mode where we only took in 1 in 096 values. Since then, the main way that we gather entropy, which is via add_interrupt_randomness(), has no such limit. This means that we will continue to collect entropy even if the input pool is apparently “full”.

This is critical, because secondly their hypothetical attacks presume certain input distributions which have an incorrect entropy estimate — that is, either zero actual entropy but a high entropy estimate, or a high entropy, but a low entropy estimate. There has been no attempt by the paper’s authors to determine whether the entropy gathered by Linux meets either of their hypothetical models, and in fact in the “Linux Pseudorandom Number Generator Revisited”[1], the analysis showed that our entropy estimator was actually pretty good, given the real-life inputs that we are able to obtain from an actual running Linux system.

[1] http://eprint.iacr.org/2012/251.pdf

The main thing which I am much more worried about is that on various embedded systems, which do not have a fine-grained clock, and which is reading from flash which has a much more deterministic timing for their operations, is that when userspace tries to generate long-term public keys immediately after the machine is taken out of the box and plugged in, that there isn’t a sufficient amount of entropy, and since most userspace applications use /dev/urandom since they don’t want to block, that they end up with keys that aren’t very random. We had some really serious problems with this, which was written up in the “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices”[2] paper, and the changes made in July 2012 were specifically designed to address these worries.

[2] https://www.factorable.net/paper.html

However, it may be that on certain systems, in particular ARM and MIPS based systems, where a long-term public key is generated very shortly after the first power-on, that there’s enough randomness that the techniques used in [2] would not find any problems, but that might be not enough randomness to prevent our friends in Fort Meade from being able to brute force guess the possible public-private key pairs.

Speaking more generally, I’m a bit dubious about academic analysis which are primarily worried about recovering from the exposure of the state of the random pool. In practice, if the bad guy can grab the state of random pool, they probably have enough privileged access that they can do many more entertaining things, such as grabbing the user’s passphrase or their long-term private key. Trying to preserve the amount of entropy in the pool, and making sure that we can extract as much uncertainty from the system as possible, are much higher priority things to worry about.

That’s not to say that I might not make changes to /dev/random in reaction to academic analysis; I’ve made changes in reaction to [2], and I have changes queued for the next major kernel release up to make some changes to address concerns raised in [1]. However, protection against artificially constructed attacks is not the only thing which I am worried about. Things like making sure we have adequate entropy collection on all platforms, especially embedded ones, and adding some conservatism just in case SHA isn’t a perfect random function are some of the other things which I am trying to balance as we make changes to /dev/random.

Theodore Ts'o • October 14, 2013 6:35 PM

A few more comments. First of all, I wasn’t aware of the Inria paper mentioned above — thanks for mentioning it. The Inria paper, although published in September 2012, is analyzing a kernel which dates before the changes made in July 2012. As I mentioned above, these changes were inspired by the “Mining your P’s and Q’s” paper, for which the authors very kindly supplied me with a pre-print before they published it in the 2012 Usenix Security conference. We now collect entropy using the fine-grained CPU counter on against every single interrupt, and collect that in a “fast mix” pool, and then periodically mix from that down into the input pool. This was done for speed reasons, but it also provides a Yarrow-like “catastrophic reseed” effect.[1] We are extremely conservative, assuming only a single bit of entropy for every 64 interrupts (where we sample the CPU counter, the jiffies counter, and the IP of the interrupt and mix all of the above into the fast pool).

[1] Note that even before the July 2012 changes, we have had a Yarrow-like catastrophic reseeding in our design between the Input pool and the output pools. I take good ideas where I can find them. 🙂

There have been some other changes made to enable better randomness on those platforms which do not have CPU counters which just hit mainline for the next 3.12 release, and I’m working with the MIPS maintainer and some of the other non-x86 arch maintainers on that front.

We also do mix in the RDRAND if it is available, on the theory that even if it has been trojan’ed by the NSA, it doesn’t hurt to mix it in, and it might help. So the use of RDRAND versus /dev/random or /dev/urandom is not an either-or proposition. These days I’m actually much more worried about non-x86 platforms which do not have either RDRAND or a CPU cycle counter register, and where you are often booting off of flash and where the userspace often tries generating a long-term public key pair very shortly after the machine is first taken out of the box and plugged in.

Finally, I have made a number of changes over the years, either in reaction to comments made by academic papers, or when I see good ideas I can steal/borrow to make /dev/random better. So when people point at papers, please remember that most of these analysis are done at a particular point in time, and that I do make changes in response to these analysis, at least if someone has called them to my attention.

Nick P • October 14, 2013 7:06 PM

@ Theodore

I appreciate you responding with plenty of useful detail. Good to hear the state of the Linux RNG’s from the guy maintaining them. 🙂

Peter Barnhart • October 14, 2013 7:16 PM

Thanks for pointing out this important paper.
Couple of comments:
1) If you’re looking for true randomness, consider almost any photo posted on apod.nasa.gov. Convert to bitmap, use any bogus PRNG to select bytes from the image.
The result will be plenty random, will not be uniform but that can be fixed.
2) It seems to me that entropy is more a function of the adversary’s knowledge than
any internal state info. If you have a megabyte of truely random bits, its entropy is 10^6 bits, but if the bad guy knows what they are, you have zero entropy.

Dirk Praet • October 14, 2013 7:44 PM

@ Theodore

Thanks for gracing this blog with your enlightening comments.

These days I’m actually much more worried about non-x86 platforms which do not have either RDRAND or a CPU cycle counter register …

To the best of your knowledge, are any of the available linuces for the ARM-based Raspberry Pi (Arch, Pidora, Raspbian) using its on-board HWRNG ?

thoth • October 14, 2013 8:57 PM

I doubt the implementers of /dev/random and /dev/urandom are cryptographers like the authors of these papers and thus of course those PRNGs are not crypto-suitable at all. I really doubt the creators of /dev/random and /dev/urandom had the intention of having their PRNGs robust enough for cryptography. Maybe they just want a workable PRNG and that’s all they want.

Isn’t it so obvious that if you want a crypto-strength PRNG, you should be looking into using something proven and made for crypto use (e.g. Yarrow and Fortuna by Schneier) rather than just taking the default PRNG as it’s common knowledge that the normal PRNGs bundled with programming SDKs and built into OSes are not good enough.

The authors of the paper may want to contribute their PRNGs to the *Nix community if they think the defaults are bad choices by approaching the kernel mailing list.

Theodore Ts'o • October 14, 2013 9:38 PM

@thoth,

I’m the original implementor of the /dev/random driver, and it was indeed meant for cryptographic uses. I collaborated with Colin Plumb, who designed the random number generator in the original PGP code base. The /dev/random driver was first implemented in 1994 (predating the Yarrow design by five years), and I created it because back in 1994, no operating system had anything like it, and programs like PGP had to sample keyboard stroke timing in user space, and only while it was running.

So Linux’s /dev/random driver was the first in-kernel CSPRNG that continuously sampled entropy from the hardware in an entropy pool. It was implemented with my having looked at many other user-space random number generator, and as I said, I recruited help from people like Colin. Over the years, I have also made changes based on comments and criticism from academic papers, and other sources. For example, when Bruce published Yarrow, I did take a look at it and take the idea of catastrophic reseeding and integrated it into Linux’s /dev/random.

Marsh Ray • October 14, 2013 11:03 PM

@Theodore Mad props to you for giving and taking with the comments here.

Now if only I could convince you guys to block /dev/urandom until it’s seeded and then make /dev/random a link to urandom. AIUI, that’s the design decision made by several BSDs and I think it’s a good one.

Gweihir • October 14, 2013 11:06 PM

Pretty much unreadable. My publishing experience is mostly with conferences that have a 6 or 8 page limit and force you to get to the point. These authors here seem to believe the more difficult to read the paper is the better.

thoth • October 14, 2013 11:34 PM

Ah.. it’s good to know much research was put into the /dev/random for cryptographic functions. Thanks for the many clarifications you have made on this post.

Mike the goat • October 15, 2013 12:06 AM

Theodore: is it true that you designed the CSPRNG to use SHA to avoid the crypto export issues of the 90s?

Bhima • October 15, 2013 12:42 AM

@ Toni – I have been using Entropy Broker to pool, mix, and redistribute entropy from multiple sources on my network, including a Raspberry Pi.

Honestly it mostly works but it’s a bit brittle and I’ve run across enough bugs that I’m not completely confident with it. Unfortunately the author is too busy to really maintain the project and it’s a bit beyond my skills to fix the things that I’ve found wrong or suboptimal with it.

If anyone knows of alternative tools which do similar things, I’d love to hear about them.

Pauli • October 15, 2013 12:42 AM

In a previous life making embedded routers, we were concerned about the lack of entropy for exactly the reasons Theodore Ts’o mentions above. My solution was to add a stage to fulfilment that created a dump of some pseudo random data (from the fulfilment machine’s /dev/urandom from memory) which was stored on the device and used to seed the kernel RNG on boot. This random dump was written on shutdown with new randomness from the kernel. The end result is some entropy would distinguish different units.

MarkH • October 15, 2013 12:54 AM

@Adrian Ratnapala:

Look up the Fortuna PRNG scheme devised by Bruce and his colleague Niels Ferguson.

One of its premises, is that realistic entropy estimation is impractical. Accordingly, Fortuna is designed to utilize various inputs without any estimation of their absolute or relative degrees of entropy.

Clive Robinson • October 15, 2013 2:33 AM

@ Pauli,

    My solution was to add a stage to fulfilment that created a dump of some pseudo random data… which was stored on the device and used to seed the kernel RNG on boot.

In FMCE production adding entropy to the product at the “end of line” is realisticaly the only way to do it. Especialy when the need for some products to have large amounts of entropy is a requirment it needs to be sourced from a reliable source (which can be a difficult ask in many FMCE Production environments)

I first had to fight the battle back last century when designing cordless phones the Korean side developers were convinced they could do it using a determanistic algorithm and the “cold start” entropy of an 8bit microcontroler… They went ahead over my objections and surprise surprise rather than get atleast 20bits of entropy required by the customer they only got around 6bits maximum. On being tasked by the MD of the company to find out what was going wrong I identified that the “oh so clever algorithm” could only give a maximum of 8bits of entropy no matter what the “cold start” entropy was.

Unfortunatly due to restrictions (PCBs etc had been manufactured) I was very limited in my options so went for a compromise of making the production line person press a button wait for a LED to illuminate and press another button and loop through a couple of times and generate some entropy from the fast counter in the CPU (no it did not give the 20bits but it was close enough to get through both the customers goods inwards test and not to cause returns issues).

I coined a phrase back then of “If you don’t have time for entropy then you don’t…” loosly based on the old RF engineering maxim “Amplifiers do and oscillators don’t…”

Luck • October 15, 2013 3:01 AM

@Theodore Ts’o: “Over the years, I have also made changes based on comments and criticism from academic papers, and other sources.”

Thank you very much for taking time to comment here.

Could you comment on the choice of XOR, cryptographically weak, as pointed out by @Mike the goat: “the Linux PRNG (see http://lxr.free-electrons.com/source/drivers/char/random.c …) when running on supported hardware – simply XOR’s the RdRAND output with its output stream” https://www.schneier.com/blog/archives/2013/10/friday_squid_bl_394.html#c1835591

Could you optionnaly answer to @ddr: “RdRand is used exclusively for memory address randomization in the Linux kernel, so technically an adversary could defeat ASLR and know exactly what the memory layout is.” https://www.schneier.com/blog/archives/2013/09/my_new_gpgpgp_a.html#c1713647 ? That page also lists other places were rdrand was the only source of randomness.

Curious about XORing RDRAND at the end • October 15, 2013 3:35 AM

Theodore, thanks very much for your comments shedding more light on the kernel’s RNG.

I’m also interested in whether you’ve considered using the entropy from a hardware RNG like RDRAND as input to the entropy (just like all the other gathered entropy input), instead of treating it specially as a final XOR on the result. The latter (current) approach seems obviously risky if one assumes the CPU has been compromised.

Even if one supposes that it’s ridiculously unlikely that the CPU might evilly notice that it’s XORing the RDRAND result with something and intentionally & indetectibly give a specific result in certain circumstances instead of honestly XORing an honest RDRAND result, wouldn’t it make more sense (and make the algorithm simpler & more uniform) to treat ALL the gathered entropy in a more uniform way, instead of treating the CPU’s RDRAND in a different special way where this XOR/RDRAND is the very last thing to influence the output?

Wesley Parish • October 15, 2013 4:37 AM

@Peter Barnhart

So you’ve read Stanislaw Lem’s His Master’s Voice too? Small world!

I’d like to get my random numbers from the Big Bang microwave background; 360 degrees per second of arc by 360 degrees per second of arc, assigning values of 1 or 0 to each second’s value depending on whether or not its value was above or below a random value that would change pseudo-randomly. Direction of sampling also assigned pseudo-randomly.

It’s not practical at this point in time, unfortunately. Your idea is practical.

speedie • October 15, 2013 5:01 AM

@Theodore

It’s good to see you really follow up with everything that concerns your baby 🙂
I feel reassured when I see the level of your dedication to your ( very important ) work on /dev/random .

Aspie • October 15, 2013 5:47 AM

Low-budget, easy to build, perhaps a moderately good
<a href=”http://web.jfet.org/hw-rng.html>source.

GentooAndroid • October 15, 2013 5:56 AM

@speedie: “please , please , tell me you’re using lynx on a phone :)”

I actually did, and will do that again.

Aspie • October 15, 2013 6:12 AM

@speedie
Nope, it’s far worse than that. I’m too busy (read lazy/disinterested) to get X11 working on my netbook. (Where I do have X11 working I prefer dillo.)

I find lynx browsing slows me down enough to read everything and follow links judiciously. Plus it’s quickly apparent if a site is 99.999% hype/ads and 0.001% content.

Ahhh, I remember PRESTEL … and the machine-gun teletype on the RSTS/E system …

Winter • October 15, 2013 6:17 AM

@Aspie
“(Where I do have X11 working I prefer dillo.)”

Where can I find dillo nowadays? I liked it a lot but now cannot find it anymore.

Czerno • October 15, 2013 6:42 AM

@Mr Ts’o : kudo’s for your work and dedication.
A question, please : many X86 platform chipsets have provided
a HW random number generator for years. Does /dev/random use them, in particular (being a user of less-well known SiS products) does Linux use the HWRNG included in SiS PCI chipsets, similar to but programmatically different from intel ones?

RDSEED • October 15, 2013 7:36 AM

@Clive Robinson

<

blockquote>Intel have consistantly failed to provide access to the raw source therefore I for one am not going to bet my life on their generator nor would I bet the lives of my loved ones or others I know.

<

blockquote>

The forthcoming RDSEED instruction might address that:
http://software.intel.com/en-us/blogs/2012/11/17/the-difference-between-rdrand-and-rdseed
http://en.wikipedia.org/wiki/Broadwell_%28microarchitecture%29

It is intended to be compliant with NIST SP800-90B and SP800-90C

“The numbers returned by RDSEED are referred to as “seed-grade entropy” and are the output of a true random number generator (TRNG)”

This looks to be the same TRNG source that seeds RDRAND.

Backdoor theories aside, it could be used as one of the sources for entropy, mixing or XOR-ing it in with entropy from other non-US-based hardware RNGs.

johny • October 15, 2013 8:17 AM

@Curious about XORing RDRAND at the end

you have wrong assumption that it is a problem to XOR random value and RDRAND “maybe not so random” value. It is not.

RonK • October 15, 2013 8:34 AM

@ johny

you have wrong assumption that it is a problem …

He explicitly states that the concern is with a compromised CPU, from which I infer he means a CPU whose microcode has been subverted to look for the particular instruction sequence RDRAND followed by XOR, and do something entirely different.

If that is his assumption he’s probably correct but the vulnerability is easily overcome.

Theodore Ts'o • October 15, 2013 8:50 AM

@Luck:

Could you comment on the choice of XOR, cryptographically weak, as pointed out by @Mike the goat: “the Linux PRNG (see http://lxr.free-electrons.com/source/drivers/… …) when running on supported hardware – simply XOR’s the RdRAND output with its output stream”

First, this is changing in the set of changes being queued for upstream. http://git.kernel.org/cgit/linux/kernel/git/tytso/random.git/commit/?h=dev

Secondly, the the primary reason for this change was not to indulge the paranoid fanatasies of those who are concerned that the Intel CPU might be able to detect the XOR in the instruction pipeline, and then use that to gimmick the value placed into the registers. If you are think that level of gimmickry might be in the Intel CPU, then you should find another CPU. What if the AESNI instructure is hiding the key someplace where it can leaked out by moduling packet transmission delays using the onboard ethernet interface? Ultimately, the theory that RDRAND might have gotten gimmicked depends on the fact that it is a standalone unit that might be easily modified in such a way that it might not be caught by Intel’s internal auditing — especially since RDRAND is documented as using AES as the final whitening step. But if the adversary is corrupting the instructure decode and execution pipeline handling, (a) it’s much more likely that this might trigger falsely, and cause user-visible program misbehaviour/crashes, and (b) it’s much more likely someone who wasn’t (hypothetically) suborned by the NSA would notice the tampering.

The main reason for making this change was so that RDRAND output would get mixed into pool as part of the extract entropy’s feedback step. This imrpoves /dev/random against theoretical forward security attacks, and also happens to place the RDRAND xor step before the final SHA transform, which helps to mollify the tin foil hat crowd.

Could you optionnaly answer to @ddr: “RdRand is used exclusively for memory address randomization in the Linux kernel, so technically an adversary could defeat ASLR and know exactly what the memory layout is.”

There are multiple API’s which create random numbers in the kernel, which trade off different levels of cryptographic strength with speed. This ranges everywhere from a completely non-cryptographic PRNG, to something to interfaces that try to return the closest approximation we have to “true randomness”. In the case of ASLR, yes, this is an interface which is designed to return randomness with very low overhead. And that’s because the cryptographic strength requirements of ASLR is quite different from that required for generating a session key, which in turn is quite different from that required for generating a long-term public key.

Consider that an attack that tries to subvert ASLR means that you’re already have code running on the target computer. Given that the NSA is purchasing zero-day exploits from Grey Hat and Black Hat vendors, there are plenty of other ways someone who has already managed to exploit a buffer overrun attack can carry out a privilege escalation attack. Also consider that if there is a hypothetical way that RDRAND can be subverted, putting it in a payload for a Stuxnet-like viral attack is extremely dangerous, since it’s much more likely an anti-virus company might capture the payload, analyze it, and discover some strange algorithm that apparently is trying to anticipate RDRAND output and use that to subvert ASLR…

Another example of these sorts of tradeoffs is the fact that we use a very weak (but fast) crypto hash as part of the TCP sequence number generation. We can’t use a full-on random number generator because of some of the requirements of how the TCP sequence number works — see the discussion in RFC 1948 for more details. But if we rekey every five minutes, we don’t need a very strong crypto algorithm, since the randomness is not being used for data encryption, but only to protect against TCP hijacking attacks by someone who is off the network path between the communicating parties. (To protect against a man-in-the-middle attack by someone on the network path, you need full on crypto, done in the userspace, which is another reason why we can afford to scrimp on the crypto used for TCP sequence number generation.)

The bottom line is that there are a huge number of engineering tradeoffs that need to be made here. It’s not just a matter of saying you want the mostest amount of crypto. Consider that way back when, the US Government spec’ed multiple levels of OS security in the “Orange Book” specification, from A1 security, to B2 security (Multics), B3 security (VMS), to C2 security (Unix with security extensions that were ultimately a complete commercial failure :-). There was maybe one OS that attempted to hit the A1 security parameters, but its performance was so Gawd-awful that it didn’t get much traction at all. And the “C2 by ’92” effort to add sufficient amounts of security features to Unix, including completely destroying the concept of setuid root programs, was a complete and total commercial failure.

@Czerno

A question, please : many X86 platform chipsets have provided
a HW random number generator for years. Does /dev/random use them, in particular (being a user of less-well known SiS products) does Linux use the HWRNG included in SiS PCI chipsets, similar to but programmatically different from intel ones?

I’m not certain of the SiS chipset per se, but the architecture used in Linux is that for these PCI-bus accessible random number generators, they are supposed to be exported to userspace via /dev/hwrandom, and then we use a userspace rngd whic his supposed to do quality control checks, and set policy such as estimating how much entropy might be contained in N bytes of data read in from /dev/hwrandom, and then feed that into /dev/random. You can either do this via a non-privileged write into /dev/random, which does not bump the entropy estimation, or there is a privileged ioctl which can be used that atomically will transfer N bytes of randomness into the entropy pools and at the same time bump the entropy estimation counter by M bytes (where M <= N).

In theory you could also write a userspace program that accesses the TPM chip (which may require access to TPM PIN’s before you are able to access it, which is another reason why this really needs to be done in userspace), and then use the on-board HWRNG in the TPM to feed entropy into /dev/random. No one has done this, but it’s certainly something you can do.

Yet another thing you can do is to take some randomness, or some secret, and just cat it into /dev/random. Here you need to be a bit careful, since if the kernel has been trojan’ed, or if /dev/random has been replaced by a named pipe by some bad guy, feeding your long-term public key into /dev/random might not be the safest thing in the world to do. But the point remains that as a non-privileged user, if you want to be extra paranoid before generating a GPG key, you can always roll a number of dice, and cat those numbers into /dev/random, and that will be mixed into the entropy pool. It can’t hurt, and against certain attacks, it could certainly help.

Joe Landman • October 15, 2013 9:17 AM

I found the “radioactive decay considered safe” interesting. If we subject the decaying atoms to a steady stream of some relevant ionizing radiation, depending upon the decay pathway, we could easily catalyze faster or slower emission. Hence effectively “hacking” the underlying physics to bias the radioactive decay based entropy source as we wish. This sort of attack would provide secondary signatures, not the least of which is that a flux of radiation capable of doing that should be detectable. But it’s not impossible.

bitmonger • October 15, 2013 10:07 AM

@joe Landon

I think influencing actual decay is not a problem, but in a real system there is a detector. Compromising that is an issue of course. Nearly any real detector can be compromised is you have access to it.

The issue is: is there deterministic process that might have less entropy that we think leading to something that looks more random than it is that might be remotely attackable. All things being equal this is a very important question.

A real security trade off I see is: a) black box, but theoretically good sources vs b) open but theoretically less good sources.

Most hardware rngs have whitening builtin so you don’t know if
they are ‘cooked’ (or plain broken), but they are usually based on
good physics.

Personally, I am not as concerned about the physics used for entropy as I am the auditablity of the whole system.

If I was concerned. I probably still rather sample shot noise from a diode or two racing oscillators and have it unbiased and used to seed /dev/random than have a device that collects quantum noise, but operates as a black box.

Luck • October 15, 2013 10:16 AM

@Theodore Ts’o: “First, this is changing in the set of changes being queued for upstream. http://git.kernel.org/cgit/linux/kernel/git/tytso/random.git/commit/?h=dev”

The exact patch is available at
http://git.kernel.org/cgit/linux/kernel/git/tytso/random.git/commit/?h=dev&id=85a1f77716cf546d9b9c42e2848b5712f51ba1ee

I indeed see that XOR will now happen earlier.

@Theodore Ts’o: “Secondly, the the primary reason for this change was not to indulge the paranoid fanatasies of those who are concerned that the Intel CPU might be able to detect the XOR in the instruction pipeline”

In our case, NSA does not need to wrap XOR (with subsequent user-visible program misbehaviour/crashes), it is enough to patch the instruction called by arch_get_random_long:

The Intel instruction called by arch_get_random_long, before giving its potentially weakened RDRAND, might XOR it with hash.l (that might be available in a predictable register). So that the subsequent XOR with hash.l, done by random.c, nullifies all random sources but RDRAND. Unfortunately, this patch leaves this precise weakness intact 🙁

@Theodore Ts’o: “Also consider that if there is a hypothetical way that RDRAND can be subverted, putting it in a payload for a Stuxnet-like viral attack is extremely dangerous”

Schneier documented how NSA is cautious with its exploits: “If the target is a high-value one, FOXACID might run a rare zero-day exploit that it developed or purchased. If the target is technically sophisticated, FOXACID might decide that there’s too much chance for discovery, and keeping the zero-day exploit a secret is more important”, quoted from https://www.schneier.com/blog/archives/2013/10/the_nsas_new_ri.html

GentooAndroid • October 15, 2013 10:20 AM

@Aspie: “I find lynx browsing slows me down enough to read everything and follow links judiciously.”

My lynx is fast (and faster than any graphical browser) because cat .lynx.cfg shows:
NFOSECS:0.1
MESSAGESECS:0.1
ALERTSECS:0.1
DELAYSECS:0.1
REPLAYSECS:0.1
Use this file with: export LYNX_CFG=.lynx.cfg

To look at error messages, try Control-H then select top link.

JT • October 15, 2013 10:41 AM

@ Toni

what technique were you considering for getting the computers on the network to be able to take advantage of the RPi’s HWRNG?
just have them ssh into it and grep output or did you have another idea?

Aspie • October 15, 2013 10:47 AM

@GentooAndroid
That’s neat.

With squid also blocking outbound requests to any site not explicitly enabled with:

acl safe dstdomain somedom

pages in lynx and dillo are equally fast and devoid of fluff.

name.withheld.for.obvious.reasons • October 15, 2013 11:15 AM

My addition to the discussion?

I use lynx to stream the source “lynx -source [site] > site.dat.html”
My usually behavoir is to then pass it through a filter if I feel that it needs to be sanitized, or, if I want to do a quick read I use “w3m -T text/html site.dat.html”

If I am paranoid I use a stream editor to render the output to one of any number of pagers or use vi/vim if I want to inspect anything that might be of question.

Okay, I know–bragging rights are for braggers. I am just explaining something I do just to minimize my risks on-line. I have separate systems for graphical browser (firefox explicitly removed image content filter–that sucks). Many have commented on the difficulty of using “any” application to touch networks that considered “public”.

I don’t considering accessing my host service as a public service, though the law apparently treats it as such. So it doesn’t matter what I access my services with when what is compromised is the confidence in the accuracy and propriety of e-mail or electronic documents that are stored in the cloud. Even though I use GPG/PGP and only infrequently use application level password protection. I pretty much have the operative environment as Bruce but have some deviations and variations to enhance the level of confidence that can be maintained by my own network and devices.

In summary, EAL-6/7 is not an option given budgets and procurement requirements–I could do a roll your own version but that won’t serve any certification of the process–maybe I can produce my own. Having done a good bit of DO-178B work on various micro-kernels and RTC OS’s, I could do a “simulated” IEC/ISO/NIST/ISCA certification but what purpose does that serve given the insistence that the NSA “must have access” to “any” system seems counterproductive at this point.

My TIG welder is at the ready to fuse the boards, and several boxes to mail them to the NSA when I have them truly secured.

Brian M. • October 15, 2013 12:15 PM

@Theodore Ts’o:
In theory you could also write a userspace program that accesses the TPM chip (which may require access to TPM PIN’s before you are able to access it, which is another reason why this really needs to be done in userspace), and then use the on-board HWRNG in the TPM to feed entropy into /dev/random. No one has done this, but it’s certainly something you can do.

I did this last night on my Toshiba Portege R200 running Ubuntu 12.04. The packages for it are already available. I had looked at /dev, and didn’t see hwrnd! Oh my, what to do?

First, I downloaded the rnd-tools package (sudo apt-get install rng-tools). This also installs TrouSerS. It temporarily created a /dev/hwrnd, but that didn’t last beyond reboot, so something was wrong. I looked up the chipset in the notebook, and the chipset doesn’t have a HRNG.

Next, I got the TPM tools (sudo apt-get install tpm-tools) and verified that the Infineon chip was discovered. After a bit of futzing, I found this blog post and configured rng-tools and restarted its daemon process. I checked the logs, and it seems to be functioning! I left a test running overnight, and I didn’t check it when I left for work. The stats say it’s producing numbers at about 7Kb/sec.

So rnd-tools interfaces with tpm-tools to feed the output from the TPM chip into /dev/random. Yay!

Jakub Narebski • October 15, 2013 12:15 PM

Long, long time ago I have heard of Ulam (I think) algorithm to make better PRNG (with longer period) out of two worse PRNG by using one (worse) PRNG to select bucket and another PRNG to write into bucket. So getting one pseudo-random number would consist of using PRNG 1 to get bucket number (table index), get data from there as result, and replace it with PRNG 2.

I wonder if something like that could be used to mix different sources of entropy…

Aspie • October 15, 2013 12:36 PM

First, apologies to other less interested folks for heading off into the woods on this thread. It’s still about security …

@name.withheld.for.obvious.reasons
It’s all a matter of degree, of course, and with faith in your lynx it sounds like you have nothing to fear at the HTML level. (Protocol attacks coming back from the site notwithstanding).

I used to use Amaya for page viewing but it lagged behind the curve and was so buggy that it would have been difficult to ascertain whether it crashed due to an attempted exploit or a misplaced comma in the source code.

I downloaded chrome recently and put it in jail before I ran it. It seemed to want root access (as if!). Even if I misread it, it got binned immediately. (It occurs to me that just as countries without Democracy usually have the word Democratic in their names, so “Don’t be Evil” fulfills the same inverse relevance to Google. A line from Yes, Minister put this succinctly: “Always dispose of the difficult words in the title of the bill. They do less harm there than in the text.” Another: “The less you intend to do about something the more you need to talk about it.” Popular modern examples in the US might be Department of Homeland Security and Patriot ACT.)

Years ago, still drunk on VMS, I hacked a rudimentary form of privileges into the hatchling that Linux then was. (It was a lot easier then but the code is long gone and would have required a lot of patching anyway.) Yet I still think the VMS security model was one of the strongest the industry has seen and with some tweaks could restrain – and monitor – suspect apps very precisely.

Some other people here may agree with Rob Pike’s assertion that UNIX died some time ago but it won’t stop twitching. (Probably even Ken and Dennis would agree). Plan9 was designed to succeed it but for whatever reason(s) never really made it out of the hatchery. Now, if Torvalds had taken Plan9 and run with it …

OpenVMS is still copyrighted but the basic premise is still strong. A fusion of the two (PlanVMS, say) with some strictly enforced standards about attached hardware (for example, reliable HRNGs) could also fill the Palladium dream without the abominable kow-towing to the DRM and closed-source it was really invented to implement and protect.

Brian M. • October 15, 2013 12:42 PM

@Clive Robinson:
Intel have consistantly failed to provide access to the raw source…

Consider this: What source is there if the “raw source” is a digital circuit? What are you expecting to receive from Intel, and what are you expecting to verify?

Many years ago, when I was in college and the 80286 was hot stuff, I implemented a PRNG in hardware. It danced through its states, and then repeated its sequence. Now imagine for a moment if I had added an unstable bit source, and a shift register to produce an N-bit value to be occasionally XORed into the PRNG circuit.

Now, let’s say I burned all of that into an ASIC and handed it to you. The chip is programmed such that you can’t read its fuse states. It is a black box. I also give you what I claim is the source file for the ASIC.

What will you do?

Clive Robinson • October 15, 2013 1:09 PM

@ Brian M,

By source I don’t mean the VHDL/Verilog or down stream netlists. What I mean is the bit stream output from the actual source of the TRNG befor debias or whitening.

And by using the right tools on it I expect it to tell me quite a bit.

As I and others have said I don’t actually expect it to meet Diehard or any of the subsiquent tests or others of my own devising, because the way it fails tells me what else to look for to check and see if they are actually being honest in what they claim.

As for your hardware PRNG if you gave it to me and gave an honest description of it then yes I would be able to verify it. Also if the occasional XORed input was from a physical source or another PRNG providing it did not XOR in two frequently then yes there are ways to detect it.

Brian M. • October 15, 2013 1:42 PM

@Clive Robinson:
What I mean is the bit stream output from the actual source of the TRNG befor debias or whitening.

And how would you suggest that Intel would open that up to scrutiny?

The Intel Secure-Key generates a 256-bit entropy sample, running “asynchronously on a self-timed circuit and uses thermal noise within the silicon to output a random stream of bits at the rate of 3 GHz.”

The “easiest” way for them to do that would be to give you a bare chip, sans any packaging, and let you hook it all up yourself. Seriously, that’s it. Put the ever-so-tiny logic analyzer probes on the right parts in the chip, and on and on. Really, in the development process, that’s exactly what they do themselves. Even if that output was sitting on a pin on the chip package, how would you know that they weren’t lying to you, if they had been compromised by the NSA? That rabbit hole is a Moebius loop in a maze of shifting mirrors.

Seriously, consider what your request entails from the manufacturer’s perspective, and how you would actually go about verifying the the whole package. At the end of it, a high-performance chip can’t be produced that can also be verified by a third party. I have worked in the manufacturing end of things, and even just implementing a chip design like that on a motherboard is extremely non-trivial.

The only CPU that I worked with that could come close to independent verification was the NCR 32032, which allowed microcode to be uploaded.

Clive Robinson • October 15, 2013 4:16 PM

@ Brian M,

First think about what you have said and quoted,

    running “asynchronously on a self-timed circuit and uses thermal noise within the silicon to output a random stream of bits at the rate of 3 GHz.”

Then run it by your sanity filters with first the simple question of, “What are the implications of self timed logic at 3GHz)”.

As for “how do you know they wern’t lying to you” how about more simply “lying to themselves” or just “kidding themselves”.

If they cannot reliably test it on chip in an externaly verifiable way then they are “kidding themselves” that it’s functioning as anything other than a fully determanistic circuit like for arguments sake a counter…

Because once it’s past de-bias and whitening it will pass any statistical measure you care to throw at it irespective of if it’s fully determanistic or compleatly unpredictable.

Your argument boils down to “Trust them because even they cann’t verify it” which is the same argument any snake oil salesman uses to flog you rotting fish oil ie “it smells bad so it must be good for you”…

Mike the goat • October 15, 2013 4:45 PM

Theodore: thanks for linking to your commit. I appreciate your work and more importantly transparency in this field. I suspect many others would be happy enough – if RDRAND is detected to just pump RDRAND derived data straight into random and do away with the whole need of having a urandom as /dev/random would never block in normal use given the speed of the hwrng stream, and I appreciate that it is somewhat conspiratorial to suggest that the Intel hwrng is somehow evil.

Unfortunately when dealing with something as fundamental (for crypto anyway) as the kernel RNG you just can’t trust anyone.

I think your patch is excellent as it moves the RDRAND mixing back to where it should be. I didn’t have a big problem with it but I did comment it would have made more sense pre-hash.

Brian M. • October 15, 2013 5:02 PM

@Clive Robinson:
“What are the implications of self timed logic at 3GHz)”

I think they can reliably test it on the chip. The key factor here is “Intel can,” not everybody else, and many people do want to test it.

I think that their design decision was actually to place a completely separate random number generating processor inside the die. From reading their literature, the logic behind “rdrand” is really sophisticated. The most effective way firewall that processor is to completely isolate it from the CPU’s bus, and allow it to be accessed only through a read-only register. Therefore, it has its own self-test. That seems the most secure way to do it, since if it’s completely isolated, then no hanky-panky in the CPU can touch it.

And that’s what everybody is concerned about, isn’t it? That the HRNG is isolated from the CPU, and is safe behind its firewall. And no suspect operands can magically change values, like
in ax, rightfoot
out rightfoot, ax
sh ax, rightfoot
mov cx, nsa
rdrand cx

It still comes down to the question of trust. What external tests are used to verify the HRNG in TPM chips? How about the HRNGs in various external chipsets?

From reading the programming manual, RDRAND behaves like /dev/random, which blocks when entropy is exhausted. From 7.3.17 of the manual:

RDRAND returns random numbers that are supplied by a cryptographically secure, deterministic random bit generator DRBG. The DRBG is designed to meet the NIST SP 800-90A standard. The DRBG is re-seeded frequently from a on-chip non-deterministic entropy source to guarantee data returned by RDRAND is statistically uniform, nonperiodic and non-deterministic.

In order for the hardware design to meet its security goals, the random number generator continuously tests itself and the random data it is generating. Runtime failures in the random number generator circuitry or statistically anomalous data occurring by chance will be detected by the self test hardware and flag the resulting data as being bad. In such extremely rare cases, the RDRAND instruction will return no data instead of bad data.

Under heavy load, with multiple cores executing RDRAND in parallel, it is possible, though unlikely, for the demand of random numbers by software processes/threads to exceed the rate at which the random number generator hardware can supply them. This will lead to the RDRAND instruction returning no data transitorily. The RDRAND instruction indicates the occurrence of this rare situation by clearing the CF flag.

So it all comes down to how much you trust Intel to incorporate a HRNG inside their chip, and nothing more than that.

@GentooAndroid:

(I have no idea why my comments are in reverse video on your version of Lynx. Maybe it’s out of date. I just downloaded 2.8.7, it it looks fine. They must have picked up my change for <brainupdate force=true subliminal=true iamalwaysright=true /> tag change correctly. I’ll talk to the guys in black (ninjas) and get them to rootkit, er, update your machine the next time you go for the fridge.)

See above for my theory on why it’s outside of JTAG.

Dave Täht • October 15, 2013 5:42 PM

@Brian M: What that total level of isolation from the rest of the chip ALSO means that it is possible to fiddle with the doping mask on the hwrng in an undetectable fashion.

http://people.umass.edu/gbecker/BeckerChes13.pdf

(I think the above paper was also discussed on ts’o’s g+ )

I love it that hwrngs are becoming more widely available. They are desparately needed for the huge number of things requiring good cryptography, not least of which is wireless.

Brian M. • October 15, 2013 9:15 PM

@Dave Täht:
What that total level of isolation from the rest of the chip ALSO means that it is possible to fiddle with the doping mask on the hwrng in an undetectable fashion.

Aaaaand we go right back to the manual for that one.

… the random number generator continuously tests itself and the random data it is generating.

Theory, schmeory, let’s see some actual tests. Go ahead and fiddle with the mask, and see if it passes the chip’s self-test. Fiddle with the output, and see what the NIST and DieHarder2 tests reveal. Seriously, I want modified chips and code. Some of the “attacks” are pretty esoteric, and some are laughable.

Remember, if a Boeing 747’s engines are changed in mid-flight with 1971 Ford Pinto engines, it will crash. Any aeronautical engineer will back me up on that, 100%. It’s a valid theoretic vulnerability! It is!

I just ran rngtest on my Ubuntu box. 21180 successes, and 16 failures. Monobit: 1, Poker: 3, Runs: 6, Long Run: 6, and Continuous Run: 0. That’s with an Infineon TPM chip. So it has a 0.0008% failure rate.

Here’s a source of entropy: YouTube videos! Now you have a good, valid reason to have lots of stupid videos loading on your computer. Yes, it’s all done for the sake of good random numbers! Sure, sure! That’s the ticket! Yeah!

@GentooAndroid:
I took a look on my Ubuntu box. Yeah, I see it. Dangit, I’m going to have to change that again. It’s supposed to be invisible! With subliminal holophonic noise output on the sound channel, too.

Nick P • October 15, 2013 10:41 PM

@ name.withheld.for.obvious.reasons

“In summary, EAL-6/7 is not an option given budgets and procurement requirements–I could do a roll your own version but that won’t serve any certification of the process–maybe I can produce my own. Having done a good bit of DO-178B work on various micro-kernels and RTC OS’s, I could do a “simulated” IEC/ISO/NIST/ISCA certification but what purpose does that serve given the insistence that the NSA “must have access” to “any” system seems counterproductive at this point. ”

Funny thing that I thought you were someone replying to one of my old comments when I first saw EAL6/7 and DO-178B. I’m practically the only one here that promotes such development standards, although not the formal evaluations. I’ve previously promoted GEMSOS, LOCK, the SKPP kernels, etc. I also say “EAL6/EAL7” so that was odd. Rubbing off on you or are have you been independently interested into all that yourself? 😉

You say you worked on DO-178B evaluations of microkernels. I’m very interested in an insider’s view on the process and these products as I’ve previously promoted them as foundations for at least medium assurance devices. I have a tad different focus now but they’re still useful tools.

  1. Do the DO-178B standards really increase quality of OS code, device drivers, and such to the levels they claim? Or is it handwaiving?
  2. What’s your opinion on INTEGRITY-178B, LynxOS-178B/LynxSecure, VxWorks MILS, and PikeOS? I know safety != security but these are all targeting both markets. You think they live up to their claims about low chance of exploitable defects? And just how useful are they really in their evaluated configuration for the wide range of stuff these companies are promoting?

(Seems to me that significant changes are made in the evaluated configuration that makes the evaluation worth a bit less as evidence of assurance.)

  1. I’ve often praised DO-178B for its supposed requirements of source to object code correspondence and traceability between artifacts (e.g. design to code). Do you guys really verify even C and C++ programs down to the object code? Is a line drawn somewhere? Aside from CompCert, I can’t even see how you could easily do the tracing. Any insight on this would be appreciated as I think such traceability is key to defeating subversion by malicious developers.

  2. It seems that INTEGRITY-178B’s EAL6 evaluations and maybe some DO-178B evaluations showed evidence of highly robust software development, but run on low assurance developed processors like PowerPC. (I like PPC don’t get me wrong but it sure ain’t EAL6.) I know some Orange Book products used custom firmware and/or microcode. Is the hardware/firmware really as much a weak link on these RTOS’s as I think or is anything done to mitigate this stuff?

  3. One proposal I had long ago was to build a medium assurance, minimalist OS out of DO-178B components. I noticed there’s kernels, networking, filesystems, graphics and I think even audio components out there. Integrating them into a system with a robust kernel and using state-of-the-art information flow techniques might be an easy way to develop an extremely low defect, more-secure-than-average system without the millions of dollars and hundreds of man-(hours/months/years) it would take to build a high assurance product from scratch. Be a nice interim solution I thought in area’s like security appliances, thin clients, authorization systems and so on. Your thoughts?

  4. Another proposal I had (and discussed with a Common Criteria insider) was refining the evaluation. I think the evaluations are too heavy and slow. One trick might be to have qualified labs evaluate the product and the process, focusing on most high payoff techniques. And I think this should happen at onset with developers and independent evaluators regularly bouncing deliverables back and forth to make the process smooth. Naturally, these labs probably wouldn’t be Cygnacom, SAIC, etc. and you wouldn’t get a CC certificate. Instead, you’d get a review posted on their website detailing the security claims, what was confirmed, proper usage recommendations, and a signature. It would be a quality improving review, a form of due diligence, and a third party endorsement all at once.

(For non-proprietary or secretive projects, I’d also advice the process’s artifacts be posted online in an easy to review manner so wide peer review can happen. My main design didn’t mention this at the outset b/c the commercial entities producing software, esp security software, probably don’t want all their I.P. posted on the internet. Gotta be practical.)

Sorry if it seems a bit much. These are things that have been bouncing around in my head for a few years. Take all the time you want to respond or don’t respond. I’m good either way. I just figure people following my posts and press releases on these DO-178B products/processes might enjoy a rare opinion from an insider, esp if semi-anonymity allows them to be a bit more honest. 😉

Clive Robinson • October 15, 2013 11:43 PM

@ Brian M,

    So it all comes down to how much you trust Intel to incorporate a HRNG inside their chip, and nothing more than that.

Err no far from it.

For instance you forgot two important words from your statment the ommission of which makes it worthless [1].

As has been pointed out on this blog many times and well before this current NSA-NIST bashing in the world press Intel have an erata sheet on their CPU’s that is quite large. If your memory stretches back a while you will remember that Intel came in for their own share of bashing in the world press due to the “pentium bug” where they got a constant wrong.

Further Intel in the past felt these hardware/firmware failings were such a significant issue that they put in a whole load of otherwise redundant hardware into their CPU’s to alow the microcode firmware in the CPU to be updated remotly without the user having control. And thus have now opened themselves to the speculation that this is in it’s self a NSA inspired back door… Which even if it’s not true still makes a rather jucicy malware target for those who have the ability to exploit it and to be fair the NSA along with GCHQ et al would come high on any list of those with the ability [2]. And I for one was pointing out the failings in “code signing” long prior to Stuxnet making them obvious, again via the worlds press.

I’ve also been pointing out the dangers around RNGs back into the last century and certainly prior to the little NetScape problem if you remember that. And I’ve a long history of designing and building RNGs of various qualities for a long time.

Which is why I’ve repeatedly in the past called Intel out for their RNG designs and coined the expression “magic pixie dust thinking” because they hid poorly designed entropy generators behind crypto primatives to hide the design failings. And in this opinion I’m very far from alone.

Rather than quote meaningless blurb from Intel’s manuals actualy do what I suggested and,

    What are the implications of self timed logic at 3GHz

Rather than rather embarisingly say,

    Aaaaand we go right back to the manual for that one…

Before quoting what is a fine piece of markiting droid speach dressed up as technical prose,

    the random number generator continuously tests itself and the random data it is generating

I urge you to please think carefully on the implications of this before making a reply, because so far it’s fairly apparent you have not, which is not a good idea.

[1] Prior to HRNG the two words “correctly working” should be added preferably with the words “verifiably tested by independant test house” as has been done by other manufactures of CPUs with HRNG’s in (the fact that one independent test house dropped the ball is neither hear nor there because reading their report showed they had done so).

[2] As I’ve said on this blog and a number of other places several times in the past much predating the CarrierIQ debacle, “test hooks” are custom made to hang a malware hat on unless you take steps to prevent it. That is any test system if not properly designed can be used to harm the system or the users of the system.

[]

name.withheld.for.obvious.reasons • October 16, 2013 3:23 AM

@ Clive Robinson

Which is why I’ve repeatedly in the past called Intel out for their RNG designs and coined the expression “magic pixie dust thinking” because they hid poorly designed entropy generators behind crypto primatives to hide the design failings.

Well said Clive, this is such a reoccurring theme in tech. Designers leave JTAG’s on the board for the “just in case” and then wonder why the hardware gets jail-broken…and that’s the simple case. The variation and plurality of design and production tradeoffs give one an endless stream of fun.

Currently I am fighting an RTL synthesis issue and timing convergence for a mixed signal application (parallel array of sensors)–MSO’s are great for debugging but in the runs that include signals (Verilog/VHDL) and some analog transients (wide-band app without FIR) at the sensor seems to be analogous (slightly).

GentooAndroid • October 16, 2013 6:46 AM

Brian M.: “@GentooAndroid: I took a look on my Ubuntu box. Yeah, I see it. Dangit, I’m going to have to change that again. It’s supposed to be invisible! With subliminal holophonic noise output on the sound channel, too.”

Lynx 2.8.6rel.4 (15 Nov 2006) and 2.8.8dev.15 both react to this example:

text in normal colors.

text in reverse video.

The case is not significant here. And this showed nothing:
ldd /usr/bin/lynx | grep ‘=>’ | sed -e ‘s:.=> ::’ -e ‘s: .::’ | LANG= xargs grep -i ‘brian’

A curious easter egg 🙁

GentooAndroid • October 16, 2013 6:50 AM

The

GREATER
sign and the
LESS
sign are forbidden in comments here 🙁

Here is the real example, where I replaced them by the strings LESS and GREATER:

LESS html GREATER LESS body GREATER text in normal colors.
LESS div class=”commentbody by-brian-m” GREATER text in reverse video.
LESS /div GREATER LESS /body GREATER LESS /html GREATER

Aspie • October 16, 2013 7:33 AM

@GentooAndroid
Try & gt and & lt (without the space between the ampersand).
e.g.
if (a &lt b) or (b &gt a)

&ltblockquote&gt doesn’t appear to work.

JT • October 16, 2013 7:41 AM

@ Bhima

thanks for that. i was thinking of something like this on the client side

mkfifo /dev/randomserver
ssh [IP] cat /dev/hwrng > /dev/randomserver

GentooAndroid • October 16, 2013 8:04 AM

@JT, @Bhima:

Thank you, we now have an excellent reason to continuously transport amounts of random data on internet.

@Aspie: “Try & gt and & lt (without the space between the ampersand).”

Thank you. The easter egg seems to be:

&lt html&gt&lt body&gt text in normal colors.
&lt div class=”commentbody by-brian-m”&gt text in reverse video.
&lt/div&gt&lt/body&gt&lt/html&gt

The case-insensitive text between quotes is important, I tried various changes and all of them broke the easter egg.

Mike the goat • October 16, 2013 8:24 AM

JT: you’re probably better off using the hwrng on the other machine to seed /dev/random periodically or even better use an entropy sharing daemon (someone suggested entropy-broker but there are others) as you are potentially creating an issue if your other machine (with the hwrng) goes offline or crashes. If you’ve compiled your software to use only your fifo for random and it blocks, well, your web server etc… is going to break.

Given how integral the /dev/random device is in Linux (used for TCP sequence numbers etc) it needs to be trustworthy – and I believe it is. Even if you don’t trust Intel’s RDRAND it is xor’d into the random stream and thus it can’t make the existing entropy any worse. Okay, bad English but I hope you understand what I am getting at.

If you are dead set against using any RDRAND derived data use nordrand as one of your kernel args on bootup or just edit random.c and ensure it isn’t called.

Luck • October 16, 2013 8:47 AM

@Mike the goat: “Even if you don’t trust Intel’s RDRAND it is xor’d into the random stream and thus it can’t make the existing entropy any worse.”

Except if NSA^W^H RDRAND knows about that.

If RDRAND is XOR(sha1(++nsakey+processorID),existing entropy), then XOR(RDRAND,existing entropy) is sha1(++nsakey+processorID).

(The existing entropy is conveniently loaded in a predictible registry; XOR only works for independent sources)

Theodore Ts'o • October 16, 2013 10:08 AM

@Luck:

Except if NSA^W^H RDRAND knows about that.

If RDRAND is XOR(sha1(++nsakey+processorID),existing entropy), then XOR(RDRAND,existing entropy) is sha1(++nsakey+processorID).

(The existing entropy is conveniently loaded in a predictible registry; XOR only works for independent sources)

You keep saying that, but it’s not true. Let’s take a look at the relevant assembly code in question, shall we?

        leal    -164(%ebp), %eax
.LVL889:
        call    arch_get_random_long
.LVL890:
        testl   %eax, %eax
        je      .L406
        .loc 3 1042 0
        movl    -164(%ebp), %eax
        xorl    %eax, (%esi)
        addl    $4, %esi
        jmp     .L405

The arch_get_random_long function is what actually calls RDRAND. It’s in a separate function since we have to test to see whether or not the CPU supports RDRAND, and even if it does support RDRAND, it can return an error at which point we have to retry the RDRAND (actually, on this generation of x86 chips, it’s highly unlikely that RDRAND will fail due to lack of entropy, since it would basically require all the cores and all the hyperthreads to be calling RDRAND at the same time, and even then the hwrng might be fast enough to keep up; the story will be different with RDSEED, and it’s a really good idea to do error checking even if most of the time the call or instruction doesn’t fail…).

You’ll also see that the XOR is to a location in memory, in extract_buf(), which calls arch_get_random_long(). So I will repeat what I said. If you think the NSA could have really trojanned the the x86 execution pipeline to the extent that it could track that a register contains RDRAND output, across a function call return, just so it can then access a memory buffer to find the location of the gimmick the value of the register containing the putative RDRAND output[1] and you really think the NSA could suborn enough Intel employees so that no one would notice and/or pull a Snowden, then I suggest you start creating your own CPU’s using 74XX TTL chips. (I’ll also note that this assumes that the NSA’s gimmicking on the x86 execution pipeline was general enough that it could support code generation on multiple different compilers — different versions of gcc and clang.)

[1] Alternatively you could posit that the corrupted x86 execution pipeline could track the register containing the RDRAND output, and convert the XOR to memory into a STORE into memory, but that could be noticed by someone who was testing for that theory.

south • October 16, 2013 10:41 AM

Not to be overly paranoid, but in addition to the possibility of our own government’s interference, has anyone given thought as to where many of Intel’s CPUs are manufactured? Just a simple tech here, but have always considered the remote possibility of additional (hidden) instructions being embedded at some of the foreign manufacturing plants, particularly China. And with transistor counts in the billions for a modern CPU, who knows what else could be buried inside.

Brian M. • October 16, 2013 11:07 AM

@Clive Robinson:

How do you, personally, go about testing the HRNG in various TPM chips, the Via Nehemiah C3 CPU, and the AMD-760MP or AMD-8000 series chipsets? I really want to know. No hand waving, please.

Also, have you looked at what the NIST tests for monobit, poker, and runs entail? Not much. Those are easy to implement in hardware, especially when the you have leading hardware designers on the job. (Once upon a time I worked for an OEM, and my boss was one of the guys who designed the 80386. The salespeople for the chipset we were using asked us, “You used those two, why not the third?” My boss replied, “Well, I realized that I could implement it in three PALs, so that’s what I did.” Everybody laughed.)

Yes, I do remember Intel’s bugs. AMD’s bugs, too. Intel could have run an available math regression suite on their chip, but they didn’t do that.

AFAIC, any time a HRNG is implemented as a black box, there will be “problems” with verification. And it really does come down to the question of trust. Like the Dilbert cartoon points out, “That’s the problem with randomness: you can never be sure.” So if the generator passes the public tests, and there’s no major repetition, then I’m calling it good and using it. Everybody has a limit to the time they can spend on a problem, and at some point I have to solve other things.

@GentooAndroid:
Maybe it’s a Linux-only thing. It’s very curious, to put it mildly. Be sure to file a bug! I wonder if it may do it on the Mac build. (When I was in high school, I was writing code part-time on a Sperry-Univac TIP 90/40 mainframe. While attempting to figure out what control codes might do on the terminal, I accidentally found out I could take down the mainframe with seven characters. Oops!)

@south:
The problem is not one of hidden instructions, it’s one of meeting performance criteria. There have been reported instances of “mislabeled” chips being sold by vendors to contractors producing military hardware. I.e., selling a non-MILSPEC part, or one that’s rated for a different frequency range, etc.

JT • October 16, 2013 11:30 AM

@gentooandroid @mike the goat

i was following Toni’s original line of thinking about taking a local RPi and turning it into a dedicated HWRG on a local network only. on a local gbit ln, the amount of traffic it would use should be trival. (I think the RPI HWRNG max output is only 1m/s)
Having not used mkfifo in that capacity before, would it continously stream or only stream when the machine actually tries to pull from the /dev/randomserver pipe?

thinking about it though it would be gleefully enjoyable if we filled up NSA datacenters with encrypted randomness for them to analize. 😛

Ive never used entropy broker, but ill look into it. you mentioned there were others, do you happen to know any names i can look for?

ACORN • October 16, 2013 1:08 PM

—Donald Knuth. Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin

John von Neumann, not Donald Knuth • October 16, 2013 1:51 PM

ACORN, you mis-attributed that famous quote. It’s from von Neumann. Knuth quoted him in his book. 🙂

Bhima • October 17, 2013 2:19 AM

@ JT: Looking at what entropy broker does with entropy data, I think there’s probably more to sharing entropy data (skillfully) than just “ssh [IP] cat /dev/hwrng > /dev/randomserver”

@ Mike the goat: What other entropy sharing daemons are there? I’d like to try them. Thanks!

Mike the goat • October 17, 2013 5:58 AM

Bhima: I recall there was one called rngd several years back but a Google search turned up nothing (there’s another product called rngd but is not an entropy sharing daemon). Looks like you are stick using either entropy-broker or rolling your own.

I would write a few lines to pump, say 10kb of noise from the hardware RNG to stdout. Make an unprivileged user and set its shell to that little program you’ve created and then generate an ssh keypair and disable password authentication. On the other side you can just put an entry in your cron to ssh into the said host and direct the output into /dev/random to seed it.

This would improve the amount of entropy available whilst also ensuring that you don’t accidentally create a DoS opportunity by somehow interrupting communication between the two hosts (if you were doing your fifo idea and using it directly, say for openssl in apache, if the connection failed and blocked you’d effectively stop https working).

You can adjust the frequency of the polling, e.g. if it is a busy server and you get delays due to blocking of /dev/random run it hourly rather than daily. You could also use a much larger chunk size and instead cache it – i.e. get your little program to pump 1MB instead of a few kB and write a daemon that monitors entropy_avail and injects a kB or so at a time whenever it starts getting low. Make a second thread that keeps an eye on your cache (in memory ideally) of the chunk of random data and when it gets low, open your connection again and get some more.

name.withheld.for.obvious.reasons • October 17, 2013 9:47 AM

@ Nick P

Sorry, didn’t notice your post on EAL and DO-178B. I will quickly respond by saying I have probably touched most InfoSEC process and qualification standards. I will need to draft a proper response to the set of questions you asked. I can say that all your questions are relevant and I share your experience in the RTOS and hardware experiences with some slight variations. I know I can give you some significant feedback. Don’t want to put too much on the table. Maybe orgs like LLNL or some contractors to government don’t appreciate comments about tech. Hopefully today, have some stuff on my plate.

Brian M. • October 17, 2013 11:13 AM

@Bhima:

There is the rngd that’s part of the rng-tools package. It injects entropy from a source into the kernel, and it can be used with an arbitrary input stream. This blog has some hints about sharing entropy sources over a network.

Clive Robinson • October 17, 2013 1:20 PM

@ Brian M,

    How do you, personally, go about testing the HRNG in various… chips…? I really want to know. No hand waving, please.

I won’t handwave but the answer will be long.

Back ground first.
When it comes to any security hardware be it built from passive components through to chips I can not see inside I follow a process to decide if it’s acceptable for use or not and at what levels.

If it is acceptable I determin at what level both in use and for use, that is it has a quantified level of “trust” as a device and it might be used in applications that require more or less “trust” than the device has. If more trust than the device has then it will need to be built into a system using other devices to achive the desired level of trust.

The process is in effect “verify then trust, but with constantly verify in use”. Which places the emphasis on verification to the required level which basicaly boils down to formal design methods and controls in manufacture, through detailed testing, and on to continual in use testing. Outside of testing much of it appears as an auditing process which I shall simply gloss over here by saying that knowing the formal methods helps decide the testing methods.

At each stage the idea is to charecterise the device into one of the following

1, Do not use.
2, Mittigate in use.
3, Trust to some level/area of use.

It’s important to note that the “do not use” and “mittigate” groups might well contain devices that would without non “trust” related issues be in the “trust” groups. The major cause of this is the limitations in resources for verification both in initial clasiffication and during use. Thus it is first important to know the limitations of the verification resources and processes.

As I’ve indicated before certain determanistic processes will pass all the standard “witness” tests and will make a simple fully determanistic counter look random. This is the major reason why you need to conduct tests as close to the entrapy source as possible and certainly befor any debias or whitening circuits.

Importantly this close to the entropy source testing is essential not just in initial testing but also in runtime testsing used to detect failure or influance of the source in use. For instance a D-type latchs can and do fail and become in effect transparent to either the D or CLK inputs which would fairly quickly be seen on the output of a wide band spectrum analyser trace connected to the Q or /Q outputs but not after de-bias or whitening.

Often the failure can be one of metastability which occures in all latches in about 1 in 10E+9 operations without external EM influance. Metastability issues may or may not cause a soft latchup in subsiquent circuits which could remain for short, long or indefinate periods, but will clear on the powersupply being cycled.

If the internal operations of the device are running at 3x10E+9 opperations per sec then without preventative action metastability events will occure around three times a second with only some fraction of them being more than a few cycles long, but the probability of a full soft latchup obviously increases with the internal operating speed. Whilst some latchups will be caught by the internal chip tests not all will and some of the test circuits themselves will be prone to latchups. Detecting latchups externaly is possible by examining the raw sorce of entropy and the downstream output after debias and whitening (where the methods are sufficiently detailed).

Another metastability issue is it is influanced by temprature and supply voltage as well as by EM energy either by conduction or radiation. In fact with a bit of care you can use metastability as a random source in it’s own right (self biasing latch) and it appears that many designers don’t actually know much about it and it’s not that well documented in academic or design documentation (it’s often considered a “black art” that’s supposadly designed out…).

The issue of metastability alone gives rise to the question of “why so fast?” For on chip TRNGs. Because few if any OSs or applications need TRNGs that run that fast, mathmatical simulations for instance might require high rates of random numbers that are well distributed but they don’t need the same aspects that security does so usually PRNGs suffice. The generation of many security functions such as nonces are actually better done by PRNG’s using Crypto Functions where the uniqunes of a nonce can be guarenteed simply by using a CTR-RNG. Thus the TRNG can be quite slow as it is only needed to generate “seed/start” values for CS-PRNGs.

The other real security problem with the speed is it’s just not possible to run anytthing other than barely minimal witness tests for bias let alone any other failing. Tests such as those based on or involving FFT and FWT are impracticle at those speeds even with the best of test equipment so high speed TRNG’s get marked down as “not verifiable in use” for some security applications.

Above basic bias issues what you are looking for are in essence “signals in noise”, if a witness test finds a signal then the generator is failed unless the signal can be mitigated in some way. The faster the generator runs the more difficult both detection and mittigation become.

Simple “down sampling” of the high speed TRNG won’t make life much easier some signals will still be present but in a less recognisable form after down conversion by down sampling.

Now if –as some people are– you are arguing about some NSA backdoor then you have the further problem of what signals to look for and where.

The NSA have in the past “cornered the market” in “brains” for signals analysis and I suspect they are well ahead of the game still. The closest the open crypto community has come to this is “digital watermarking” back at the turn of the century, and to be honest they were not that good at it and basicaly gave up on it after quite a short time.

What the NSA would be looking for is synchronisation signals that make themselves visable after noise signal transformation by debias and whitening. The obvious way is to add the signal at the output, the less obvious is to inject it upstream of whitening or debias. To inject a signal upstream of the output they need to do this by either designing a signal that exploits weaknesses in the debias and whitening used, or weaken the debias and whitening in some way to pass a signal. There are three ways to find such signals the first and easiest is by finding where it is being injected into the entropy noise signal, the second and much harder is by cross corelating the input with the ouput, the third and well nigh impossible is by examination of the output alone.

So for ease of verifying with complex tests access to the output of the entropy source is required, and at one point was a standard and expected “test port” on stand alone TRNGs. Obviously the faster such a system runs the more difficult it is to test and the greater the potential for “smoke and mirrors” to hide behind (however the reality is very much OS/App related).

It is this lack of verification information and ability to test the raw entropy that makes me cautious and I see those on chip TRNGs with these problems not as verifiable systems in a “trust” group but as either “aditional seasoning” to a “trusted” TRNG where the on chips failure won’t detract from the “trusted” TRNG or as something that has to be mittigated against by the addition of additional entropy and whitening. Either way I don’t trust them sufficiently for security critical work, hence my comments about not betting my life or the lives of others on them.

And I guess one of the problems with on chip TRNGs is they feel like they have been designed by a commity of “ideas men” and the result is a “jack of all trades” soloution that does not fit well for any of the tasks you might reasonably expect to do.

I might be treating some on chip TRNG’s unfairly but at the end off the day if I cannot verify I won’t trust for security critical systems. And there is also a limited amount of expenditure I’m prepared to expend on verification thus I will drop a suitable DSP chip in to run various signal detecting algorithms on a slow TRNG entropy source output because my need for high quality “seed/start” values is comparitvly modest in a given design. But there is no economic justification for me putting testing systems in place for chip manufactures that want to make life difficult.

As you noted with your “three PALs” story I can do it my own way more economicaly…

Luck • October 17, 2013 4:17 PM

In my current kernel (3.2.0-55-generic #85-Ubuntu SMP Wed Oct 2 12:29:27 UTC 2013 x86_64 x86_64 x86_64 GNU/Linux) the call to arch_get_random_long seems to be inlined

L1:mov %esi,%ecx
mov $0x0,%ecx
data32 xchg %ax,%ax (0x666690)
xchg %ax,%ax – (0x6690)
test %ecx,%ecx
je .L2
xor %rax,-0x90(%rbp,%rdx,1)
add $0x8,%rdx
cmp $0x10,%rdx
jne .L1
L2

But I am not confident enough to understand what data32 xchg %ax,%ax does exactly. If it was rdrand, then an evil CPU might insert xor -0x90(%rbp,%rdx,1),%rax immediately after occurence of data32 xchg %ax,%ax.

(how I got that assembly code: LANG= sed ‘s:\x1f\x8b\x08\x00:GZIPHEADER:’ < /boot/vmlinuz-3.2.0-55-generic | LANG= grep -aA20000000 GZIPHEADER | LANG= sed ‘s:^.*GZIPHEADER:\x1f\x8b\x08\x00:’ | gunzip -c > /tmp/vmlinux; objdump -d /tmp/vmlinux > /tmp/dump; grep -A1 extract_buf /boot/System.map-3.2.0-55-generic; vim dump ; edit out everything but the last for() loop of extract_buf)

Luck • October 17, 2013 4:21 PM

LANG= sed ‘s:\x1f\x8b\x08\x00:GZIPHEADER:’ %lt /boot/vmlinuz-3.2.0-55-generic | LANG= grep -aA20000000 GZIPHEADER | LANG= sed ‘s:^.*GZIPHEADER:\x1f\x8b\x08\x00:’ | gunzip -c %gt /tmp/vmlinux; objdump -d /tmp/vmlinux %gt /tmp/dump; grep -A1 extract_buf /boot/System.map-3.2.0-55-generic; vim dump ; edit out everything but the last for() loop of extract_buf

Sorry for the missing %lt and %gt in previous message.

I understand that I do not have the technical level to continue discussing here my assuptions or fears. Let’s say @Theodore Ts’o is right.

Luck • October 17, 2013 4:58 PM

Please replace “,%rax immediately after occurence” by ” immediately and blindly after every occurence”.

Luck • October 17, 2013 4:59 PM

Please replace “,%rax immediately after occurence” by “%lt internal register of RDRAND%gt immediately and blindly after every occurence”.

Brian M. • October 17, 2013 5:28 PM

@Clive Robinson:
I will drop a suitable DSP chip in to run various signal detecting algorithms on a slow TRNG entropy source output because my need for high quality “seed/start” values is comparitvly modest in a given design.

OK, so it seems that you use your own chips. Fair enough. If you need total validation, I agree, that’s the only way to do it.

The Intel page I linked above (Section 3.3, Figure 4) shows that the entropy source undergoes comparison to a test source. The result of that comparison is fed to the conditioner. According to their documentation, at that point the number generation would be completely shut down until the entropy tests pass.

Which actually does follow your own methodology.

The possible attacks you outlined seem rather esoteric to me, given that the NSA would have to be running a load of code on the machine in order to possibly influence the RNG process. Like Theodore Ts’o commented, at that point you have larger problems than random numbers.

As for trusting my life to random numbers, well, it’s not on my risk calculation. I do a lot of walking, and pedestrian fatalities are far higher than fatalities from random numbers.

NVIDIA boasts that “we find that a single GeForce 8 GPU generates Gaussian random numbers 26 times faster than a Quad Opteron 2.2 GHz CPU…” so I’m sure that full RNG verification will continue to remain problematic.

Peter Barnhart • October 17, 2013 7:34 PM

@Wesley Parish
Thanks for your comment –
actually, I hadn’t heard of the book – I’ve read very little Sci-Fi in the past 30 years, but it sounds like a fun read.
I think you would probably find the cosmic microwave background has lots of non-random components. The trick is to sample an obviously random natural source pseudorandomly, the idea being that the two would be uncorrelated.
Question is if apod can supply entropy fast enough for whatever the application is. I’m assuming a relatively light demand rate. The hardware sources described by most of the posters are far faster.

Bhima • October 18, 2013 5:37 AM

@ Brian M. & Mike the goat: Thanks for the tips but it appears, to me at least, that Entropy Broker is a better option… despite its flaws and fading support.

Also, how do we report this spam?

name.withheld.for.obvious.reasons • October 18, 2013 7:01 AM

Hello Nick P,

Your comments about the Emperor’s new clothes (my paraphrasing of your post) is apropos but it would be nice if there was some humor mixed in…

Let me first respond by describing some of my work habits. As a classic engineer (old school NASA type) I keep a notebook journal at the ready, ticking every 15 minutes in my log book. I find it very useful to have work sketched out and useful for drawings, layout, or circuit design. I have worked in nearly every major sector in a multitude of capacities…I’ve learned to wear many hats and I can wear them all at the same time.

I believe that interdisciplinary and multi-disciplinary skills will be necessary for the engineers of the future…material, structural, electronic, mechanical, software, documentation, standards, quality control, information assurance, project management, and a half dozen others.

I attempted at one time to work with a graduate school to engage the faculty (they said they supported it, but could not deliver) and developed a cirriculm that also sefved as a training program for an aerospace company. The GM of the company and the director of the institute at the graduate school where both on-board but unable to follow through.

The above describes one of the most problematic issues I deal with on a regular basis, ignorance allows one to avoid responsibility (I see inaction as ignorant). I am employing my experience to set a framework and answer a few of your questions in a general way…and…I would prefer to take some of this offline as your statement about development and management are quite timely–I’m drafting a framework that is an answer to compartmentalized 1950’s management practices. I revisited QA/QC practices, my concern for process and procedure was given a kick last year…there is some extreme irony of late.

Maybe we can exchange keys, I am willing to post a pseudo account to contact me but in order to make that work we might need to encode a sequence (I need to re-read some of your posts to develop a “second order” contextual reference that can be used to act as a one-time shared key. “How do you know she’s a witch?”, and “I have a cunning…” She’s dressed like one–plan.

Gotta go now…will return with some feedback you can use.

Peter Barnhart • October 19, 2013 8:28 PM

@ Joe Landman and bitmonger

Note that some radioactive beta decay rates show an annual periodicity, in the case of radon about +/- 5%. See work of Ephraim Fischbach and Jere Jenkins and many colleagues, eg. ArXive 1207.5783v1
Guessing is an influence of solar neutrinos modified by the Earth’s orbit eccentricity.

JAMES • February 22, 2014 12:29 PM

HIJACK AUDIO TO STREAM A KNOWN AUDIO SEQUENCE TO RANDOM SEED GENERATOR LONG ENOUGH TO CAUSE A KNOWN SEED AND THEN ATTACK SYSTEM. REFERENCE IS MADE TO THE UNKNOWN AUDIO OUTPUTS ON SOMEONES APPLE COMPUTERS. THE SOUND OUTPUTS ARE A POSSIBLE SYMPTOM OF HIJACKED AUDIO. MAYBE THE OTHER RANDOM SEED INPUTS ARE BLOCKED OR ALSO HIJACKED.

Anon • February 29, 2016 12:14 AM

This entire debate is purely academic. Most things which need good entropy, like generation for private keys, doesn’t use your random source at all – they are hardcoded to create their own PRNG sequences from predicable starting seeds. (throw a few printf()’s into the set_seed() call if you’re not yet convinced). Looks random. Isn’t. Prime numbers are so much fun.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.