|
||
|
2 January 2014 Dual_EC_DRBG backdoor: a proof of concept
From: Jon Callas <jon[at]callas.org> Tantalising! I've no time to look (and wouldn't know an eliptic curve if it slapped me in the face). Comments? 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 If integer factorization is difficult (as is suspected) then B.B.S. with large M should have an output free from any nonrandom patterns 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": 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
-----BEGIN PGP SIGNATURE-----
|