Dual EC, The Saga Continues: BUT MAYBE I'M BIASED

dual-ec-but-biased.md

Dual EC, The Saga Continues: BUT MAYBE I’M BIASED

Bla bla bla this is my personal opinion bla bla bla.

Patents. Can’t live with violating them, can’t live without violating them. The entire concept of patented cryptography is a bit beyond what I have the energy to deal with right now. Whatever. We’re going in.

It didn’t click with me yesterday, reading the crypto news, that I had already quoted one Dan Brown with whom we are now concerned. No, not the one who wrote the novels. One of the other ones. I cited him in my timeline of trying to reconstruct where and when exactly Dual EC DRBG went so wrong. Specifically, the paper has a casual mention (bottom of page 7) that the proof of security relies on initialization value Q being random, because if it is not random, an adversary in-the-know can recover the prestates and everything’s downhill from there. Therefore – and I quote – it is generally preferable for Q to be chosen randomly.

Generally. It’s the sort of typical academic understatement that people condemned to read LaTeX-formatted papers just blithely accept. (I want to make something clear: I am not a cryptographer. I just hang around a lot of them. Please don’t ask me to review any mathematical proofs.) No suggestions are made as to when it’s not preferable, but whatever. Of course, Theorem 5 in the paper is also dependent on the randomness of Q to provide forward secrecy, an advertised and frankly critical feature. (The paper actually encourages the reader to skip reading Theorem 5!)

The paper ends with a recommendation to use Dual EC. That, in and of itself, is fine. If an implementor of the algorithm uses this recommendation yet misses the part about random vs. nonrandom Q then they’re not a very good implementor. So far, so good.

We’re going to jump forward and back in time a bit here. Hold on tight as we zoom forward to yesterday, December 27, 2013. Daniel Brown of Certicom (i.e. the same person who wrote the paper discussed above) submitted this letter to the Crypto Forum Research Group. The text formatting is wonky so I will reproduce it in full here.

-----Original Message----- From: Alyssa Rowan Sent: Friday, December 27, 2013 10:22 AM

---

1. Specific documented example: Dual_EC_DRBG - a backdoor that couldn't have been more obvious if you'd erected a flashing neon sign and driven a mounted parade with a marching band through it. We have no reason to expect other 'enablings' to be as obvious, of course.

1. Dual_EC_DRBG, as specified in NIST SP 800-90A and ANSI X9.82-3, allows an alternative choice of constants P and Q. As far as I know, the alternatives do not admit a known feasible backdoor. In my view, it is incorrect to imply that Dual_EC_DRBG always has a backdoor, though I admit a wording to qualify the affected cases may be awkward.

2. Many things are obvious in hindsight. I'm not sure if this was obvious.

3. The possibility of a backdoor was known quite early. Such knowledge undermines the effectiveness of any backdoor. For a backdoor to be effective, the implementer would have to be naïve or malicious.

4. A malicious implementer likely has many other means to subvert the security of the user. I.e. this threat is not so specific to Dual_EC_DRBG.

5. Either CMVP or CAVP (I forget which) insisted on the default P and Q. But the stated purpose of these validation programs, IIRC, is only to protect communication with USG/CAG, in which the user is already trusting these entities extensively. I'm not aware of any promises to protect non-USG communication in the CMVP or CAVP.

6. Modern cryptography usually likes provable security, especially in refereed conferences like CRYPTO. Well, Dual_EC_DRBG has such an assurance. Can anybody in CFRG suggest another DRBG with published security proof? I've seen a preprint proof for HMAC_DRBG, but forget if it has been refereed.

7. Note, just in case you're wondering, the proof above excludes the case of a backdoor relationship between P and Q: i.e. it applies only to the alternative choices of P and Q.

8. All considered, I don't see how the ANSI and NIST standards for Dual_EC_DRBG can be viewed as a subverted standard, per se. But maybe that's just because I'm biased or naive.

Best regards,

Dan

And a little earlier the same day:

Maybe I'm biased, but for a PRNG, I'd recommend Dual_EC_DRBG with alternative P&Q, at least on systems that can afford the extra latency, e.g. high-end user equipment, if only because of the refereed security analysis. Also, considerable attention, because of the potential backdoor, has been paid to Dual_EC_DRBG, yet no major attack since that security analysis has been uncovered.

I get the feeling this guy is married to the algorithm. Now, maybe everyone who actually regularly reads CFRG (not me) already knows offhandedly that Dan Brown is the one who wrote the proof in the first place and the reason he’s “biased” doesn’t need to be reiterated. I’m not saying there’s something wrong with the proof: it’s fine as far as I know (given the MASSIVE CAVEAT we already went over) and I guess that in principle it’s not wrong to use Dual EC with correctly random values. It’s just… why? Almost no-one used Dual EC in the first place because of the “extra latency” and we already went over elsewhere how that makes RSA’s excuses about why it was the default in BSAFE look pretty dumb.

Well, if “really likes formal proofs” is the worst thing someone can say about you, you’re probably doing okay. Case closed! … Hahaha just kidding. This year is the year that just won’t stop giving me reasons to cry right up until the deadline.

What if I told you that Dan Brown has a patent on backdooring Dual EC?

Well then I wouldn’t be lying to you. Welcome to priority date JANUARY 2005, everyone.

“An elliptic curve random number generator avoids escrow keys by choosing a point Q on the elliptic curve as verifiably random.”

“Intentional use of escrow keys can provide for back up functionality. The relationship between P and Q is used as an escrow key and stored by for a security domain. The administrator logs the output of the generator to reconstruct the random number with the escrow key.”

Wow! You literally patented using Dual EC as a backdoor! And you come to us in 2013 with apologetics for the use of the algorithm in light of, surprise, a real-world backdoor – and we should keep using this algorithm you happen to have a patent on! You shoved the backdoorability into an understated aside in the proof!

And I’m not fluent in legalese but I think this patent also covers using a verifiably randomly generated Q! Wow! Wow! Wow!

Many things are obvious in hindsight. I guess this is one of them. This patent apparently slipped by everyone’s radars until the renewed interest late this year in the Dual EC backdoor. It was conveyed to me by Matthew D. Green via Tanja Lange ultimately via @nymble.

I don’t see how any of this is okay. You can’t patent backdooring an algorithm then act surprised when it comes out that people backdoored it and go on about how the standards aren’t really subverted because you can use different non-backdoored values (possibly in a way you have a patent on). But maybe that’s just because I’m biased or naive.

I got a lot of feedback that I don’t use enough “real swear words,” whatever that means. Are these real enough?

Why didn't you mention that Dan Brown was in Matthew Green's list of people in the ANSI group who created the standard?

@Thue: There is US8396213, though it's assigned to Certicom and only lists Brown as an inventor, so it's still a slight stretching of the truth. It's not identical, but uses a lot of the same language (including going so far as to explicitly name wiretapping by "trusted law enforcement agents" as a possible application).

@seandougall Yes, it seems to be essentially (though perhaps not legally) the same patent. 0xabad1dea should just have linked to that instead of the other application.