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

[Anonymous Coward]

One presumes that any encryption standard the US is going to reccomend has in fact been broken by the NSA or other security organzation. The US has been very clear that it does nto want its citizens of anyone else in the world to use encyption that the US cannot break.

So i would posit that the standard has already been broken by someone, and, if need be, can be decrypted as needed. Perhaps it won't be cheap, but it will be possible.

Re:ECMQV broken

[Coryoth]

One presumes that any encryption standard the US is going to reccomend has in fact been broken by the NSA or other security organzation. The US has been very clear that it does nto want its citizens of anyone else in the world to use encyption that the US cannot break.

And likewise the US has been very clear that it does not want its government, military, businesses using an encryption system that can be broken by other countries. The NSA has 2 roles, Signals Intelligence (which may involve breaking encryption) and Information Assurance (which involves providing secure computing to US government and business). ECC is out there and available, so pretending it doesn't exist just because they can't break it hardly helps them in stopping people using it. That means, from the Signals Intelligence perspective ECC is a moot questions, breakable or no. Export controls make little difference considering the company (Certicom) with all the patents on ECC (hundreds, literally) is Canadian. On the other hand, if it is good, strong, and secure, then it is entirely sensible for the Information Assurance arm to promote it as a standard for US business. Let's be honest, RSA has looked weak the last couple of years. You could just as easily claim that this announcement is an effort to move US government and business to a more secure system. Maybe this announcement means that the NSA knows how to break RSA, and figures other countries either know too, or will figure it out soon.

In short, there is no reason to expect that the NSA can break ECC, and to claim otherwise is just shotting your mouth off with absolutely zero basis. There are other perfectly good explanations, why not consoder them instead/as well?

Jedidiah.

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.

Obligatory Wikipedia Link

[Brock Lee]

wikipedia: Elliptic Curve Cryptography

ECC: What and Why?

[clap_hands]

Elliptic curve cryptography is (if you squint your eyes) a translation of older crypto techniques onto slightly more exotic mathematical objects. Rather than (say) integers modulo a prime, ECC uses a group of an elliptic curve over some finite field. But the new techniques are analogous to the old: Diffie-Hellman, ElGamal, DSA. The advantage is meant to be that keys can be a lot smaller for an equivalent level of security.

I suppose I have to get rid of enigma now

[multi-flavor-geek]

And I was just getting the kinks out of a usb powered enigma machine to provide encryption for online banking. I mean damn? Who could ever crack enigma?

Re:Wait, what?

[clap_hands]

You can find collisions for SHA-0 faster than expected, and it's claimed that you can do the same for SHA-1 (the attack hasn't yet been published, but it's pretty certain to be genuine). The SHA-2 algorithms (that is, any of SHA-224, SHA-256, SHA-384, or SHA-512) remain uncompromised. See: SHA article on Wikipedia.

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.

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.

Key agreement

[ebvwfbw]

Everyone, what is proposed is the key agreement algorythm. Please don't confuse this with the encryption method. I see a lot of messages that are misleading on what this is.

WTH is it? When a key needs to be exchanged between two machines (like two routers for example), a mutually agreed upon key must exist no matter which encryption you use - blowfish, aes, des, and on and on. The idea is that only the two machines would know what the real key is and it is done automatically.

Diffy-helman has been used for decades (Patent expired in 1997) for this and can be found as close as your nearest cisco router that has encryption enabled. The new algorithm adds a few new twists to it. Those twists may make the key easier to crack, however. Buyer beware, don't bet your life on a mutually agreed upon key like that. Be sure your keys are very secure. This goes for the so called quantum encryption channel as well. I don't think it is as secure as they say it is.

However for most all of us in the world this is perfectly safe for digital signature encrypted data. If you have a need to be absolutely sure a signature is valid, don't use the network. Get it on paper.