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

  • Dual EC exploitation: the use of Dual EC for key escrow (i.e., for a deliberate back door) and
  • Dual EC escrow avoidance: modifying Dual EC to avoid key escrow.

The patent filing history also shows that

  • Certicom knew the Dual EC back door by 2005;
  • NSA was informed of the Dual EC back door by 2005, even if they did not know it earlier; and
  • the patent application, including examples of Dual EC exploitation, was publicly available in July 2006, just a month after SP800-90 was standardized.

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:

  • 60644982.pdf (19 pages of scans, OCRed pdf file): the 21 January 2005 provisional patent application and related documents.
  • 11336814.pdf (591 pages, mostly scans, OCRed pdf file): the 23 January 2006 patent application and related documents.
  • 13770533.pdf (68 pages, OCRed pdf file): the pending 19 February 2013 patent application and related documents. This application was published on 4 July 2013.

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

Secrecy-order review

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.

If a defense agency concludes that disclosure of the invention would be detrimental to the national security, a secrecy order is recommended to the Commissioner for Patents. The Commissioner then issues a Secrecy Order and withholds the publication of the application or the grant of a patent for such period as the national interest requires.

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:

Defense AgencyRecommendation Reviewer NameReviewer Command Date Reviewed
NSASecrecy Not RecommendedJennifer Ferragutreviewer_command02/02/2006

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.

Patent examination

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"].

II. Claims 19, 30-32, 33-36 are drawn to establishing escrow key with elliptical [sic] curve random number generator, classified in class 380, and subclass 286 ["key escrow or recovery"].

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 Canadian patent office registered the Canadian application with number CA 2594670. According to the Canadian Patents Database the "National Entry for Canada" was only on 12 July 2007, about a month before the publication of the US patent application, and the request for examination came only on 24 January 2011. According to the Canadian Help: Administrative Status Definitions page:
    For applications filed on or after October 1, 1996, the request must be made within 5 years from the filed date of the application.

    This means that the request was made at the latest possible time. The Canadian Patents Database shows that the patent was granted on 23 December 2014 as Patent 2594670.

  • The European patent office registered the application as EP 06704329 in summer 2007. The application was published in bulletin 2007/42 on 17 October 2007. The Designated contracting states were AT, BE, BG, CH, CY, CZ, DE, DK, EE, ES, FI, FR, GB, GR, HU, IE, IS, IT, LI, LT, LU, LV, MC, NL, PL, PT, RO, SE, SI, SK, TR. The filing date according to WIPO is 13 July 2007, i.e. one day after the entry date for Canada; the Espacenet page shows a fax on that date and registration of the request for 16 July 2007. The Google patent search page puts the application date on 17 October 2007 (the publication of the bulletin), with effective date 21 August 2007; amusingly, this was exactly the date of the Shumow-Ferguson presentation of the back door at the Crypto rump session.

    On 4 July 2012 the European patent office granted the patent with claims on how to avoid escrow and how to use it. The claims on escrow use are more refined than in the application; see Espacenet page or local copy. The patent was published in bulletin 2012/27; no opposition was filed before 5 April 2013. This means that the European patent was granted before the US one and with farther reaching claims. Meanwhile the patent has lapsed (because of lack of maintenance fees) in AT, BE, BG, CH, CY, CZ, DK, EE, ES, FI, GR, IE, IS, IT, LI, LT, LV, MC, PL, PT, RO, SE, SI, SK leaving DE, FR, GB, HU, LU, NL, TR. The last recorded payments are 15 November 2012 to GB, 8 January 2014 to FR, 10 January 2014 to NL, and 15 January 2014 to DE. See the Espacenet page for details and timing.

  • The Espacenet page on the international patent lists the following Japanese publications: JP2013174910 (A), JP2012073638 (A), JP2008529042 (A), and JP5147412 (B2). The B2 indicates that JP5147412 is a granted patent; the others are applications (in 2013, 2012, and 2008 respectively). A cursory inspection of the granted patent (via OCR and Google Translate) suggests a fairly close match between the JP5147412 claims and the claims in the 814 Patent Application (but only the Dual EC escrow avoidance claims, not the Dual EC exploitation claim). Further input is welcome; click on the references and then on 'download' to get the full pdf files instead of single pages.

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