Posts
Guess Who Owns The Patent to RSA's Backdoor Algorithm? Blackberry
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.
Elliptic curve random number generation
Abstract
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.
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.)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:
- "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.
I've only found a few who have made public announcements advising their customers about Dual EC use: Cisco and SafeLogic. The OpenSSL Foundation has had many discussions about Dual EC in their own forum. Please leave a comment if you know of other advisories by the remaining companies which I've missed.
What I find most interesting is that the patent specifically says that setting max_outlen to about half the bits will disable any backdoor. Why did the members of the standard committee not do this? Or if the low max_outlen was forced though, why did the members of the standard committee not publish their disagreement? Everybody on the ANSI standard committee is deeply suspect, especially Daniel Brown and by extension Certicom.
ReplyDeleteAs at least Brown was aware at the time (see the patent), the high outlen makes Dual_EC_DRBG broken if an attacker can solve a single instance of the elliptic curve discrete log problem. In addition to the possibility that P and Q from the standard were constructed.
Appendix C of the NIST standard also contains an obviously flawed argument that a high outlen will result in better randomness. Padding the outlen with more bits in a trivial way will obviously not make something non-random acceptably random. Surely the people on the standard committee could see that the Appendix C argument was flawed?
An interesting thing is that the NIST standard does support selecting P, Q, and outlen to make Dual_EC_DRBG secure. My guess is so that Daniel Brown could publish his 2006 security proof for Dual_EC_DRBG, which assumed those changes.
Also, while using the standard's P and Q were required for FIPS validation ("shall"), the NIST standard actually allowed choosing a smaller outlen ( only"should" use outlen=max_outlen). Which would probably have invalidated the backdoor. So fx OpenSSL could have made a backdoor-free version for FIPS-validation, even though they claim otherwise (they say they had to use the provided P and Q, but ignore outlen).