One point this doesn't (appear to) consider is the type of vulnerability which is possible to embed. Forcing a curve parameter with the prefix 0xBADA55 is eminently feasible given the many available design choices (as this shows, though I'm not sure this was in dispute), but there's a long way between this and the type of vulnerability that the NSA would be most comfortable with.
Consider Dual_EC_DRBG: by all indications this was a "NOBUS" vulnerability (exploitable by "nobody but us") since the private key to unlock the backdoor had to be created at design time and wouldn't be recoverable by any other user of the system. With the NIST seed-hashing technique used to generate these curves, however, only a relatively small number of bits of structure can be forced in the result (assuming no preimage attack on SHA-1, which is still presumed difficult even now, let alone in 1999 when the curves were specified).
This more or less makes Jerry Solinas in the thought experiment resort to weakening the curve by forcing the choice into suitably large set of privately-known weak curves (which might only constitute 1 in a billion of the publicly acceptable curves). However, it's not possible for these attacks to insert enough structure for a Dual_EC style private key so they end up weak against all attackers (including other nation states) in theory if they can perform the same analysis. This (assuming that no one else has discovered the weak class of curves) is a very risky needle to thread when you are still recommending NIST-384 for use in protecting top secret information even now over 15 years later.
One way to get a NOBUS vulnerability that allows GCHQ to recommend a curve (and thus see it deployed on systems they care about) and break that same curve is for the vulnerability to be mitigated with an additional parameter check. For instance, maybe a particular weak curve is safe to use if you exclude a small subset of points. GCHQ's implementations do the additional check, but nobody else does that (why would it ever occur to them to check? would they even know what to check for?).
Dual_EC is, of course, the gold standard of NOBUS backdoors: it's literally a strongly-encrypted backdoor!
This is an updated version of a paper Bernstein and his team wrote a year ago, known in the community as "BADA55".
Bernstein is talking about curve standards. The idea Bernstein is discussing is (his term) curve "rigidity". A rigid curve standard can generate only one or a very few curves. A non-rigid generation procedure might generate millions or billions of different curves. That's bad news, because it means that corrupt standards bodies can search those billions of curves for one with a weakness that only they know about.
The most popular curve standard is NIST's. NIST's curves aren't rigid at all: they start with a random seed. There are as many possible curves you can generate as there are seeds.
Now, we've known for a long time that we want rigid curve generation. The second-most-popular curve standard, the Brainpool curves, attempt rigidity. Bernstein doesn't like the Brainpool curves. BADA55 criticizes Brainpool and other standards for attempting but not fully achieving rigidity. Most rigidity attempts involve starting from some mathematical constant, like the digits or pi or stuff like that. The basic logic of BADA55 is that there are too many constants and variants on constants to meaningfully constrain curve generation. The good guys will say they're starting from pi, and the bad guys will just respond that they're using e, the square root of 2, and sin(2). As long as the bad guys can justify a couple million different combinations of constants, they will have enough search space to find weak curves.
Since Bernstein doesn't know any secret curve vulnerabilities (or isn't publishing them), he models curve vulnerabilities by searching for curves that begin with the bytes B:A:D:A:5:5. If you can make "badass", the logic goes, you can make any evil curve.
The historical context of this paper is worth knowing. There's an ongoing effort to standardize and deploy Curve25519, Bernstein's (very excellent) curve standard. Indeed, it is likely that within a year or two, Curve25519 will be the second-most widely deployed curve on the Internet, because browser vendors appear happy to adopt it (it's fast in software, NIST didn't produce it, and has many good implementations).
But when Curve25519 went to the IETF/IRTF, there was pushback: some people felt the Brainpool curves should be standardized, and Microsoft felt like what should be standardized first should be a "nothing up my sleeves" generation procedure that could produce lots of curves for IETF/IRTF. The debate on the CFRG list was pretty bitter, as was the dialog between Tanja Lange (a Curve25519-associated researcher) and Manfred Lochter (a Brainpool guy) at a recent NIST curve summit.
So the updates in this paper include consideration of the Microsoft NUMS procedure, in addition to Brainpool and ANSSI.
Thanks for the explanation! I was reading the paper but not being an expert I could hardly pass beyond the abstract.
So if I understand correctly, the idea would be to have only one curve that has been thoroughly examined for weaknesses and then use that curve and only that curve (ideally) in encryption applications, for example for future versions of TLS or whatever other encryption scheme supports elliptic curves.
That would avoid introducing potentially exploitable curves to consumer applications, and maybe even make the NSA's work harder, right?
Now my other question is, I'm guessing there's no easy way to determine the rigidity of a curve without the proper knowledge and tools, but if there was a way (let's say some smart guy managed to make an algorithm to determine the curve's weakness) the interested parties could determine the other party's curve weakness and negotiate a minimum level? So if you are using a very nonrigid curve then the other party could say "hey, I won't send encrypted messages to you unless you use a curve's rigidity index > X". Does this make sense? is this were future consumer encryption is/should be moving?
EDIT: I'm assuming a nonrigid curve can be considered "weak" by your explanation. A rigid one would be much stronger since it would leave less space for exploitable curves, right?
Most curve-enabled applications work with only a few curve standards; in fact, most curve-enabled apps work only with the NIST curves. Everyone implementing a protocol has to agree on which curve they're going to use. There are crazy oddball protocols that attempt to let participants select arbitrary curves, but mainstream applications don't do that.
The issue is that you want the standard to be transparent; you want to believe that there's a reason for every parameter in the standard, and that the reason isn't "because this curve is broken".
The NIST standards have a bunch of relatively sensible rules for generating the curve parameters they come up with. But they're not rigid, because the first rule, off which every other rule is based, is "start with a random number; here's the random number we came up with, so let's just use that one".
The Brainpool standards have relatively sensible rules too. But to keep the process transparent, they start with a mathematical constant, in a sort of "who could argue with pi" argument. Bernstein's point is that the space of all permutations of a pretty small set of mathematical constants gives you a lot of room to find a weak curve. Maybe it's sqrt(2)+sin(2)+e/pi. Well, then you, the bad guy, just write a standards doc that says "the square root of 2, sin(2), e, and pi are fundamental mathematical constants that we chose so nobody has to worry we made up numbers to find a weak curve".
> Now, we've known for a long time that we want rigid curve generation
>A rigid curve standard can generate only one or a very few curves. A non-rigid generation procedure might generate millions or billions of different curves. That's bad news, because it means that corrupt standards bodies can search those billions of curves for one with a weakness that only they know about.
This looks like a contradiction.
It wouldn't surprise me in the least if every concrete function had some degree of weakness, and if finding that weakness requires vast computational resources, then we hardly need corrupt standards bodies to find them in advance.
Say NSA knows about a weakness --- perhaps something that requires an additional parameter check when receiving a point on a curve --- that comes up in only 1 out of every 1,000,000 generated curves of a particular form.
The worry is that NSA could come up with a set of possible "first principles" mathematical constants and search through 1,000,000 permutations of those constants to find that 1 weak curve. Then they'd write a standard suggesting that the permutation they chose follows naturally from mathematics, and their starting point was selected to be transparent and to guarantee that they hadn't manipulated the standard to weaken it. Obviously, they've done the very opposite thing, but the point of BADA55 is that you can manipulate standards surreptitiously this way.
The point isn't that it's possible to find weak curves. Of course it is possible to do that.
"More and more Internet traffic is encrypted.
This poses a threat to our society as it limits
the ability of government agencies to monitor
Internet communication for the prevention of
terrorism and globalized crime."
and then adds
"Fortunately, under reasonable assumptions,
it is feasible for agencies to fool users into
deploying cryptographic systems that the users
believe are secure but that the agencies are able
to break."
See the last section (Afterword: removing the hat):
First, in case this is not obvious to the reader, we do
not actually endorse the attacker's perspective. Our goal
in analyzing the security of systems is to prevent attacks.
I met Bernstein a few months ago after he gave a talk about this same subject. In his talk he pretended to be a Verizon employee, explaining how vital it is to him and his company that they can track what their users are doing on their network in order to improve their advertising services. (Without breaking character at any point, pretty impressive.) I guess it's easier to reason about these things when you're trying to break something, rather than trying to prevent it from happening.
Consider Dual_EC_DRBG: by all indications this was a "NOBUS" vulnerability (exploitable by "nobody but us") since the private key to unlock the backdoor had to be created at design time and wouldn't be recoverable by any other user of the system. With the NIST seed-hashing technique used to generate these curves, however, only a relatively small number of bits of structure can be forced in the result (assuming no preimage attack on SHA-1, which is still presumed difficult even now, let alone in 1999 when the curves were specified).
This more or less makes Jerry Solinas in the thought experiment resort to weakening the curve by forcing the choice into suitably large set of privately-known weak curves (which might only constitute 1 in a billion of the publicly acceptable curves). However, it's not possible for these attacks to insert enough structure for a Dual_EC style private key so they end up weak against all attackers (including other nation states) in theory if they can perform the same analysis. This (assuming that no one else has discovered the weak class of curves) is a very risky needle to thread when you are still recommending NIST-384 for use in protecting top secret information even now over 15 years later.