NSA Turns To Commercial Software For Encryption

Roland Piquepaille writes "According to eWEEK, the National Security Agency (NSA) has picked a commercial solution for its encryption technology needs, instead on relying on its own proprietary code. "The National Security Agency has purchased a license for Certicom Corp.'s elliptic curve cryptography (ECC) system, and plans to make the technology a standard means of securing classified communications. In the case of the NSA deal, the agency wanted to use a 512-bit key for the ECC system. This is the equivalent of an RSA key of 15,360 bits." This summary includes the NIST guidelines for public key sizes and contains more details and links about the ECC technology. Since the announcement, Canadian Press reports that Certicom's shares more than doubled in Toronto."

Public key vs. symetric

[autopr0n]

You can't really compare symetric key systems like AES with public key systems like ECC or RSA. With a symetric system you need keey your key secret, with public key you have two keys (encryption and decryption), and you only need to keep one of them secret. The other you can distribute far and wide.

A lot of times, people will create symetric keys and then use public key systems to distribute them.

Re:OSS ECC? ECC vs AES

[espo812]

What makes ECC so much better vs AES with a key size of 256?

I'm sure a small ammount of googling could tell you this, but comparing ECC to AES is like comparing apples to oranges. ECC is a public key algorithm, and AES is a symmetric key algorithm. Thus, you would have to look up the fundamental differences between public and private key algorithms to find the differences between ECC and AES.

The difference between ECC and algorithms like RSA, for example, is that elliptic algorithms can work with smaller keysizes, and this should have been noticable from the slashdot post that points out the commercial product uses a smaller keysize than the equiviliant strength RSA key.

Re:OSS ECC? ECC vs AES

[daserver]

GnuPG can use DSA which is ECC. And as the other one said you can't compare sym. crypto with asym. crypto.

Canada

[nuggz]

FWIW I'm Canadian.

Canada has many exceptions to US restrictions. This makes sense. It is cheaper to work together, and we do in many military and space applications.
Our interests are basically very similar, and both countries are generally trustworthy of each other.

The only conflict are on specific policy issues.
It also matters which government is in power in each country.

There have been quite a few times where state and provincial officials have banded together to fight both federal governments.

Plus if it works well, why shouldn't they use it?

This isn't software, it's patents.

[Garin]

As far as I understand the deal, this has nothing to do with licensing software. They couldn't have gone with an OSS version (or "roll their own") as so many suggest because they're not licensing just software, they're licensing patents.

You'll note that they've also got sublicensing rights on those patents. There could be a software component to this deal, but as far I can tell it appears that this is mainly about patents.

Re:Privatization

[espo812]

Oh come on, I know Bush's administration is all for privatization and turning to the private sector and all, but this?

I believe that the technological divide between the NSA and the private sector has been shrinking over the years. I also don't think they would have selected this product if they didn't have good reason to. I suspect that this product was probably developed with some degree of NSA involvement, either contract work there or by former contractors/employees. And, low and behold, as I RTFA it says:

Certicom has worked with the NSA, based at Fort Meade, Md., on several classified projects in the past, and this agreement is essentially an outgrowth of that work, officials said.

So, it appears to have a lot of NSA involvement in the development. Actually, RTFAing a bit more closely it appears NSA is licensing the algorithm from Certicom. So they may not even be using the code from Certicom, they could be developing all the systems in house. Clearly, they wouldn't make a move like this without thoroughly analyzing the algorithms involved.

So what comes out is a solution that was produced much cheaper than a similar inhouse effort, and this will save the tax payers money (which sounds good to this poor college student.) I have to say I'm surprised at the Agency going after a commercial product for classified purposes, but I'm sure they have good reasons.

Re:Size of key

[espo812]

I wonder: how can they tell that a 2 ^ 512 possibility range is as secure as a 2 ^ 15360 probabilities scheme?

Because breaking RSA does not involve brute forcing the bits, it involves factoring huge ass numbers into primes. Look up the differences between symmetric and asymmetric (or private and public) key cryptosystems.

Re:Size of key

[inburito]

Maybe because discrete logarithm problems in ordinary number groups are much easier to solve than in elliptic number groups.

As a matter of fact, discrete log problem for ordinary numbers has been improving steadily whereas Elliptic curve group discrete log techniques have not seen significant improvement in the past 20 years. This difference accounts for today's reduced key-size requirements for elliptic curves.

Re:What about license abuse?

[randyest]

The NSA practically can't not follow the license -- it's world-wide and allows granting sub-licenses, and is only restricted to use above a certain security level. The NSA would have to use relatively insecure implementations of the technology to violate the license, and I think that's unlikely:

Certicom Corp. (TSX: CIC), a leading provider of wireless security solutions, today announced that the National Security Agency (NSA) in Maryland has purchased extensive licensing rights to Certicom's MQV-based Elliptic Curve Cryptography (ECC) intellectual property. ECC is becoming a crucial technology for protecting national security information.

This agreement will give the NSA a nonexclusive, worldwide license with the right to grant sublicenses of MQV-based ECC covered by many of Certicom's US patents and applications and corresponding foreign rights in a limited field of use. The field of use is restricted to implementations of ECC that are over GF(p), where p is a prime greater than 2256. Outside the field of use, Certicom will retain all rights to the technology for other industries that require the same levels of security, including state and local government agencies. Certicom will continue its policy of making its intellectual property available to implementers of ECC under normal commercial terms on a non discriminatory basis.

Re:Size of key

[LT Grant]

If you look back at Dr Chris Monico's work at cracking ECC-109 [nd.edu] you can get some more background on the equivalences and how they match up and how the two are compared and how they are very different. 109 took a lot of computational time (biggest ever so far I believe), and this is vastly bigger, as if I remember correctly ECC encryption doesn't grow linearly, but exponentially. The code used to crack ECC-109 has been somewhat improved in ECC2-109 [ecc2.com] based mainly on things Dr Monico saw in 109 and based on some research he and I did regarding a paper by Teske of Waterloo.
Hope that is informative.

Re:OSS ECC? ECC vs AES

[quadelirus]

In cryptography it's usually not a program that gets lisenced, but an algorithm (or cryptosystem). My guess would be that ECC has the copyright or patent or whatever you get on their algorithm which would make it illegal to write a program using elliptic curve cryptography (or at least their algorithm) without permission from the company. I once wrote a project that used the RSA cryptosystem for education purposes and I had to obtain permission from RSA legal to use the cryptosystem. (However it might be public now...)

Also between AES and ECC. My guess would be ECC is much more secure than AES. If a 512-bit key for ECC is the equiv of a 15360-bit key in RSA that sounds extremely secure. As far as the last time I checked a 4096-bit RSA key was virtually unbreakable in any normal time span by even the fastest supercomputers built.

Finally what the other replies to your question have been, about comparing apples and oranges: AES is a symmetrical key, meaning, the key that encrypts also decrypts.

Public/Private Key encryption deals with two keys, the public key is freely available to anyone becuase when a message is encrypted with the public key it can not be decrypted with the public key. It must be decrypted with the private, or secret key.

Re:OSS ECC? ECC vs AES

[graf0z]

GnuPG can use DSA which is ECC.

No, DSA != ECC.

DSA and ECC both do encryption by exponentation, relying on the assumtion that the reverse function - the logarithm - is infeasible with the used keylengths. They are both called "Discrete Logarithm Systems".

But the multiplication is done in completly different mathematical contexts: DSA multiplies in the rings Z/p (that are the natural numbers modulo p, p being a prime) where ECC multiplies in suitable "elliptic curve groups over finite fields" . That are finite sets of "numbers" paired with an complicated operation called "multiplication". These "numbers" behave quiet odd.

The main practical difference is the neccessary keylength. Depending on the chosen eliptic curve, ECC keys are 4-8 times smaller than DSA keys. They get much closer to the "no attack is faster than the brute force attack"-paradigm than other public key algorithms like DSA or RSA.

Unfortunatly, huge classes of suitable elliptic curves got patented.

Google for free ECC software. There are at least some libraries published by academic research groups.

/graf0z.

Re:FUD

[quadelirus]

I stated this in another post, but I've got a link now:

The NSA is not lisencing software, it is lisencing the right to use Certicom's ECC cryptosystem. Cryptosystems now are usually known even when proprietary to allow mathematicians and cryptographers the ability to test the security of it. (The RSA cryptosystem for instance is thoroughly explained on RSA's web-site, but you would still need a lisence to use the algorithm in a program)

I found a tutorial by Certicom on their ECC cryptosystem here [certicom.com].

PS. I could be wrong, but from the article it seems that "intellectual property" and "This is the first time that the NSA has endorsed any sort of public-key cryptography system." that they are not actually lisencing software but are in fact lisencing the cryptosystem. If I am wrong, I humbly apologize.

Re:FUD

[randyest]

I'll take that bet aginst you. The NSA didn't demand the source code, they wrote the source code. Note that NSA is not buying some software tool, they are licensing a patented encryption concept. The NSA will implement this ECC encryption technology in many different ways, on their own:

This agreement will give the NSA a nonexclusive, worldwide license with the right to grant sublicenses of MQV-based ECC covered by many of Certicom's US patents and applications and corresponding foreign rights in a limited field of use. The field of use is restricted to implementations of ECC that are over GF(p), where p is a prime greater than 2256.

Re:OSS ECC? ECC vs AES

[pyrbe]

Bouncycastle Crypto APIs [bouncycastle.org] support atleast Elliptic Curve DSA and Elliptic Curve basic Diffie-Hellman (according to release notes). Possible other ECC algorithms too.

Evidence for Quantum Computer

[Markus Registrada]

This isn't proof that they don't have a quantum computer. It's evidence that they do have, or expect to, or expect others to have soon. A quantum computer isn't magic. The best guess about the power of quantum computers, as applied to decryption, is that they can crack a 2N-bit cipher about as fast as an ordinary computer cracks an N-bit cipher.

So, when we see the NSA not just adding key bits, but adding bits and then doubling them, we see evidence of countermeasures against quantum computers. This doesn't mean they have quantum computers. Remember that they are not just guarding secrets they transmit today against attack now, but against attack ten years from now, when revelation might still be damaging.

Once we all do have quantum computers, I wonder what amusing revelations will come from cracking old ciphertexts. You can bet the NSA will keep busy at it, and so will the Brits, and the French, and the Germans, and the Russians, and the Israelis. (No doubt a few of the biggest corporations go on that list too.)

Re:512 bits?

[damiam]

If it's 15360, then you have to try 2^15360.

No, you don't. You have to find the factors of a prime number of that length. That leaves significantly less than 2^15630 possibilities, especially if you're using a decent factoring algorithm.

Re:Size of key

[Metex]

Ugh this is actually pretty easy to calculate,
for the rsa key in order to find the approximate number of keys possible you use the simple equation 2^k / (ln 2^k) this gives you an 'approximation' for all possible primes you can have in k-bits.

As for the ECC system I cant remeber the exsact computation off the top of my head to calculate key space but it has a much higher key concentration per bit added to key. not as high as a symetric cryptographic system with a 2^k keyspace but pretty high up there.

As for your reduction useing a ratio it wont work out since they both use diffrent keyspaces.

Re:Size of key

[jareds]

Note that both ECC and RSA are NP-complete

This has not been proven, nor is it even commonly believed to be true.

Sun and ECC

[pmsyyz]

Sun likes [sun.com] Elliptic Curve Cryptography. They have helped add it to Mozilla's Network Security Services [mozilla.org] and to OpenSSL.

Just a Wild Guess, But...

[Nom du Keyboard]

Just a wild guess, but what are the chances that NSA developed this secretly years ago and either planned to, or already does, use it. When the civilian cryptography sector finally caught up with them and actually patented the algorithm, NSA had to license it or stop using it. It wouldn't be the first time NSA has been shown to be far ahead of publicly known cryptographic knowledge. Differential Cryptology comes to mind.

Re:Size of key

[joeblarnystone]

The best known means for solving the Discrete Log Problem over an EC is much slower then the best known means for factoring integers. This is why they can claim that a 512 bit ECC key is equivilant to a 15630 bit RSA key. The time it would take to solve both problems is equivilant.