3
$\begingroup$

I've read that Blum Blum Shub is a CSPRNG, defined by x_n+1 = x_n^2 mod M. I didn't understand that, and couldn't find any sources on how big should M be.

Are 32 bits enough? 64 bits? Or are even more bits required?

$\endgroup$
4
  • $\begingroup$ Is this really a CSPRNG, even for arbitrary choices of x_0 and M ? $\endgroup$ Feb 19 at 16:01
  • $\begingroup$ According to what I found it's a CSPRNG for M a semiprime with both of its divisors congruent to 3 (mod 4), and safe primes, and for all values of x_0 which aren't 0 or 1 $\endgroup$ Feb 19 at 17:03
  • $\begingroup$ Did you look at Wikipedia and see that it is related to factoring as RSA so one needs to choose the primes according to current factoring records or better see at keylenght.com $\endgroup$
    – kelalaka
    Feb 19 at 17:25
  • 1
    $\begingroup$ @MikeOunsworth crypto.stackexchange.com/q/3454/18298 $\endgroup$
    – kelalaka
    Feb 20 at 9:53
3
$\begingroup$

The usual definition for the Blum-Blum-Shub (BBS) generator goes as follows:

Let $N$ be a Blum-Integer of unknown factorization. Let $j$ be the "extraction rate". Let $x_0$ be a uniformly random non-negative integer smaller than $N$. Define $x_{i+1}=x_{i}^2\bmod N$. For a request of $M=jk$ random bits, compute all $x_i$ up until at least $x_k$ and concatenate the $j$ least significant bits of each of those values as the random output.

The classic, original BBS construction used an extraction rate of 1. Later analysis (PDF) suggested that $j$ can safely be of order $O(\log\log N)$. Follow-up concrete analysis (PDF) suggests the following bound (Theorem 3):

The BBS Generator is $(T_A,\varepsilon)$-secure if $$T_A\leq \frac{L(n)}{35\delta^{-2}n\log_2 n}-2^{2j+9}n\delta^{-4}$$ where $\delta=(2^j-1)^{-1}M^{-1}\varepsilon$, n being the bitlength of $N$, $L(n)$ being the effort to factor $N$, and $(T_A,\varepsilon)$-secure meaning that an adversary can distinguish the output from random with effort $T_A$ and success probability $\varepsilon$.

Now let's pick $n=3072$ for fun for which the standard estimate is $L(n)\approx 2^{128}$ work effort. Let's also pick $j=4$ and $k=32$ extracting 4 bit from each squaring and wanting 128 bit. Let's also suppose we want $\varepsilon=2^{-1}$ success probability for the adversary. This gives us $\delta=(2^{1}\cdot 31\cdot 128)^{-1}\approx 2^{-13}$. This in turn gives us $2^{2\cdot 4+9}\cdot n\cdot 2^{52}\approx 2^{79}$ and $\frac{2^{128}}{35\cdot 2^{26}\cdot n\cdot \log_2 n}\approx 2^{81}$. Therefore an adversary in this scenario requires about $2^{81}$ work to break this BBS generator with success probability $1/2$.

Using the above, you can also try and estimate other parameter values, but I guess you already noticed that for BBS to be secure you either need rather large moduli or extract at a very slow rate and / or only extract a few bits from a seed. In general, you're better off using a generator like AES-CTR DRBG.

$\endgroup$
1
  • $\begingroup$ I'll probably try to extract the explicit formula for $\varepsilon$ later as the current formulation is ... rather annoying to work with. $\endgroup$
    – SEJPM
    Feb 20 at 10:44
2
$\begingroup$

I only found this:

n sollte hinreichend groß sein; für kryptografische Anwendung mindestens etwa 200 Dezimalstellen. (German Wikipedia)

which translated means as much as

n should be sufficiently large; for cryptographic application at least about 200 decimal digits.

This was added in 15th September 2008 before that it has been 100 digits.

So I would assume that it should be at minimum 665 bits. And since the last update is more then 10 years old for sure more today.

$\endgroup$
4
  • $\begingroup$ Do you know why it has to be that large? $\endgroup$
    – Command Master
    Feb 19 at 14:23
  • $\begingroup$ How do you arrive at 665 bits? I would think 200 decimal digits = 200 bytes = 1600 bits? $\endgroup$
    – gowenfawr
    Feb 19 at 14:38
  • $\begingroup$ @gowenfawr log2(10^200) is 664.38..., so I think 665 bits is about the same $\endgroup$
    – Command Master
    Feb 19 at 14:39
  • $\begingroup$ > Do you know why it has to be that large? No sorry $\endgroup$ Feb 19 at 15:34

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.