Secure entropy extractor for thermal noise collected from camera input? I have read this paper (pdf) which talks about measuring the entropy of thermal noise collected from camera input. They estimate the minimum entropy at about 4 bits per pixel. Probably estimating 1 bit per color looks to be the safest option from looking at the X500's camera:



The paper mentions some future research work on how to extract the random data. Edit: I have found that paper by the same authors which discusses some methods which I will read up on some more.

What I would like to know is how I can extract the entropy from each pixel in an information-theoretic way ie. to get true randomness. Hash functions will not be suitable for this purpose. It should also be simple to understand an implement in software.

One idea was to take the least significant bit for each color of a pixel. XOR the 3 bits together. Output 1 bit. After all the pixels have been processed and all the bits have been output, then run them through the Von Neumann extractor and this is the final output.

Another is to take an accumulator S, initialize to zero. XOR the next byte onto it, and rotate one bit. Repeat with 8 bytes or as many as needed. In theory it takes known regularities in the input and eliminates them one by one. The bits in the byte are biased, hence the rotations. We might also expect RGB values being biased, so we want to make sure equal amount of R, G and B goes into every bit.

Are any of these methods information-theoretically secure? I am open to any proper methods (or references to any prior papers) on how to do this properly in a conservative manner from any reputable cryptographers on here.
The question asks for an entropy extractor suitable for a particular camera, that is information-theoretically secure, but rejects hash on the rationale that hash functions are not perfectly secure. I'm afraid that for the same definition of secure in these statements, there's nothing on the book; perhaps nothing possible.



A method considered in the question seems to be: XOR the low-order bit of the readings of the three color channels, and feed the result to a Von Neumann extractor. Even assuming that the experimental data in the question holds, it is not information-theoretically possible to prove this will give a result indistinguishable from random, or even just unbiased. Rather, it could be demonstrated that for some model of the input, the output is biased; and more surprising things have occurred in similar attempts in practice. That's because:


There is reason to believe that the channels of the same pixel are heavily correlated; combining several of them is some arbitrary way not taking their nature into account can theoretically leave us with less entropy than in any channel alone, even if the combiner is information-theoretically secure under the assumption that its inputs are not uncorrelated.
The Von Neumann extractor is guaranteed to yield unbiased output if it is fed with mutually independent bits; but here there are reasons to fear that consecutive readings are mutually related (like: the analog route taken by pixels in the same scanning row is the same, hence the capacity of that line creates correlation).
Keeping only the low-order bit of a reading with known entropy is guaranteed to lower the entropy to at most 1 bit per sample, but there's no theoretical minimum, no matter how high the entropy before truncation is, unless some detailed hypothesis is made on the initial samples (in particular: it is quite conceivable that an ADC has its low-order bit constant while it recovers from a large input change).




Cryptographic entropy extractors, based on a hash or similar primitive, are the best thing around with a sound security rationale that does not require knowing some model of the physics and hardware in the entropy source. They are robust: a sound cryptographic entropy extractor convincingly gives output computationally indistinguishable from random for any mishap in its input, except for loss of entropy in the input ever since initialization, or leak of the extractor's internal state thru side channels.

By contrast, simple extractors relying on a some model of the source at their input tend to fail because the model is inaccurate, perhaps even briefly (for example: ADC saturation caused by a power supply transient, internal recalibration after some time or a temperature change).



If one insists on something extremely simple (not secure in a cryptographic sense), with a level of theoretical justification that it is unlikely to be catastrophic for a natural entropy source of unknown model, one could use


a multiplicative scrambler with a large $n$-bit state (detailed below); that's a simple entropy accumulator, of easily tuned capacity; it's output is provably perfectly random if its input is, and it smoothly degrades to a simple PRNG otherwise;
fed with all the bits output by the sensor's channels;
with sub-sampling  of its output keeping every $s$th bit, with sub-sampling factor $s$ coprime with $n$ and such that the residual bit rate is comfortably below the entropy rate on input estimated by the empirical data at hand (say, by a safety/fudge factor of 8, or 2 if the next step is taken); thus here, if we feed 24 bits per pixel and have an estimated 2.1 bit entropy per pixel (which the second figure on the right column justifies), we want $s$ at least 8*24/2.1 or 2*24/2.1; rounding up to the next prime number in order to widen our choice of $n$, that's $s=97$, or $s=29$ with the next step;
optionally followed by a Von Neumann extractor, which will divide the average bit rate by 4 (and make it irregular, which might be unwelcome); it is likely to remove a residual bias that could be present for low $n$ even if everything else goes as planned; it makes cryptanalytic attacks trying to distinguish the output from random more involved;
taking care to discard the early output until the number of discarded bits is several times $n$;
with precautions that nothing in the above can have any feedback to the entropy source (which would invalidate the hypothesis that the model of the source has nothing to do with the scrambler).


A multiplicative scrambler is built around a LFSR, based on a binary polynomial of degree $n\ge1$. The polynomial must have the constant term set (ensuring it does not lose entropy), and is often chosen primitive (which avoids a number of poor choices; and maximizes the expected period for input stuck at 0, though that's not essential here). For example, with $x^{23}+x^{18}+1$, the schematic of a scrambler used in telecoms goes



In telecoms, $n$ must be small (for quick resynchronization of the descrambler in case of error). We rather want something with a larger state, like $x^{256}+x^{187 }+x^{125}+x^{60}+1$, taken from eq-primpoly-w5.txt of Jörg Arndt's Tables of mathematical data, quoting Janusz Rajski, Jerzy Tyszer: Primitive Polynomials Over GF(2) of Degree up to 660 with Uniformly Distributed Coefficients, in Journal of Electronic Testing: Theory and Applications, vol.19, pp.645-657, 2003. A software implementation can use an array $b$ of 256 bits, and an 8-bit index $i$ (all operations on index being truncated to 8 bits)


for each input bit $x$


$i\gets i+1$
$x\gets x\oplus b_i\oplus b_{i+60}\oplus b_{i+125}\oplus b_{i+187}$
$b_i\gets x$
output $x$