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: