3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ What are you sampling? $\endgroup$
    – Paul Uszak
    Jul 11 at 20:26
  • $\begingroup$ @PaulUszak XORed output from multiple ring oscillators. $\endgroup$
    – DurandA
    Jul 11 at 23:28
  • 1
    $\begingroup$ Not familiar with hardware part, what is the weakness of ring oscillators? Dependence of consequent samples or bias away from 50%? $\endgroup$
    – Fractalice
    Jul 14 at 9:38
  • $\begingroup$ @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. $\endgroup$
    – DurandA
    Jul 16 at 4:59
  • $\begingroup$ @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. $\endgroup$
    – Paul Uszak
    Aug 19 at 22:54
0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – DurandA
    Jul 12 at 1:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – Paul Uszak
    Jul 12 at 4:40
  • $\begingroup$ "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)? $\endgroup$
    – DurandA
    Jul 16 at 3:44
  • $\begingroup$ @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. $\endgroup$
    – Paul Uszak
    Jul 16 at 12:51
  • $\begingroup$ Have you measured the entropy per tick at the Sampler? That's the crucial measurement. $\endgroup$
    – Paul Uszak
    Jul 16 at 12:52

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.