Published in

Vault12

# 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.
• 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

• 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

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

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

# 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 -vreading 2097152 bytes of dataRead 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 = 255Calculating statistics on original sequenceCalculating statistics on permuted sequencespermutation tests:      99.99 percent completestatistic  C[i][0]  C[i][1]----excursion     3845        0numDirectionalRuns     8304        3lenDirectionalRuns       82      854numIncreasesDecreases     5930       10numRunsMedian     8144        2lenRunsMedian     2288     1720avgCollision     9654        0maxCollision      433      204periodicity(1)     1455       29periodicity(2)       28        1periodicity(8)     2996       32periodicity(16)     8229       35periodicity(32)       41        3covariance(1)      229        0covariance(2)      799        0covariance(8)      421        0covariance(16)     7136        0covariance(32)     3487        0compression     7488        6(* denotes failed test)** Passed IID permutation testsChi square independencescore = 65162.2, degrees of freedom = 65535, cut-off = 66659.4** Passed chi-square independence testChi square goodness-of-fitscore = 2285.22, degrees of freedom = 2295 cut-off = 2510.06** Passed chi-square goodness-of-fit test** Passed chi square testsLRS testW: 5, Pr(E>=1): 0.864829** Passed LRS testIID = Truemin-entropy = 7.92358`
`\$ python iid_main.py ~/entropy-direct.bin 8 -vreading 1999996 bytes of dataRead 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 = 255Calculating statistics on original sequenceCalculating statistics on permuted sequencespermutation tests:      99.99 percent completestatistic  C[i][0]  C[i][1]----excursion     7875        0numDirectionalRuns*    10000        0lenDirectionalRuns     6435     3562numIncreasesDecreases      394        4numRunsMedian*    10000        0lenRunsMedian       40       48avgCollision*    10000        0maxCollision     5222     1236periodicity(1)*        0        0periodicity(2)       46        2periodicity(8)     1955       39periodicity(16)      512      15periodicity(32)     7632       39covariance(1)*        0        0covariance(2)      141        0covariance(8)     6251        0covariance(16)     5847        0covariance(32)     5980        0compression     7540        3(* denotes failed test)** Failed IID permutation testsIID = False`
`python iid_main.py ~/entropy-3b2.bin 8 -vreading 2097152 bytes of dataRead 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 = 255Calculating statistics on original sequenceCalculating statistics on permuted sequencespermutation tests:      99.99 percent completestatistic  C[i][0]  C[i][1]----excursion     5990        0numDirectionalRuns     6878        8lenDirectionalRuns      939     5563numIncreasesDecreases     1204       13numRunsMedian      220        1lenRunsMedian     1198      966avgCollision     8953        0maxCollision     6838     1137periodicity(1)      909       16periodicity(2)     3748       45periodicity(8)     8752       22periodicity(16)     9318       16periodicity(32)     8374       20covariance(1)     3183        0covariance(2)     4537        0covariance(8)     3617        0covariance(16)     2460        0covariance(32)      316        0compression     1473        6(* denotes failed test)** Passed IID permutation testsChi square independencescore = 65285.8, degrees of freedom = 65535, cut-off = 66659.4** Passed chi-square independence testChi square goodness-of-fitscore = 2269.05, degrees of freedom = 2295 cut-off = 2510.06** Passed chi-square goodness-of-fit test** Passed chi square testsLRS testW: 4, Pr(E>=1): 1.000000** Passed LRS testIID = Truemin-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.

# References

--

--

## More from Vault12

Protecting the future of money

## Get the Medium app

Personal Crypto Security: Protecting the future of money