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?

-

migrated from security.stackexchange.comAug 4 '12 at 21:43

This question came from our site for Information security professionals.

Isnt it because Blum Blum Shub to crack takes integer factorization, which is cryptographically safe as in RSA. If the number is very large, this is considered to be very secure, e.g. 4096 bytes is a complete over-kill and 2048 is currently in use, so by generating very big random number, which is reversible only via integer factorization, is considered to be secure because of the amount of the best known search method required to do so - en.wikipedia.org/wiki/Integer_factorization_records –  Andrew Smith Aug 3 '12 at 19:38
@AndrewSmith, not quite! That's a popular misconception. The security of BBS is related to the hardness of factorization. However, as I explain in my answer, there is no guarantee whatsoever that BBS with a 2048-bit modulus offers any security at all. (I think the same is true even for a 4096-bit modulus.) I know this sounds like it contradicts everything you've read about BBS, but it's actually not a contradiction: the proof of security for BBS comes with some fine print that almost never gets mentioned, and which makes the proof far less useful than most people realize. –  D.W. Aug 3 '12 at 23:22
(cont.) As I explain in my answer, for BBS to be provably secure, you need a really big modulus -- far larger than anything you would ordinarily use with RSA. If you're using BBS with a 2048-bit modulus, you're using something that has no proof of security (using BBS this way renders the security warranty null and void; the proof is no longer applicable), so you've negated the only possible benefit of BBS. If you use BBS with a much larger modulus, the resulting thing is dog-slow. BBS is a nifty theoretical construct, but of negligible relevance to practical crypto-engineering. –  D.W. Aug 3 '12 at 23:31
I think that generating random key externally properly, and installing it on a machine, with the persistence for the block cipher in cbc would be a very nice thing to have, assuming it's working OK with persistence, because any loss of the previous block would cause repeat. –  Andrew Smith Aug 4 '12 at 11:18
Like this: en.wikipedia.org/wiki/… –  Andrew Smith Aug 4 '12 at 11:24

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:

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.

-
Absolutely wonderful answer. I had no idea about the caveats in its security proof - I'm now rather surprised that BBS gets mentioned as a functional CPSRNG at all! –  Polynomial Aug 4 '12 at 8:16
Can a no-seed PRNG have any cryptographic security at all? If not, what use-cases are there for the term? –  Paŭlo Ebermann Oct 22 '12 at 19:35
@PaŭloEbermann, perhaps my wording was crummy. Sorry about that. I was referring to a scheme that gathers imperfect entropy from multiple sources and uses them to generate crypto-quality pseudorandom bits. Think of /dev/urandom or Fortuna or Yarrow or that sort of mechanism. Dealing with non-uniformly distributed inputs of uncertain entropy is a major challenge. In contrast, a PRG is a scheme that takes a perfect seed (uniformly random distributed), which is easier (a stream cipher suffices). –  D.W. Oct 23 '12 at 2:41
Ah, okay.I edited your sentence to hopefully make this clearer, feel free to revert or edit again. –  Paŭlo Ebermann Oct 23 '12 at 16:55
Perfect, thank you @PaŭloEbermann! I appreciate it. –  D.W. Oct 23 '12 at 17:35

BBS has a so-called "security proof" which shows it to be secure as long as the quadratic residuosity problem is hard; the latter is believed to be as hard as integer factorization, which is itself believed to be a hard to solve problem.

Gee, the description of the quadratic residuosity problem on Wikipedia really lacks clarity. In simpler words, the problem is: given a big integer N which is the product of two primes p and q of similar sizes, such that both p and q are equal to 3 modulo 4, and a value y modulo N, decide whether y is a square (i.e. whether there exists an integer x such that x2 = y modulo N). About N/4 integers modulo N are such squares. Among the 3N/4 non-squares, N/2 are easily determined not to be squares with the Jacobi symbol. The remaining N/4 are called pseudosquares: these are the values which are not squares, but for which the Jacobi symbol still returns 1. The QRP is about distinguishing true squares from pseudosquares.

The best known method for solving the QRP is to factor N (once N is factored, i.e. p and q are revealed, one can work modulo p and modulo q, and deciding whether a value is a square modulo a prime is easy). The best known algorithms for factoring big integers are still prohibitively expensive when N is big enough and was generated with random p and q (current record is 768 bits).

Note my use of the term "believed": the security of BBS is only proven up to the QRP. There is no proof that the QRP is as hard as factorization. And there is no proof either that factorization is really hard (but 2500+ years of research have not come up with an efficient factorization method, so it must not be trivial). Thus, the security status of BBS is somewhat similar to that of RSA. Use a 2048-bit modulus N, and you will be fine.

Other PRNG (e.g. AES in CTR mode, or the stream ciphers from eSTREAM) do not have such a nifty security proof. They rely on craftsmanship: they are believed secure because smart people have tried to break them and did not succeed. This is good enough as long as the said people were trained cryptographers, there were at least several dozens of them, they spent several months or years working on the algorithm, and they did not find the slightest dent in the cover of the algorithm. That's the case for AES or the eSTREAM portfolio; that's not the case for homebrewed designs slapped together in a fortnight and launched into the Wild without any further ado. The best of such designs is RC4, which has a few biases (nothing critical, but academically "broken" nonetheless), and has survived analysis for so long mostly because the designer was Ron Rivest, and Ron is very smart.

Thus, a security proof, even as limited in its scope as that of BBS, is a nice thing to have, which explains why it is regularly suggested.

On the other hand, BBS is awfully slow. You might produce perhaps a dozen kilobytes per second worth of random data on a modern PC core, while any decent cryptographic PRNG would run 10000 times faster. There are many applications for which the slowness of BBS is a bottleneck.

-
"Use a 2048-bit modulus, and you will be fine." - Not quite. This is a widespread misconception. In fact, if you use a 2048-bit modulus, you've rendered the proof of security irrelevant. There is no proof that 2048-bit BBS is secure. There's no proof that the security of BBS with a 2048-bit modulus has anything to do with the security of factorization or QRP: the QRP might be hard, factoring a 2048-bit number might be hard, but breaking 2048-bit BBS could be easy, for all we know. The proof of security doesn't rule this out. See my answer for explanation why. –  D.W. Aug 3 '12 at 23:33
@D.W.: he would still be fine, though. As you show, there is very little protection to be obtained from the "security proof". But, in practice, nobody knows how to break a BBS except by factoring the modulus, and nobody knows how to factor a 2048-bit modulus with existing technology. A 2048-bit BBS is "as secure" as a 2048-bit RSA in that sense: people looked at it, nobody found a way to break it. I have no qualms in recommending 2048-bit RSA, which has no proof of security at all; even NIST does it. The same should apply to BBS. (Except that BBS is too slow to be of much use, of course.) –  Tom Leek Aug 10 '12 at 1:02
Tom, your point is well taken. Thank you for taking the time to explain. (Although, if you are operating in a regime where there is no proof of security, there is no longer any clear reason to use BBS instead of, say, AES-CTR.) –  D.W. Aug 10 '12 at 6:00