1
$\begingroup$

Bob wants to generate four thousand English letters for a proper one-time pad without resorting to hand-thrown dice, despite the advantages. Rolling dice would be too slow and tiresome.

Bob does not trust commercially available TRNG software, and he wants to oversee the process. Nevertheless, he still wants to use a computer for increased speed and ease, carrying out and recording random number generation using some attached equipment (via USB) and a sensor.

The software on this air-gapped computer will be TAILS. Suppose either the hardware or the software is compromised. If so, this will not matter (or can it?) thinks Bob, because he will control the parameters and watch the random number generation process moment-by-moment from start to finish and then analyze the results. He does not want a process that merely spits out a complete file that he is supposed to trust.

The speed of key generation should be: not too slow, not too fast, just right for visual inspection.

What simple, cheap equipment and software can Bob use, as outlined above, on a non-dorked computer to generate high-quality random numbers in a way that is faster and easier than throwing dice? The adversary, operating passively and actively, is highly engaged, wonderfully resourced, and agile.

$\endgroup$
8
  • 1
    $\begingroup$ A good starting point for generating your own (truly) random numbers: HRNG. Many computer already have such a device built in. $\endgroup$ Sep 27 '19 at 8:30
  • 1
    $\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
  • 1
    $\begingroup$ @PaulUszak I finally understand. TAILS does not have blocking. By the way, I really appreciate you looking into this. This is one of the core problems with OTP, as you well know, and I want to solve it. $\endgroup$
    – Patriot
    Sep 27 '19 at 11:41
2
$\begingroup$

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.

enter image description here

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

enter image description here

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.

$\endgroup$
2
  • 1
    $\begingroup$ Hope you don't mind :-). Check Proton. $\endgroup$
    – Paul Uszak
    Jul 21 at 18:57
  • 1
    $\begingroup$ Have you seen the Dice-O-Matic? Never mind the hardware; it's ludicrously brilliant/silly. But the dice are read by .Net optical recognition. OpenCV is available for free and it's world class. $\endgroup$
    – Paul Uszak
    Jul 31 at 14:28
1
$\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).

$\endgroup$
7
  • 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$ 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$ Sep 27 '19 at 23:26
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.

$\endgroup$
2
  • $\begingroup$ "There are essentially 2 sources for camera input, visible light and radiation that causes the sensor to think it is getting visible light. " Actually no. The sensor will generate noise in complete darkness. Try it with your iPhone. The noise(entropy) arises from myriad sources such as reset noise, quantisation error , $\frac{1}{f}$ noise but mainly Johnson–Nyquist thermal noise. The hotter the better! $\endgroup$
    – Paul Uszak
    Jul 21 at 18:51
  • $\begingroup$ If you want to see this concept in reality, see the Phononic Instrument. Don't be dissuaded by the size; that's just silly Steampunk stuff. The major issue is the light level inside the integrating sphere. Networked webcams will not send an image below a certain threshold. You just get black. Hence the Null Gamma Device. $\endgroup$
    – Paul Uszak
    Jul 31 at 14:36
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 (now £11! due to global semiconductor shortage) , 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.

$\endgroup$
18
  • 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$ 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$ 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$ 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$ Oct 1 '19 at 13:09

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.