Dual EC DRBG
Certicom's patent applications regarding Dual EC key escrow
The Canadian company Certicom (now part of Blackberry) has patents in multiple countries on
The patent filing history also shows that
This page presents the details.
Publicity and the avoidance thereof
In early 2005, Certicom began trying to patent both Dual EC exploitation and Dual EC escrow avoidance. The patent applications list Daniel R. L. Brown and Scott A. Vanstone as "inventors".
Certicom never drew public attention to these patenting efforts, or to the possibility of a back door in Dual EC. The main U.S. patent application was broadly publicized by Tanja Lange in a talk with Daniel J. Bernstein and Nadia Heninger at 30C3 on 28 December 2013, in a followup blog post by Matthew D. Green the same day, and in a followup blog post by Melissa Elliott the same day.
Certicom received United States patent 8,396,213 on Dual EC escrow avoidance in March 2013. The patent application had included a claim regarding Dual EC exploitation, but this claim does not appear in the issued patent. This discrepancy led observers to ask why the claim was gone, and to speculate that Certicom had voluntarily removed the claim for some reason or that the United States patent office (USPTO) had forced Certicom to remove the claim on the basis of prior art.
The actual story is that the USPTO decided that Certicom had submitted two inventions in a single application: one for Dual EC escrow avoidance and one for Dual EC exploitation. In such situations the applicant is required to limit the application to one of the inventions, and can continue pursuing the second invention only by promptly filing a second application and paying a separate fee. The second application (called a "continuation"/"division") can be pursued in parallel to the first application, or can be pursued serially. Certicom chose the serial approach: canceling some of the claims in the first application, and then filing a second application with other claims once the first application was allowed by the USPTO. See below for more details.
Sources regarding the US patent
The December 2013 news was based primarily on the following documents:
However, this page is based on a wealth of further information publicly available from the Patent Application Information Retrieval (PAIR) site of the USPTO:
The above applications will be referred to for the remainder of the document as: the 982 Provisional, the 814 Patent Application, and 533 Patent Application.
To find the 814 Application data on PAIR, search for publication number US 20070189527. "Continuity Data" links to the other applications; "Transaction History" is a timeline; "Image File Wrapper" contains the documents mirrored above.
We acknowledge support in the patent investigation and interpretation for the US patent by an expert who chose to remain anonymous.
The provisional patent application
The provisional patent application does not claim to have invented Dual EC per se, and does not clarify who invented Dual EC. It cites ANSI X9.82 [60644982.pdf, page 2, paragraph 0003]:
The American National Standards Institute (ANSI) has set up an Accredited Standards Committee (ASC) X9 for the financial services industry, which is preparing a [sic] American National Standard (ANS) X9.82 for cryptographic random number generation (RNG). One of the RNG methods in the draft of X9.82, called Dual_EC_DRBG, uses elliptic curve cryptography (ECC) for its security. Dual_EC_DRBG will hereinafter be referred to as elliptic curve random number generation (ECRNG).
The provisional patent application describes the Dual EC back door [60644982.pdf, page 4, paragraph 0010]:
The applicant has recognised that anybody who knows an integer d such that Q = dP ... can compute U from R as U = eR. ... The truncation function means that the truncated bits of R would have to be guessed. ... The updated state is u = z(U), so it can be determined from the correct value of R. Therefore knowledge of r and e allows one to determine the next state to within a number of possibilities somewhere between 26 and 219. This uncertainty will invariably be eliminated once another output is observed, whether directly or indirectly through a one-way function. ... It has therefore been identified by the applicant that this method potentially possesses a trapdoor, whereby standardizers or implementers of the algorithm may possess a piece of information with which they can use a single output and an instantiation of the RNG to determine all future states and output of the RNG, thereby completely compromising its security.
The provisional patent application also describes ideas of how to make random numbers available to "trusted law enforcement agents" or other "escrow administrators". For example [60644982.pdf, page 9, paragraph 0039]:
In order for the escrow key to function with full effectiveness, the escrow administrator ... needs direct access to an ECRNG output value r that was generated before the ECRNG output value ... which is to be recovered. It is not sufficient to have indirect access to r via a one-way function or an encryption algorithm. ... A more seamless method may be applied for cryptographic applications. For example, in the SSL and TLS protocols, which are used for securing web (HTTP) traffic, a client and server perform a handshake in which their first actions are to exchange random values sent in the clear.
The provisional patent application also describes various ways to avoid the back door, such as [60644982.pdf, page 7, paragraphs 0028 and 0031] choosing P and Q as hashes of random seeds in a way similar to ANSI X9.62:
An arbitrary string is selected ... the hash is then converted to a field element ... regarded as the x-coordinate of Q ... To effectively prevent the existence of escrow keys, a verifiable Q should be accompanied with either a verifiable P or a pre-established P.
It is clear that Brown and Vanstone were aware of the Dual EC back door, and ways to exploit it, by January 2005 when the provisional patent application was filed. Technically, the applications were filed by Certicom, but both Brown and Vanstone signed a "Declaration and Power of Attorney For Patent Application" document in April 2006 [11336814.pdf, pages 39–41] declaring that they were the "inventors" and had reviewed the 23 January 2006 patent application, which includes a priority claim to the January 2005 provisional. Further, the 23 January 2006 patent application contains all of the quotes given above, except that instead of "verifiable" it used the phrase "verifiably random".
The current rules for US secrecy orders on patent applications are stated at http://www.uspto.gov/web/offices/pac/mpep/s115.html on the USPTO website:
[Applications] are screened upon receipt in the USPTO for subject matter that, if disclosed, might impact the national security. Such applications are referred to the appropriate agencies for consideration of restrictions on disclosure of the subject matter as provided for in 35 U.S.C. 181.
The USPTO referred Certicom's provisional patent application to the Department of Defense for review. Eventually DoD returned a "Department of Defense: Access acknowledgment/Secrecy order recommendation for patent application" form [60644982.pdf, page 19] recommending against a secrecy order:
According to the USPTO, the referral letter was mailed on 7 April 2005, and the response was entered into PAIR on 27 February 2006. The response itself states that the referral was on 7 March 2005 and that the response was forwarded on 7 February 2006.
The 814 Application was referred to DoD on 13 March 2006. The Navy responded "No comments" on 15 March 2006. NSA recommended against a secrecy order [11336814.pdf page 48] on 16 April 2007.
Provisional patent applications cannot directly result in a U.S. patent. They serve as a placeholder, or proof that an inventor has possession of an invention. They can be used to secure an earlier priority date for a full patent application.
As is common for most patent applications, the USPTO began its examination of the 814 Application by rejecting all claims. The USPTO engaged in several iterations [see generally 11336814.pdf] of rejections based on "prior art" and for wording reasons (e.g., in re Bilski). Certicom responded with several modifications of the patent text (particularly in the claims), disputes of the USPTO's assessment of the prior art, and submissions of additional literature. Our review of the cited literature did not find any previous literature on the Dual EC back door or any clues about who designed Dual EC, despite such helpful entries as a "foreign reference" to a Canadian patent application [11336814.pdf pages 118ff] for "Fuel cell having improved condensation and reaction product management capabilities".
On 22 March 2010 [11336814.pdf pages 155ff] the USPTO informed Certicom that they needed to fork the patent application to cover the following two topics separately:
I. Claims 1-12, 13-14, 15-18, 20-21 and 22-29 are drawn to a method for generating an elliptic curve random number, classified in class 380 [cryptography], and subclass 44 ["a detail of a predetermined digital sequence signal generator"].
Certicom was then required to choose one of these topics and restrict the application to that topic, while being free to file a new "continuation/division" application for the other topic. On 22 April 2010, Certicom chose the first topic [11336814.pdf page 163]. This is why the resulting patent did not contain any claims regarding Dual EC exploitation.
As mentioned above, U.S. law allows "continuation/division" applications to be split off of existing applications as long as the application being forked is still pending (i.e. the application has not been abandoned, and the patent has not been issued). On 19 February 2013, a few weeks before the first patent was issued, Certicom filed a new application. The new application was referred to DoD on 1 March 2013, and a few days later [13770533.pdf page 66] NSA recommended against a secrecy order.
Interestingly, the claims in the new application [13770533.pdf pages 51–55] do not actually cover Dual EC exploitation: they are for other mechanisms of Dual EC escrow avoidance. However, Certicom is still free to file further claims for Dual EC exploitation, retaining the original 21 January 2005 priority date. As of February 2014, the new application is under examination. It was published on 4 July 2013 as publication US 2013/0170642.
International patent applications
The 814 patent application (from 2006) was filed internationally under the Patent Cooperation Treaty (PCT). The international publication number is WO2006/076804. This filing alone does not lead to national patents: the applicant needs to request examination in the designated countries (and pay the applicable fees). Searching for WO2006076804 on http://patentscope.wipo.int shows applications filed in Canada, Europe, and Japan:
The PCT stipulates (with certain exceptions) that international patent applications are published 18 months after the priority date. WIPO published the patent application on 27 July 2006 in full length, see Espacenet page or local copy. This means that a clear explanation of the back door and its (ab-)use was publicly available as of July 2006.
Authors of this "Certicom's patent applications regarding Dual EC key escrow" page (alphabetical order)
Last modified: 2015.07.29