# Use of scrambler LFSR for randomness extraction of semi-random source

I am using a linear feedback shift register (LFSR) in a scrambler configuration as a randomness extractor for a weakly random source. This source is semi-random (aka. Santha-Vazirani source): the bits are correlated and biased (with a min-entropy of ~0.5 per bit). Here is an example of a LFSR in a scrambler configuration (this one is 12-bit while I am using a 32-bit register) with a downsampler:

The weakly random entropy source feeds the LFSR scrambler directly and the output is highly downsampled (one output bit is taken for every e.g. 1000 weak bits). This method has been proposed here. However, I did not find examples where LFSR scramblers are used as randomness extractors. Hence, I have the following questions:

1. Is using a scrambler for randomness extraction of semi-random data a valid use? How does it compare to other extractors? For example, a von Neumann extractor is only suitable for biased, independant (not correlated) input and is linear time.
2. How to compute how much downsampling/decimation is required at the output of the LSFR so that the output is suitable for cryptographic use (given an estimation of the input min-entropy)?
3. What implications does taking the whole register at once (e.g. output 32 bits every 32000 weak input) rather than 1 bit every 1000 input have?

context: The LFSR is used in the following TRNG:

• What are you sampling? Jul 11, 2021 at 20:26
• @PaulUszak XORed output from multiple ring oscillators. Jul 11, 2021 at 23:28
• Not familiar with hardware part, what is the weakness of ring oscillators? Dependence of consequent samples or bias away from 50%? Jul 14, 2021 at 9:38
• @Fractalice The sampled signal from the oscillators has both strong periodicity and bias characteristics. You can see both in these noise images I generated. In the 4x3-stages image, we can distinguish some line patterns which is a direct consequence of the periodicity/the lack of jitter. Compared to true random data, the oscillators produce more white pixels which means a bias towards 1. Jul 16, 2021 at 4:59
• @DurandA You can't do that. The eye can't distinguish between autocorrelation (R) of $R \leqslant 10^{-3}$ and $R > 10^{-3}$. These are commonly accepted correlation limits. Aug 19, 2021 at 22:54

TRNG:no.

1. No. Scrambling ~ permutation. That's not security, it's obfuscation.

2. This is the crux of your question and entirely subjective. Most here will know that I am a strong advocate of one time pads, but. Share your details of your TNRG. 50 MHz? No. No commercial TRNG does that as you will encounter autocorrelation. Share...

3. Irrelevant :-).

We can work on this, but $$H_{\infty}$$ will be much reduced.

• I will update the question with the TRNG design (basically this but with 32-bit LFSR in scrambler configuration). However, I do not understand your negative reaction about the sampling frequency of 50 Mhz from the weak entropy source. How is this frequency relevant to the security of the system as long as enough entropy is collected by the randomness extractor? Jul 12, 2021 at 1:28
• Negative reaction: experience.. Ring osillotors are notoriously stable. I've seen decimation rates of 1024. The only reason we make them is that its easy for silicon. Jul 12, 2021 at 4:40
• "That's not security, it's obfuscation": the security of the system does not depend on the knowledge of the LFSR configuration. As shown by @fgrieu here, adding another LFSR in a descrambler configuration will reveal the original input—whose bias can be exploited to predict future output. Instead, the system relies on decimation at the LFSR output for randomness extraction. Given that you know the complete design of the system and latest generated values, do you have a better than random chance of predicting future value(s)? Jul 16, 2021 at 3:44
• @DurandA The security of a TRNG doesn't come from a 'hidden' design. It comes from some internal physical property that you exploit. Ring oscillator jitter/propagation delay can only be described statistically at the macro level. If there's no bias (uniform distribution, not Gaussian), you'll be safe. Jul 16, 2021 at 12:51
• Have you measured the entropy per tick at the Sampler? That's the crucial measurement. Jul 16, 2021 at 12:52