Using one RNG to sample another

Suppose you have two pseudorandom bit generators.

They’re both fast, but not suitable for cryptographic use.

How might you combine them into one generator that is suitable for cryptography?Coppersmith et al [1] had a simple but effective approach which they call the shrinking generator, also called irregular decimation.

The idea is to use one bit stream to sample the other.

Suppose the two bit streams are ai and bi.

If ai = 1, then output bi.

Otherwise, throw it away.

In NumPy or R notation, this is simply b[a > 0].

Examples in Python and RFor example, in Python >>> import numpy as np >>> a = np.

array([1,0,1,1,0,0,0,1]) >>> b = np.

array([1,0,1,0,0,1,1,0]) >>> b[a > 0] array([1, 1, 0, 0]) Here’s the same example in R.

> a = c(1,0,1,1,0,0,0,1) > b = c(1,0,1,0,0,1,1,0) > b[a>0] [1] 1 1 0 0 Linear Feedback Shift RegistersCoppersmith and colleagues were concerned specifically with linear feedback shift register (LFSR) streams.

These are efficient sources of pseudorandom bits because they lend themselves to hardware implementation or low-level software implementation.

But the problem is that linear feedback shift registers are linear.

They have an algebraic structure that enables simple cryptographic attacks.

But the procedure above is nonlinear and so less vulnerable to attack.

A potential problem is that the shrinking generator outputs bits at an irregular rate, and a timing attack might reveal something about the sampling sequence a unless some sort of buffering conceals this.

Other stream sourcesWhile the shrinking generator was developed in the context of LFSRs, it seems like it could be used to combine any two PRNGs in hopes that the combination is better than the components.

At a minimum, it doesn’t seem it should make things worse [2].

There is a problem of efficiency, however, because on average the shrinking generator has to generate 4n bits to output n bits.

For very efficient generators like LFSRs this isn’t a problem, but it could be a problem for other generators.

Self-shrinking generatorsA variation on the shrinking generator is the self-shrinking generator.

The idea is to use half the bits of a stream to sample the other half.

Specifically, look at pairs of bits, and if the first bit is a 1, return the second bit.

If the first bit is a 0, return nothing.

Related postsGoogle Adiantum and ChaChaEntropy extractor from μRNG[1] Coppersmith, D.

Krawczyk, H.

Mansour, Y.

The Shrinking Generator.

Advances in Cryptology — CRYPTO ’93.

Lecture Notes in Computer Scienc, vol.

773, pp.

22–39.

Springer, Berlin.

[2] If a and b are good sources of random bits, it seems b sampled by a should be at least as good.

In fact, if a is poor quality but b is good quality, b sampled by a should still be good.

However, the reverse could be a problem.

If b is biased, say it outputs more 1s than 0s, then if a is a quality sample, that sample will be biased in favor of 1s as well.

.

. More details

Leave a Reply