3
$\begingroup$

Let's say the system has a hardware randomness generator, generating random numbers using a proven truly random process. The distribution of the numbers though, is unknown.

Assume the randomness source generates data blocks $P_1$, $P_2$, ..., $P_n$. There is an one-way function $f(x)$. The output data blocks are $Q_1$, $Q_2$, ..., $Q_n$. There is an initialization vector $Q_0$. The length of $P_n$ blocks, $Q_n$ blocks, $Q_0$, input and output block length of function $f(x)$ are all equal.

For each output block $Q_n$, there is:

$$ Q_n = f(P_n \oplus Q_{n-1}) $$

Questions:

  • Can the process above extract the randomness from the hardware source, given a proper $f(x)$ and $Q_0$?
  • What is the requirement for the one-way function $f(x)$ and the initialization vector $Q_0$ for this process to work properly?
  • Can I replace the $\oplus$ with something else without breaking the randomness? (Replacing it can allow me to relax the block length restriction.)
  • Can I extend this method into combining multiple randomness inputs?
Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Important clarification needed. Are you trying to develop a proper gold standard TRNG (entropy in > entropy out)? With $|P_x| = |Q_x| $ you can only have a pseudo random number generator with some bits of true entropy added in. This aspect changes everything as one way functions (or IVs) are not required for a proper TRNG. $\endgroup$
    – Paul Uszak
    Jul 25, 2018 at 20:52
  • 1
    $\begingroup$ Plus if the entropy input rate cannot be measured as you have no detailed input data /distribution, how can you proceed with correct entropy extraction? $\endgroup$
    – Paul Uszak
    Jul 25, 2018 at 21:00
  • 1
    $\begingroup$ Xor'ing anything with random data will not reduce the randomness. $\endgroup$
    – zaph
    Jul 25, 2018 at 22:14
  • $\begingroup$ @Paul Uszak This is not a gold standard TRNG, as this algorithm is used only to seed the crypto used in TLS sessions. One of the use cases involves a STM32 on-chip hardware RNG that is such a black box that the only instruction of use is “power it on, feed it the system bus clock signal, and start reading from a memory address for random bytes.” $\endgroup$
    – Maxthon Chan
    Jul 31, 2018 at 3:39

2 Answers 2

Reset to default
3
$\begingroup$

If hash collisions of f don't exist then information is neither created nor destroyed by f and $f(Q_{n-1}\oplus p_n)$ has as much entropy as $Q_{n-1}\oplus p_n$ which has as much entropy as $p_n$. If (for example) $p_n$ only introduced one bit of entropy then someone with $Q_{n-1}$ and access to the same randomness source can deduce the only two possible values for the next hash.

By "extract randomness" I think what you mean is that all blocks of P should have as much entropy as there are bits in P? A good hardware random number generator should already do that. If it doesn't then bits must be destroyed to turn them into entropy. Either $P_n$ gets mapped onto a space of fewer bits or you take multiple instances of $P_n$ and compress them into one. For example you could use the central limit theorem to take several samples from your unknown distribution and generate a normal distribution. Then you can turn the normal distribution into a uniform one.

Improve this answer
$\endgroup$
4
  • $\begingroup$ So you're suggesting that $Q$ needs to be shorter than $P$ to destroy excess bits? $\endgroup$
    – Paul Uszak
    Jul 26, 2018 at 5:55
  • $\begingroup$ In the non-iterative case Q = f(P) that is a necessary criteria. I don't think it is sufficient. mixing bits back in with Q_{i+1} = F(P + Q_i) is more complex. If all your Q_i are private except the last one then you don't need to shorten $\endgroup$
    – IIAOPSW
    Jul 26, 2018 at 12:00
  • $\begingroup$ I should add destroying bits is only needed if you have less entropy than bits and no way to get more entropy. $\endgroup$
    – IIAOPSW
    Jul 26, 2018 at 12:16
  • $\begingroup$ Does “concatenate them hash to a shorter length” destroy bits? For example $Q_n = SHA512(P_n // Q_{n-1})$ where P and Q blocks are both 512 bits long? $\endgroup$
    – Maxthon Chan
    Jul 31, 2018 at 3:35
-2
$\begingroup$

See the following application note for the controller you're using:-

AN4230 Application note: STM32 microcontrollers random number generation validation using NIST statistical test suite.

This is an extract:-

The purpose of this application note is to provide guidelines to verify the randomness of the numbers generated by the random number generator peripheral embedded in a selection of STM32 microcontrollers. This verification is based on the National Institute of Standards and Technology (NIST) Statistical Test Suite (STS) SP 800-22rev1a (April 2010).

The nature of these devices is that they produce uniformly distributed 32 bit words, notwithstanding the previous output. The note shows the STM32 TRNG passing all of the NIST randomness tests, and this is from the datasheet:-

The RNG passed the FIPS PUB 140-2 (2001 October 10) tests with a success ratio of 99%.

So you don't really need to do anything with the RNG output other than use it as is for TLS seeding. Entropy extraction is unnecessary as that's done on-chip. If you trust it, that is.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ If the chip I bought is a genuine ST part, those datasheets will apply fully. If the part is a clone (as commonly found on Chinese markets from often questionable sources) this guarantee will be questionable at best. $\endgroup$
    – Maxthon Chan
    Jul 31, 2018 at 18:29
  • $\begingroup$ @MaxthonChan Well, whilst you can't test the actual unpredictable entropy content of the output stream for any commercial TRNG, you can easily test it's uniform distribution with the standard tools (ent, FIPS, Diehard etc.) It will be uniform though or the chip would be considered faulty. The randomness extraction is done for you unless I've misunderstood the question. $\endgroup$
    – Paul Uszak
    Jul 31, 2018 at 20:52
  • 1
    $\begingroup$ @Paul Uszak the issue of course is that statistical tests prove nothing about security or entropy. Consider a 48-bit seed, plus a counter, passed through SHA2. This is completely insecure and trivial to predict for anyone knowing the seed (such as a nefarious manufacturer). Yet it would easily pass any statistical test, even BigCrush. If your hardware isn’t inside your trust boundary, you’ve already lost. $\endgroup$
    – rmalayter
    Aug 15, 2018 at 22:59
  • $\begingroup$ @rmalayter I think that wild conspiracy theories are frowned up on here. I know. We're required to trust our chips. $\endgroup$
    – Paul Uszak
    Aug 15, 2018 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.