Slashdot Mirror

← Back to Stories (view on slashdot.org)

NSA Announces New Crypto Standards

Posted by Zonk on from the less-tasty-crackers dept.

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."

4 of 220 comments (clear)

  1. ECMQV broken by Anonymous Coward · · Score: 5, Interesting
    ECMQV has been partially broken -- I'd be wary of using it in any standards.

    Would any cryptographers here care to comment?

    1. Re:ECMQV broken by Anonymous Coward · · Score: 5, Interesting

      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.

  2. Re:I like my encryption broken. by Dwonis · · Score: 5, Interesting

    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.

  3. Alfred Menezes and Scott Vanstone by Anonymous Coward · · Score: 5, Interesting

    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.