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."
Recommended Elliptic Curves (Score:5, Informative)
Recommended Elliptic Curves for Government Use, NIST document (PDF file) [nist.gov]
Re:Huh? (Score:2, Informative)
Obligatory Wikipedia Link (Score:5, Informative)
Goverment is slow (Score:2, Informative)
ECC: What and Why? (Score:5, Informative)
Re:Good encryption? (Score:5, Informative)
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.
Re:Wait, what? (Score:5, Informative)
Re:ECMQV broken (Score:1, Informative)
Of course, if you had actually opened AC's link, you would have seen a paper describing a weakness in ECMQV. Elliptic curves aren't the best objects on which to base an encryption scheme, as they have far too much structure.
Re:Good encryption? (Score:5, Informative)
-
Re:I suppose I have to get rid of enigma now (Score:1, Informative)
Well, this Polish fellow [wikipedia.org] and his buddies did.
Ok, there's a lot of misunderstanding on this (Score:5, Informative)
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.
Re:ECMQV broken (Score:2, Informative)
Breaking into stuff Signals Intelligence [nsa.gov]
and providing good encryption Information Assurance [nsa.gov]
Re:Obligatory Wikipedia Link (Score:5, Informative)
Menezes-Qu-Vanstone key agreement is essentially a varation/extension of Diffie-Hellman using a combination of a "static" and "ephemeral" public keys to compute the shared secret. The extra wrinkles in the procedure eliminate the possibility of a couple of subtle man in the middle attacks that can be made against EC Diffie-Hellman for certain parameters.
Jedidiah.
Re:Makes you wonder... (Score:5, Informative)
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 [cr.yp.to]) 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.
Re:ECMQV broken (Score:3, Informative)
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. Course the NSA also shortened the key to 56 bits. So this isn't a clear case of them helping against their interests.
Well, yes and no. The actual key is 56 but the entire length is 64 with the 8 bits of parity. That parity was important back in the day of noisy communications channels and costly retransmissions.
The DES changes suggested by NSA to IBM resulted in DES's resistance to differential cryptanalysis attacks, which were unknown to the public for at least another decade. Rest assured they know of techniques that others don't. They don't hire all those mathematicians for their social graces.
Re:ECMQV broken (Score:4, Informative)
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
Re:ECMQV broken (Score:5, Informative)
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.
Re:ECMQV broken (Score:5, Informative)
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.
Re:ECMQV broken (Score:1, Informative)
That's what people used to say about the undocumented values chosen by NSA and IBM for the S-boxes in DES.
Then when people outside NSA discovered differential cryptanalysis [wikipedia.org] twenty years later it turned out that IBM and NSA had actually designed the S-boxes to make DES especially hard to break [ibm.com] using differential cryptanalysis.
Key agreement (Score:5, Informative)
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.
Re:ECMQV broken (Score:2, Informative)
...
In response to another question above: ..., 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.
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,
OK, you got some things right, other less so.
With genus 3 curves you DO NOT get key size equal to a third of the length of the key size for elliptic curves. What you get is that the FIELD over which you define the curve and implement the arithmetic gets smaller! To one third. The key has a size equivalent to 3 field elements, hence has the same size as with EC.
If you take into account the attacks by Gaudry, Theriault, Gaudry Thome and Theriault... then already for genus 3 you have to use a slightly bigger key, but 5 to 10% more bits. Not a big deal, and also the field size increases accordingly, so it is a few bits more than one third that of the field used for an elliptic curve.
The advantage is that the operations are performed on smaller fields. On the other hand there are many more of them (the number of finite field operations to operate in the jacobian variety of a hyperelliptic curve of genus g is in practice between O(g^2) and O(g^3), asymptotically closer to the second bound). This means that the multipliers in the arithmetic unit can be made smaller, making the hardware cheaper - or requiring less multiprecision arithmetic in software - but the software implementing the formulae for the oeprations gets more complicated. It is a balance of costs and performance.
The sweet spot for normal security (160-256 "geometric" bits, where the RSA keys could be defined "arithmetic") is still with the elliptic curves: for larger security (as for the 320 bits used by the german "NSA", the BSI, of the 520+ bits adopted by NSA) the sweet spot are genus 2 HEC (see the papers by Avanzi and Wollinger at CHES [Cryptographic Hardware and Embedded Systems] 2004, for a nice divisor doubling formula in even characteristic see the paper by Lange and Stevens at SAC [Selected areas in Cryptography] 2004). I am a very strong proponent of low genus HEC in odd characteristic (fields of the type GF(p) - the integers modulo p in simplified terms) and of Trace Zero Varieties (expecially those constructed from elliptic curves - I have nice implementation results and tricks in even characteristic with my student Emanuele Cesena - his Thesis will be discussed shortly).
Roberto
--
/_/ Faculty of Mathematics and
_/_/ Dr. Roberto Avanzi, Junior Professor
_/ Horst Görtz Institute for IT-Security
/ Ruhr University Bochum
Re:Good encryption? (Score:2, Informative)
The discrete logarithm problem (DLP) is the following one: Given a group G generated by an element g, and a second element h of G, find an integer t such that g^t=h.
It is clear where the name discrete logarithm comes from: One could (with some abuse of notation) write that t is the logarithm of h to the base of g. This name is used even when the group G is written additively, i.e. the operation is not a "multiplication" but an "addition" and the "exponentiation" g^t is written as t times g (t.g), hence we speak of "scalar multiplication".