Vault12
Published in

Vault12

How to get true randomness from your Apple device with particle physics and thermal entropy

Source Code
True Entropy App

A Noisy Phone

Amplified difference between 2 blank iPhone pictures taken with lens closed

The Raw Data

  • Start the iPhone in video recording mode.
  • Copy all RGB pixels of each video frame.
  • Subtract from each pixel in a given frame a pixel in the same position on the next frame.
First few difference frames
  • It takes the camera a few frames to focus on the scenery. While the camera is focusing, the difference between each frame is big, as evidenced by large values in the mean, deviation and pixel min-max range.
  • Once the camera is focused, the mean rapidly converges to almost zero. This will be a useful attribute for us to detect if the camera field of view has changed — we can reject all difference frames where the mean is larger than a small value like 0.1.
  • In a focused, stable view the min/max range becomes much smaller, just ± 20 pixels on average, and very rarely reaching ± 40 pixel intensity. That is exactly the behavior of the relatively small thermal noise present in every pixel of a camera image for which we are looking.

Zero Sequences

Expected zero sequences in 518kb sample
  • When generating entropy with the lens uncovered, avoid too bright conditions that eliminate sensor sensitivity.
  • The improbably long sequence of zeroes is a telltale sign of such oversaturated spots in the difference frame. Before we generate entropy, we will scan for such improbably long sequences and eliminate them from the sample data because they contain no real thermal noise.

Dealing With Correlations

High correlation areas
  • Break local group by accessing the pixels in different order. For example, we can take all red pixels in their natural order, going from 1st pixel to the last pixel in the frame. We will take green pixels in the reverse order, going from last to 1st. For blue pixels, we can use orthogonal order that replaces rows with columns in the frame (instead of 0,1,2,3 ordering will be 0,10,20,…1,11,21…). This way correlated pixels in the clumps we have seen above will never be used together.
  • Instead of using frames one after another, we can use frames that are more distant from each other in time. For example, at 30 frames per second, we can buffer 15 frames, and then extract entropy by using frame 1 and 16, 2 and 17, etc. That means we will be mixing in frames that are half a second apart — which should be enough for timing correlations to dissipate away.
  • We will mix in red, green and blue channels in parallel from different frames, since there will be less correlation between pixels of different colors in different frames. For example the “red” pixel 10 on frame 1 is less correlated with the “blue” pixel 321 on frame 15, while it might be strongly correlated with the “blue” pixel 9, 10 and 11 in the same frame 1.

From Normal to Uniform

Von Neumann extractor

  • If you have a pair of 0,0 or 1,1 just toss them away: they do not produce anything.
  • If you have 1,0 or 0,1 pair, use the final bit as your result and it will have a uniform random distribution: the probabilities of these two pairs are exactly the same!
  • If you have a 1,0 or 0,1 pair, use final bit as your result (classic Von Neumann).
  • If you have a 1,1 or 0,0 pair, convert it into 1 or 0 and add it to a temporary buffer.
  • After you are done processing the initial data, run the Von Neumann extractor again on the buffer you collected.

Quick Test: Chi-Squared

  • Formulate a theory about whatever you want to test and then calculate what you expect to observe if your idea is correct.
  • Observe real-world events and record the observed values.
  • The chi-squared statistic is calculated by summing together across all events the following: (ObservedValue - ExpectedValue)²/ExpectedValue
  • Use a lookup table or chi-squared calculator to answer the key question: what is the probability that the observed events are the result of your theory?
for i in {1..10}; do dd if=/dev/urandom bs=1k count=1k &> /dev/null | ent -t | cut -d, -f4; done194.700684 308.307617 260.475586 236.611328 316.724609 306.418945 262.301270 240.013184 205.627930 257.049805

All Together At Once

  • Take two video frames as big arrays of RGB values.
  • Subtract one frame from another, that leaves us with samples of raw thermal noise values.
  • Calculate the mean of a noise frame. If it is outside of ±0.1 range, we assume the camera has moved between frames, and reject this noise frame.
  • Delete improbably long sequences of zeroes produced by oversaturated areas. For our 1920x1080=2Mb samples and a natural zero probability of 8.69%, any sequence longer than 7 zeros will be removed from the raw data.
  • Quantize raw values from ±40 range into 1,2 or 3 bits: raw_value % 2^bits.
  • Group quantized values into batches sampled from different R,G,B channels, at big pixel distances from each other and in different frames to minimize the impact of space and time correlations in that batch.
  • Process a batch of 6–8 values with the Von Neumann algorithm to generate a few uniform bits of output.
  • Collect the uniform bits into a new entropy block.
  • Check the new block with a chi-square test. Reject blocks that score too high and therefore are too improbable to come from a uniform entropy source.

Generating Entropy

High tech entropy generation with a pencil

Sending Entropy

  • To work with a Zax relay you need to install the Glow client library: npm i -g theglow.
  • Pick a secret key for your target device or server. This can be any random 32 bytes generated anyway you like. For example, generate a key file cat /dev/urandom | head -c 32 | base64 > station_key.txt on a secure machine and use that file on a single target server. You can also use TrueEntropy’s “AirDrop” mode to generate the initial key entropy directly.
  • Init a station with that key: cat station_key.txt | glow key --set. Or you can use glow key --generate to avoid creating an extra file. That command will also print out the resulting public key.
  • Copy your device public key (PK): glow key --public
  • Paste that public key in the Recipient slot of the TrueEntropy app and specify a relay URL.
  • Copy the Device Key from the TrueEntropy app.
  • Download the encrypted blocks uploaded by the TrueEntropy app, for example to download 5 blocks at once: glow download https://zax-test.vault12.com [Device/Sender Public Key] -n 5 We used our test relay in this example[6], for any production use you should deploy your own relays from source. For direct entropy use, you can pipe it into any destination: glow download https://zax-test.vault12.com [Device/Sender Key] --silent --stdout | ent

The Real Test: SP800–90B

python iid_main.py ~/entropy-3b1.bin 8 -v
reading 2097152 bytes of data
Read in file /home/fallout/entropy-3b1.bin, 2097152 bytes long.
Dataset: 2097152 8-bit symbols, 256 symbols in alphabet.
Output symbol values: min = 0, max = 255
Calculating statistics on original sequence
Calculating statistics on permuted sequences
permutation tests: 99.99 percent complete
statistic C[i][0] C[i][1]
----
excursion 3845 0
numDirectionalRuns 8304 3
lenDirectionalRuns 82 854
numIncreasesDecreases 5930 10
numRunsMedian 8144 2
lenRunsMedian 2288 1720
avgCollision 9654 0
maxCollision 433 204
periodicity(1) 1455 29
periodicity(2) 28 1
periodicity(8) 2996 32
periodicity(16) 8229 35
periodicity(32) 41 3
covariance(1) 229 0
covariance(2) 799 0
covariance(8) 421 0
covariance(16) 7136 0
covariance(32) 3487 0
compression 7488 6
(* denotes failed test)
** Passed IID permutation tests
Chi square independence
score = 65162.2, degrees of freedom = 65535, cut-off = 66659.4
** Passed chi-square independence test
Chi square goodness-of-fit
score = 2285.22, degrees of freedom = 2295 cut-off = 2510.06
** Passed chi-square goodness-of-fit test
** Passed chi square tests
LRS test
W: 5, Pr(E>=1): 0.864829
** Passed LRS test
IID = True
min-entropy = 7.92358
$ python iid_main.py ~/entropy-direct.bin 8 -v
reading 1999996 bytes of data
Read in file /home/fallout/entropy-direct.bin, 1999996 bytes long.
Dataset: 1999996 8-bit symbols, 256 symbols > in alphabet.
Output symbol values: min = 0, max = 255
Calculating statistics on original sequence
Calculating statistics on permuted sequences
permutation tests: 99.99 percent complete
statistic C[i][0] C[i][1]
----
excursion 7875 0
numDirectionalRuns* 10000 0
lenDirectionalRuns 6435 3562
numIncreasesDecreases 394 4
numRunsMedian* 10000 0
lenRunsMedian 40 48
avgCollision* 10000 0
maxCollision 5222 1236
periodicity(1)* 0 0
periodicity(2) 46 2
periodicity(8) 1955 39
periodicity(16) 512 15
periodicity(32) 7632 39
covariance(1)* 0 0
covariance(2) 141 0
covariance(8) 6251 0
covariance(16) 5847 0
covariance(32) 5980 0
compression 7540 3
(* denotes failed test)
** Failed IID permutation tests
IID = False
python iid_main.py ~/entropy-3b2.bin 8 -v
reading 2097152 bytes of data
Read in file /home/fallout/entropy-3b2.bin, 2097152 bytes long.
Dataset: 2097152 8-bit symbols, 256 symbols in alphabet.
Output symbol values: min = 0, max = 255
Calculating statistics on original sequence
Calculating statistics on permuted sequences
permutation tests: 99.99 percent complete
statistic C[i][0] C[i][1]
----
excursion 5990 0
numDirectionalRuns 6878 8
lenDirectionalRuns 939 5563
numIncreasesDecreases 1204 13
numRunsMedian 220 1
lenRunsMedian 1198 966
avgCollision 8953 0
maxCollision 6838 1137
periodicity(1) 909 16
periodicity(2) 3748 45
periodicity(8) 8752 22
periodicity(16) 9318 16
periodicity(32) 8374 20
covariance(1) 3183 0
covariance(2) 4537 0
covariance(8) 3617 0
covariance(16) 2460 0
covariance(32) 316 0
compression 1473 6
(* denotes failed test)
** Passed IID permutation tests
Chi square independence
score = 65285.8, degrees of freedom = 65535, cut-off = 66659.4
** Passed chi-square independence test
Chi square goodness-of-fit
score = 2269.05, degrees of freedom = 2295 cut-off = 2510.06
** Passed chi-square goodness-of-fit test
** Passed chi square tests
LRS test
W: 4, Pr(E>=1): 1.000000
** Passed LRS test
IID = True
min-entropy = 7.90724

Future Improvements

  • We are taking the camera as a given constant, yet it is quite configurable and an extremely powerful device! What camera settings can be adjusted and automated to maximum noise variance in all conditions? The app will then be less sensitive to selecting a proper view and can just adjust itself to generate perfect entropy in any conditions.
  • We used the Von Neumann extractor since it was the simplest to implement and it offered a perfect educational canvas to demonstrate how each bit sequence is converted from biased raw source to uniform. However, cutting-edge extractors in the industry leverage “sum-product theorem” (sources are mixed up as X*Y+Z over specific field) and might be much more powerful given the number of noise pixel values we are getting from each frame.
  • Want to relax IID assumptions and avoid careful setup of a non-correlated quantizer? Easy — use any good universal hash function. The only new requirement is that the universal hash will require a one-time seed. We can make an easy assumption that the iPhone local state of /dev/urandom is totally independent from thermal noise camera is seeing, and simply pick that seed from everybody's favorite CSPRNG.
  • We are not actually extracting the maximum amount of entropy. Newer iOS devices support HD resolution of 3840x2160 per frame. The higher the resolution, the more variance of each pixel noise the camera will detect, and we can even start extracting 4-bit datapoints in the same “perfect” conditions. The downside is that now the device has to process 8Mb of data before the the first bit of entropy is generated, and it slows down initial output and requires a huge memory footprint. We left the default at 2Mb per frame for better responsiveness, but you are welcome to change that if you are looking for maximum entropy throughput[8].
  • Not surprisingly, most of the cycles in our app are spent on running the extractor logic on the iOS device CPU — that is by far the main performance bottleneck in the app right now. Calculating the frame difference noise takes only 0.1 seconds on the iPhone7 over a 2Mb frame, while running the extractor over the same frame takes up to 5–7 seconds. To maximize the bandwidth of thermal entropy, one solution would be only capture raw noise values from the iPhone and run the extractor on the target machine. Such a setup would allow us to generate entropy at a theoretical maximum speed for camera resolution in the tens of megabytes per second.
  • The chi-square test is the simplest and quickest realtime tests we can run as entropy blocks are generated. The SP800–90B we used for static testing has a massive array of entropy assessment and health algorithms. Adding a few realtime health checks, the SP800–90B suite can provide additional safeguards when used in production.

One More Thing

References

--

--

Protecting the future of money

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store