ABSTRACT: We discuss how to configure and use turbid, which is a Hardware Random Number Generator (HRNG), also called a True Random Generator (TRNG). It is suitable for a wide range of applications, from the simplest benign applications to the most demanding high-stakes adversarial applications, including cryptography and gaming. It relies on a combination of physical process and cryptological algorithms, rather than either of those separately. It harvests randomness from physical processes, and uses that randomness efficiently. The hash saturation principle is used to distill the data, so that the output is virtually 100% random for all practical purposes. This is calculated based on physical properties of the inputs, not merely estimated by looking at the statistics of the outputs. In contrast to a Pseudo-Random Generator, it has no internal state to worry about. In particular, we describe a low-cost high-performance implementation, using the computer’s audio I/O system.
Other keywords: TRNG, HRNG, hardware random number generator, uniform hash, unbiased coin flip.
The basic objective is to provide a copious supply of randomly-generated numbers, with quality and quantity suitable for a wide range of applications. Some specific applications are discussed in reference 1. Quality requires, among other things, defending against various possible attacks. Some well-known attacks are discussed in reference 1. Some background and theoretical ideas are outlined in section 6 and developed more fully in reference 1.
Right now, in this section, we give a broad outline of what is possible and what is not possible.
So far, we have analyzed the HRNG mainly in terms of the density of adamance, denoted by ρ. We choose a criterion ρmin very close to 100%, and then build a generator that produces ρ > ρmin. We are not pretending to achieve ρ = 100% exactly.
Here are some of the criteria on which a random generator can be judged:
These criteria conflict in complex ways:
These conflicts and tradeoffs leave us with more questions than answers. There are as-yet unanswered questions about the threat model, the cost of CPU cycles, the cost of obtaining raw randomness from physical processes, et cetera. The answers will vary wildly from machine to machine.
If you are stuck somewhere without turbid or other fancy tools, and you need some hard randomness right away, you might try the following:
Open-circuit the mic input on the computer. On a desktop this is trivial. On a laptop with a built-in microphone, this means finding a piece of wood or plastic with a diameter between 3 and 3.5 mm and sticking it into the mic jack. Use alsamixer to turn all the gains all the way up. Then use the command:
:; arecord --disable-softvol -f S32_LE -r 44100 -d 3 noise.wav :; aplay noise.wav :; cat noise.wav > /dev/random
Play back the file, and listen to it using speakers or headphones. If it doesn’t sound like white noise, try again until it does. Then stuff the file into /dev/random. You can use the .wav as-is; there is no need to reformat the data.
If the machine doesn’t have audio circuits at all, for a few dollars you can buy a USB audio dongle and use that.
If you have a decent A/D converter, it should have a bandwidth on the order of 18kHz or more, and should provide several bits of randomness per sample ... provided the mic input really is open-circuited and the gains are turned all the way up. If we degrade that to 1 kHz and 1 bit per sample, the noise.wav file should still contain 3000 bits of hard randomness, which should be plenty enough for initializing a cryptologically-strong PRNG.
Then use the PRNG to generate as many random samples as you like.
If you are in not such a big hurry, you should verify the randomness of the data. This can be done, approximately, using only relatively prosaic tools, as folllows:
:; arecord -f S32_LE -r 44100 -t raw --disable-softvol -d 3 noise.raw :; aplay -f S32_LE -r 44100 -t raw noise.raw :; <noise.raw od -t d4 -j400 -v -w4 -Anone -N8192 > noise.csv :; gnumeric noise-graphs.gnumeric :; gnumeric noise.csv # copy-and-paste into the other worksheet
Then you can use a spreadsheet app to look at the data. First look at it as a function of time, as in figure 1.
Then take the Fourier transform and look at it as a function of frequency, as in figure 2.
The spreadsheet used to produce these figures is cited in reference 2.
It is worth doing a certain amount of checking, because it’s easy to get fooled. The red signal (in figure 5) has at most 1 bit of randomness per sample. As you can see, it’s a two-state system. Problems like this, with too little randomness per sample, can arise naturally when the audio system digitizes the signal too coarsely.
Things are even worse in figure 5. It is a low-pass filtered version version of the previous signal. The samples are now correlated with one another, to a significant degree. The red signal has an effective bandwidth of only about 6000 Hz, even though the sample rate is the same as the blue signal, namely 44100 Hz. So the red signal has much less total randomness.
You can’t determine any of this just by listening, because all three signals sound more-or-less the same.
The Fourier transform will tell you the bandwidth, which is important, but it won’t tell you much about the amount of randomness per sample, which is also important.
If turbid runs as non-root, it will open its output FIFOs in your $HOME/dev/ directory, look for its control files in your $HOME/etc/turbid/ directory, and scribble a .pid file in your $HOME/var/run/ directory.
If turbid runs as root, it will use the system /dev/ and /etc/turbid/ /var/run/ directories.
It is remarkably easy to mis-configure a soundcard in such a way that it produces much less randomness than it otherwise would. This section outlines the general procedure; see appendix B for details on specific soundcards.
Terminology: we use the term soundcard loosely, to apply not just to individual cards per se, but also to audio I/O systems embedded on the mainboard, and to USB dongles, external pods, et cetera.
Turbid automatically takes commands from the configuration file turbid.tbd if it exists in the working directory. Other configuration files can be invoked using the “@” sign, as in turbid @foo.tbd for example.
If that doesn’t work, some investigation is required. The command aplay -L (capital letter L) and/or aplay -l (lowercase letter l) to see what audio devices are available. If there are none, or only trivial devices such as “null”, you might try bestowing membership in the “audio” group to the user who will be running turbid. If the card you want to use is not visible, check that the hardware is installed (lspci -v -v or lsusb -v -v). Then check that the appropriate drivers are loaded.
hw:CARD=Intel,DEV=0 HDA Intel, CX20561 Analog Direct hardware device without any conversions
in which case you can invoke turbid card hw:CARD=Intel,DEV=0.
card 0: Intel [HDA Intel], device 1: CX20561 Digital [CX20561 Digital] Subdevices: 1/1 Subdevice #0: subdevice #0
in which case you can invoke turbid card hw:0,1 where the zero is the card number and the 1 is the device number on that card.
Once you have identified a suitable card, if it’s not the default, you will have to specify card ... on the turbid command line (or in some .tbd configuration file) from now on.
Plug something such as a cable or a Y-adapter into the output port for the chosen channel and leave it plugged in from now on, at all times when turbid is running. That’s because I have seen situations where plugging and unplugging causes the mixer settings to get changed behind your back. The pulseaudio daemon is infamous for this, but there may be other culprits.
Use alsamixer to adjust the output to some reasonable level. You don’t want the output to clipped or otherwise distorted.
If you want to use some other filename, that’s fine, but then you will need to add the mixer someother.ctl option to every turbid invocation from now on.
Another option is to leave the turbid amplitude alone and use alsamixer to adjust the mixer settings until the desired output level is obtained. Then re-save the configuration as described in step 7.
In all cases, when we talk about a measured voltage – output voltage or input voltage – we mean RMS voltage (unless otherwise stated). If you are using an oscilloscope or something else that measures peak voltage, keep in in mind that the zero-to-peak amplitude of a sine wave is 1.4 times the RMS value ... and the peak-to-peak excursion is 2.8 times the RMS value.
As a point of reference, the ancient voltmeter I use for this is rock solid up to 1 kHz. There is a 1-pole corner at 4 kHz. Above roughly 30 kHz the bottom drops out. You do not need to check your voltmeter with anywhere this level of detail.
Note that turbid applies the sine option cumulatively, so that turbid ochan 0 sine -3 sine -3 is the same as turbid ochan 0 sine -6.
turbid sine 0 Vopen .272 show xvout exit turbid sine -6 Vopen .136 show xvout exit
This will print a line of the form:
XVout: 0.272 # freq: 440 sine_level: 0 Vopen: 0.272 XVout: 0.271356 # freq: 440 sine_level: -6 Vopen: 0.136
The two XVout values are not quite identical, because 6 dB is not exactly a factor of 2 in voltage. Also the voltmeter is subject to roundoff error and other inaccuracies.
Put the XVout: line into a file with a nice short name, perhaps “x”. Put @x on the turbid command line from now on.
turbid @x ochan 0 sine 1
and measure the voltage across the resistor. Then get turbid to do the calculation for you
turbid @x sine 1 Rload 100 Vloaded .173 show Rout exit
This will print a line of the form
Rout: 57.2254 # Rload: 100 Vloaded: 0.173 sine_level: 0
Stick that line into the “x” file. That allows turbid to know the XVout and Rout values. That means turbid knows what voltage it is outputting, so you don’t have to measure it with a voltmeter.
For an explanation of how this is calculated, see appendix E.
This is scary, because if you try to monitor the input in such a way that the microphone bias voltage gets routed to a real stereo input, it is entirely possible for the DC on the right channel to blow out your speaker.
However, on most machines I don’t know how to do this. It may be that the hardware doesn’t support it, or the ALSA drivers don’t support it, or I’m not smart enough to figure it out. If anybody has good information on this, please let me know.
It may not be entirely obvious a priori what is your best is. You may have to go through the calibration process on each input to decide which provides the most unpredictability per unit time.
Take a moment to think about the following issue: We want to set up full-duplex audio. Full duplex means that the input subsystem is independent of the output subsystem. Most likely, you will have to fiddle with mixer settings (using alsamixer) to get this to work. Presumably you already have the output working (section 4.1), so now we need to get the input working without messing up the output.
This is trickier than it might seem, because recording engineers very commonly want to monitor the signal that is being recorded, so mixers usually provide a path whereby the input signal can be looped back to some output. This kind of loopback interferes with what we are trying to do. This kind of mixer mis-configuration is sometimes hard to detect. Note the contrast:
|Recording engineers want to do input, with immediate re-output via the mixer (hairpin).||We want to do output, with immediate re-input via the QA box (loopback).|
Therefore, when configuring the input subsystem, by far the safest procedure is to use a signal that comes from somewhere else. So we need two systems:
So ... here’s the plan:
In other words, turbid needs to do input, it needs to do output, and the two things need to be independent.
To help you interpret the numbers that turbid puts put, please refer to the discussion of units (such as ibu and dBx) in appendix D. Here are some of the things you might observe at this stage:
Set the recording-mode controls on the mixer to enable the chosen input port as the capture source. To check for clipping, fire up
turbid @x ochan 0 ichan 0 show clipping
For pedestrian listening-type mixer settings, the output might be something like this:
Input clip check: top 1 times @ 0.0402663 ibu bot 1 times @ -0.0399549 ibu Input clip check: top 1 times @ 0.0379069 ibu bot 1 times @ -0.0378201 ibu Input clip check: top 1 times @ 0.0433064 ibu bot 1 times @ -0.0342267 ibu
Here’s how to decode that: An ibu is an input buffer unit. The value that can possibly occur in the input buffer is 1 ibu. In the example here, the signal in the input buffer achieved a high-water mark that is only a few percent of the maximum possible value, and it hit that mark only once. Similar words apply to the minimum value. Conclusion: Clipping is not a problem here. We have lots of headroom.
The next step is to turn the mixer gain sliders up as high as they can reasonably go (usually all the way). If there is a “Mic Boost” slider, turn it up also, as high as it can go without clipping when there is nothing but noise on the input. You want every element in the input-chain to be turned up as high as it can go without clipping.
Typical output, with the gain all the way up, feeding the input with high impedance:
Input clip check: top 1 times @ 0.1709 ibu bot 1 times @ -0.1704 ibu Input clip check: top 1 times @ 0.1733 ibu bot 1 times @ -0.1754 ibu Input clip check: top 1 times @ 0.1669 ibu bot 1 times @ -0.1762 ibu
This is still good, no clipping, lots of headroom.
Use the voltmeter to re-measure the output level signal. It should be within 1% or so of the open-circuit voltage measured previously. It won’t be quite the same, because the calibration box imposes some slight load on the output. This mostly serves to make sure you did not inadvertently disturb the output-channel mixer settings during step 19.
Fire up turbid @x ochan 0 ichan 0 sine 1 show clipping to see what happens when the calibrator signal is applied to the input. The results may look like this:
Input clip check: top 834 times @ 1 ibu bot 784 times @ -1 ibu Input clip check: top 831 times @ 1 ibu bot 787 times @ -1 ibu Input clip check: top 779 times @ 1 ibu bot 847 times @ -1 ibu Input clip check: top 799 times @ 1 ibu bot 821 times @ -1 ibu
Here’s how to decode that: The maximum possible value in the input buffer is 1.0 ibu. The signal achieved that level hundreds of times. There is rampant clipping going on.
Lower the calibrator amplitude to make the clipping go away. For example: turbid @x ochan 0 ichan 0 sine -15 show clipping. Typical output:
Input clip check: top 1 times @ 0.5824 ibu bot 1 times @ -0.5783 ibu Input clip check: top 1 times @ 0.5851 ibu bot 1 times @ -0.5744 ibu Input clip check: top 1 times @ 0.5764 ibu bot 1 times @ -0.5774 ibu
A peak value on the order of 0.9 ibu is nice.
Do not cure saturation by lowering the gain of the input channel! That would reduce the rate of production of unpredictability. Instead, just lower the amplitude of the calibrator signal. In the unlikely event that you can’t lower the output signal enough, increase the amount of attenuation. This may require an additional resistor in the calibration box.
turbid @x ochan 0 ichan 0 sine -15 show clipping lbw 1 sine -6 Input clip check: top 1 times @ 0.2993 ibu bot 1 times @ -0.3091 ibu Input clip check: top 1 times @ 0.2938 ibu bot 1 times @ -0.3074 ibu Input clip check: top 1 times @ 0.3034 ibu bot 1 times @ -0.3044 ibu
If you’re curious, you can measure the noise floor directly:
turbid @x ochan 0 ichan 0 sine -11 show clipping lbw 1 sine -100 Input clip check: top 1 times @ 0.03504 ibu bot 1 times @ -0.03155 ibu Input clip check: top 1 times @ 0.03184 ibu bot 1 times @ -0.03368 ibu Input clip check: top 1 times @ 0.03663 ibu bot 1 times @ -0.0304 ibu
The most important objective at this step is to make sure there is no AGC (automatic gain control) on the input. AGC will drive you crazy. If necessary, fiddle with the mixer controls to make sure AGC is turned off.
Note that you can give the sine ... option more than once, and turbid will do the arithmetic for you. So you can use the first sine ... to set the level at a nice round number, and then use another sine -6 to reduce the voltage by a factor of 2 from there.
Now hook up the QA cable. From now on we will not be jumpering across the QA cable resistors; we are using them as a standard of comparison for calibrating the input impedance of the soundcard. Attach the voltmeter to the high side of the resistor, the side toward the output stage of the soundcard. (The low side will be measured by the input stage of the soundcard.)
Restart turbid, passing it the new voltmeter reading. This might be slightly higher than the previous reading (because the high impedance of the QA cable loads the soundcard output somewhat less than a direct connection to the soundcard input does), but not much higher (and certainly not lower).
Using this information, turbid will be able to determine the input impedance R of the soundcard port you are using.
Restart turbid, passing it this R value. The command should look something like turbid -v -A -8 -F 440 -V .200 -Q 1.31e-6 -R 9400. As a check, observe that the Vin/Vmeter/divider number is close to unity. (The Vin/Vmeter number itself will be small compared to unity, because there is a voltage divider between what the voltmeter is measuring and what the soundcard input is measuring.)
At this point turbid will also be displaying a number (Kout) which is basically the voltage (as would be measured by the voltmeter) corresponding to the internal representation of a certain “standard” sine wave.
Restart turbid, passing it this K value. From now on, we no longer need the voltmeter. You should erase the -V argument from the command line. We will rely on the calibrated output of the soundcard to complete the calibration of the input. This has the advantage that the soundcard can probably be trusted over a wider frequency range than the voltmeter can.
You can test this by changing the frequency of the calibrator. The command should look something like turbid -v -A -8 -F ... -Q 1.31e-6 -R 9400 -K .152. Verify that Vin/Vout/divider ratio remains near unity over a wide range of frequencies. It will start to drop off at high frequencies (above 15 or 20 kHz).
Restart turbid, passing it the option “-F BB”. Overall, command should look something like turbid -v -A -8 -F BB -Q 1.31e-6 -R 9400 -K .152. This does not actually emit a negative-frequency sine wave; instead it emist a broadband probe signal. The program will then print out a measurement of the bandwidth. See appendix C for an explanation of the measurement technique.
This completes the calibration process. See section 5 for a discussion of normal (non-calibration) operations.
Please send me <email@example.com> the .ctl file for your card, and the values for the -Q -R -B and -K settings. I will add it to the distribution, so that others may use that brand of cards without having fuss with calibration.
Note the contrast:
|Calibration Box||QA Box|
|A calibration box is used temporarily for calibration. You need only one, since it is unlikely that you will be calibrating more than one machine at a time. You don’t need this at all if somebody has previously calibrated an identical machine and given you the the .ctl file for your mixer, and the .tbd file for turbid itself.||For long-term quality assurance, a simpler box is used. For this you need one box per machine. You don’t need this at all if you’re not interested in integrity checking.|
|If you are mass-producing things, you may want to build an QA cable with resistors built right into the cable (rather than a box per se). That is fine for integrity monitoring, but not convenient for calibration. We will pursue that topic here.|
The following tools will be needed only temporarily for building the calibration box, so if you don’t have them on hand you will have to buy or borrow them:
The following components will be needed, so if you don’t have them on hand you will have to go to an electronics-hobby store and buy them:
The following tools will be needed whenever you are calibrating a soundcard. This assumes you have already built the calibration box:
Figure 11 shows the circuit diagram for the QA box.
“Production mode” stands in contrast to “calibration mode”.
In production mode, you must provide values for Q, R, and B. No other parameters are needed, but there are a lot of options, as we now discuss.
To verify that turbid is working, you can look at the output, e.g. od -A n -t u1 -N 32 /dev/hrandom (or $HOME/dev/hrandom if you are running it as non-root). Also, turning up the verbosity level (turbid -v or turbid -vv) will display some information about the internal workings. The meaning of some of the dislayed items is documented in section 4.
If you are running a lot of legacy applications you might want to turn on the -f option as described in section 5.3. The program will write random bits to the output fifo, and will block waiting for somebody to read them. For example: turbid -Q 2.076e-07 -R 2800 -B 36200 -f. You can add the -d option if you want it to detach and run as a daemon.
The output of turbid is double-buffered, 512 bytes per buffer. The main reasons for this include:
Note that you have to be careful when using dd, because it unwisely counts blocks, not bytes. If you want to use dd to capture, say, a megabyte from /dev/random, it is advisable to use two copies of dd in a pipeline:
dd if=/dev/random obs=512 | dd bs=512 count=2k
The first dd performs reblocking while the second dd does the counting. A similar scheme is required at the output of turbid if you want to use dd with a blocksize that is not a divisior of 512 (and possibly under other conditions).
In code that you write yourself, no reblocking is required. You can keep out of trouble very easily, just by paying attention to the number of bytes actually returned by each read() request (which will sometimes be less than the number requested).
While we’re discussing buffering, note that the Linux /dev/random can buffer approximately 4096 bits, but you can’t trust ioctl(, RNDGETENTCNT, ) to tell you how much is really there. Sometimes when the ioctl reports 4096 bits, the buffer can be exhausted by reading as little as 342 bytes (2736 bits).
If you specify turbid -f, a subprocess will take some of the output and feeds it to /dev/random whenever the latter is running short of randomness. This means that applications such as GnuPG that rely on /dev/random will run nicely, without blocking.
Runtime efficiency would be improved by rewriting the applications to use /dev/hrandom directly, but this is not always convenient.
You should leave this feature turned off if you are not running as root, since /dev/random doesn’t trust deposits from non-root sources.
Also, you may want to leave it turned off under the following conditions: Suppose some application is consuming vast quantities of low-grade randomness from /dev/urandom (perhaps to obliterate a multi-gigabyte file or some such). Due to a misfeature of the Linux kernel random-number system, every byte you read from /dev/urandom takes one byte away from the pool of stored randomness in /dev/random. Therefore the feeder subprocess, in the attempt to keep /dev/random happy, will consume a great deal of randomness from /dev/hrandom, in competition with other processes that want to use /dev/hrandom.
As discussed in section 10, this problem is intrinsic to /dev/urandom. Avoid using /dev/urandom. The solution is to use /dev/srandom instead. See section 5.4.
The turbid program comes bundled with a Stretched Random Generator. Its density of randomnes is strictly greater than zero but less than 100%. To use it, read from /dev/srandom.
The SRNG seeds itself, and reseeds itself every so often, using random seed material from the HRNG. Reading from /dev/srandom consumes randomness 10,000 times more sparingly than reading from /dev/hrandom or /dev/random or /dev/urandom. It is also less compute-intensive than /dev/urandom.
The principle of operation is as follows: In addition to the seeding/reseeding process, there is a state variable, a deterministic update function, and a hash function. Between reseedings, at each iteration we deterministically update the state variable and feed it to the hash function. The output of the hash function is the output of the SRNG.
The update function treats the state variable as three 32-bit registers. Each register has a random starting point. The first register is updated by adding a random odd addend. The second is a Linear Feedback Shift Register. The third is another LFSR, with a different period. (This design was chosen because each register can be separately tested, in contrast to one big 96-bit LFSR which would be harder to test.) Each register separately has a period on the order of 232 and combined they give a period on the order of 296. The period is billions upon billions of times longer than it needs to be, because after 10,000 iterations the state variable is strongly perturbed using 128 bits of pure randomness from the HRNG.
It is commonly assumed that having a super-long period is a hallmark of a good PRNG. However, that’s neither necessary nor sufficient. A 4000-bit LFSR has a period of 24000 or so, but it can easily be cryptanalyzed on the basis of only 4000 observations (unless it is protected by a strong one-way function installed between the LFSR and the observable output). It is necessary to have a period long compared to the interval between reseedings, but it is not necessary to make it much longer than that. In summary, if the period is long enough, making it longer confers no advantage.
Unlike the HRNG, the SRNG must assume that the hash function has the one-way property. That is, we assume an adversary (even after ∼10,000 observations of the output of the hash function) cannot infer anything useful about the state variable.
The defining property of a SRNG is that it has an average density of adamance that is greater than zero but less than 100%. Let’s take a moment to discuss where in the output-stream this adamance is to be found. Suppose you have 1024 bits of adamance available for seeding your generator, which you then use to put out a very long output string.
Turbid is meant to be easy to use, yet robust enough to handle a wide range of applications, including high-stakes adversarial applications. It is a True Randomness Generator (TRNG), specifically a Hardware Randomness Generator (HRNG)
This stands in contrast to garden-variety “Random Number Generators” that may be good for non-demanding applications, but fail miserably if attacked. See reference 1 for a discussion of the range of applications, and of some of the things that can go wrong.
We now explain some theoretical ideas that will be important:
We have implemented a generator using these principles. Salient engineering features include:
If you ask three different people, you might get six or seven different definitions of “random”.
At a minimum, we need to consider the following ideas:
For example: Once upon a time I was working on a project that required a random generator. The pointy-haired boss directed me to get rid of my LFSR and instead use the value of the program counter (PC) as saved by the last interrupt, because that was «unpredictable». I kid thee not. In fact the PC was a terrible RNG. Successive calls tended to return the same value, and even if you got two different values, one of them was likely to be the PC of the null job (which was hardly surprising, since it was an event-driven system).
I tried to explain to him that even though the PC was not reliably predicatable, it was not reliably unpredictable. In other words, it was squish, with no useful lower bound on the amount of randomness.
The terminology is not well settled. I have heard intelligent experts call items 1, 2, 4, and 5 on the previous list “random”. I have also heard them call items 3, 4, and 5 “non-random” or “not really random”. Sometimes even item 2 is included in the catagory of “not really random”.
We consider the terms “random” and “non-random” to be vague, clumsy, and prone to misunderstanding. If a precise meaning is intended, careful clarification is necessary. This remains something of an unsolved problem, especially when talking about PRNGs.
Beware that in the cryptology community, the word «entropy» is rather widely abused. Sometimes it is thrown around as an all-purpose synonym for randomness, even in situations where the signal contains absolutely no real physics entropy. This is a bummer, because in physics, entropy has an agreed-upon, specific, and exceedingly useful meaning.
On the other hand, in the long run it’s not much of a problem, because it turns out that the physics entropy was almost certainly never what you wanted anyway. There exist distributions where the entropy is infinite but the adamance is only two bits. An adversary would have a rather easy time guessing some outputs of such a distribution, even though the entropy is infinite.
The essential concept here is probability distribution. The entropy is only one property of the distribution. See reference 1 for more discussion of this point.
In this document, and in reference 1, we use the word “entropy” in the strictest sense: “entropy” means physics entropy. The terms entropy and adamance are assigned very formal, specific meanings.
The contrast between a TRNG and a PRNG can be understood as follows:
|A Pseudo-Random Generator (PRNG) depends on an internal state variable. That means that if I wanted to, I could give my friend a copy of my PRNG (including the internal state) and then his PRNG would produce the same outputs as my PRNG.||A True Random Generator (TRNG) such as a Hardware Random Generator (HRNG) has the property that the outputs are unpredictable in principle. It does not have any internal state. If I give a copy to my friend, not only can he not predict the output of my TRNG, I cannot even predict the output of my own TRNG.|
|A high-quality PRNG depends on the assumption that it is computationally infeasible for any adversary to infer the internal state by observing the outputs. More generally, the assumption is that the adversary will find it not worthwhile to infer the internal state. This is a moving target, depending to some degree on the value of whatever the pseudo-random distribution is protecting.||A proper TRNG does not have any internal state. It does not need to be initialized.|
|Every PRNG depends on some crucial assumptions, namely the existence of a one-way function that is resistant to cryptanalytic attack.||To a lesser extent, the same is true for every practical HRNG that I know of.|
|This is probably not a serious limitation for a well-implemented PRNG. That’s because all of modern cryptography relies on similar assumptions. If these assumptions were to break down, the RNG would be the least of your problems. Still, one should always keep in mind that these assumptions are unproven.||This is even less of a problem for a HRNG, because any attack will be much more difficult to carry out. It is a known-codetext attack, with vastly less codetext available.|
Pseudo-random generators, as a class, suffer from a number of problems. For starters, the state variable must be initialized, which is often remarkably problematic. Thereafter, the state variable must be preserved and defended for all time, which is problematic, too.
Initializing the secret internal state variable is called seeding the PRNG. A basic PRNG is seeded only once, at the start of operations. There is some finite amount of randomness in the seed. As the PRNG produces more and more output, the density of randomness in the output goes asymptotically to zero.
The rand() or random() functions provided by typical computer languages are in fact basic pseudo-random generators of this kind.
The concept of PRNG cannot stand on its own, because any PRNG requires a seed. We have to ask where the seed came from. If it came from some other PRNG, we have to ask where the other seed came from. The only way to avoid infinite regress is to use a HRNG to provide a seed.
To be clear: A HRNG can exist without a PRNG, but not vice versa.
Higher security can be obtained if the PRNG is wrapped within a larger system that re-seeds the PRNG every so often. The overall system could be considered an “improved” PRNG, but really it sits in a gray area between the basic PRNG and a TRNG. I prefer to call it a Stretched Random Generator (SRNG).
item Unlike a TRNG, a SRNG produces an output that is predicable for a time, if the adversary captures the seed.Unlike a simple PRNG, the SRNG remains predicable for only a bounded amount of time, i.e. until the next reseeding.
The SRNG is a hybrid, with some internal state and some physical source of randomness. This may be able to produce symbols more copiously than a purely stateless system, while remaining highly resistant to cryptanalysis.
Note the contrast:
Understanding turbid requires some interdisciplinary skills. It requires physics, analog electronics, and cryptography. If you are weak in one of those areas, it could take you a year to catch up.
This section exists mainly to dispel some misconceptions. Sometimes people decide that the the laws of physics do not apply to electronics, or decide on the basis of “intuition” that the noise in their audio system is negligible. If you do not suffer from these particular misconceptions, feel free to skip to section 7.3.
|A digital logic gate has considerable noise immunity. Noise, if it is not too large, is eliminated at every step. This requires both nonlinearity and power dissipation.||A linear analog system cannot eliminate noise in the same way. The fundamental equations of motion do not allow it.|
In principle, there are many physical devices that could be used as the source of raw randomness. We prefer the audio system (the “soundcard”) because such things are cheap, widely available, and easy to calibrate. We have a provable lower bound on the rate at which they produce randomness, and this rate in sufficient for a wide range of applications. This provides a way to make typical hosts very much more secure than they are now.
In contrast, a video frame-grabber card would produce randomness more copiously, but would be much more costly. Calibration and quality-assurance monitoring would be much more difficult.
There are many other sources that “might” produce usable randomness, but for which a provable nonzero lower bound is not available.
As mentioned before, we need a lower bound on the amount of randomness per sample. This is needed to ensure that the hash function’s buffer contains “enough” randomness, as discussed in reference 1.
Let us briefly explore the consequences of mis-estimating the amount of randomness in the raw data:
- 1a) If we make a slight overestimate, it means that the hash function, rather than putting out 2160 different outputs, will put out some rather smaller ensemble. In mild cases this may not be noticeable in practice.
- 1b) A major overestimate may allow an adversary to focus an attack on the few output-words being produced.
- 2a) If we modestly underestimate the amount of randomness in the raw data, there is no serious harm done.
- 2b) A major underestimate will reduce the total randomness production capability of the machine. This means the processes that consume random symbols may block, waiting for the HRNG to produce a usable output.
We looked at the power spectrum of the signal produced by a number of different sound cards. Based on these observations, and on general engineering principles, we can list various hypotheses as to what physical processes could be at work, namely:
Some of these are undoubtedly fine sources of randomness. The only problem is that except for item #1, we cannot calculate their magnitude without a great deal more engineering knowledge about the innards of the card. Using these sources might produce a HRNG that is correct, but not provably correct. Since we want something that is provably correct, we simply ignore these other contributions. They can’t hurt, and almost certainly provide a huge margin of safety.
That is: We need randomness in the raw data, and we need to know a provable lower bound on the amount of randomness. Turbid consistently applies the principle that having extra randomness is OK, and underestimating the amount of randomness is OK. This may give us less-than-optimally efficient use of the available randomness, but it guarantees correctness. Turbid consistently chooses correctness over efficiency.
Just to help you get the lay of the land, here are the key characteristics of a few soundcards. The older cards are of historical interest only. More recent cards perform better.
|Card||Q / µV||RIn / Ω||Kout||B||N||σ / µV||s / bits||ROut / Ω|
|Thinkpad cs4239 (Line)||19.6||7900||.037||9000||44100||1.07||0|
|Thinkpad cs4239 (Mike)||1.65||10100||.038||7300||44100||1.09||1.58|
Note that the CT4700 reports itself as “ENS1370” so it uses the ens1370.ctl control file.
By way of analogy, let us consider the relationship between code-breakers and code-makers. This is a complex ever-changing contest. The code-breakers make progress now and then, but the code-makers make progress, too. It is like an “arms race” but much less symmetric, so we prefer the term cat-and-mouse game.
At present, by all accounts, cryptographers enjoy a very lopsided advantage in this game.
There is an analogous relationship between those who make PRNGs and those who offer tools to test for randomness. The PRNG has a hidden pattern. Supposedly the tester “wants” the pattern to be found, while the PRNG-maker doesn’t.
We remark that in addition to the various programs that bill themselves as randomness-testers, any off-the-shelf compression routine can be used as a test: If the data is compressible, it isn’t random.
To deepen our understanding of the testing issue, let’s consider the following scenario: Suppose I establish a web server that puts out pseudo-random bytes. The underlying PRNG is very simple, namely a counter strongly encrypted with a key of my choosing. Each weekend, I choose a new key and reveal the old key.
The funny thing about this scenario is the difference between last week’s PRNG and this week’s PRNG. Specifically: this week’s PRNG will pass any empirical tests for randomness that my adversary cares to run, while last week’s PRNG can easily be shown to be highly non-random, by means of a simple test involving the now-known key.
As a modification of the previous scenario, suppose that each weekend I release a set of one billion keys, such that the key to last week’s PRNG is somewhere in that set. In this scenario, last week’s PRNG can still be shown to be highly non-random, but the test will be very laborious, involving on the order of a billion decryptions.
Note that to be effective against this PRNG, the randomness-testing program will need to release a new version each week. Each version will need to contain the billions of keys needed for checking whether my PRNG-server is “random” or not. This makes a mockery of the idea that there could ever be an all-purpose randomness tester. Even a tester that claims to be “universal” cannot be universal in any practical sense.2 An all-purpose randomness tester would be tantamount to an automatic all-purpose encryption-breaking machine.
To paraphrase Dijkstra: Measurement can prove the absence of randomness, but it cannot prove the presence of randomness. More specifically, any attempt to apply statistical tests to the output of the RNG will give an upper bound on the amount of randomness, but what we need is a lower bound, which is something else entirely.
As described in reference 1, we can calculate the amount of randomness in a physica process, based on a few macroscopic physical properties of the hardware. It is entirely appropriate to measure these macroscopic properties, and to remeasure them occasionally to verify that the hardware hasn’t failed. This provides a lower bound on the randomness, which is vastly more valuable than a statistically-measured upper bound.
As discussed in reference 1, tests such as Diehard (reference 9) and Maurer’s Universal Statistical Test (reference 10) are far from sufficient to prove the correctess of turbid. They provide upper bounds, whereas we need a lower bound.
When applied to the raw data (at the input to the hash function) such tests report nothing more than the obvious fact that the raw data is not 100% random. When applied to the output of the hash function, they are unable to find patterns, even when the density of randomness is 0%, a far cry from the standard (100%) we have set for ourselves.
A related point: Suppose you suspect a hitherto-undetected weakness in turbid. There are only a few possibilities:
The foregoing is a special case of a more general rule: it is hard to discover a pattern unless you have a pretty good idea what you’re looking for. Anything that could automatically discover general patterns would be a universal automatic code-breaker, and there is no reason to believe such a thing will exist anytime soon.
There are some tests that make sense. For instance:
On the one hand, there is nothing wrong with making measurements, if you know what you’re doing. On the other hand, people have gotten into trouble, again and again, by measuring an upper bound on the randomness and mistaking it for a lower bound.
The raison d’etre of turbid is that it provides a reliable lower bound on the density of randomness, relying on physics, not relying on empirical upper bounds.
We ran Maurer’s Universal Statistical Test (reference 10) a few times on the output of turbid. We also ran Diehard. No problems were detected. This is totally unsurprising, and it must be emphasized that we are not touting this a serious selling point for turbid; we hold turbid to an incomparably higher standard. As discussed in section 8.2, for a RNG to be considered high quality, we consider it necessary but nowhere near sufficient for it to pass statistical tests.
To summarize this subsection: At runtime, turbid makes specific checks for common failures. As discussed in section 8.3 occasionally but not routinely apply general-purpose tests to the output.
We believe non-specific tests are very unlikely to detect deficiencies in the raw data (except the grossest of deficiencies), because the hash function conceals a multitude of sins. You, the user, are welcome to apply whatever additional tests you like; who knows, you might catch an error.
We must consider the possibility that something might go wrong with our randomness generator. For example, the front-end transistor in the sound card might get damaged, losing its gain (partially or completely). Or there could be a hardware or software bug in the computer that performs that hashing and control functions. We start by considering the case where the failure is detected. (The other case is considered in section 9.2.)
At this point, there are two major options:
We can ornament either of those options by printing an error message somewhere, but experience indicates that such error messages tend to be ignored.
If the throttling option is selected, you might want to have multiple independent generators, so that if one is down, you can rely on the other(s).
The choice of throttling versus concealment depends on the application. There are plenty of high-grade applications where concealment would not be appropriate, since it is tantamount to hoping that your adversary won’t notice the degradation of your random generator.
In any case, there needs to be an option for turning off error concealment, since it interferes with measurement and testing as described in section 8.
We can also try to defend against undetected flaws in the system. Someone could make a cryptanalytic breakthrough, revealing a flaw in the hash algorithm. Or there could be a hardware failure that is undetected by our quality-assurance system.
One option would be to build two independent instances of the generator (using different hardware and different hash algorithms) and combine the outputs. The combining function could be yet another hash function, or something simple like XOR.
For a discussion of the Fortuna class of random generators, and how that contrasts with turbid, see reference 11.
For a discussion of the Linux device driver for /dev/random and /dev/urandom, see reference 12.
There is a vast literature on hash functions in general. Reference 13 is a starting point. Reference 14 is a useful literature survey. Reference 15 was an influential early program for harvesting randomness from the audio system; it differs from turbid in not having calibration features. Reference 16 uses the physics of a spinning disk as a source of randomness.
Methods for removing bias from a coin-toss go back to von Neuman; see reference 17 and references therein; also reference 18.
Reference 19 suggests hashing 308 bits (biased 99% toward zero) and taking the low-order 5 bits of the hash to produce an unbiased result. This is correct as far as it goes, but it is inefficient, wasting 80% of the input adamance. Presumably that reflects an incomplete understanding of the hash-saturation principle, in particular the homogeneity property discussed in reference 1, which would have led immediately to consideration of wider hashcodes. There is also no attempt to quantify how closely the results come to being unbiased.
Thanks to Steve Bellovin, Paul Honig, and David Wagner for encouragement, incisive questions, and valuable suggestions.
Practical sources of randomness can be characterized in terms of the adamance density. The raw sources have an adamance density greater than zero and less than 100%. The methods disclosed here make it possible to produce an output that approaches 100% adamance density as closely as you wish, producing symbols that are random enough for any practical purpose. It is important to have a calculated lower bound on the adamance density. In contrast, statistical tests provide only an upper bound, which is not what we need.
It is possible to generate industrial-strength randomness at very low cost, for example by distilling the randomness that is present in ordinary audio interfaces.
In order to refine our notions of what is random and what is not, consider the following million-character strings. We start with
That seems distinctly non-random, very predictable, not very complex. Next, consider the string
That seems also non-random, very predictable, not very complex.
That is somewhat more interesting. The digits pass all known tests for randomness with one narrow exception (namely tests that check for digits of π). However, they must still be considered completely predictable. Finally, consider the two strings
The million-character string represented by example E5 is, as far as anybody knows, completely random and unpredictable. Example E4 is very similar, except that the letter “A” appears more often than it would by chance. This string is mostly unpredictable, but contains a small element of nonrandomness and predictability.
Following Solomonoff (reference 20 and reference 21) and Chaitin (reference 22) we quantify the surprisal of a string of symbols as follows:
Let z be a string of symbols. The elements of z are denoted zk and are drawn from some alphabet Z. The number of symbols in the alphabet is denoted #Z.
Let PC(z) be the probability that computer programs, when run on a given computer C, will print z and then halt. The surprisal is defined to be the negative logarithm of this probability, denoted $C(z) := − logPC(z). In this paper we choose to use base-2 logarithms, so that surprisal is measured in bits. Surprisal is also known as the surprise value or equivalently the unexpectedness. It is intimately related to entropy, as discussed below.
Note that we are using one probability distribution (the probability of choosing a computer program) to derive another (the probability PC(z) of a symbol string). To get this process started, we need to specify a method for choosing the programs. Better yet, using the notions of measure theory, we realize that probability need not involve choosing at all; instead all we really need is a method for assigning weight (i.e. measure) to each of the possible programs. Here is a simple method:3 Consider all possible programs of length exactly L* (measured in bits, since we are representing all programs as bit-strings). Assign each such program equal measure, namely 2−L*. Then test each one and count how many of them produce the desired output string z and then halt, when run on the given computer C. The measure of a string is the total measure of the set of programs that produce it. A string that can be produced by many different programs accumulates a large probability.
In this construction, a short program X (i.e. one which has a length L(X) less than L*) is not represented directly, but instead is represented by its children, i.e. programs formed from X by padding it with comments to reach the required length L*. There are at least 2L*−L(X) ways of doing the padding, and each way contributes 2−L* to the total measure. This means that a string z that can be produced by a short programs X will have a probability at least 2−L(X), no matter how large L* is. We take the limit as L* becomes very large and use this in the definition of PC(z).
Usually the probability PC(z) is dominated by (the children of) the shortest program that produces z. Therefore some people like to use the length of this shortest program as an estimate of the surprisal. This is often a good estimate, but it should not be taken as the definition.
The explicit dependence of PC(z) on the choice of computer C calls attention to an element of arbitrariness that is inherent in any definition of surprisal. Different people will assign different values to “the” surprisal, depending on what resources they have, and on what a priori information they have about the situation.
In an adversarial situation such as cryptography, we suggest that probabilities be defined in terms of the adversary’s computer. If you have multiple adversaries, they can be treated as a single adversary with a parallel computer.
In this section, for conciseness, we drop the subscript C ... but you should remember that the probabilities and related quantities are still implicitly dependent on the choice of C.
A relatively minor objection to this definition of surprisal is that PC(z) includes contributions from arbitrarily-long programs. That is a problem in theory, but in practice the sum is dominated by relatively short programs, and the limit converges quickly.
A much more serious objection is that even for modest-sized programs, the definition runs afoul of the halting problem. That is, there may well be programs that run for a million years without halting, and we don’t know whether they would eventually produce string z and then halt. This means the surprisal, as defined here, is a formally uncomputable quantity.
We will duck both these issues, except for the following remarks.
In this section we shift attention from the unpredictability of strings to the unpredictability of the individual symbols making up the string.
Let us re-examine the examples given at the beginning of this section. Example E5 has surprisal $(z) very close to L(z) log(#Z). We classify strings of this sort as absolutely-random, by which we mean algorithmically-random.
Examples E1, E2, and E3 all have surprisal much less than their length. These strings are clearly not absolutely-random.
The interesting case is example E4. Intuitively, we think of this as “somewhat unpredictable” but more predictable than E5. To make this notion quantitative, we introduce the notion of surprise density. The following quantity tells us the surprise density of the string z in the region from i to j:
where Front(z,i) is the substring formed by taking the first i symbols of the string z.
The surprise density for examples E1, E2, and E3 is zero for any region not too near the beginning. The surprise density for example E5 is as large as it possibly could be, namely 100% of log(#Z). Example E4 illustrates the interesting case where the surprise density is quite a bit greater than zero, but not quite 100% of log(#Z).
As mentioned in section 6.2, we consider the unadorned term “random” to be ambiguous, because it means different things to different people. Some people think “random” should denote 100% surprise density, and anything less than that is “non-random” even if it contains a great deal of unpredictability. Other folks think that “random” refers to anything with an surprisal density greater than zero, and “non-random” means completely predictable. Yet other folks extend “random” to include pseudo-random strings, as long as they are “random enough” for some application of interest. Even some professionals in the field use the word this way; reference 23 and the more recent reference 24 speak of “deterministic random number generators”, although it could be argued that it is impossible in principle for a process to be both deterministic and random. The randomness of a PRNG comes from the seed. Calling a PRNG “deterministic” seriously understates the importance of the seed.
In the space of all possible strings, almost all strings are absolutely-random, i.e. are algorithmically-random, i.e. contain 100% surprise density. However, the strings we find in nature, and the strings we can easily describe, all have very little surprise density. We can summarize this by saying: “All strings are absolutely-random, except for the ones we know about”.
We can use similar ideas to describe PRNGs and contrast them with HRNGs.
|Most of modern cryptography revolves around notions of computational intractability. (I’m not saying that’s good or bad; it is what it is.||In contrast, there is another set of notions, including adamance, entropy, and the related notion of unicity distance, that have got nothing to do with computational intractability.|
|The long strings produced by a good PRNG are conditionally compressible in the sense that we know there exists a shorter representation, but at the same time we believe them to be conditionally incompressible in the sense that the adversary has no feasible way of finding a shorter representation.||The long strings produced by a HRNG are unconditionally, absolutely incompressible. Specifically, the set of strings collectively cannot be compressed at all. As for each string individually, it is not compressible either, except possibly for trivially rare cases and/or trivial amounts of compression.|
This section is a collection of details about certain soundcards. (You can refer back to table 2 for a summary of the performance of a few soundcards. Also, section 4 provides step-by-step procedures that apply to “generic” soundcards.)
Soundcards generally include mixer functions. You have to initialize the mixer, to set the sliders on the features you want and/or to set the switches to bypass the features you don’t want. This is a bit of a black art, because the soundcards typically don’t come with any “principles of operation” documentation.
Graphical user interface (GUI) programs such as alsamixer may help you make some settings, but may not suffice to fully configure the mixer. All too often, the card has “routing switches” and other features that the GUI doesn’t know about. A reasonable procedure that gives complete control is to invoke “alsactl -f record.ctl store”, edit record.ctl, then “alsactl -f record.ctl restore”. Or you can use amixer to fiddle one setting without disturbing others.
The Intel High-Definition Audio spec (reference 25) describes the codec but says remarkably little about mixer functions.
This is yet another example of hype and deception from Creative Labs. The device itself, the box it comes in, and the advertising all prominently mention USB, 24-bit audio, and 96 kHz sampling rates. However, according to all available evidence, the device will not transmit 24-bit audio via USB to the DACs or from the ADCs (no matter what the data rate). It also will not transmit 96 kHz samples via USB to the DACs or from the ADCs (no matter what the word size).
Apparently the only way in which the Extigy can deal with 24 bits or 96 kHz is by shipping it digitally (e.g. via S/PDIF) to/from some other device.
It also has astonishingly poor input sensitivity. It’s about 5 times worse than a typical cheap sound card, and about 100 times worse than a decent 24-bit soundcard, as you can see from table 2.
The Extigy is no good for present purposes. I recommend you do not buy this product. Many other Creative Labs products have problems, too, so in fact I recommend that you never buy anything made by them.
This is a high-end system, with eight analog inputs, eight analog outputs, 96000 frames per second, and 24 bits of resolution. M-Audio was previously known as Midiman.
Each of the eight analog input and each of the eight analog outputs has a pushbutton that I call the “pro/con” switch. Professional studio equipment (pro) runs at lower impedances and lower signal levels than consumer-grade home audio equipment (con). That is, the pro setting (switch pushed in) means lower impedance and lower open-circuit voltage on output, and lower impedance and greater voltage-sensitivity on input. Whether you care about the lower impedance depends on the impedance of whatever the card is hooked to.
The card does not have an 8×8 or 10×10 mixer board. It is apparently 10×2. We bypass it, as discussed below.
The alsa driver always expects 10 channels of output: 8 analog plus 2 S/PDIF. If you are only interested in a subset thereof, you have to pad things so the buffer has 10 samples per frame anyway. Similarly, the alsa driver always produces 12 samples per frame on input: 8 analog plus 2 S/PDIF plus 2 from the mixer. For present purposes we use the 8 analog inputs and ignore the others, since they contain no additional randomness. Therefore you must pass the --channel-mask 255 option to turbid; otherwise the program will have less randomness than it thinks it has, by a factor of 8/12ths.
Each of the eight analog inputs is always routed directly to its own DAC, so the PCM input functionality is always unaffected by the sliders and switches on the mixer.
The routing can be set so that each of the eight analog outputs is fed directly from the PCM data. This is recommended. This makes the PCM output functionality independent of the sliders on the mixer.
Getting this to work requires the following tricks:
As usual, you will need the .ctl file (included in the turbid bundle) plus the settings in table 2.
The same jack doubles as a Line-In port and Mike-In port, depending on software settings. Unlike the typical Mike-In port as described in section 4.3, this Mike-In port is stereo and does not provide power to the microphone. This would be bad if you wanted to connect a microphone that needed power, but it’s ideal for our purposes. Basically it’s like an ordinary Line-In port, with higher sensitivity.
For reasons discussed in reference 8, the Johnson noise in any Ohmic resistor is nice white noise. Voltage samples are independent and identically distributed (IID), according to a Gaussian normal distribution with zero mean and variance given by
where k is Boltzmann’s constant, T is the temperature (300 K), B is the power-averaged bandwidth as defined in section 4.7, and the brackets ⟨⋯⟩ denote the ensemble average.
The principle of the bandwidth measurement is as follows: Equation 2 tells us the variance of the voltage right at the resistor. The quantity we actually measure has been amplified, according to some gain function G which depends on frequency. So a more complete description is
|4 k T R |G(f)|2 df (3)|
where the subscript o on σo indicates this is the quantity we observe, and fmax is some “large enough” frequency; the real, relevant bandwidth B is hidden in G, which goes to zero at large frequencies. Since G is presumably an even function of frequency, we can rewrite this as
|2 k T R |G(f)|2 df (4)|
and in a discrete (sampled) system this becomes
|2 k T R |G(k Δf)|2 Δf (5)|
where we identify the sampling frequency N = MΔf = 2 fmax, covering the whole range of positive and negative frequencies. We can write this in the suggestive form
|σo2 = 4 k T R G*2 B (6)|
where G*2 is some nominal mid-band power gain, if we identify
||G(k Δf)|2 Δf (7)|
and we call B the power-averaged bandwidth.
By definition the gain G is Vo / Vr, where Vr is the voltage right at the resistor, and Vo is what we observe.
This expression applies to any Vo/Vr ratio, whether Vr comes from thermal noise or from any other source.
We choose to inject a non-thermal probe signal Vr. It is constructed to be “white” – i.e. it has constant magnitude independent of frequency. That allows us to pull it outside the summation:
and by Parseval’s theorem we can rewrite that frequency-domain expression as a time-domain expression
It is easy to get a good lower bound on B. At compile time, we know the root-mean-square (RMS) magnitude of the internal representation of the probe signal; by construction it is -15dBFS. Then given K and R (and Zref) we know ⟨Vr2⟩ in the passband. At frequencies outside the passband this voltage will roll off a little, because of the anti-aliasing filter in the soundcard output stage. This will cause us to under-estimate B by a little, which is harmless. Finally we determine ⟨Vo2⟩ by summing the squares of the observed voltage samples and multiplying by the appropriate calibration factors (involving Q).
You might have thought based on the form of equation 3 that we would need to take a Fourier transform, but we don’t, because of Parseval’s theorem.
In the turbid software, whenever possible, voltages are measured in SI volts.
If that is not possible, e.g. when representing raw readings as they come from the hardware, before calibration, anything that is linear in voltage is measured in input buffer units such that 1.0 ibu is full scale i.e. the largest thing that can be represented.
Meanwhile, anything that is measured in dBx is measured relative to a reference level that is 15 dB below full scale. This means that a rail-to-rail square wave (such as might result from extreme clipping) peaks at 1.0 ibu, has an RMS of 1.0 ibu, and a power level of +15 dBx. Similarly a sine wave that peaks at exactly 1.0 ibu has an RMS of 0.707 ibu, and a power level of +12 dBx.
As always, a dB is a power measurement. This includes dBx. It does not depend directly on the peak voltage. As a corollary, the peak voltage of a zero-dBx sine wave √2 higher than the top of a zero-dBx square wave.
Suppose we have an output circuit with some voltage source and some Thévenin equivalent series resistance Z that we want to determine. We connect some external load resistance and measure the voltage. Then we connect some different load, and measure the voltage again. If one of the loads has infinite resistance, that gives us a direct measure of the open-circuit voltage.
On the ith measurement, the voltage is:
So if we plot the inverse voltage (1/Vi) as a function of the inverse resistance (1/Ri), we should get a straight line with slope Z/Voc and intercept 1/Voc.
The output port plus the QA box form a linear circuit with some known open-circuit voltage Vj and Thévenin equivalent series resistance Rj. The input port has some input impedance Z and some gain G, both of which we need to determine. We can observe the digitized input signal Xj.
So if we plot the observed inverse gain Vj/Xj as a function of the calibration network equivalent resistance Rj, we should get a straight line with slope 1/GZ and intercept 1/G. You can easily check this formula in the limiting cases Rj=0 and Rj→∞.
For some perspectives on Johnson noise and the Nyquist formula, including what happens when there is a frequency-dependent gain, see reference 26.
This has some interesting implications and ramifications for our randomness generator. There are a couple of regimes to consider:
In this regime, assuming the goal is to collect noise samples, you don’t want to add any additional resistance in parallel with what’s already there. That would just move the flat part of the curve to a lower voltage. (It would also push the corner frequency out to a higher frequency, but that doesn’t do any good if the digitizer doesn’t go that high.)
There are various ways of dealing with this.
In this regime it makes sense to add some resistance. This whitens the noise. It lowers the peak noise per unit bandwidth. However, remember that the area under the curve is independent of the resistance. So as long as the corner frequency is not large compared to what your digitizer can handle, you’re not losing anything by lowering the resistance.
If the added external resistance dominates the internal resistance, that provides a nice convenience: It means you know what the resistance value is. This simplifies the calibration.
The block size can plausibly be as small as the period, and as large as the buffer. On input, a small block size seems to have little or no effect on efficiency. In contrast, output block size seems to have a significant effect on efficiency. Larger blocks are more efficient. I have no clue how to explain the contrast.
Some ALSA timing is shown in figure 13. This is peculiar in a couple of ways. For one thing, the capture i/o buffer is a different size from the playback i/o buffer. Also, the first readi has been artificially delayed by 10 milliseconds relative to the first writei, just to clarify the relationship between the two streams.
Each rectangle represents an i/o call. The bottom of the rectangle is the number of frames (input or output) before the call, and the top is the number of frames (input or output) after the call. Similarly the left edge is the time at the start of the call, and the right edge is the time upon return from the call.
In figure 13 the command was turbid show timing comb 0 freq 1000 ochan 0. You can see that the playback process has a lot of work to do, so the corner of one red rectangle does not meet the corner of the next. In contrast, the capture process has very little work to do, so the rectangles very nearly meet corner-to-corner.
Now consider what happens when we use snd_pcm_link(...) to synchronize the two streams. At the time of the first write to the playback device, the playback stream starts running (obviously) ... and the capture stream also starts running (because it is linked). The artificial 10 ms delay is still there, but it affects only the left edge of the first rectangle, not the right edge.
All of Volume I is available online: