Skip to content

@0xabad1dea /dual-ec-but-biased.md
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Dual EC, The Saga Continues: BUT MAYBE I'M BIASED

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?

@neheb

My take:

The guy seems like a shill for the NSA. I've read some of his other postings on the CFRG mailing list and it's weird that he defends not only DUAL_EC_DRBG but also Dragonfly, the totally unproven and problematic PAKE algorithm.

Given that he works for Certicom(as far as I can tell) and that Certicom has a close relationship to the USG(as far as I can tell) none of this should be too surprising.

An NSA guy also heads the CFRG. Gotta get my popcorn ready to watch what will happen with the CFRG.

@Thue

There are two things that make the backdoor work

1) Chosen Q
2) Too little truncation in the output function.

The patent application specifically mentions that both are necessary. And in "The Many Flaws of Dual_EC_DRBG", Matthew Green specifically writes:

Unlike those previous EC PRGs which output anywhere from 2/3 to half of the bits from the x-coordinate, Dual-EC outputs nearly the entire thing.

Brown's proof paper also says that the output function needs to truncate more bits to make the proof work, and uses it in his proof, but forgets to mention it in his glowing conclusion. Along with forgetting to mention the potential backdoor he so clearly knew about. And the Dual_EC_DRBG he proves is secure is not the Dual_EC_DRBG mentioned in the standard, because the too small truncation is fixed in the standard.

The patent says:

[0041] Another alternative method for preventing a key escrow attack on the output of an ECRNG, shown in Figures 3 and 4 is to add a truncation function to ECRNG to truncate the ECRNG output to approximately half the length of a compressed elliptic curve point. Preferably, this operation is done in addition to the preferred method of Figure 1 and 2, however, it will be appreciated that it may be performed as a primary measure for preventing a key escrow attack. The benefit of truncation is that the list of R values associated with a single ECRNG output r is typically infeasible to search. For example, for a 160-bit elliptic curve group, the number of potential points R in the list is about 280, and searching the list would be about as hard as solving the discrete logarithm problem. The cost of this method is that the ECRNG is made half as efficient, because the output length is effectively halved.

Why did the committee not do this in addition to adding a method to randomly choose P,Q, and leaving the backdoored P,Q in there by default? That would have stopped the specific backdoor attach cold, but according to the patent and Green's analysis.

@Thue

I guess that in principle it’s not wrong to use Dual EC with correctly random values

Yes, it is wrong. Kristian Gjøsteen showed that it is insecure because it truncates too few bits in the output function. Brown's proof also assumes more its are truncated, but the Dual_EC_DRBG standard does not allow that.

@Thue

What if I told you that Dan Brown has a patent on backdooring Dual EC? Well then I wouldn’t be lying to you.

Well, I think you would actually be lying to me :). The google page lists the document ad "Publication type: Application". I think it would say "Publication type: Grant" if the patent had actually been granted.

But Certicom certainly have other ECC patents (they basically invented ECC), which I would not be surprised to learn do cover Dual_EC_DRBG. So there perhaps is a conflict of interest anyway.

@Thue

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

@seandougall

@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).

@Thue

@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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.