BADA55: safe curves for elliptic-curve cryptography
safecurves.cr.yp.to
safecurves.cr.yp.to
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.
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).
The point I believe is that you still need to retry until you find a "safe curve" and they found the BADA55-VPR-224 A tweaking that.
Or am I missing something that made it easier?
video: https://www.youtube.com/watch?v=maBOorEfOOk (audio kinda broken)
slides: http://cr.yp.to/talks/2014.05.13/slides-dan+tanja-20140513-4...
These alternatives check all the boxes I'm aware of... and it makes fun of the verifiably random procedure.
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.
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).
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.
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?
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.