6
$\begingroup$

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ ($\hspace{.03 in}$just checking) ​ Can you provide a seed? ​ ​ ​ ​ $\endgroup$ – user991 Feb 21 '16 at 11:00
  • 3
    $\begingroup$ "Hash functions will not be suitable for this purpose." - Why? $\endgroup$ – otus Feb 21 '16 at 11:10
  • 2
    $\begingroup$ @otus : ​ There's not publicly known proof that their outputs are uniformly distributed for long uniformly distributed inputs. ​ ​ ​ ​ $\endgroup$ – user991 Feb 21 '16 at 12:39
  • $\begingroup$ @RickyDemer, It sounded like an additional restriction (can't be based on hash functions), which is why I asked. While a hash function on its own is not necessarily a good extractor, many extractors are based on hash functions so it would be useful to know whether that is a hard requirement for some reason. $\endgroup$ – otus Feb 21 '16 at 15:21
  • $\begingroup$ @otus : ​ ​ ​ Huh. ​ Good point. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user991 Feb 21 '16 at 16:06
2
$\begingroup$

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

multiplicative scrambler

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$
$\endgroup$
0
$\begingroup$

I'm not a reputable cryptographer, I just build true random number generators for interest.I have such a camera based device that generates true random numbers on the bench next to me.

There's really no practical way that you can avoid some form of hash for entropy extraction. You are even alluding to it youself with your XOR + rotate proposal. That's what hash functions like SHA do internally.

I infer that you want to avoid cryptographic hashes like SHA and this is exactly the same decision I made. SHA Shma. You don't need a non invertable cryptographic hash as you're inputting true randomness into the function so inverting it just gives you randomness back. A lot of TRNGs don't use cryptographic methods.

Unfortunately your CMOS entropy source will contain significant variations in entropy rate. You'll be able to see these if you perform a graphic equalisation on the camera image. Von Neumann will not help with auto correlation at all. If you're just messing about then this doesn't matter. If you want to use your device for production, correlation will kill you. You will have to treat the entire image as a single entropy block. A matrix extractor will work perfectly.

  1. Generate matrix M consisting of good random numbers. Its size will depend on the degree of compression you will need to achieve full entropy. You need the compression because your image is not 100% entropy, so you need to squeeze it down to the pure stuff.
  2. Matrix I is the image.
  3. Your output entropy is therefore [M].[I]

It's actually surprisingly easy but it's still a kinda hash. Only thing is that it is very slow. That's why no commercial TRNG uses cameras. I wrote my own 512 kb substitution /permutation network instead, and my device outputs 0.3 bits /pixel at 120 kb /s. It's this low because my camera images are JPEGs and I assume you're dealing with TIFFs. Extraction will be much faster if you use JPEGs instead. But it's really random.

$\endgroup$
  • 1
    $\begingroup$ Wouldn't you then need a "true" random number generator to get those random number for the matrix M, so that it doesn't create any biases in the result...? $\endgroup$ – ilkkachu Sep 11 '16 at 8:32
  • $\begingroup$ @ilkkachu The noise distribution of the pixels in the matrix will truly random. This is due to the diffusion interface where the "pixel" actually works. So, if the matrix M is the pixel field, you'll have truly random field. The lowest effective "two bits" that I see on a pixel if I read from it with a 16-bit ADC are truly random. There's a lot more hardware discussion that would need to happen to tell if this would be true in all cases, but CMOS images are truly terrible at room temperature due to noise. $\endgroup$ – b degnan Sep 11 '16 at 20:14
  • $\begingroup$ @ilkkachu No, actually you don't. You just need some "decent" random numbers. You could flip a coin or pull some from a pseudo random source. I drew 256 paper based numbers from a box that my cat had dug through for one of my extractors. The matrix M is only a kind of hash /compressor for the true random input. If the size of matrix M exceeds any possible length of correlation and your input images are of something truly random (noise), you'll get perfect random numbers. I wish I could describe this algebraically, but I can't. $\endgroup$ – Paul Uszak Sep 11 '16 at 21:25

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.