NSA Announces New Crypto Standards 220
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."
ECMQV broken (Score:5, Interesting)
Would any cryptographers here care to comment?
Wait, what? (Score:3, Interesting)
Weren't the SHA algorithms broken? Or, at least, SHA-1?
Good encryption? (Score:4, Interesting)
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:ECMQV broken (Score:5, Interesting)
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.
Makes you wonder... (Score:3, Interesting)
-Charles
Re:Huh? (Score:4, Interesting)
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.
Re:Good encryption? (Score:3, Interesting)
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
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
Re:I like my encryption broken. (Score:5, Interesting)
Re:This is good news (Score:5, Interesting)
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 (Score:5, Interesting)
Alfred [uwaterloo.ca] 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 [certicom.com]. 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.
Canadian (Score:4, Interesting)
Re:ECMQV broken (Score:5, 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.
I'd guess the latter (Score:3, Interesting)
Basically, the P=NP conjecture says that, if it's easy to prove, it's easy to solve. So, for example, it's easy to check that a jigsaw has been completed correctly, but jigsaws seem hard to solve. A proof of the conjecture would imply that there is in fact an easy (mathematically speaking) way of solving jigsaws.
The interesting thing about the conjecture is that a proof of it for any one instance (prime factorisation, jigsaws, whatever) would instantly give a proof for every other instance. It would be one of the major mathematical discoveries of the century, and would instantly render dodgy every form of public-key encryption currently known to man.
As such I severely doubt that the NSA has solved the problem of easy prime factorisation. Even with their renowned culture of secrecy, word would have leaked out. They may have found a way of making it slightly less tough though, or, as the parent says, built a bloody big computer cluster.
Who knows?
Re:I'd guess the latter (Score:3, Interesting)
Regards,
Steve
Re:ECMQV broken (Score:5, Interesting)
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,
If I'm unclear or if anyone else has other questions, I'm happy to explain anything further.
Re:ECMQV broken (Score:3, Interesting)
The NSA has some hella good mathematicians working for them. As others have already pointed out, the NSA has on occassion announced that certain cryptosystems are insecure before anyone on the outside had even developed the theorems necessary to attack the system.
And as any true tin-foil-hatter knows, the NSA developed quantum computers fifteen years ago.
They have vested interests in promoting standards 5-10 years behind their current technologies.
The side of the house interested in reading people's mail might, but the other half of the agency is interested in keeping secrets secret, and that means letting Americans have encryption that the Chinese can't break.
Re:Key agreement (Score:2, Interesting)
I have heard this argument a number of times. I have a feeling you have no idea just how hard it is to forge a signature and get away with it. It can be done, sure. It also depends on the document.
You seem to have a great deal of confidence in digital signatures. I'm not sure why you are that confident. The big picture right now is that most users machines are not secure. That is, you don't have to break the key nor encryption. You can compromise the machine and that is well known to happen for Windows based clients. Own the machine and you have a rigged game.
There is also the issue of the signature itself. Just how careful is the certificate authority? From my experience not very careful. This can be corrected, however.
I don't want to kill DS, they can be very useful. I don't think it should be considered legitimate any more than a physical document that was signed without a witness. With physical documents there are also fingerprints on them as well as a lot of other forensic evidence. For example it was trivial to show that a 30+ year old memo during the last Presidential race was fake, for many reasons. Even though the man that supposedly wrote the memo is dead, it was supposedly written over 30 years ago and it was faxed. With a digital document all bets are off. You have a doc that is signed, any and all of it can be faked. You can't even go back and try to get physical evidence.
How about the retention of the DS data? Could I come back in 30+ years from now and challenge a document signed today and be sure if it is fake or not? If you would bet that 30+ years from now we could be sure, as PT Barnum would say "A fool and his money are soon parted."
Re:Good encryption? (Score:3, Interesting)
This is why it's so good to have algorithms like these published: they can be examined by others, tested by others, and their security (or lack thereof) can be established, known, and understood.
I've often toyed with hooking my geiger counter up to my computer, generating a CD full of random numbers (really random, not computer-generated pseudorandom numbers) and using one-time pad encryption [wikipedia.org] to send email to my Mom. :-)
...laura