6
$\begingroup$

In a previous question I asked if (and why) BlueRand can or cannot be considered as a TRNG.

Established that it's not a TRNG (due to the reasons explained by some users in the previous question), is it possible to create a TRNG that uses JPEG images as entropy source? How can I extract randomness from a JPEG image?

$\endgroup$
  • 1
    $\begingroup$ Use a randomness extractor? $\endgroup$ – mikeazo Jan 19 '17 at 20:00
  • $\begingroup$ @mikeazo thank you for the answer, let's assume I simply use a Cryptographic hash function as a randomness extractor. This will be considered as a PRNG or a TRNG? $\endgroup$ – Riccardo Leschiutta Jan 19 '17 at 20:06
  • 1
    $\begingroup$ From the wikipedia article: For a given source, a randomness extractor can even be considered to be a true random number generator (TRNG); but there is no single extractor that has been proven to produce truly random output from any type of weakly random source. $\endgroup$ – mikeazo Jan 19 '17 at 20:10
  • $\begingroup$ @mikeazo It would be extremely useful for everyone interested in randomness extraction if you could quantify a weakly random source in bits of entropy per byte, taking total unadulterated randomness as 8 bits /byte. $\endgroup$ – Paul Uszak Jan 20 '17 at 16:23
3
$\begingroup$

All original JPEGs are sources of true entropy due to:

  1. Noise on the image sensor. However small it might be, it is unavoidable due to the very nature of the stochastic photoelectric effect on the silicon detectors, be they CCD or CMOS. There are also other noise sources such as reset noise, thermal noise etc. This means that what ever you take a photo of, it will contain truly random noise across the image sensor.

  2. Compression. Once the image is captured by the sensor, the JPEG algorithm kicks in. Various processes occur that have the effect of reducing the intensity of high frequency noise both level and colour wise. So the randomness /entropy of the image drops significantly, perhaps to only 10% of that originally captured. This remaining noise is then losslessly compressed into a final jpg file. You could look up the JPEG algorithm. The consequence of the lossless compression is that tiny changes to the input image result in huge changes to the compressed jpg file. This is akin to changing a word in a zip file which then results in a totally different zip. It’s also akin to the avalanche effect.

Since every original JPEG file ever taken throughout the known universe is unique, this forms a perfect source of entropy.

Since the format of a jpg file is highly structured, it cannot be used directly as a source of uniformly distributed random numbers. It has huge correlations between bytes as you would expect of a standardised file format. This is why you have to treat the file as one sequence of unique bytes, some of which are hugely correlated whilst others are totally fixed such as the golden byte. Never ever open up the file and work on the image. You have to extract the entropy out of the jpg file itself, after measuring it with something like a minimum entropy calculation. I have a JPEG based true random number generator called a Photonic Instrument which you can see. Ignore the dumb ass humour and focus on the science, especially the Kullback–Leibler divergence graph. It produces JPEGs with a min. entropy of approx. 100 kbits /frame, which is about 5 bits /byte, and can do 4 frames /s.

You will have a true random number generator if you extract less than 100 Kbits from each frame / file. This is the golden rule of true random number generation. A common way to extract entropy is by hashing. It can be any kind of hash function, and not necessarily cryptographic at all. In fact, cryptographic hash functions can lead to the Cryptographic Hash Function Extraction Fallacy, which means if you use one you risk producing random looking output from any kind of rubbish input like a simple counter. I avoid them like the plague and am suspicious of any generator using them. Since you know that JPEGs are a source of true entropy in this case you are okay using one for this example, but you could do better.

You have to ignore the bleating of the theoreticians who say there are no extractors that work on all sources. You just have to ensure that [entropy out] < [entropy in]. Otherwise there wouldn’t be a thriving commercial market selling true random number generators would there? Hash it and there you go. You can use any of them (like MD5) but they don’t go over 1024 bits. You could write your own as I did which is a simple substitution permutation network with a block size of up to 512 kbits. That can hash my 20 Kbyte frame in one go. Alternatively, use SHA-1 several times over the jpg, making sure you add a counter to change the initial state, or use a kinda of block chaining hash mode.

This is all a lot of talk so try this… Take 10 pictures with your phone of anything at all. Hash each picture with SHA-1. The resulting 200 bytes will be truly random. Go from there and prove the naysayers wrong…

$\endgroup$
  • $\begingroup$ This interesting. It's good point that they probably wouldn't repeat depending on the source. If you used a camera you could generate the jpegs. Even there would be some regularity like lines and shapes and geometric principles. $\endgroup$ – marshal craft Jan 28 '17 at 3:40
  • $\begingroup$ @marshalcraft The avalanche effect of the Huffman coding within the JPEG means that any image regularities are totally subsumed by the random noise on top of it. $\endgroup$ – Paul Uszak Jan 28 '17 at 18:16
  • $\begingroup$ If a .JPG file is large enough, could it not be split into smaller files (just a straight binary cut into smaller files), and each smaller file hashed to gather pure randomness more efficiently? Do you use a data to randomness ratio, for example should a data source be about a thousand times more than the number of random bytes extracted (through hashing)? Also, would prefixing, inserting or appending a few pseudo-random bytes (or deleting a few bytes) to (from) a file before hashing it yield different but equally pure randomness? $\endgroup$ – r_alex_hall Aug 14 '17 at 18:12
  • 1
    $\begingroup$ @r_alex_hall Yes they could be split, but. The extraction ratio is determined by measuring the entropy of the JPEGs using compression + safety margin. Splitting makes the measurement process harder. If you add pseudo randomness, you can't count it in the entropy measurement as then the system becomes a pseudo generator rather than a true one. It's like adding water to a malt whiskey... $\endgroup$ – Paul Uszak Aug 15 '17 at 23:31
3
$\begingroup$

If you consider the entire process including taking the pictures then you may be able to create a TRNG this way.

However, given the JPGs, all you can do is create a PRNG because from the same JPGs as seed it would create the same output so it can obviously not be truly random.

$\endgroup$

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.