Slashdot Mirror
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."
Recommended Elliptic Curves for Government Use, NIST document (PDF file)
Creative Demolition
wikipedia: Elliptic Curve Cryptography
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.
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?
Technically fully half the NSA's job is Information Assurance, which is to say providing strong crypto and information security solutions to US governemnt and US companies. It was the Information Assurance people that provided us with SELinux as a demo of how a secure system could easily be achieved just working from a commodity OS. They are supposed to believe that strong encryption is good for society - US society anyway.
Jedidiah.
Craft Beer Programming T-shirts
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.
I'm generally about the last person who would say "trust the government", but the NSA has a proven track record of giving GOOD encryption advice in their public announcements. They have recommended minor changes to encryption and hashing algorithm standards that, several years later, were discovered to make them signifigantly harder to crack.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
People keep using the term "broken", as though SHA is no longer useful, that's not the case. SHA-0 and 1 are still perfectly useful hashing systems. The fact that there are collisions means nothing, that is a known property of hashes.
Finding a hash collision, is a bitch however. Hash functions, by their nature, aren't reversable, so that means that you have to sit and try and brute force a collision. You take the value you want, and just keep hashing data until finally after a number of tries that needs exponential notation to express, you find a collision.
What has happened is that a group has shown how to find a collision in the hash faster than just by brute force for SHA 0 (and also 1 they claim). So it takes a lot less work to find a collision. Now that's a relitive term, it's still a ton of processing time. What's more, just finding a collision does you no good in most cases, a bunch of random garbage won't be mistaken for a genuine message even if the hashes match. You need to generate a message that has the same hash, and is also a plausable replacement. That's a hell of a lot harder to do and requires a LOT more computation.
So SHA hasn't been broken in that it's not usable, it's just been shown to be not as strong as previously thought, you can find a collision faster than by straight brute force. It still takes a long time, it's just not as long as you'd predict based on hash size.
However, in this case, they are talking about the new SHA-2 standards, which remain unbroken.
Perhaps does the gov't know of a "quick" way to do large prime factorization unknown to the rest of us? With RSA resting so heavily on big primes, it would be uniquely vulnerable to something like a new way to do factorization.
Actually factorization has been looking a little weak for the last couple of years. There hasn't been any big breakthrough, and 1024-bit (and up) RSA isn't exactly broken right now, but there have been a steady number of papers that have offered various improvements to the basic Number Field Sieve algorithm (such as Dan Bernstein's facorization circuit) that it is beginning to look as if it is merely a matter of time before at least 1024-but RSA is considered insecure.
Certainly if you have enough compute power the present NFS with improvements will be good enough to break RSA keys out. The NSA is not exactly lacking in potentially dedicated compute power.
Jedidiah.
Craft Beer Programming T-shirts
A finite field is essentially a set of q=p^n numbers, where p is a prime and n is a positive integer. The characteristic of the finite field is defined to be p. Fields themselves have the operations addition, subtraction (so we have additive inverses), multiplication, and division (so we have multiplicative inverses), are commutative, associative, have the elements 0 (additive identity) and 1 (multiplicative identity), and all distributive properties hold. Examples of fields are the rational numbers, real numbers, and complex numbers, which by definition have characteristic 0. For crypto, we use finite fields because finite things are nicer to work with. The best example of a finite field is F_p = {0,1,2,..., p-1}. All arithmetic is done modulo p, so in the case of F_5 = {0,1,2,3,4} we have
4*2 = 8 = 3 mod 5 and 4*4 = 16 = 1 mod 5, so the inverse of 4 is 4.
For the case of the finite field q=2^n, n>0, elements are polynomials of degree at most n-1 with coefficients in F_2 = {0,1}. Arithmetic is done modulo an irreducible polynomial of degree n, like x^2+x+1 if n=2, which means that
x*x = x^2 = -x-1 = x+1 (in F_2, -1 = +1).
For elliptic curves, the points of the elliptic curve are the elements in the group we work with and are ordered pairs (x,y) satisfying y^2 = x^3+ax+b, where x,y,a, and b are in the finite field. Hope this helps!
-- Eric
SKIPJACK, as far as we know, is quite secure with no backdoors. What the NSA did do was keep the algorithm secret and only allow it to be implemented in hardware on chips that also implemented a key escrow system. They were up front that that was on the chip.
The point here is that they weren't foisting a weak algorithm on people - the algorithm is pretty strong. They were foisting hardware onto people that let NSA decrypt anything you encrypted with that hardware. The distinction is important because anyone (not just the NSA) can break a weak algorithm, but only the NSA can exploit hardware key escrow designed specifically for them.
If ECC was breakable by NSA that doesn't make it a good system to promote, because other countries could also have found the weaknesses. The point is that they do want to promote systems that are secure from other people, and pushing weak algorithms is a really bad way to do that.
Jedidiah.
Craft Beer Programming T-shirts
Remind me not to let you design any security systems. An additional weakness in a "secure" system is an additional weakness, regardless of what is was designed to do.
Given what was implemented, I think you're massively overreacting. Each chip had a secret key and an ID number. When the chip encrypted data it first encrypted its session key using its secret key and included that and the ID in the message. That meant the NSA had to look up the secret key for that ID chip, and then decrypt the session key. Is this a significant extra weakness? To be a weakness you either need: the NSA's ID/secret key table, or the ability to break the algorithm. If the NSA can't keep secrets, or the algorithm is breakable, then the whole question is moot. This is hardly a significant reduction in the strength of the system.
Yes, this system is weaker than a system that used purely session keys: if you want to spend the time you can break the secret key for a given chip, and then decrypt everything thereafter from the chip. That presumes it is at all feasible to break the algorithm - and I suspect the NSA is quite good at designing strong algorithms. In short the system was exactly as strong as the algorithm, and in fact SKIPJACK was declassified and is still considered a very strong algorithm.
Jedidiah.
Craft Beer Programming T-shirts
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.