Random number generator issue

Question

I wrote a litte random generator using a geiger tube. I use a 16bit timer that overflows every ~1ms; when i get a reading form the geiger (~36count/minute), i save the current timer value as "random number".

But if run the test ent i get a completly different result for the chi-squared-test, in binary mode is fine, but in byte mode it fails miserably.

This is just a side project only for a little presentation, but i would like to have an idea to understand what is wrong.

binary mode

ent lestobaremetal.txt -b
Entropy = 0.999990 bits per bit.

Optimum compression would reduce the size of this 654560 bit file by 0 percent.

Chi square distribution for 654560 samples is 9.08, and randomly would exceed this value 0.26 percent of the times.

Arithmetic mean value of data bits is 0.5019 (0.5 = random).
Monte Carlo value for Pi is 3.123203285 (error 0.59 percent).
Serial correlation coefficient is -0.001670 (totally uncorrelated = 0.0).

byte mode

ent lestobaremetal.txt   
Entropy = 7.986452 bits per byte.

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

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

Arithmetic mean value of data bytes is 128.1813 (127.5 = random).
Monte Carlo value for Pi is 3.123203285 (error 0.59 percent).
Serial correlation coefficient is -0.001851 (totally uncorrelated = 0.0).

UPDATE:

The random stream is generated in this way: the pulse from the GM tube is stretched by a 555 astable timer to 5mS duration. The stretched pulse is fed into the INT0 pin on an atmega328. When the external interrupt is generated, the current TCNT1 16-bit counter value is taken and sent over uart to the pc. The timer is run with prescaler 1 at 16MHz, for an overflow every ~4ms

Here you can find the binary file with the data collected in a couple of days: lestobaremetal.txt
More about the proect:
Source code
Hardware schematics and layout

Answer 1

Both ent tests distinguish the files from random data with high confidence (99.84% for the bit test, >99.99% for the byte test). That follows from the "randomly would exceed this value.." reports.

It would only be an issue in actual use if the random data was directly used. Which would be bad practice in cryptography, where the rule is that the output of an unconditioned TRNG is, under operating conditions, fed exclusively to

• a monitoring scheme which ensures that the unconditioned TRNG outputs some entropy;
• and a PRNG processing the output of the unconditioned TRNG.

Note: if the PRNG is not cryptographically secure (which is often the case for hardware ones), its output is further processed with a CSPRNG.

With this structure the monitoring scheme's purpose should not be to try to determine that/if the TRNG is near-perfect. It should be to rule out that the TRNG is badly broken (like, insure that the entropy rate if at least 0.5).

The ent test is ill-suited to the purpose: it is not operating in real time, is not designed to ignore minor defects, and most importantly it fails to detect some huge, not-unlikely defects: if there was a triple-trigger for every Geiger event, making three identical or incremental values recorded for each Geiger event, that would not be detected by ent (except for very small input), when that's a disaster.

---

Still, from an engineering perspective, it is interesting to understand what makes the ent tests fail. Some ideas (before the question was updated with raw data and code):

• The Geiger event determines when a free-running 16-bit timer clocked at about $2^{16}/10^{-3}$Hz (about 70 MHz) is sampled. It could be that there is some analog feedback from the counter, or from something derived from the same clock as the counter, to the sampling logic. For example, if when the Geiger event occurs near the active edge of the clock, the current state of the low-order bit of the counter influences (by e.g. capacitive coupling) the decision of the gate that determines if the event is going to be registered as having happened before or after the edge, then that low-order bit is going to be biased. It may be that ent's byte test will detect this bias more accurately than it's bit test (because the biased bit is always at the same position in a byte).
• If the sampling is in software (e.g. an interrupt triggered by the Geiger event reads the 16-bit timer), then the latency in the processing of that interrupt can play a role. For example, if the 16-bit timer generates an interrupt of identical priority when it overflows, that makes it impossible that some 16-bit values (those right after the overflow) get sampled, creating a bias. I believe ent's byte test would detect that kind of issue more selectively than it's bit test.

---

Summary (before the question was updated with raw data and code):

• The ent tests failed, and that's likely related to some minor imperfection. We can only make guesses at which.
• It is no indication that this unconditioned TRNG is unsuitable to seed a (CS)PRNG, which is the Right Thing to do with an unconditioned TRNG.
• The enttest is not adequate for an unconditioned TRNG source; not even in an exploratory phase, much less for the continuous surveillance of the unconditioned TRNG, as necessary in serious cryptographic uses.

---

Update: Mystery solved!

Summary frequency analysis of the raw data demonstrates beyond doubt that byte values 0x11 and 0x13 have been filtered out. That's what allows ent to raise alert. Certainly, XON/XOFF software flow control strikes again!

0x00 281  0x01 300  0x02 343  0x03 313  0x04 322  0x05 321  0x06 295  0x07 342  0x08 317  0x09 319  0x0A 337  0x0B 320  0x0C 328  0x0D 308  0x0E 324  0x0F 344
0x10 316  0x11   0  0x12 320  0x13   0  0x14 314  0x15 376  0x16 336  0x17 325  0x18 295  0x19 342  0x1A 325  0x1B 338  0x1C 326  0x1D 293  0x1E 324  0x1F 296
0x20 328  0x21 300  0x22 322  0x23 313  0x24 340  0x25 334  0x26 342  0x27 315  0x28 336  0x29 295  0x2A 313  0x2B 305  0x2C 322  0x2D 341  0x2E 303  0x2F 331
0x30 308  0x31 339  0x32 371  0x33 325  0x34 323  0x35 319  0x36 324  0x37 309  0x38 337  0x39 296  0x3A 323  0x3B 338  0x3C 335  0x3D 302  0x3E 335  0x3F 348
0x40 331  0x41 318  0x42 334  0x43 285  0x44 323  0x45 348  0x46 323  0x47 333  0x48 325  0x49 370  0x4A 345  0x4B 318  0x4C 338  0x4D 302  0x4E 330  0x4F 326
0x50 332  0x51 308  0x52 307  0x53 362  0x54 300  0x55 292  0x56 335  0x57 333  0x58 352  0x59 355  0x5A 317  0x5B 326  0x5C 329  0x5D 334  0x5E 316  0x5F 331
0x60 318  0x61 324  0x62 293  0x63 318  0x64 302  0x65 324  0x66 317  0x67 313  0x68 297  0x69 310  0x6A 330  0x6B 334  0x6C 300  0x6D 340  0x6E 310  0x6F 317
0x70 324  0x71 335  0x72 309  0x73 335  0x74 333  0x75 336  0x76 314  0x77 313  0x78 354  0x79 333  0x7A 294  0x7B 333  0x7C 324  0x7D 340  0x7E 343  0x7F 336
0x80 309  0x81 294  0x82 352  0x83 324  0x84 306  0x85 295  0x86 314  0x87 342  0x88 324  0x89 311  0x8A 331  0x8B 292  0x8C 305  0x8D 318  0x8E 324  0x8F 321
0x90 307  0x91 325  0x92 335  0x93 329  0x94 324  0x95 335  0x96 318  0x97 336  0x98 335  0x99 302  0x9A 310  0x9B 342  0x9C 315  0x9D 326  0x9E 290  0x9F 323
0xA0 308  0xA1 319  0xA2 347  0xA3 323  0xA4 305  0xA5 312  0xA6 336  0xA7 293  0xA8 323  0xA9 310  0xAA 352  0xAB 323  0xAC 305  0xAD 312  0xAE 340  0xAF 306
0xB0 305  0xB1 311  0xB2 334  0xB3 333  0xB4 303  0xB5 324  0xB6 343  0xB7 308  0xB8 305  0xB9 309  0xBA 331  0xBB 322  0xBC 332  0xBD 329  0xBE 311  0xBF 327
0xC0 350  0xC1 349  0xC2 352  0xC3 313  0xC4 319  0xC5 350  0xC6 282  0xC7 316  0xC8 305  0xC9 348  0xCA 316  0xCB 325  0xCC 335  0xCD 337  0xCE 295  0xCF 309
0xD0 305  0xD1 344  0xD2 325  0xD3 311  0xD4 296  0xD5 301  0xD6 349  0xD7 285  0xD8 328  0xD9 308  0xDA 323  0xDB 338  0xDC 276  0xDD 299  0xDE 323  0xDF 314
0xE0 286  0xE1 360  0xE2 315  0xE3 308  0xE4 329  0xE5 321  0xE6 302  0xE7 315  0xE8 346  0xE9 326  0xEA 315  0xEB 352  0xEC 346  0xED 319  0xEE 333  0xEF 289
0xF0 320  0xF1 309  0xF2 317  0xF3 325  0xF4 312  0xF5 366  0xF6 331  0xF7 316  0xF8 283  0xF9 344  0xFA 336  0xFB 302  0xFC 331  0xFD 310  0xFE 347  0xFF 335

---

Note 1: As a minor aside, the 16-bit counter is sampled by software in an interrupt, rather than in hardware by an input capture mechanism. It follows that any variation in interrupt latency influences what's sampled. In many CPUs, interrupt latency varies slightly according to foreground activity (like, a multi-cycle instruction or access to a peripheral requiring wait states increases latency). The ATMega328P has instructions lasting 1 to 4 cycles, thus this could have some minor influence, especially on the low-order bits. While I have seen the uncertainty in sampling by interrupt about halved by putting a CPU in wait/sleep mode rather than in a loop with a 2-cyles branch, that's a non-scalable kludge, and using the ATMega328P's Input Capture Unit would be best (depending on what pin the signal to sample is connected, that could be software-only change).

Note 2: putting a radioactive source nearby will have several effects:

• The entropy rate (in bit/s) will increase.
• The samples will get closer, and that will increase a currently minor issue: by design, the difference between a 16-bit sample and the next (modulo 65536) is biased.
• Odds of upset in the nearby logic/CPU will increase, which could have dramatic negative side effects.

Note 3: Proper monitoring of the unconditioned source is best done with knowledge of which is high and low byte of 16-bit samples. This currently is possible only by timing considerations (especially with the disappearing bytes). We can solve that and make the output plain ASCII by sending a 16-bit sample as 4 characters, the first in PQRSTUVWHIJKLMNO and the others in pqrstuvwhijklmno, with the low-order 4 bits of each character equal to 4 bits of the 16-bit sample (I suggest, in big-endian order, which is the most common in crypto).

Note 4: In some cryptographic contexts, adding a proper CSPRNG somewhere will be essential. If this unconditionned generator was used as /dev/random directly, it would be easy to distinguish the output from good randomness, at least if it can be timed when the output becomes available! Proper monitoring is important too, and essential if an adversary can approach the device (sabotage is a thing; and forcing Geiger events to occur is not rocket science).

Answer 2

We can't tell how you get from a binary 16 bit timer to a file full of bits. Have you simply stored the timer values? I'm assuming that the file type is wrong though, in that the files are actually binary. Otherwise you'd seriously fail the compression tests. You've labelled them .txt.

The gently failing chi values just mean that the data files are not very random. Without knowing how you processed the entropy, it's hard to tell exactly what the problem is. The compression tests are extremely basic, just using the old Shannon log(p) entropy formula. That doesn't work for true entropy estimation as the data is very rarely IID (identically and independently distributed). It's usually highly correlated. John Walker (the ent author) says this indirectly in his bug report:-

BUGS: Note that the “optimal compression” shown for the file is computed from the byte- or bit-stream entropy and thus reflects compressibility based on a reading frame of the chosen width (8-bit bytes or individual bits if the -b option is specified). Algorithms which use a larger reading frame, such as the Lempel-Ziv [Lempel & Ziv] algorithm, may achieve greater compression if the file contains repeated sequences of multiple bytes.

At 36 clicks/min, I would not expect too much correlation. The only semi-reliable entropy measurement technique for a TRNG's raw output is a compression test using something more powerful like PAQ8 derivatives (eg. fp8.exe). There are more exotic measures in NIST Special Publication 800-90B (Section 6) but they're highly mathematical and you'll have to write and test code. And how would you test it - against what?

Of course this could just be a consequence of the randomness of entropy. It's pesky that way. You really need to repeat this several times and see if the chi scores appear uniformly spaced across 0-100%. It's common to run the p scores through a Kolmogorov–Smirnov test to check that the ps are uniformly distributed. But even the KS tests can be off. That's just the nature of the beast.

You also get dead time on a Geiger tube, so rapidly occurring events can be missed. This undermines the output distribution and reduces the entropy measure. And radioactive decay events are a Poisson distribution, so can occur close together, confounding the tube. Don't forget that you're trying to measure to a 15ns resolution that I don't think a household Geiger tube can do. That's why no one uses radioactive decay in a TRNG commercially (HotBits is not commercial).

Supplemental:

You can't simply store the ISR readings and hope to get IID (independently and identically distributed) numbers. Not at all. The confusion probably stems from common parlance in saying that radio active decay is random. It is random, in the sense of entropy. It is not IID in the sense of a pseudo random number generator. This is why chi fails. All subsequent tests will also fail spectacularly such as Diehard.

If you're so minded, there's User’s Guide to Running the Draft NIST
SP 800-90B Entropy Estimation Suite. I have no experience of that. I just compress the data with paq8px and divide by 2 to get an entropy value. You seem to have almost totally in-compressible data in the sample file (compressed only by 0.03%), so entropy = 1 byte/byte (100%) as you thought. I'm bigly surprised and would not have thought that possible without initial processing. But I would now say that it's only 0.5 bytes /byte as a security precaution and to guard against improvements in compression algorithms.

You then have to somehow convert the raw data into uniform random numbers. It's common to hash the raw data or use a matrix multiplier (essentially the same thing). You can use any sort of hash, CRC, Pearson or SHAx. Look up randomness extraction. SHAx might not fit into your particular AVR, I don't know. I use Pearson hashes because I like them.

Ideally, you could do SHA1(80 bytes of raw data) to get 20 perfectly random bytes out. That should pass all tests. You should be able to simulate this with your data file on a PC.