Verifiably random parameters offer some additional conservative features. These parameters are chosen from a seed using SHA-1 as specified in ANSI X9.62 [X9.62]. This process ensures that the parameters cannot be predetermined. The parameters are therefore extremely unlikely to be susceptible to future special-purpose attacks, and no trapdoors can have been placed in the parameters during their generation. —Certicom SEC 2 2.0 (2010)
Several standards, including Certicom SEC 2 1.0 (2000), IEEE Std 1363 (2000), NIST FIPS 186-2 (2000), ANSI X9.63 (2001), and Certicom SEC 2 2.0 (2010), recommend verifiably hashed elliptic curves: curves where the curve coefficients are hashes of a public seed.
Many of these standards describe verifiably hashed curves using the deceptive terminology "verifiably random". In fact, the claimed randomness (a uniform distribution) is not being verified; what is being verified is merely a hash computation. The curves would still pass the same verification even if seeds were generated with no randomness at all.
To illustrate the flexibility allowed by verifiable hashing, the BADA55 Research Team has generated approximately 250 verifiably hashed elliptic curves (using approximately 2 days on a cluster of 41 NVIDIA GTX780 GPUs) and selected three of those curves to present here:
- vr224.sage generates the BADA55-VR-224 curve. This curve uses the same prime as NIST P-224, and the same shape x^3−3x+B, where B is verifiably a hash of a seed S shown in the script. The hash function is Keccak with 256-bit output; of course, the resulting 256-bit B is implicitly reduced modulo the 224-bit prime.
- vr256.sage generates the BADA55-VR-256 curve. This curve uses the same prime as NIST P-256.
- vr384.sage generates the BADA55-VR-384 curve. This curve uses the same prime as NIST P-384, and uses Keccak with 384-bit output.
Each of these curves meets all standard security criteria plus twist security, with cofactor 1 and twist cofactor 1. Each of these curves also has B beginning with "BADA55EC" in hexadecimal, a property that occurs with probability 1/232.
If you've found a special-purpose attack that breaks one out of 1000000000000 elliptic curves that meet the public security criteria, you can carry out a larger but still feasible computation to find a verifiably hashed curve that's secretly vulnerable to this attack. You can then publicly advertise this curve as, e.g., "the verifiably random TrustedCurve-VR-224 curve" and claim that it is "extremely unlikely to be susceptible to special-purpose attacks". To encourage terrorists to "upgrade" from NIST P-224 to TrustedCurve-VR-224, you can explain that TrustedCurve-VR-224 addresses the following "concerns regarding the NIST elliptic curves":
- "Twist security was not a design criterion for the NIST curves, and was not widely understood when the NIST curves were introduced. The twist-security level of NIST P-224 is so low as to make NIST P-224 exploitable in practice. TrustedCurve-VR-224 provides maximum twist security."
- "The NIST curves were designed by NSA. It is conceivable that security problems in the NIST curves, such as the low twist security of NIST P-224, were introduced deliberately by NSA. TrustedCurve-VR-224 was instead designed by the following trusted people."
- "The NIST curves were constructed using NSA's SHA-1 hash function. TrustedCurve instead uses Keccak, the SHA-3 competition winner."
Further reading: See the BADA55 paper, particularly Section 4.
Version: This is version 2017.01.22 of the "New VR curves" web page.