Cryptography Developments: Elliptic Curves – Part 1

cryptography-1091256_640

I recently wrote about the NSA’s surprising announcement in August. They urged the community to work on post-quantum cryptography. More surprisingly, they also recommended that organizations that have not yet converted from traditional RSA-based public-key systems to the newer ECC (or Elliptic Curve Cryptography) should not bother doing so.

RSA security relies on the difficulty of factoring products of large prime numbers. Large prime numbers, maybe about 150 digits each for a product of about 300 digits. ECC is similarly based on the difficulty of solving a specific category of math problem, in this case having to do with (no surprise) elliptical curves. NSA had been pushing ECC, requiring government agencies and strongly recommending other organizations to protect their secrets with ECC.

For the details, read “A Riddle Wrapped in an Enigma” by Neal Koblitz and Alfred J. Menezes, two highly respected cryptographers, the second a co-author of the Handbook of Applied Cryptography. But to summarize their excellent paper:

Where Did ECC Come From? 1985–1995

The NSA used to have a monopoly on cryptography. Then the personal computer was the Time magazine “Machine of the Year” in 1983. Industry and even ordinary people could own computers and use decent cryptography.


NSA headquarters at Fort Meade
NSA headquarters at Fort Meade

Congress decided that off-the-shelf products made more sense than extremely expensive custom-built systems, with classification adding even more expense. NSA’s Cryptographic Modernization Program led to its Suite A and Suite B algorithms. Suite A algorithms remain secret, needed for applications which themselves are too secret to even mention. But Suite B algorithms are not just known by name, you can read about them on Wikipedia and follow the links to download reference implementations in various programming languages.

The NSA clearly preferred the young field of ECC in the first decade of (relatively) open cryptography. (the background is here). By the early 1990s NSA had developed the Digital Signature Algorithm (or DSA) and NIST proposed it as a U.S. government standard. But supporters of RSA claimed that the NSA was pushing something with a back door.

The American National Standards Institute (or ANSI) had a meeting in December 1995, at which RSA supporters were criticizing ECC. An NSA representative was sitting quietly in the meeting, as usual, but what followed was unprecedented. While the RSA-versus-ECC debate became more heated, the NSA representative slipped out to make a phone call. He returned with the authorization to announce that the NSA believed that ECC was good enough to protect communication among all U.S. government agencies including the Federal Reserve.

Wow!

ECC Becomes Official: 1995–2005

NSA became more visible in its support of ECC. Crypto ’97 saw the first-ever public presentation by an NSA member at a major cryptography conference. It was on ECC.

In 2000, NIST published FIPS-186-2, defining 15 elliptic curves providing varying security levels.

NSA paid US$ 25 million to Certicom in 2003 to license 26 ECC patents. In early 2005 it posted the paper “The Case for Elliptic Curve Cryptography” on its website. It said, “Elliptic Curve Cryptography provides greater security and more efficient performance than the first generation public key techniques (RSA and Diffie-Hellman) now in use.”

NSA announced the Suite B ciphers in February, 2005, permitting their use to protect classified U.S. government data up through Top Secret. Approved asymmetric ciphers were ECC only, no RSA: ECC with 128 bits of security using curve P-256 for Secret, and ECC with 192 bits of security using curve P-384 for Top Secret.

Things Get Messy: 2005–2015

Government and industry were only very slowly converting to ECC, so in 2010 NSA updated Suite B to allow RSA and DSA to protect up to Secret (but not Top Secret) if they used a 2048-bit modulus to provide 112 bits of security.

The Dual Elliptic Curve Deterministic Random Bit Generator (or Dual EC_DRBG) was a cryptographically secure pseudorandom number generator algorithm. Two researchers had pointed out the possibility of a back door in Dual EC_DRBG at the Crypto 2007 conference. This wasn’t too alarming, as it was only the possibility of a back door. Besides, Dual EC_DRBG was about 1000 times slower than other DRBGs included in the same standard. Even if the possibility turned out to be true, who would be using it anyway?

Suddenly, Ed Snowden

Ed Snowden turned over a large archive of NSA documents and various media worldwide began publishing fragments in the summer of 2013. Documents published in September 2013 showed that the NSA had in fact inserted a back door into Dual EC_DRBG. And it was used. Reuters reported that RSA the company had accepted a secret US$ 10 million payment from NSA to make Dual EC_DRBG the default in their then-popular BSAFE toolkit. In the past few weeks we have learned that a Dual EC_DRBG backdoor is in Juniper firewalls, as described here, here, and here.

Cryptographers have studied Elliptic Curve Cryptography since the mid 1980s. Dual EC_DRBG is the only ECC algorithm for which anyone has openly discovered a way to insert a back door. But, all of ECC looked very questionable after the Dual EC_DRBG revelations. Most back doors become open doors for the bad guys as well as Big Brother, so of course ECC in general was questioned.

In August 2015 NSA made that announcement to basically give up on ECC.

What Does August’s Announcement Mean?

Did NSA push curves with back doors into FIPS-186-2?

Has NSA discovered that the categories of curves specified in FIPS-186-2 are all weak?

Has NSA developed, or are they about to develop, a general-purpose quantum computer?

Has NSA clumsily over-reacted to the Snowden revelations?

Come back next week to see what Koblitz and Menezes have to say!

As for why this is such a big deal, Learning Tree’s System and Network Security Introduction course explains why we need trustworthy cryptography.

image sources

  • National_Security_Agency,_2013: https://en.wikipedia.org/wiki/National_Security_Agency#/media/File:National_Security_Agency,_2013.jpg

Type to search blog.learningtree.com

Do you mean "" ?

Sorry, no results were found for your query.

Please check your spelling and try your search again.