# Extracting randomness from highly-biased RNG

I have a source with a very low entropy (like 3 entropy bits per 1024 source bits). But I need to construct a 128 bit seed from the source.

Will it be helpful to XOR 350 bits with jump 128 bits, e.g. $n_0\oplus n_{128}\oplus\dots\oplus n_{128*350}$ or maybe some more times?

EDIT: The source is SRAM so the bits are fairly independent. Distribution of min-entropy is on the histogram. The first bar is like 500 bits, but the others are much lower so I cut the first one.

• I'd say use this! or some other randomness extractor: en.wikipedia.org/wiki/… Jun 26 '17 at 9:09
• Be careful with the keyword randomness extractor. Not all of them are suitable for cryptographhic use. Especially if you don't know how your entropy is spread over all those bits, simple binary operations are quite likely to be insecure.
– tylo
Jun 26 '17 at 9:22
• @tylo i thought its fine as long as you feed it correctly "so long as each bit has the same probability of being one and there is no correlation between successive bits" A Von Neumann extractor might not be the most efficient, but should be simple enough that you can see when the NSA messes with your implementation. Jun 26 '17 at 10:57
• @daniel Please re-read the question. It is exactly stated like that.
– tylo
Jun 26 '17 at 11:05
• @daniel It is taken from uninitialized SRAM, see link Jun 26 '17 at 11:17

If the source as 3 entropy bits per 1024 source bits, constructing a 128-bit seed requires $\lceil128\cdot 1024/3\rceil=43691$ source bits at least.

The "XOR 350 bits with jump 128 bits" translates to (correcting the question's formula) $$o_i=n_i\oplus n_{i+128}\oplus n_{i+2\cdot128}\oplus n_{i+3\cdot128}\oplus\dots\oplus n_{i+348\cdot128}\oplus n_{i+349\cdot128}$$ That can not be guaranteed to work. For example, a source that outputs one truly random independent unbiased bit every precisely 256 bits, and outputs 0 the rest of the time, has a rate of 4 entropy bits per 1024 bits, but the 128-bit seed generated by the proposed method has a single bit of entropy (and worse, can take only two values).

Without a model of the source, a common solution is to hash the entropy source. That protects against a wide array of accidental failure modes (like unwanted feedback of the conditioned output to the entropy source). Of course, it remains of paramount importance, and difficult, to reliably detect a broken or rigged source that does not meet its assumed entropy rate.

For the utmost output entropy and common Merkle-Damgård hashes, it is best to truncate a hash wider than the output: there may not be quite 256-bit entropy in the output of SHA-256 with ample entropy in the input, in particular if the last message block hashed is constant. So for a 256-bit seed it is best to use SHA-512/256. For up to desired 240-bit seed, and all except adversarially rigged entropy source, SHA-256 truncated to the seed width is fine.

It is reasonable to use HMAC-SHA-512(K, N) truncated to the seed size, where N is the input entropy, and K remains unknown to the designer of the entropy source; this way, the best said designer can hope is make the output repeat, but s/he has no control on the values at the output.

EDIT: if the source is (the power-on state of) SRAM, and its addressing is natural (matches physical organization), then the proposed "XOR bits with jump 128 bits" entropy extractor makes me especially nervous: it is all too possible that all the bits entering a given $o_i$ share a common bias, because they are on the same row or column (or a small number of these). Using an odd jump could help somewhat. This illustrates the need to have a model of an entropy source to make recommendations about its conditioning.

Also, beware that adversarial control of the power-on conditions might reduce your entropy rate (think system reset without a power cycle after the RAM has been set to a repeatable state, slow controlled power rise at low temperature obtained by evaporation of an appropriate liquefied gaz, and other things hackers do); and that some marketed-as-SRAM really is DRAM with a hidden refresh, or could become so for cost-optimization reasons.

Even with the same mask set, the entropy rate might change drastically from one fabrication batch to another; it should at least be validated on "corner lot" wafers. Even if things are done once at wafer testing time, don't assume that all wafer testers will yield the same entropy, and that it won't depend on the testing temperature, which someone at the fab might decide to change (e.g it is common that at start of production of a new chip test is performed at several controlled temperatures, then move to different temperature(s) when the process has stabilized).

EDIT2: If the thing must be done in silicon, a 128-bit CRC for the source might be the way to go, e.g. using primitive polynomial $x^{128}+x^{99}+x^{62}+x^{33}+1$ (source: eq-primpoly-w5.txt in Jörg Arndt's useful and ugly page of mathematical data).

In a non-adversarial context, a CRC is a fine alternative to a hash, because for any natural entropy source (not designed with knowledge of the CRC polynomial, and not influenced by the CRC being computed), the output will be unbiased, and all input bits will have the opportunity to influence all output bits (for standard definition of CRC in crypto and telecoms, that is remainder of the division by the CRC polynomial of degree $k$ of a polynomial of degree $m+k$ which $m$ high-order coefficients are the entropy bits, and the $k$ low-order bits are zero).

Notice that "I don't have place to store all the needed ~50 Kbits" is no excuse not to use a hash or MAC: SHA-256 and HMAC-SHA-256 can be computed with 128 bytes of temporary memory, regardless of the input length.

FINAL NOTE: With that idea of RAM content as entropy source, be at the very least cautious about the (aforementioned) attack where an adversary makes a reset (or many) without removing power!

• Main problem is that it must be done during boot and I don't have place to store all the needed ~50 Kbits. So anything simple enough should be good. Could you explain why CRC will extract the randomness? Jun 26 '17 at 11:52

The simplest solution is to use Pearson hashes. 50% of all cryptographic problems can be solved with Pearson hashes. Some numbers to put things into perspective:-

• Assume 60K of physical SRAM
• Assume 3 bits /1024 bits entropy (0.29%)
• Exclude 10K for variable storage, leaving 50K SRAM for entropy generation
• That's 1200 bits of pure entropy to be harvested
• 128 bits (8 bytes) actually required

This can be extracted with 8 Pearson hashes that requires 8no. 256 byte derangements. Total storage required for the 8 permutations is only 2048 bytes. The derangements are generated during development and fixed for all time. It's a hybrid hash and matrix extractor.

You will have used all of the available SRAM giving you a safety factor of 9. The large safety factor will mitigate irregularities in your entropy estimation, and eliminate all funky physical artefacts caused by the layout on the die. One of the other selling points of Pearson is simplicity. This extractor only requires about 10 - 15 lines of C code in addition to the 2D derangement array. And it's easily debugged without weird cryptographic libraries.

I do not champion the idea of cryptographic randomness extractors in these situations. It's a common fallacy that a cryptographically secure function has to be used. Truthfully, it does more harm that good in that any old rubbish input (such as a simple counter) will create uniformly distributed random numbers. The allows the extractor and device to pass randomness tests creating a false sense of security. Much simpler hashes and matrix methods are proven more reliable, such as those by ID Quantique.

Please answer the following truthfully. Are you a terrorist, conspiring to overthrow a Western government through violence or an active agent of Chinese military intelligence? If you're not any of these, it's fair to say that you needn't concern yourself with the device being booted under liquid helium to ascertain the SRAM state.

This technique will create a true random number generator satisfying the golden rule of (entropy in) > (entropy out). By a factor of 9. (There's an interesting philosophical debate as to whether this makes the numbers 9 times more random.)

• Turning upside-down the Aero Clean duster I use on the CPU fan of incoming PCs is enough to make it pour a liquefied gaz that evaporates at −26.3 °C, and that might throw some TRNG in disarray. Some realize it and properly react, some do not. Liquid N2 is used by the gallons my two favorite ice-cream shops, and some Australian ones.
– fgrieu
Jun 26 '17 at 16:37
• @fgrieu I guess it's up to Kesha's risk analysis to see how often this might be done. Incidentally, do you have 3 examples of where this has been successfully used with micro controllers to actually recover useful data? Jun 26 '17 at 16:38
• I have a circuit diagram for how to make SRAM boot up with whatever values you want. Why waste address space on your bootloader ROM you're going to throw away after booting anyway? Jun 26 '17 at 17:35
• "50% of all cryptographic problems can be solved with Pearson hashes" An odd thing to say about a hashing scheme that provides no security whatsoever. Jun 26 '17 at 18:02
• @fgrieu your french spelling of gas is great, this may be why french bottled water is more expensive. (Also spraying liquefied gas to break a crypto system is hilariously close to spraying a padlock and shattering it with a hammer) Jun 27 '17 at 13:02