Abstract
Dual EC is an algorithm to compute pseudorandom numbers starting from some random input. Dual EC was standardized by NIST, ANSI, and ISO among other algorithms to generate pseudorandom numbers. For a long time this algorithm was considered suspicious – the entity designing the algorithm could have easily chosen the parameters in such a way that it can predict all outputs – and on top of that it is much slower than the alternatives and the numbers it provides are more biased, i.e., not random.
The Snowden revelations, and in particular reports on Project Bullrun and the SIGINT Enabling Project, have indicated that Dual EC was part of a systematic effort by NSA to subvert standards.
This paper traces the history of Dual EC including some suspicious changes to the standard, explains how the back door works in real-life applications, and explores the standardization and patent ecosystem in which the standardized back door stayed under the radar.
This work was supported by the European Commission through the ICT program under contract INFSO-ICT-284833 (PUFFIN), by the Netherlands Organisation for Scientific Research (NWO) under grant 639.073.005, and by the U.S. National Science Foundation under grants 1018836 and 1314919. “Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.” Permanent ID of this document: d3ueael2e7c4i2s3b7a0cek0d2o3o5r4e2d. Date: 2015.08.01.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
These extra documents were obtained by journalist Jeff Larson in January 2014. We are indebted to Larson for allowing us to present this new information here.
- 2.
As above, we are indebted to Larson for tracking down this information.
- 3.
CAVS stands for NIST’s Cryptographic Algorithm Validation System. “Cryptographic algorithm validation is a prerequisite to the Cryptographic Module Validation Program (CMVP).” See http://csrc.nist.gov/groups/STM/cavp/.
References
Amann, B., Vallentin, M., Hall, S., Sommer, R.:Revisiting SSL: A large-scale study of the Internet’s mosttrusted protocol (2012). http://www.icsi.berkeley.edu/pubs/techreports/ICSI_TR-12-015.pdf
Ball, J., Borger, J., Greenwald, G.: Revealed: how US and UK spy agencies defeat internet privacy andsecurity. The Guardian, 5 September 2013. http://www.theguardian.com/world/2013/sep/05/nsa-gchq-encryption-codes-security
Barker, E.: Letter to Bruce Schneier (2007). https://github.com/matthewdgreen/nistfoia/blob/master/6.4.2014%20production/109%20-%20Nov%2028%2020d07%20Letter%20to%20Bruce%20from%20Barker%20-%20Wired%d20Commentary%20.pdf
Bernstein, D., Heninger, N., Lange, T.: The year in crypto, 2013. In: Presentation at 30th Chaos Communication Congress. https://hyperelliptic.org/tanja/vortraege/talk-30C3.pdf
Bernstein, D.J., Lange, T., Niederhagen, R.: Certicom’s patent applications regarding Dual EC key escrow (2014). https://projectbullrun.org/dual-ec/patent.html
Brown, D.R.L.: Re: Dual\(\_\)EC\(\_\)DRBG (2014). http://permalink.gmane.org/gmane.ietf.irtf.cfrg/2300
Brown, D.R.L., Vanstone, S.A.: Elliptic curve random number generation. Patent application published by WIPO (2006). http://tinyurl.com/oowkk36
Checkoway, S., Niederhagen, R., Everspaugh, A., Green, M., Lange, T., Ristenpart, T., Bernstein, D.J., Maskiewicz, J., Shacham, H., Fredrikson, M.: On the practical exploitability of Dual EC in TLS implementations. In: 23rd USENIX Security Symposium (USENIX Security 14), pp. 319–335. USENIX Association, August 2014. https://projectbullrun.org/dual-ec/documents/dualectls-20140606.pdf
George, R.: Life at both ends of the barrel: an NSA targeting retrospective, keynote talk at Infiltrateconference (2014). http://vimeo.com/97891042
Gjøsteen, K.: Comments on Dual-EC-DRBG/NIST SP 800-90, draft December 2005, 2006. http://www.math.ntnu.no/~kristiag/drafts/dual-ec-drbg-comments.pdf
Green, M.D.: Results of a recent FOIA for NIST documents related to the designof Dual EC DRBG (2015). https://github.com/matthewdgreen/nistfoia
Hoffman, P.: Additional random extension to TLS, Internet-Draft version 01, February 2010. http://tools.ietf.org/html/draft-hoffman-tls-additional-random-ext-01
Hoffman, P., Solinas, J.: Additional PRF inputs for TLS, Internet-Draft version 01, October 2009. http://tools.ietf.org/html/draft-solinas-tls-additional-prf-input-01
Joint Technical Committee ISO/IEC JTC 1, Informationtechnology, Subcommittee SC 27, IT Security techniques. US national body comments on ISO/IEC 2nd CD 18031. Attachment 10 to SC27 N3685(2003). https://projectbullrun.org/dual-ec/documents/us-comment-to-iso.pdf
Johnson, D.: Minding our Ps and Qs in Dual\(\_\)EC (2004). http://csrc.nist.gov/groups/ST/crypto-review/documents/Email_Oct
Johnson, D.: Number theoretic DRBGs (2004). http://csrc.nist.gov/groups/ST/toolkit/documents/rng/NumberTheoreticDRBG.pdf
Kelsey, J.: 800-90 and Dual EC DRBG (2013). http://csrc.nist.gov/groups/SMA/ispab/documents/minutes/2013-12/nist_cryptography_800-90.pdf
Kelsey, J.: Dual EC in X9.82 and SP 800-90 (2014). http://csrc.nist.gov/groups/ST/crypto-review/documents/dualec_in_X982_and_sp800-90.pdf
Larson, J., Perlroth, N., Shane, S.: Revealed: The NSA’s secret campaign to crack, undermine Internetsecurity. ProPublica, September 2013. https://www.propublica.org/article/the-nsas-secret-campaign-to-crack-undermine-internet-encryption
Menn, J.: Exclusive: Secret contract tied NSA and security industry pioneer. Reuters, December 2013. http://www.reuters.com/article/2013/12/20/us-usa-security-rsa-idUSBRE9BJ1C220131220
National Institute for Standards and Technology. DRBG validation list. http://csrc.nist.gov/groups/STM/cavp/documents/drbg/drbgval.html
National Institute for Standards and Technology. Internal draft of X9.82 section 9.12, 2004? https://github.com/matthewdgreen/nistfoia/blob/master/6.4.2014%20production/011%20-%209.12%20Choosing%20a%20DRBG%20Algorithm.pdf, received through FOIA
National Institute for Standards and Technology. RNG workshop and standards development (2004). http://csrc.nist.gov/groups/ST/toolkit/random_number.html#RNG%20WSD
National Institute for Standards and Technology. The NIST SP 800-90A Deterministic Random Bit Generator ValidationSystem (DRBGVS); current version from 2013, first version from 2009, 2013. http://csrc.nist.gov/groups/STM/cavp/documents/drbg/DRBGVS.pdf
National Institute for Standards and Technology. Compilation of public comments on 2005 draft of SP 800-90 (2014). http://csrc.nist.gov/groups/ST/toolkit/documents/CommentsSP800-90_2006.pdf
National Institute for Standards and Technology. NIST FOIA material released to COV: X9.82 and NIST SP800-90 process, 10 June, 2014. http://csrc.nist.gov/groups/ST/crypto-review/review_materials.html
National Institute of Standards and Technology. Special Publication 800-90: Recommendation for random numbergeneration using deterministic random bit generators, 2012. First version June 2006, second version March 2007. http://csrc.nist.gov/publications/PubsSPs.html#800-90A
nymble. Interesting patent on use of ECC random number generator for ‘escrow’. Designed as backdoor in 2005. Twitter post on 3 December, 2013. https://twitter.com/nymble/status/408023522284285952
Patent Application Information Retrieval (PAIR). Image file wrapper for provisional application 60644982 (2005). https://projectbullrun.org/dual-ec/documents/60644982.pdf
Patent Application Information Retrieval (PAIR). Image file wrapper for patent application 11336814 (2006). https://projectbullrun.org/dual-ec/documents/11336814.pdf
Perlroth, N., Larson, J., Shane, S.: N.S.A. able to foil basic safeguards of privacy on web. International New York Times, September 2013. http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html
Rescorla, E., Salter, M.: Opaque PRF inputs for TLS. Internet-Draft version 00, December 2006. http://tools.ietf.org/html/draft-rescorla-tls-opaque-prf-input-00
Rescorla, E., Salter, M.: Extended random values for TLS, Internet-Draft version 02, March 2009. http://tools.ietf.org/html/draft-rescorla-tls-extended-random-02
Schneier, B.: Did NSA put a secret backdoor in new encryption standard? (2007). http://archive.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115
Schoenmakers, B., Sidorenko, A.: Cryptanalysis of the Dual Elliptic Curve pseudorandom generator. Cryptology ePrint Archive, Report 2006/190 (2006). https://eprint.iacr.org/2006/190
Shumow, D., Ferguson, N.: On the possibility of a back door in the NIST SP800-90 Dual EcPrng.CRYPTO 2007 Rump Session, August 2007. http://rump2007.cr.yp.to/15-shumow.pdf
United States Patent and Trademark Office.Review of applications for national security and property rightsissues. Manual of Patent Examining Procedure, Section 115 (2013). http://www.uspto.gov/web/offices/pac/mpep/s115.html
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Bernstein, D.J., Lange, T., Niederhagen, R. (2016). Dual EC: A Standardized Back Door. In: Ryan, P., Naccache, D., Quisquater, JJ. (eds) The New Codebreakers. Lecture Notes in Computer Science(), vol 9100. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49301-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-662-49301-4_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-49300-7
Online ISBN: 978-3-662-49301-4
eBook Packages: Computer ScienceComputer Science (R0)