Blum Blum Shub vs. AES-CTR or other CSPRNGs Following on from D.W.'s comments on a previous question, what properties does Blum Blum Shub have that make it better / worse than other PRNGs? Are there significant implementation difficulties or security issues with BBS?
Blum-Blum-Shub is a stream cipher: given a short key, it produces an effectively unlimited-length stream of pseudorandom bits.  Other well-known examples of stream ciphers include AES-CTR and RC4.

Blum-Blum-Shub gets mentioned a lot by non-expert cryptographers.  I suspect this is because it comes with a "proof" of security, which sounds like a wonderful thing to have.  It might not hurt that BBS was mentioned in Applied Cryptography, and some developers may have walked away from that thinking that BBS is the bee's knees.

However, I personally don't recommend BBS.  The proof of security turns out to be highly misleading, and it comes with some fine print that makes the proof close to useless in practice.  You are probably better off using AES-CTR (AES in counter mode).  AES has been carefully vetted and is widely trusted.  AES-CTR should provide excellent security -- while also providing excellent performance.

BBS has two problems:


BBS is very slow -- excruciatingly slow.
Also, the existence of the "proof of security" is highly misleading and usually misinterpreted.  Practical folks almost always draw the wrong conclusions from the "proof of security".


These two problems are linked.   The standard proof of security says that if you choose a modulus N that is large enough, then no attacker will be able to efficiently break BBS.  However, the standard proof does not say how large N has to be, to achieve any desired level of security.  More recently, researchers have worked out how large a modulus you need, and (here comes the fine print:) it turns out N needs to be ridiculously large to have any decent level of provable security.  I'll summarize some of their results below:

Result 1. Suppose you use BBS with a 768-bit modulus.  You've read that 768 bits is enough to make factoring infeasible, so this sounds peachy.  You've read that it is safe to extract O(lg n) bits in each iteration; here n = 768, and lg n = 9.58, so you decide to extract 9 bits in each iteration.  You use it to generate a pseudorandom stream of 107 bits (about 1MB of pseudorandom data).  How much security do you get?  Answer: the security proof guarantees security against any adversary that uses at most 2-264 steps of computation.  Yes, this is an utterly ridiculous and useless statement!  To put it in plain English, the security proof guarantees absolutely nothing useful at all.

The lessons is: With natural-sized parameters, there is no guarantee that your use of BBS will be secure in practice.  The "proof of security" is useless for ordinary-sized parameters.

Result 2. Suppose you learn about this result, and decide to use a longer modulus.  Suppose you decide to use BBS with a 6800-bit modulus, and extract 5 bits on each iteration.  Suppose you extract no more than one million pseudorandom bits from the BBS generator.  Then, there is a proof showing that it will take at least 2100 steps of computation to break BBS (given plausible assumptions).  This means you should have a reasonable level of security.  My estimate is that, on my machine, producing one million bits (128KB) of output with BBS would take about 5-10 minutes, whereas with AES-CTR it would take less than a second. 

In other words, to achieve even a mild degree of security in practice, BBS needs an enormous modulus -- far long than anything you'd use with RSA.  This large modulus makes BBS very slow.  It's far slower than AES -- and probably far weaker, too, as AES is believed to be safe for use even if you extract far more than one million bits of pseudorandom output.

Result 3. Here's another way to think about it.  A third researcher worked out the ratio in level of security between BBS and factoring.  He found that it's possible that there could be an attack that breaks BBS and is 1054 n3 times faster than any algorithm for factoring algorithm (for factoring the BBS modulus).  For instance, for a 1024-bit modulus (n = 1024), someone might be able to break BBS 1063 times as fast as they can factor.  Since we know you can factor a 1024-bit modulus with fewer than 1024 steps of computation, this guarantee about 1024-bit BBS is utterly useless: it is no guarantee of security at all.

As another example, for a 8192-bit modulus, the result says that there might be some clever algorithm for breaking BBS up to 1065 times faster than we know how to factor a 8192-bit modulus.  This is a huge ratio.  It says that BBS might be far easier to break than RSA is.  It means our proof of security for BBS is meaningful only if we use an enormous modulus, and only if we believe that factoring a modulus of that size is stupendously hard.  If we're willing to assume that factoring such a modulus is stupendously hard, we can deduce that breaking BBS is pretty hard; but because we need to use such an enormous modulus, the resulting BBS scheme will be enormously slow.

For more details, see the following research papers:


Another Look at Tightness, Sanjit Chatterjee, Alfred Menezes, and Palash Sarkar, Selected Areas in Cryptography 2011.
Concrete Security of the Blum-Blum-Shub Pseudorandom Generator, Andrey Sidorenko and Berry Schoenmakers, Cryptography and Coding 2005.
and, this sci.crypt post from Dan Bernstein: Re: BBS PRNG strength recommendation parameters




Footnote on terminology: Theorists sometimes call stream ciphers by the name "pseudorandom generators" (PRGs).  Confusingly, this is not the same as a "pseudorandom number generator" (PRNG).

The term "pseudorandom number generator" (PRNG) is not always used consistently.  There are two possible meanings.  Some folks use it as a synonym for stream cipher.  Personally, I prefer to reserve PRNG for a scheme that is used to generate pseudorandom numbers, using no explicit input (but somehow gathering entropy from the environment).  With my preferred terminology, you use a PRNG to generate a short cryptographic key; then you use a stream cipher (a PRG) to stretch the short crypto key into a very long keystream of pseudorandom bits.  But others use the term differently.

Given this opportunity for confusion, if the meaning of the term is not clear from context, it may be best to avoid the term PRNG.