NSA Announces New Crypto Standards

Proaxiom writes "This week the NSA announced the new US government standard for key agreement and digital signatures, called Suite B. Suite B uses Elliptic Curve Diffie-Hellman (ECDH) and Elliptic Curve Menezes-Qu-Vanstone (ECMQV) for key agreement, and Elliptic Curve Digital Signature Algorithm (ECDSA) for signature generation/verification. This shouldn't be too surprising given that the NSA licensed Certicom's EC patents for $25 million last year. ECMQV is patented by Certicom. ECDH and ECDSA appear to be generally unencumbered."

Comments

ECMQV broken

[Anonymous Coward]

ECMQV has been partially broken -- I'd be wary of using it in any standards.

Would any cryptographers here care to comment?

Re:ECMQV broken

[Coryoth]

ECMQV has been partially broken -- I'd be wary of using it in any standards.

Would any cryptographers here care to comment?

The paper itself isn't online, so I can only judge from the abstract. It does sound like a reasonable approach (on a completely cursory inspection), but there are a lot of details there, and I am a little unfamiliar with some of the stuff they reference.

As to how severe the break is: they claim they've reduced the complexity from O(q^{1/2}) down to O(q^{1/4}). Now I presume that q here is referring to the characteristic of the finite field that the curve group is over (I'm guessing, I would have to read the paper to know for sure - they don't say - but this is the logical choice). That is, of course, in cryptographic terms fairly significant. In practical terms most serious ECC implementations are using q in the order of 2^200 or more, so it doesn't necessarily represent a serious compromise.

As I say, with only the abstract to go on I really can't comment much. It does look interesting, but I would have to see more.

Jedidiah.

Re:ECMQV broken

[bluGill]

You would presume that. However it is important to recall that the NSA made changes to the original DES standard that made it more resistant to differential attacks, something that the rest of the cryptography world wouldn't "invent" for 15 years or so.

I know for a fact that several government agencies (Those three letter names before homeland security) used DES encryption for a lot of stuff 10 years ago, because I worked for a company selling it. (We couldn't tell you who they were, but there are only so many places where you can tell someone what city you are going to but not what organization[1]) I also can't tell you what level of security our products were trusted to.

Course the NSA also shortened the key to 56 bits. So this isn't a clear case of them helping against their interests.

[1]Not the IRS, we sold the IRS some stuff too, but AFAIK no encryption. Several engineers "regretted" not putting a backdoor in after they learned the IRS was sending tax data with our equipment.

Re:ECMQV broken

[Anonymous Coward]

As a grad student studying crpyto I think I can answer some questions out there. Elliptic curves are the best available as far as security goes. The structure is beautiful, but its the lack of a small enough factor base that keeps the elliptic curve discrete log free of a subexponential attack. The best attack is Pollard's Rho, which runs in exponential time. Well, if you have a quantum computer, then you can break this stuff in polynomial time via Peter Schor's algorithm, but we aren't anywhere close to having a big enough quantum computer.

Another alternative to elliptic curves are hyperelliptic curves, which allow the same amount of security with a much smaller key size, as long as you don't use a curve with genus greater than 4, since there are faster ways to attack those guys. The big problem with hyperelliptic curves is that the arithmetic, while efficient, isn't as efficient as in an elliptic curve.

For the curious:
elliptic curve: E: y^2 = x^3 + a*x + b
hyperelliptic curve: C: y^2 = f(x),
where the degree of f(x) = 2*g +1 or 2*g + 2 and g is the genus of the curve. So a hyperelliptic curve of genus 1 is an elliptic curve.

In response to another question above:
In crypto we work with these curves over a finite field, which is basically a set of numbers of the size q=p^n, where p, the characteristic, is a prime. We either work with p=2 and n~163 or p = a 163-bit prime and n=1. Elements in the finite field of p elements looks like {0,1,2, ..., p-1} and you do arithmetic modulo p. If you work in the finite field of 2^n elements, the elements of the finite field look like polynomials with degree n with coefficients either 0 or 1. The size of the group that we work with and do the key exchange and everything in has size in the range [((sqrt(q) - 1)^(2g), ((sqrt(q) + 1)^(2g)], so about q^g. That's why hyperelliptic curves are nice: with genus 3 curves, your key size is a third of the length of the key size for elliptic curves.

If I'm unclear or if anyone else has other questions, I'm happy to explain anything further.

Good encryption?

[Husgaard]

What they are now recommending is believed to be state-of-the-art, and practically unbreakable.

If this really is the case, this would cause them problems eavesdropping.

So the question remains: Have they found a successful attach on ecliptic curves, or have they finally seen the light and realized that strong encryption is good for society?

Re:I like my encryption broken.

[Dwonis]

Are you aware that any above-average worm-writing criminal has more computational resources at his/her disposal than an an average government agency? Criminals are able to leverage the computing power of zillions of vulnerable Windows machines to break your data. White-hats and spooks typically aren't.

Re:This is good news

[Coryoth]

The good thing about elliptic curve methods for cryptology is that they have a completely different "hard" function to our current cryptographic methods.

I'm not sure what you mean here. ECC protocols and standard Diffie-Hellman both rely on the hardness of solving the Discrete Log Problem over a finite group. All ECC buys you over standard Diffie-Hellman is a different group (the group formed by the set of points of the curve over some finite field), for which known methods for the discrete log problem are extremely (maximally, in theory) inefficient.

It is that there is an alternative cryptographic method out there, that should quantum computers be invented tomorrow, we would still have an effective method of cryptography.

Not true in the least. The protocols in Suite B are Elliptic Curve Diffie-Hellman, and Elliptic Curve Menezes-Qu-Vanstone (which is essentially a extended/more complicated version of Diffie-Hellman). Both are entirely useless in a situation where the Discrete Log Problem is easy. As there exists a quantum computing algorithm than solves DLP incredibly efficiently it is safe to say that in the advent of Quantum Computing these protocols will be rendered completely useless.

While marking work as a tutor at my university, I was lucky enough to be marking with somebody who has written a thesis on the subject.

I think perhaps he's been having some fun at your expense.

Jedidiah.

Alfred Menezes and Scott Vanstone

[Anonymous Coward]

When I was an undergrad at the University of Waterloo (located in Waterloo, Ontario [Canada]), I had the benefit of having both Alfred and Scott as professors.

Alfred taught C&O 487, which is Applied Crytography. He is an excellent lecturer and actively involved in the crypto community. His level of intelligence, professionalism, and kindness never cease to amaze me.

Scott "taught" C&O 331, which is Coding Theory. He's a down-to-Earth kind of guy, who really didn't know how to teach a class, but boy did he sure know how to simplify tough concepts. His trademark is that he's what we called a "celebrity professor". He never used his office (located at St. Jerome's on campus) to the point where if you looked through his window, you'd never see him there, and everything would be packed up in boxes. His computer was never hooked up and chairs were stacked up such that no one could actually sit down with him and have a conversation :).

He was a celebrity professor because he worked at Certicom, and was one the company's original founders. He was paid the highest amount out of any C&O professor at the University, and barely ever made it to teach class. He'd spend the day at Certicom instead, and send one of his grad students over from Toronto to Waterloo (despite the weather, since Coding Theory is only available in the Winter term) to teach the class. Sometimes, when there were no grads available to do his teaching duties, he'd ask Alfred (who wrote his PhD under the supervision of Mr. Vanstone) to fill in. Whenever Alfred taught the class I learned 200% more than if Scott were to teach the exact same material.

All that aside, it's nice to see these two fellows get their name in bright lights after all of their hard work throughout the years.