Re: [dsfjdssdfsd] provability & Dual_EC ... [was Blum-Blum-Shub ambiguity in 4086 ...]

[Dan Brown <[e-mail]>]

Hi Jon,

Thanks for forwarding your interesting email here.

You raise the provability issue about BBS (which is different from the two issues about BBS that I previously raised, which were some attacks), and also extend it to Dual_EC, and perhaps any "public-key" DRBG.

Specifically, you say that no public-key DRBG/PRNG can be proved secure. By contrast, BBS claim a security proof (but I have not reviewed the BBS proof at all).  Gjosteen and I claim a security proof CRYPTO 2007 for Dual_EC.  Therefore, it would be interesting if we could find some common ground.  To that end, I've taken some time to write a reactionary missive that I think addresses your concerns.

Firstly, the Dual_EC proof is only about its quality as a DRBG, PRNG, or PRG.  Specifically, any PRG, including HMAC_DRBG, CTR_DRBG, starts with an initially random fixed length secret seed, maintains a state, and outputs a long stream, with the aim to provide some measure of indistinguishability for the existing outputs even permitting the adversary to access the latest current state.  Our claims ignored the threat of state compromise recovery (aka prediction resistance).  As usual, a security proof, like any proof, has some hypotheses, and its conclusions are only as a strong as its hypotheses.  Also, it is implied by our CRYPTO 2007 paper, that what's required to be initially short secret seed is not only the conventional running state s, but also trapdoor-component of the state log_P(Q).  To force log_P(Q) to be random, one can just choose P and Q to be random.  To do that, choose them yourself, derived from the same entropy source you needed for the running state, or else choose them as nothing up my sleeve numbers ideally perhaps via NIST SP 800-90A alternative formulation.  These techniques help to make log_P(Q) known to nobody at all. If log_P(Q) has been chosen by (or for) you, by some authority, then the Dual_EC, according to the proof, seems secure against everybody but those who know both the running secret state and the value of log_P(Q).

Secondly, you also critique of Dual_EC and BBS that the p's and q's themselves need a DRBG to be generated.  But then so does any DRBG, once one insists on uniform keys (like conventional security assmuptions for HMAC and AES-CTR usually do).  That's what entropy conditioners can help resolve, transitioning from biased raw entropy, to something more like the keys that conventional crypto algorithms usually expect.  Also, a variable output-length DRBG is not needed either, because the input states to DRBG are fixed length (with the exceptional of continuously reseeding DRBG).   Maybe it's a greater nuisance to generate the public-key DRBG seeds, but I don't see it as some essential obstacle.

That all said, I disagree {with /and perhaps even if} the conventional wisdom {that / is} the public-key PRNGs are more secure, by some kind of default.  Security should be measured by firstly (a) what attacks are known, and by secondly (b) what the valid proofs claim and assume.  It's still on my to-do list to review the security proof for HMAC_DRBG, and see what assumptions it hypothesizes. It is also my hope that the somebody will prove the security of CTR_DRBG, even if in the ideal cipher model (which may be necessary because its backtracking resistance depends on related keys, and most standard assumptions about AES don't involve related keys).  As far as I know, there's no fundamental difference in being able to prove security of schemes built from symmetric and asymmetric primitives.  The fixed version of Dual_EC (i.e. truncated to 50% of bits per point and "verifiably random" P & Q), the HMAC_DRBG and CTR_DRBG are free from any known attacks. It is also good to have security proofs to complement the lack of attacks.

I also sympathize with your general point that security proofs have the danger of dazzling and, thereby, lulling some people into passive acceptance. That's a psychological issue, and I don't have any kind of workaround for it.  I think many other people have written lots on the general topic (see Another Look ...).  I wonder how much other factors can induce similar effects: implementations, advertising, publication, ...

You rightly point out a commonality between some public-key DRBGs, namely Dual_EC and BBS, and their potential for a private key to be abused as a backdoor.  That said, some differences between BBS and Dual_EC (only the insufficiently truncated version and backdoored version) include a different in impact upon adversarial knowledge of the private-key-like "trapdoor" (portion of the effective secret state):


1.      Given also one output, Dual_EC allows computation of future states (i.e. same consequence as state reveal for any DRBG), and distinguishing of previous past output from random.

2.      Given also one running secret state, BBS allows computation of future and past states (and thus outputs).

So arguably, the weak version Dual_EC improves on BBS slightly on the narrow aspect of the backtracking resistance: only distinguishing is possible, not computation.  (To be fair, though, BBS is better on the aspect of semming to require invasive access to the internal secret state before backtracking.)  The significance of this is that (computational) backtracking resistance is helpful, perhaps needed, for forward secrecy.  Notice that there seems some growing demand for forward secrecy. This brings me back to my second issue about BBS in my original email on this thread.

Again the fully corrected version of Dual_EC does not have any known backtracking vulnerability at all, and like, HMAC_DRBG, even has a security proof (under various reasonable assumptions).   Its main disadvantages are being relatively slow, and hard-to-explain differences between the possibly-backdoored version.

Best regards,

Dan


From: dsfjdssdfsd [mailto:[e-mail]] On Behalf Of Jon Callas
Sent: Monday, March 17, 2014 12:53 PM
To: [e-mail]
Cc: Jon Callas
Subject: Re: [dsfjdssdfsd] Blum-Blum-Shub ambiguity in 4086 ...

I found my missive in question, and upon re-reading it, I think it bears repeating here.

The thread starts with
<http://www.metzdowd.com/pipermail/cryptography/2014-January/019423.html>

and the message I quote from below is
<http://www.metzdowd.com/pipermail/cryptography/2014-January/019426.html>.

The discussion started with the blog post <http://blog.0xbadc0de.be/archives/155> which purports to show how DUAL_EC_DRBG *must* have been backdoored from the start. That blog post is the antecedent of "it" in the paragraph first paragraph.

----

It's nice work on a technical level, but I think it fails at its goal, that is to be a piece of polemic -- even mischaracterizing the Ferguson/Shumow CRYPTO Rump Session talk (their last slide explicitly said they were not suggesting a back door).

Lest you think I'm saying something nice about DUAL_EC_DRBG, I'll repeat what I've said before, "Only an idiot would use it." It's slow, has biases in its output that hashes and ciphers don't, and cannot be proved secure.

Let me rewind to the first public key based DRBG/PRNG -- Blum-Blum-Shub. (DRBG is the name NIST gave to what you and I would call a PRNG, it's Deterministic Random Bit Generator. If you think of a complete design of an RNG, you want at least three major sections -- "entropy" collection, entropy pool management, and conditioned output. A DRBG is the output stage.)

Blub-Blum-Shub uses an iterated RSA-like operation to generate random bits. It was developed in 1986 and is a brilliant piece of mathematics. It was one of the very, very few bits of early crypto to have a sound theoretical basis.

Many people who haven't thought it through have sung its praises over the years, mostly because they got seduced by the sound theoretic basis. Blum-Blum-Shub has two of the three flaws that DUAL_EC_DRBG has: it's slow, and you can't prove it secure.

I'm sure you thinking, 'What do you mean, "can't be proved secure? Didn't you just say that it had a sound theoretical basis?"' Yup, and the sound theoretical basis gives you the good mathematical pseudo-randomness of the output. The slow part is pretty obvious. The inobvious part is that it can't be proven secure.

As an iterated, RSA-like operation, the core of it is two prime numbers, p and q. The security resolves down to the secrecy of the two primes.

And this leaves you with the question of how you get the primes. Well, if you generate them at run time, then you push the construction of your RNG down to the turtle below you. Your random number generator requires random p and q and you get those by using some other random number generator, one presumes.

Alternatively, you could use a fixed p and q, and then you have the *exact* flaw as DUAL_EC_DRBG -- you have a fixed private key that can be used to jimmy the thing open.

Matt Green wrote a great blog post last week at <http://blog.cryptographyengineering.com>, which you should read. I'll summarize a bit and say that Micali and Shnorr did their own public-key based PRNG which also has Step 1 being "generate large primes p and q" and they helpfully gave test P and Q. I'm not merely being ironic. As someone who implemented the AES-CTR DRBG, having test vectors is really, really nice. NIST's test vectors for that are really, really annoying and I'll complain at length to anyone who cares.

Anyway, Matt Green identifies the Micali-Shnorr generator as a precursor to DUAL_EC_DRBG in both design and having a fixed key that you use for whatever purporses, testing or compromise.

I have a couple points:

(Point 1) Any public-key based PRNG is going to have the issue that either you have a fixed key, or you have to generate a key using some other secure means. This is why I use terms as strong as "can't be proven to be secure" despite having a mathematical "sound theoretical basis."

I think there's a huge security philosophy problem here -- security proofs that are mathematical can have underlying engineering assumptions that render them insecure to the point of being silly.

I think that people get blinded by this as well, and if there's a mathematical proof they're blinded by it, if not cowed by the math and stop prodding at the engineering and operational security.

Going back to Blum-Blum-Shub, look at the Wikipedia article on it at <http://en.wikipedia.org/wiki/Blum_Blum_Shub>. There are some interesting statements there, like the first sentence of the security section:

   The generator is not appropriate for use in simulations, only for
   cryptography, because it is very slow.

That makes me splutter. As an engineer, I'd argue that slow alone makes it not suitable for cryptography. I'm tempted to argue that for simulations, speed isn't an issue, but really, if you slow things down enough, it's not suitable for anything. I also have a long-standing twitch at *any* security discussion that brings in performance. Performance is not security, and many security sins have their root cause in a performance worry, usually an artificial one.

The remainder of the section reads:

   However, there is a proof reducing its security to the
   computational difficulty of the Quadratic residuosity problem.
   Since the only known way to solve that problem requires factoring
   the modulus, the difficulty of Integer factorization is generally
   regarded as providing security. When the primes are chosen
   appropriately, and O(log log M) lower-order bits of each xn are
   output, then in the limit as M grows large, distinguishing the
   output bits from random should be at least as difficult as
   factoring M.

   If integer factorization is difficult (as is suspected) then B.B.S.
   with large M should have an output free from any nonrandom patterns
   that can be discovered with any reasonable amount of calculation.
   Thus it appears to be as secure as other encryption technologies
   tied to the factorization problem, such as RSA encryption.

This is interesting because nowhere do they address the central engineering issue -- that a fixed p,q is not secure yet a variable one requires another RNG to seed the RNG.

Also look at the section in the Handbook of Applied Cryptography on "Cryptographically secure pseudorandom bit generation":

<http://books.google.com/books?id=nSzoG72E93MC&lpg=PA185&dq=Cryptographically%20secure%20pseudorandom%20bit%20generation&pg=PA185#v=onepage>

We find an RSA-based generator there along with Micali-Shnorr and Blum-Blum-Shub and *all* of these have a recipe that starts unironically with (essentially):

1. Setup. Generate two RSA-like secret primes, p and q.

This is a blind spot that's been there forever -- two of the three flaws of DUAL_EC_DRBG have been staring us all in the face since 1986. Despite mathematical brilliance, the security of public-key based PRNGs have always been flawed with something that could be used as a back door.

(Point 2) History looks different when you look backwards than when you look forwards. Everyone has a tendency to act as if things were predetermined when we analyze the decisions of the past. We also assign intent when we have to explain a WTF. Yet the usual answer to "What were you thinking?" is "They weren't." To quote the great philosopher David Byrne, "And you might say to yourself, 'My God, what have I done?'"

The general flaws have been there forever, and in general we still don't see them. In specific, the documents on Micali-Shnorr and DUAL_EC_DRBG were up front about the flaw all along.

Would the NSA exploit such a flaw? Hell, yes. We keep seeing this from leaked documents, over and over. It's clear that they have taken the hacker philosophy that nothing is out of scope or out of bounds to heart as an operating principle. You can see it in the recent ANT toy catalog, as well as the BULLRUN statement that sent us all into a tizzy.

We have *assumed* that the BULLRUN statement that they're after damaging standards means that DUAL_EC_DRBG is backdoored. People have said it so loudly and so often that it's part of conventional wisdom now. Yet until BULLRUN, it was part of conventional wisdom that despite the speed problems, mathematics made public key PRNGs more secure.

I know that one of my personal blind spots is that I'm a contrarian. I'm also a cynic who believes that stupidity is one of the fundamental forces of the universe. So I find myself in the ironic position of defending a thing I never liked because yes, really, people *can* be that stupid. We all defer to authorities, are cowed by proofs, and lose our critical thinking skills when faced with a standard. I am reminded of Markoff Chaney from Illuminatus! as well as Poe's Purloined Letter.

If we want to look at this as a root-cause exercise, we can go back to Blum-Blum-Shub and see the kernel of the flaws and blindness of them. You can see that despite it being there from the start, we didn't *understand* it. You can see the progression through Micali-Shnorr through the ANSI X9 committee, and then on to NIST.

I'm left wondering if something can really be a backdoor if it was there all along, we just didn't grok it. Was the purloined letter hidden?

I can't help but feel that calling it a back door is just too cheap and easy and convenient. It wasn't that we were collectively stupid and snookered ourselves, it was demons and those in league with them.

This leaves the question of what they *have* been doing with that $250M, which is a good question. I lean towards private standards like those used in telecom etc. In the public world, we're good at doing it to ourselves.

     Jon