How can I quickly generate thousands of letters randomly, and strongly mitigate the risk of any compromise?

Question

I want to generate English letters in a truly random manner without resorting to hand-thrown dice, despite their advantages. Rolling dice would be too slow and tiring as I need four thousand letters.

Using commercially available TRNG software is unacceptable. Depending on a computer to generate the letters by itself, without my oversight is absolutely out of the question. But I still want to use a computer, albeit an air-gapped computer, because of increased speed and ease, that will carry out and/or record a process of random number generation using some sort of attached equipment (via USB) and/or sensor.

I feel confident about the air-gapped device I built. The real estate on that device is probably clean. For software, it's basic: TAILS. If either hardware or software are bad, this will not matter (or will it?) because I am going to control all parameters and watch the process of random number generation at work moment-by-moment. I do not want a process that merely spits out a complete file that I must trust. Not too slow, not too fast, just right. I want to supervise the process from start to finish.

What simple, cheap equipment and/or software can I and Joe Schmoe use, as outlined above, to generate high-quality random numbers in a way that is faster and easier than throwing dice while still strongly mitigating the risk of compromise, especially against a highly engaged, agile attacker who operates in both passive and active modes?

What process, mechanical or otherwise, can I use on an undorked computer that I control, employing such simple, cheap equipment, that will enable me to generate letters in a truly random manner--most importantly, that yields values which are cryptographically sound--for a proper one-time pad?

Answer 1

1. Flip a coin 256 times and write down the result as tthttttthhhtthhtttht….

2. Expand it by your favorite modern KDF—say, HKDF-SHA256 or SHAKE128, or SHA-256 followed by ChaCha—into 4000 characters.

   (Using a KDF or hashing first smooths out any slight nonuniformity of the coin tosses.)

3. You can verify that the computation was done correctly by redoing it on another computer, which is more than you can say for any particular piece of equipment you might otherwise use for the sampling.

You can substitute dice if you like: roll a die 50 times and write down the result as 52632113351226463416…. Either way the cost of breaking this system will be tremendously higher than any hare-brained scheme you cook up to sample all 4000 characters directly from physical observations.

Alternatively: Hire Raphael Weldon, who apparently takes longer to get bored than you or I do. But beware, because his dice are apparently slightly biased—as Karl Pearson invented the field of statistics to ascertain (paywall-free).

Answer 2

If you can generate random numbers, you can have a private conversation. --Whitfield Diffie

The idea is to use an air-gapped computer that cannot, will not, and never has, touched a network; it had to eliminate any metacontent possibly associated with key generation; it had to be low-cost; the hardware and software had to be common; bias had to be reduced or eliminated; it had to be very difficult and costly to subvert or perform an active attack against it--a primary objective, a starting point; and most importantly, it had to be very simple and faster than rolling dice.

The goal is to address the nagging problem of key generation for the one-time pad.

Create some six-sided dice with bar codes, numbered 1 to 6. Find a bar code scanner. Use OpenOffice Calc or a similar program with the function that you see in the picture above (or alter it as you see fit with whatever works). As you scan the dice, the document will populate Column A. Stop and populate Column B. The one-time pad values will pop up in Column C. With thirty or so dice, a shoe box with a cover, lots of shaking, and a hand-held bar-code scanner, you can generate pad material faster than rolling dice.

Answer 3

As a follow up to Paul Uszak's method of using a camera, I have analyzed that method for generating TRNG output, and if done correctly, it is sound, this works best with a DSLR that has a removable lens. A Sony A-6000 series camera is a good option.

There are essentially 2 sources for camera input, visible light and radiation that causes the sensor to think it is getting visible light. The easiest way to get radiation input is to take the lens off, put on the lens cap, and point the camera at a radiation source, preferably a beta source, such as uranium ore or an isotope disk. A pure alpha emitter will possibly be blocked or not generate a signal, and a gamma emitter might damage the sensor and will probably not be detected anyway.

If going for radiation, my suggestion would be Thallium-204, which is a beta emitter, combined with an alpha/beta emitter such as Uranium ore or metal. If nothing is detected with a long shutter speed, try taking off the lens cap.

Once you have adjusted the ISO/shutter/f-stop/focus settings to get a good particle activity pattern, start snapping pics. A 24 megapixel camera picking up 1% of the pixels with particle activity will get you at least 24KB worth of entropy after processing per image, which can be converted very safely into usable bits using Keccak as an entropy conditioner.

If you are using visible light with ISO noise as your source, I would go with a clear night sky with the focal point as close as possible to blur the stars out, this gives you photons at a pretty constant rate but sends them all over the sensor. Take each image with the lens pointing in a slightly different location. Use the smallest aperture/highest f-stop.

You can also use a radiation source for light, apply phosphorescent paint to the inside of cardboard box that will be sealed to block all light, and adjust the focus point manually on the paint. Then place the emitter in the box with the camera, and it will excite the paint so it can be detected by the camera. I think you may be able to mix Uranium Dioxide powder directly into glow paint, but high output beta emitters at a distance will give a more random pattern.

Entropy conditioning:

Conditioning is required to eliminate bias and convert the input, which may be extremely sporadic in terms of bit rate, into a usable random bit source.

My recommendation for converting the TRNG data source into usable bits would be a pair of Keccak instances both operating in an unbalanced duplex mode. If you have an image from a 24MP DSLR, capturing 6000x4000 pixel images, break that into 96 500x500 pixel sub-images if you are getting a full frame image of activity. Absorb 8 sub-images to set the initial state. For each additional 4 sub-images absorbed, squeeze 288-bits. You will get 6336 bits per image. Process 2 images in parallel using this method and XOR the outputs together, resulting in 6336 bits from 2 images. At 47 bits per 10 letters, you get 1348 letters per 2 images, so 6 images gets you the required 4000 letters.

Obviously, if the camera is lower resolution you will need more images. If you are not getting activity at the edges of the image, ignore all edge blocks and use only the inner 60, which gives you 3744 bits or 796 letters. You will need to do the math yourself based on the resolution of the camera, but 1000x1000 or 500x500 is a good sub-image size to use for this application, 500x500 makes it easier to omit the edge blocks without losing most of the image. Smaller blocks also mean more mixing of the image into the Keccak state.

Breaking the entropy conditioning down, output bits is 13.2% of the input, or a ratio of 7.57:1. This assumes a minimum entropy of 1 bit per 1000 pixels, which is extremely conservative, you will probably be getting at least 100. Since you can afford to be conservative with this method due to the low number of letters required, that is just fine. If you want a consistent bitrate into the Keccak instances for auditing and performance purposes, preprocess the sub-images with a 512-bit hash function first.

Answer 4

Upon careful reflection, I suggest the following three alternatives. They are in increasing order of effort.

1.

Get the 4000 bytes from a blocking implementation of \dev\random. That will generate information theoretic secure output within an hour of computer usage as the entropy will come from your mouse and key strokes. You won’t have to do anything other than use the machine. So you type:-

 dd if=/dev/random of=my_letters bs=1 count=4000 iflag=fullblock

and keep surfing/typing till it completes and the random characters appear in my_letters. This took 37 minutes on my machine. Inclusion of an entropy collector like HAVEGE will help greatly, but I don't entirely trust the entropy rate estimation for it.

Stuff about dd here. Caution: dd is short for 'disc destroyer'.

Note. In TAILS, dev/random = dev/urandom and therefore unsuitable for OTP generation.

2.

Take 63 photos a blank wall in a very dark room. This seems like a lot, but isn’t. It’s just 63 consecutive presses of the shutter. Say 5 minutes. Try to get the lighting so that the entire view finder is illuminated i.e all pixel values > 0. If you have ISO control, turn that up to the max. It's 99% pure entropy from the many types of noise within all CMOS camera sensors. The cheaper the camera, the better. You simply consider the JPEG encoding of the sensor's image as the post processing component of NIST's generic TRNG architecture, as:-

You then treat it as a bit fixing, block entropy source. There will be no semantic content within the image, so it's just the efforts of the JPEG algorithm to capture the noise. And that's essentially quantum noise, just like the best laboratory phase based TRNGs. Typically I would then measure it's entropy with a compression algorithm like cmix, but that'll take hours (so I haven't), and you only need 4000 bytes. You can be confident that the image contains >> 4000 bytes of entropy within any decent camera frame as there's nothing else. The piling up lemma will deal with that. You don't have to open the image raster, just use the raw .jpg.

And then use your favourite programming language to do $ \operatorname{SHA-512}(jpg_i) $ in a loop of 63 file hashes and concatenations. Or do cat jpg_i | sha512sum >> my_letters 63 times which is not as monotonous as it sounds with automatic consecutive image numbering and command recall.

This online TRNG uses this technique.

3.

Acquire a Zener diode (now £11! due to global semiconductor shortage) , some batteries and a hammer. Don’t laugh – it works perfectly. Build something like:-

and plug it into an Arduino’s analogue to digital converter. There will be lots of quantum Avalanche noise created (>1Vpp). The Arduino then just forwards the raw samples to a PC for you to follow the hash based extraction procedure described above. This time you’ll have to use cmix (or equivalent) to measure the entropy rate to ensure that you’re hashing more than 1024 bits of entropy. That's to be in lock-step with NIST’s definition of ‘full’ entropy. I use a safety factor of 3, so hash 3072 bits each time. A little C programming will be required, but Arduino’s are used in schools.

cmix details here, and it's greedy for RAM.

I recommend option 1 for zero effort, but option 3 for maximum fun. And option 3 is not limited to 4000 characters of course.