1
$\begingroup$

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?

|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ A good starting point for generating your own (truly) random numbers: HRNG. Many computer already have such a device built in. $\endgroup$ – AleksanderRas Sep 27 '19 at 8:30
  • $\begingroup$ @AleksanderRas Excellent. This use case distrusts all in-built devices to generate the values, but that is still some good info. $\endgroup$ – Patriot Sep 27 '19 at 8:35
  • 1
    $\begingroup$ Small pair of related questions then that depends on your mindset. Does TAILS have a blocking /dev/random, and if so would you trust it? I think I would, and you know me. $\endgroup$ – Paul Uszak Sep 27 '19 at 10:34
  • $\begingroup$ @PaulUszak Interestingly, TAILS also uses rngd as an auxiliary source of entropy. $\endgroup$ – Patriot Sep 27 '19 at 11:16
  • $\begingroup$ That's not really what I meant. You don't need HAVEGE. You just need to discover whether it's \dev\random is of the blocking variety. Is it? $\endgroup$ – Paul Uszak Sep 27 '19 at 11:33
0
$\begingroup$

  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).

|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ This doesn't answer the question at all. Patriot is looking for true random number generation, and this isn't it. You're not realising that a proper one time pad cannot be made algorithmically with a pseudo random number generator. The key has to be as long as the message, or 4000 characters. $\endgroup$ – Paul Uszak Sep 27 '19 at 21:18
  • 1
    $\begingroup$ I quote: ‘most importantly, that yields values which are cryptographically sound’ (emphasis original). If you're not interested in cryptography, I submit that this is not the site for you. $\endgroup$ – Squeamish Ossifrage Sep 27 '19 at 21:20
  • 1
    $\begingroup$ I quote: "...in a way that is faster and easier than throwing dice." It looks as if I'm needed here as there are still huge misconceptions of how to make one time pads. And their role in theoretical information security. Plus, your quote doesn't mean what you think it means... $\endgroup$ – Paul Uszak Sep 27 '19 at 21:44
  • $\begingroup$ Squeamish, this answer can do without the comparison by who is bored more easily; personally I don't think that entire section doesn't bring anything to the table. $\endgroup$ – Maarten Bodewes♦ Sep 27 '19 at 22:31
  • 3
    $\begingroup$ @MaartenBodewes The bias of dice is also relevant because part of my point is that it's much harder to get something indistinguishable from uniform random by observing physical processes like die rolls than by using cryptography. $\endgroup$ – Squeamish Ossifrage Sep 27 '19 at 23:26
1
$\begingroup$

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:-

generic

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 (<£3) , some batteries and a hammer. Don’t laugh – it works perfectly. Build something like:-

breadboard

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.

|improve this answer|||||
$\endgroup$
  • 2
    $\begingroup$ What's your model for the distribution of digital camera readouts in a dark room which justifies your claim about its entropy? $\endgroup$ – Squeamish Ossifrage Sep 27 '19 at 20:51
  • 2
    $\begingroup$ Using demosaiced JPEG or PNG output can't be ideal because the sensor's color filter array means that for each RGB pixel actually only one color was measured at that location. And how do you account for information loss from JPEG compression, or more alarmingly, the camera's noise reduction algorithm? If were going to do this at all you'd simplify it quite a bit by using RAW files instead, but even then I understand some cameras apply a bit of noise reduction to those. $\endgroup$ – Luis Casillas Sep 27 '19 at 22:18
  • 2
    $\begingroup$ In 1. you also expand the entropy, so this is not true random and in 2. you somehow seem to expect that a blocking /dev/random gives you the raw entropy, which it usually does not. Note that I had a few cheap cameras just give black output, so hardware breakdown could be a real issue with your entropy gathering device. $\endgroup$ – Maarten Bodewes♦ Sep 27 '19 at 22:44
  • 2
    $\begingroup$ $\operatorname{SHA512}(m \mathbin\| \cdot)$ compresses a long message $m$ into a 512-bit intermediate state before combining it with the rest. There are only $2^{512}$ possible intermediate states, so the number of distinct values of the output of this SHA512-CTR construction is $2^{512}$ and the entropy is at most 512 bits. (Which is not a security problem—SHA512-CTR (on prefix-free inputs, anyway) makes a perfectly good stream cipher!—but it may not sit well with your dogmatic adherence to ‘entropy’. And technically SHAKE128 can produce more distinct outputs, hence ‘higher entropy’.) $\endgroup$ – Squeamish Ossifrage Sep 28 '19 at 0:51
  • 1
    $\begingroup$ Re your new (1), if you don't like how NIST tools ‘estimate entropy’, I have very bad news for you about how /dev/random ‘estimates entropy’. $\endgroup$ – Squeamish Ossifrage Oct 1 '19 at 13:09
1
$\begingroup$

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.

|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.