5
$\begingroup$

As an appendix for my bachelor thesis, I proposed a solution for a TRNG that uses JPEG images as entropy source.
It's open source and available on GitHub.

My question is: can this be really considered as a TRNG?

Obviously I tried to create a TRNG (and not a PRNG or a CSPRNG), but you know... the devil is in the detail.
Here some info, so you can help me enstablish if it can be considered as a TRNG or just a bottle of snake oil :)

How it works

  • It uses two different input images (with the same resolution). These images are considered independent because captured in two different moments.
  • It uses the Mixing technique, so the output will be unpredictable if at least one of two images is unpredictable.
  • Only some of the total amount of pixels are considered. The CSPRNG SecureRandom sets for each considered pixel how many consecutive pixels have to be discarded. In this manner the correlation between consecutive pixels is avoided. This also guarantees that if the generator is run twice two different outputs will be generated.
  • Only the BLUE channel is considered. So the correlation between different channels is avoided.
  • The noise that can be found inside an image is located in the least significant bits (LSB). For this reason only the LSB of each input byte is used. You can choose to consider the second least significant bit too.

Bruce Schneier guidelines

In Applied Cryptography, Bruce Schneier lists some guidelines to check if a generator could be considered as (CS)PRNG or TRNG:

  1. For our purposes, a sequence generator is pseudo-random if it has this property:
    It looks random. This means that it passes all the statistical tests of randomness that we can find.

  2. For a sequence to be cryptographically secure pseudo-random, it must also have this property:
    It is unpredictable. It must be computationally infeasible to predict what the next random bit will be, given complete knowledge of the algorithm or hardware generating the sequence and all of the previous bits in the stream.

  3. Philosophy aside, from our point of view a sequence generator is real random if it has this additional third property:
    It cannot be reliably reproduced. If you run the sequence generator twice with the exact same input (at least as exact as humanly possible), you will get two completely unrelated random sequences.

And the solution I proposed:

  1. I executed some tests, and seem promising. Maybe other tests are required (?)
  2. It doesn't use hash functions. Each output bit is dependent on a specific pixel only. So, if an attacker knows the previously created bits, he cannot foresee the future ones.
  3. It uses a CSPRNG just to choose the pixels to consider. So, executing the generator twice, each time two different outputs will be generated.
$\endgroup$
  • 1
    $\begingroup$ I seem to remember that the jpeg data or even the bits describing the finest details in a jpeg image, are not random. Because of this, hiding encrypted data in jpeg images (as part of Steganography) can be detected. This lead me to assume that you are putting to much faith in the random nature of jpeg data. $\endgroup$ – Jacco Jan 15 '17 at 19:01
  • 1
    $\begingroup$ Possible duplicate of Is Jericho Comms TRNG reliable? $\endgroup$ – J.A.K. Jan 15 '17 at 19:20
  • 2
    $\begingroup$ Lol. So asking about a year later again, and stating the intend to plagiarize. For the small chance the bachelor part is true, I really hope you're found out. $\endgroup$ – deviantfan Jan 15 '17 at 19:32
  • 1
    $\begingroup$ @deviantfan That's a way of reasoning that I just cannot fathom. If it is just about entropy / randomness without directly relating to system security, I'd say it's more on topic here, the same goes for the other question. I cannot count the number of times that somebody had a question closed on SO only to proclaim "hey, but that question over there wasn't closed, how come". Doesn't make it any more on-topic (or off-topic for that matter). Besides that, crypto is relatively new to the game. $\endgroup$ – Maarten - reinstate Monica Jan 16 '17 at 16:46
  • 2
    $\begingroup$ Using SecureRandom (a seeded CSPRNG) as input for a TRNG...there's something fundamentally wrong just there. $\endgroup$ – Maarten - reinstate Monica Jan 16 '17 at 16:50
12
$\begingroup$

Just no.
If you use some files and a CSPRNG as data source for a deterministic algorithm, it's not a true random number generator.

According to your own Schneier quote:

If you run the sequence generator twice with the exact same input (at least as exact as humanly possible), you will get two completely unrelated random sequences.

It sounds like your generator will generate the same numbers, so... don't mistake the CSPRNG for your generator. The CSPRNG is input for your generator. (And even if not, same input for CSPRNG is same output).

There are other problems (like thinking two images of the same place are independent), but they don't really matter anymore.

...

Obviously I tried to create a TRNG

That's a pretty good giveaway that you don't really know what your doing. A TRNG can't be created with some software piece on a turing-machine-alike. Nobody can, never.

$\endgroup$
  • 3
    $\begingroup$ Well said deviantfan. The CSPRNG is the only random part there, the rest is just added complexity. If you strip away the random selection of pixels, it is only as good as your random choice of an image. If it is as good as the CSPRNG, it can obviously never become a TRNG. $\endgroup$ – J.A.K. Jan 15 '17 at 19:10
8
$\begingroup$

I think you have fundamentally misunderstood the entropy source in Jericho Comms, the open-source project you're getting this from. This actually does have a source of hardware randomness.

You propose taking just the least significant bit of the color as input data. What you fail to mention is using the raw, unprocessed CCD noise.

JPEGs will not work as TRNG. They are processed and optimized, stripping info from the LSB, so the output is software randomness. Also, the whitepaper suggests using a constant stream of images acquired during "viewfinding" for higher entropy

From the whitepaper:

..their testing was done against the optical sensor noise by capturing frames from the view finder with the lense cap still on. Independent testing of their results shows that this does give some entropy in the resulting data. ... To prevent interference or bias by software noise reduction and compression, a digital camera's RAW mode [74] should be used.

Because, as your academic peers have proven, that is likely a sound way of implementing a hardware TRNG. If you were to preserve the randomness of the imaging chip this might work. But unless you have direct control over the process of taking the picture, it will be unreliable.

$\endgroup$
  • 1
    $\begingroup$ JPEGs work perfectly, and you do not have to use any form of raw output from the image sensor. It is entirely irrelevant that They are processed and optimized, stripping info from the LSB. All that does is reduce the available entropy in the JPEG file. You have to realise that all original JPEGs taken in the world are unique due to sensor noise (irrespective of what they're looking at). Your error is in assuming that you extract linearly from sequential JPEG bytes. Take it as a bit fixing block source with auto correlation of FILESIZE and extract from there... $\endgroup$ – Paul Uszak Jan 17 '17 at 11:47
  • 2
    $\begingroup$ @PaulUszak if I understand correctly, the fact that each JPEG image is different from the others tells us that some entropy is present (despite the FFT and quantization) due to the sensor noise. But because of the programmatic output of the JPEG decoding algorithm it's an error trying to extract it linearly from the file bytes. What do you mean by Take it as a bit fixing block source with auto correlation of FILESIZE and extract from there? $\endgroup$ – Riccardo Leschiutta Jan 18 '17 at 20:15
  • $\begingroup$ "JPEGs work perfectly". Yeah. For a PRNG! But i'm talking about the research done towards CCD noise; that whitepaper is the reason the asker believes his scheme to be a true RNG $\endgroup$ – J.A.K. Jan 18 '17 at 22:54
  • $\begingroup$ I have updated my answer so this distincion is more... distinct. $\endgroup$ – J.A.K. Jan 18 '17 at 22:55
  • $\begingroup$ You previously stated that "JPEGs will not work as PRNG" and now I've persuaded you to admit that they work for a "PRNG!". Now think hard. If you xored together all the bytes of a say a 1MB .jpg file (without decoding the raster image), would the resultant single byte be truly random? If so, I think that we're getting there... $\endgroup$ – Paul Uszak Jan 19 '17 at 0:30
2
$\begingroup$

No.

It is not a TRNG. At best you have designed a PRNG, based on another PRNG. There are several flaws, three being...

  1. The architecture is wrong. You base this on BlueRand. BlueRand is not a TRNG. It is a PRNG. The developer has made the common mistake of confusing entropy with complexity. He has opened the JPEG file. Never, never ever open the JPEG file. What he believes to be entropy is actually the complexity generated by Fourier transformations and quantization. The LSB only contains the programmatic output of the JPEG decoding algorithm.

  2. Java SecureRandom is used to select pixels for randomness extraction. This is where the pseudo randomness is coming from and why BlueRand passes randomness tests. Virtually anything that you process on the basis of SecureRandom selections will pass as you're using a very good random number generator to pick them! This is also a common falacy of using cryptographic functions for randomness extraction. They can extract randomness from any old rubbish as they themselves produce pseudo randomness.

  3. Your design has no proof of the golden rule of TRNGs, that being (entropy out) < (entropy in). You cannot output more true randomness than the combined entropy content of the two JPEG files. Minimum entropy of a really low light JPEG may be 5 bits /byte. You can work out yourself if your system passes this test...

Hint. You can create a TRNG based on JPEG files if you understand that every original JPEG is unique, keep them very low light and only extract randomness from the JPEG as an undecoded stream of entropy.

$\endgroup$
  • 1
    $\begingroup$ @RiccardoLeschiutta I apologise as I'm having difficulty explaining this clearly. Ignore the fact that your file represents an image. Treat it as just a unique sequence of bytes, some of which are fixed, some vary truly randomly and all are correlated in complex ways. To get true randomness from the file, run it though a SHA-1 hash. The resultant 20 bytes are truly random. Then discard the .jpg and get another one --> TRNG. $\endgroup$ – Paul Uszak Jan 19 '17 at 0:38
  • 1
    $\begingroup$ @RiccardoLeschiutta If you were to post another question such as "how to extract randomness from a JPEG file", I could explain it in more detail. $\endgroup$ – Paul Uszak Jan 19 '17 at 0:40
  • 1
    $\begingroup$ @PaulUszak "The resultant 20 bytes are truly random", but because you used a hash function as the extractor, you only get to think of it as 80-bits of entropy. Also, the jpeg would need to stay within the confines of the RNG and not be exportable or extractable $\endgroup$ – Richie Frame Jan 19 '17 at 1:52
  • 1
    $\begingroup$ @RichieFrame Why 80 bits and not 160 bits if you hashed a .jpg containing 100 kbits of min. entropy? $\endgroup$ – Paul Uszak Jan 19 '17 at 2:27
  • 1
    $\begingroup$ @PaulUszak I remember it being standard practice that the max allowed entropy of a hash function extractor for a TRNG source is the smaller of half the digest size of the hash function or the entropy of its input, I could be wrong $\endgroup$ – Richie Frame Jan 19 '17 at 8:01

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.