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

13 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 Coryoth · · Score: 4, Interesting

      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.

      --
      Craft Beer Programming T-shirts
    2. Re:ECMQV broken by bluGill · · Score: 4, Interesting

      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.

    3. 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. Wait, what? by FireballX301 · · Score: 3, Interesting

    AES and Secure Hashing Algorithm also are included in Suite B.

    Weren't the SHA algorithms broken? Or, at least, SHA-1?

  3. Good encryption? by Husgaard · · Score: 4, Interesting
    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?

    1. Re:Good encryption? by xquark · · Score: 3, Interesting

      Because they are the worlds largest employer of mathematicians. Lets say out of every 1000
      mathematicians they have working for them only 1 or 2 of them turn out to be real geniuses,
      thats still more than enough to do the work they need...

      Its all about playing the numbers :D

      Arash
      _________________________________________ _________
      Be one who knows what they don't know,
      Instead of being one who knows not what they don't know,
      Thinking they know everything about all things.
      http://www.partow.net

      --
      Arash Partow's Philosophy: Be a person who knows what they don't know, and not a person who doesn't know.
  4. Re:Huh? by iabervon · · Score: 3, Interesting

    The NSA is responsible for advising the government and critical private-sector infrastructure on how to protect data. If there's a backdoor in an NSA-recommended standard, heads will roll (only figuratively, of course; they use the electric chair). Academic cryptography research is not believed to be too far behind the NSA, and it is reasonable to guess that the Chinese government is about even with the NSA. So a backdoor inserted by the NSA would probably be discovered by the Chinese within a year and academics worldwide within 5 years, at which point terrorists destroy the US economy and wipe out military deployments.

    The NSA may not really want our private data to be kept secure, but they do want the banking network to be kept secure. In general, they prefer to get data by finding plaintext or keys on seized equipment, rather than breaking encryption, because anybody can break encryption about equally well, but the government has an advantage in seizing things. That's not to say that they don't insert backdoors in things they don't intend to be secure (like consumer operating systems), particularly in implementations (where the hole can easily involve use of a secret key). But such things don't get this sort of announcement.

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

  6. Re:This is good news by Coryoth · · Score: 4, Interesting

    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.

    --
    Craft Beer Programming T-shirts
  7. 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.

  8. Canadian by cameldrv · · Score: 3, Interesting

    The fact that they are foreign doesn't really provide any real assurance. Do a search for Crypto AG sometime. The NSA has set up front companies in the past to sell comprimised crypto equipment.

  9. Re:I'd guess the latter by LnxAddct · · Score: 3, Interesting

    In the 1970's it was estimated that the NSA is at a lower bound 50 years more advanced in mathematics then society and 200 years for an upper bound. This notion was reinforced when they protected DSA from differential attacks 15 years before anyone even knew such a thing existed. There were other algorithmic changes made that people still haven't found the significance of.
    Regards,
    Steve