tl;dr: these are a joke on the NIST curves and the "verifiably random" way in which they were defined. While being safe curves, they've been tweaked to include the hex string "BADA55" in the "verifiably random" B constant derived using B=SHA3(seed). This demonstrates how other curve parameters could've been tweaked (by, say, the NSA) even in a "verifiably random" standard like the NIST curves.
At the same time these could conceivably serve as drop-in replacements for the NIST curves, but then people would have to recognize that djb is a BADA55.
Hurrah! Curves that have a cofactor of 1. (One of the things I didn't like about DJB's speed hacked curve25519…)
Since they share the same field as the NIST curves it also means that software won't need any other code for these.
I do wish they'd strengthened their verifyably random practices beyond the brainpool technique, instead of just complaining about it. :)
For example, they took their non-public nothing up my sleeve choice (C), then hashed it (H(C)) and announced H(C) and this procedure to the world, then put H(C) in a Bitcoin transaction and took M to be the block hash of the block 100 after the block confirming it (because it takes 2^66 sha256 operations to retry a single Bitcoin block if you don't like its outcome, and 100 after ensures that there would be a race with the public network), then picked their random seed as HMAC(M||next-week's NIST random beacon,C) you'd have a random value who's selection someone could only compromise by either inverting H() or controlling the announcing team, and controlling the NIST beacon, and doing 2^66 sha256 * the number of retries on that step (or compromising sha256 to make bitcoin mining trivial).
Someone interested in a serious, rather than derisive, attempt at selecting good curves with cofactor 1 may want to look at the recent paper by Bos, Costello, Longa and Naehrig[0].
Appears to be both. They're drop in replacements. There are plenty of reasons to argue against DJB's other curves (need different code, have some 'insecure' characteristics that other curves have specifically designed out (non-prime order), don't use a 'verifiably random' initialization, require special key selection (high bit must be 1) to be compatible with DJB's software— which precludes some key generation techniques like the homorphic public derivation used by some Bitcoin software, etc.).
These alternatives check all the boxes I'm aware of... and it makes fun of the verifiably random procedure.
"Verifiably random" is a strategy to obtain the property Bernstein terms "rigidity". Curve25519 uses a different strategy; from safecurves:
Prime chosen "as close as possible to a power of 2" for efficiency reasons ("save time in field operations"). Prime chosen "slightly below 32k bits, for some k" for efficiency reasons ("no serious concerns regarding wasted space"). k=8 chosen for "a comfortable security level". 2^255-19 chosen above 2^255+95, 2^255-31, 2^254+79, 2^253+51, 2^253+39 "because 19 is smaller than 31, 39, 51, 79, 95". Montgomery curve shape y^2=x^3+Ax^2+x chosen for efficiency ("to allow extremely fast x-coordinate point operations"). (A-2)/4 selected as a small integer for efficiency ("to speed up the multiplication by (A-2)/4"). Curve and twist orders required to be {4prime,8prime} for security ("protect against various attacks ... here 4, 8 are minimal"). Primes required to be above 2^252 for security ("theoretical possibility of a user's secret key matching the prime"), ruling out A=358990 and A=464586. A=486662 chosen as smallest positive integer meeting these requirements
Each of the parameters of the curve has a straightforward explanation; they're explainable from first-principles.
I'm not sure what the "non-prime order" objection you're describing is.
The leading 1-bit on the key prevents a potential timing attack.
The rest of your objections seem to boil down to "Curve25519 isn't a NIST curve, and NIST curve software doesn't naturally support it". That is indeed a valid objection if the only curve software you can use supports only the NIST curves.
> I'm not sure what the "non-prime order" objection you're describing is.
Curve25519 has a cofactor of 8— its order is prime*8. This directly reduces rho security by about 1.5 bits, and since many discrete log attacks exploit a composite order for further speed up almost all other requirement sets for curve selection (including NIST and Brainpool) have required curves to have a cofactor of 1 in an abundance of caution (a small cofactor isn't know to create weakness right now, except via the direct reduction against rho attacks, but its obviously prudent to ask the cofactor be 1 out of the same kind of caution that suggests building systems which are twist secure or not using fields of small characteristic).
> The leading 1-bit on the key prevents a potential timing attack.
Yes, it does. But the timing attack can be prevented another way (e.g. always doing that outer loop and throwing away the result is one example— using a bit interleaved precomputed table is another) but that is slower. The consequence here is that existing curve25519 implementations are incompatible with some very useful forms of key generation. The effect is that implementations must sacrifice either security (by not being able to use public key derivation techniques that improve security) or compatibility (by ending up with private keys that don't have the high bit set and being unable to use the widely distributed fast curve25519 code).
WRT the compatibility— it's not just about "only use the NIST curves", many things already have fast, well tested and reviewed constant time code for doing operations over the fields used by the NIST curves. The BADA55 curves curves instead would just be constant changes. It's a much smaller change than changing to something that uses a totally different field. This may be a consideration for some.
In the same way that VPR managed to find a very simple sounding transcendental constant that achieved the BADASS property the same sort of attack could potentially be employed against DJB's design criteria (though, admittedly, not a one in a million one). Not that I'm suggesting those curves are rigged, but several of his mandated criteria are very different than ones commonly used for purely performance reasons. At the same time DJB doesn't like SECP256k1 which has an almost identical design strategy because it achieved performance in a different way (though also a way that gives up about 1.5 bits of rho security).
Aren't you oversimplifying here, like, a lot? All things being equal, you want a cofactor of 1. But all things aren't equal; you also want a performant curve, which is hard to get with a curve with a cofactor of 1.
What you actually care about is the attacker effort using Pollard's Rho taking into account the whole curve and all its parameters. Which, on Curve25519, is 2^126; that's not "spinal tap grade security", but the dial there is turned at least u to "10".
More importantly: this isn't how curve software is actually going to be attacked. NIST P-224 twist security is much more important than whether you have 2^126 or 2^259 vs. Rho. This cofactor discussion seems to me a little like debating whether attackers are going to factor RSA-3072 or RSA-4096.
(Note that Hamburg's "Goldilocks" curve has a cofactor of 4.)
I'm not sure I want to dig into the "rigidity" of BADA55 vs. SECP256k1, except to say that the NIST p- curves have a much bigger rigidity flaw than the other 3 options we're discussing.
> The effect is that implementations must sacrifice either security (by not being able to use public key derivation techniques that improve security) or compatibility (by ending up with private keys that don't have the high bit set and being unable to use the widely distributed fast curve25519 code).
How does that follow? I'm not a crypto expert, but I would think you would derive your keys whichever way you want, except at length one bit shorter, and then add the '1' bit; Or, equivalently, derive it at the length you want and then set the top bit to 1. If your KDF is foiled by reducing one bit of information from the output, wasn't it bad to start with?
If I didn't know any better, reading your posts I'd think Curve25519/SafeCurves were haphazardly thrown together in the name of performance, yet in the end were roughly the same speed as the highly secure NIST curves.
What these guys just did here is actually a very clever idea in another way. Suppose that there exists a weakness in 1 in 2^30 curves, and each curve takes 2^10 steps to generate. If they picked seeds NIST style (or even using cos(1), exp(cos(1)), sin(sha3(5)) or other permutations) then they would be able to find a weak curve in 2^40 steps. Here, however, they're adding another trivial property, namely presence of BADA55EC at the start of B, which only 1 in 2^32 curves have. Hence, this increases the difficulty of finding a malicious curve to 2^72, which is actually pretty close to what many people consider a secure cryptographic safety margin.
My preference would be to not bother with such tricks and adopt a standard for nothing-up-my-sleeve numbers (eg. find the lowest N such that sha(N) results in desirable properties) to avoid people from end-running around the whole concept with prime square roots, cosines, exp and log and the like, but this is still an interesting concept.
At the same time these could conceivably serve as drop-in replacements for the NIST curves, but then people would have to recognize that djb is a BADA55.