Score:4

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

us flag

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:

LFSR scrambler

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:

TRNG

Paul Uszak avatar
cn flag
What are you sampling?
DurandA avatar
us flag
@PaulUszak XORed output from multiple ring oscillators.
Fractalice avatar
in flag
Not familiar with hardware part, what is the weakness of ring oscillators? Dependence of consequent samples or bias away from 50%?
DurandA avatar
us flag
@Fractalice The sampled signal from the oscillators has both strong periodicity and bias characteristics. You can see both in [these noise images](https://docs.google.com/document/d/1srb3rwd-MhxEhMsq1V8GMYIejlq99ZZWdcyAHJvAths/edit?usp=sharing) 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.
Paul Uszak avatar
cn flag
@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.
DurandA avatar
us flag
@PaulUszak I think that these noise images can help to build intuition when pattern are very apparent. Of course, the opposite is not true and this cannot used for any entropy assessment.
b degnan avatar
ca flag
@DurandA as you can prove that jitter in a ring oscillator is a function of 2-way channel shot noise (not Johnson) per each switch. You only need one RO with the sample significantly slower (within the noise margin). In silicon, this is fine, and if you do monte carlo simulations, you might see this behavior, but you can always measure it.
Score:0
cn flag

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.

DurandA avatar
us flag
I will update the question with the TRNG design (basically [this](https://crypto.stackexchange.com/q/89709/39499) 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?
Paul Uszak avatar
cn flag
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.
DurandA avatar
us flag
"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](https://crypto.stackexchange.com/a/89712/39499), 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)?
Paul Uszak avatar
cn flag
@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.
Paul Uszak avatar
cn flag
Have you measured the entropy per tick at the Sampler? That's the crucial measurement.
DurandA avatar
us flag
"_It comes from some internal physical property that you exploit._" Since the ring oscillator are only weakly random, it is required to "extract" the entropy using a randomness extractor which will produce a much smaller output. In my case, I accumulate 1000 weakly random bits from the ring oscillators to produce 1 bit. The question is whether a LFSR is OK for this task and how it compares to e.g. a secure hash function.
DurandA avatar
us flag
Yes, the min-entropy is ~0.54/bit (edited) as per `ea_non_iid` from SP800-90B. I know there is [some controvery](https://crypto.stackexchange.com/questions/83882/whats-wrong-with-nist-sp-800-90b) about this test but I am not aware of a better technique to estimate the min-entropy without an expensive oscilloscope to characterize the jitter.
DurandA avatar
us flag
I clearly understand how an `[biased independant source] -> [LFSR]` design can be exploited. What about `[biased correlated source] -> [LFSR] -(mostly uniform correlated)-> [decimator]` as proposed?
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.