Elliptic curve random number generation

Abstract

The existence of this patent does not mean that Brown and Vanstone were responsible for Dual EC. In fact, the generator appears to be an NSA invention, and may date back to the early 2000s. What this patent demonstrates is that some members of the ANSI committee, of which RSA was also a member, had reason to at least suspect that Dual EC could be used to create a wiretapping backdoor. (Update: John Kelsey confirms this.)

"The BlackBerry Algorithm Library for Secure Work Space provides a suite of cryptographic services utilized by the BlackBerry Cryptographic Library for the BlackBerry Secure Work Space (BBSWS). BBSWS provides the secure operation and management of iOS and Android devices when used in conjunction with BlackBerry® mobile device management solutions."

"The BlackBerry Cryptographic Algorithm Library is a suite of cryptographic algorithms that provides advanced cryptographic functionality to systems running BlackBerry 10 OS and components of BlackBerry Enterprise Service 10."

"The BlackBerry Tablet Cryptographic Library is the software module that provides advanced cryptographic functionality to BlackBerry Tablets."

Other companies that have Dual EC DRBG in their products are Microsoft, RSA, Cisco, Juniper Networks, McAfee, Symantec, Samsung, Lancope, SafeLogic, GE Healthcare, Thales eSecurity, Panzura, Catbird Networks, ARX, Kony, CoCo Communications, Riverbed Technology, OpenSSL Foundation, Certicom, and Mocana.





Meet Certicom , a subsidiary of Blackberry Ltd, who provides the core technology for the National Security Agency (NSA) Suite B standard for secure government communications. Certicom holds 350 patents, many of which cover key aspects of Elliptic Curve Cryptography (ECC) including this one An elliptic curve random number generator avoids escrow keys by choosing a point Q on the elliptic curve as verifiably random. An arbitrary string is chosen and a hash of that string computed. The hash is then converted to a field element of the desired field, the field element regarded as the x-coordinate of a point Q on the elliptic curve and the x-coordinate is tested for validity on the desired elliptic curve. If valid, the x-coordinate is decompressed to the point Q, wherein the choice of which is the two points is also derived from the hash value. 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.Certicom was acquired by Research In Motion (now known as Blackberry Ltd) in March 2009 but it has been in business since 1985. The patent authors are two Certicom employees Daniel Brown and Scott A. Vanstone who are also members of the ANSI X9.82 standardization committee. Matthew Green, a cryptography professor at Johns Hopkins, wrote a blog post describing Dual EC DRBG's history with Brown and Vanstone, ANSI and the NSA on December 28, 2013 To date, Blackberry has not made a public announcement about its use of Dual EC DRBG but here are the Blackberry products that use it according to NIST