SafeCurves:
choosing safe curves for elliptic-curve cryptography


Introduction
Curve parameters:
Fields
Equations
Base points
Prime proofs
ECDLP security:
Rho
Transfers
Discriminants
Rigidity
ECC security:
Ladders
Twists
Completeness
Indistinguishability
More information:
References
Verification

BADA55 elliptic curves

This page introduces four elliptic curves at three different security/performance levels:

  • BADA55-VR-224 and BADA55-VPR-224 are designed as replacements for NIST P-224.
  • BADA55-VR-256 is designed as a replacement for NIST P-256.
  • BADA55-VR-384 is designed as a replacement for NIST P-384.

BADA55-VR

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), ANSI X9.63 (2001), and Certicom SEC 2 2.0 (2010), recommend "verifiably random" elliptic curves, where "verifiably random" means that the curve coefficients are hashes of a public seed. The NIST elliptic curves are "verifiably random".

The BADA55-VR curves are also "verifiably random". They are designed to address 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.
  • 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.
  • The NIST curves were constructed using NSA's SHA-1 hash function.

The BADA55-VR curves are "verifiably random" using the SHA-3 competition winner Keccak rather than SHA-1. They are twist-secure, with cofactor 1 and twist cofactor 1. They use the same primes as the NIST curves, and the same curve shape x^3−3x+B; there are no known ways for discrete-logarithm attacks to exploit those primes.

BADA55-VR-256

BADA55-VR-256 uses Keccak with 256-bit output (keccakc512). The BADA55-VR-256 curve x^3−3x+B is defined from a seed S by the formula B=H(S), where H is the hash function. New seeds were generated until a curve was found meeting all security criteria.

The following Sage script includes the seed S and verifies that x^3−3x+B passes the standard security criteria (with cofactor 1), plus twist-security (with cofactor 1):

     S = 0x3ADCC48E36F1D1926701417F101A75F000118A739D4686E77278325A825AA3C6
     B = 0xBADA55ECD8BBEAD3ADD6C534F92197DEB47FCEB9BE7E0E702A8D1DD56B5D0B0C
     # not verified in this script: B is keccakc512 hash of S
     p = 2^256 - 2^224 + 2^192 + 2^96 - 1    
     k = GF(p)
     E = EllipticCurve([-3,k(B)])
     n = E.cardinality()
     print n != p
     print n.is_prime()
     print (2*p+2-n).is_prime()
     print Integers(n)(p).multiplicative_order() * 100 >= n-1
     print Integers(2*p+2-n)(p).multiplicative_order() * 100 >= 2*p+2-n-1
     cmdisc = ((p+1-n)^2-4*p).squarefree_part()
     if cmdisc % 4 != 1: cmdisc *= 4
     print -cmdisc > 2^100

BADA55-VR-224

BADA55-VR-224 uses the same hash function as BADA55-VR-256 but uses a smaller prime; of course, B is implicitly reduced modulo the prime. Sage script:

     S = 0x3CC520E9434349DF680A8F4BCADDA648D693B2907B216EE55CB4853DB68F9165
     B = 0xBADA55ECFD9CA54C0738B8A6FB8CF4CCF84E916D83D6DA1B78B622351E11AB4E
     # not verified in this script: B is keccakc512 hash of S
     p = 2^224 - 2^96 + 1
     k = GF(p)
     E = EllipticCurve([-3,k(B)])
     n = E.cardinality()
     print n != p
     print n.is_prime()
     print (2*p+2-n).is_prime()
     print Integers(n)(p).multiplicative_order() * 100 >= n-1
     print Integers(2*p+2-n)(p).multiplicative_order() * 100 >= 2*p+2-n-1
     cmdisc = ((p+1-n)^2-4*p).squarefree_part()
     if cmdisc % 4 != 1: cmdisc *= 4
     print -cmdisc > 2^100

BADA55-VR-384

BADA55-VR-384 is similar to BADA55-VR-256 but uses a larger prime. 256-bit output is not long enough so BADA55-VR-384 instead uses Keccak with 384-bit output (keccakc768). Sage script:

     S = 0xCA9EBD338A9EE0E6862FD329062ABC06A793575A1C744F0EC24503A525F5D06E
     B = 0xBADA55EC3BE2AD1F9EEEA5881ECF95BBF3AC392526F01D4CD13E684C63A17CC4D5F271642AD83899113817A61006413D
     # not verified in this script: B is keccakc768 hash of S
     p = 2^384 - 2^128 - 2^96 + 2^32 - 1
     k = GF(p)
     E = EllipticCurve([-3,k(B)])
     n = E.cardinality()
     print n != p
     print n.is_prime()
     print (2*p+2-n).is_prime()
     print Integers(n)(p).multiplicative_order() * 100 >= n-1
     print Integers(2*p+2-n)(p).multiplicative_order() * 100 >= 2*p+2-n-1
     cmdisc = ((p+1-n)^2-4*p).squarefree_part()
     if cmdisc % 4 != 1: cmdisc *= 4
     print -cmdisc > 2^100

BADA55-VPR

The choice of the seeds from which the [NIST] curve parameters have been derived is not motivated leaving an essential part of the security analysis open. ... Verifiably pseudo-random. The [Brainpool] curves shall be generated in a pseudo-random manner using seeds that are generated in a systematic and comprehensive way. Our method of construction is explained in Section 5. —Brainpool standard (2005)

The Brainpool standard criticizes the NIST curves for the non-"motivated" choice of seeds and instead recommends "verifiably pseudorandom" curves using "systematic" choices of seeds. The standard specifies various curves x^3+Ax+B mod p where A and B are generated as hashes of seeds derived from e = exp(1), the base of natural logarithms, and p is generated as a hash of a seed derived from π. However, the method used to generate the Brainpool curves has come into question, as illustrated by the obviously nonrandom overlap of digits between the following coefficients A and B (underlines added):

     Curve-ID: brainpoolP256r1
     p: A9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377
     A: 7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9
     B: 26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6

Here is how this overlap was produced. Brainpool uses SHA-1, which generates only 160 bits, so Brainpool concatenates multiple SHA-1 outputs to obtain A, and concatenates multiple SHA-1 outputs to obtain B. Brainpool uses a single seed-increment function to search for the first secure curve, to move from the first part of A to the second part of A, and to move from A to B. (The complete procedure is more complicated and does not always produce the same type of overlap; see the Brainpool standard for full details.) Johannes Merkle, lead author of the Brainpool TLS RFC, writes "I admit that this is unfortunate."

The BADA55-VPR curves are "verifiably pseudorandom" curves as recommended by Brainpool, with "systematic and comprehensive" explanations for their seeds. The BADA55-VPR curves are designed to address the following concerns regarding the Brainpool curves:

  • Twist-security was not a design criterion for the Brainpool curves. The twist-security level of, e.g., the 256-bit Brainpool curve is so low as to make that curve exploitable in practice.
  • Brainpool uses NSA's SHA-1 hash function.
  • As shown above, Brainpool does not properly separate the hash inputs used for A and B.

The BADA55-VPR curves use maximum-security full-length SHA-3-512 (adequate for any reasonable prime size without concatenation), and complement the A seed to obtain a B seed that is guaranteed to be different.

BADA55-VPR-224

Brainpool already uses exp(1) = e and arctan(1) = π/4 (π and π/4 are equivalent here since bits are taken starting from the most significant), and MD5 already uses sin(1), so BADA55-VPR-224 uses cos(1). BADA55-VPR-224 generates the full 160-bit seed as a 32-bit counter followed by cos(1). It uses the first counter value that produces a secure curve. Sage script:

     cos1 = 0x8A51407DA8345C91C2466D976871BD2A
     print cos1 == Integer(RealField(128)(cos(1))*2^128)
     S = 0x000000B88A51407DA8345C91C2466D976871BD2A
     print S == 184*2^128 + cos1
     # not verified by this script: 184 is first counter giving secure curve
     T = 0xFFFFFF4775AEBF8257CBA36E3DB99268978E42D5
     print S+T == 2^160-1
     A = 0x7144BA12CE8A0C3BEFA053EDBADA555A42391FC64F052376E041C7D4AF23195EBD8D83625321D452E8A0C3BB0A048A26115704E45DCEB346A9F4BD9741D14D49
     # not verified in this script: A is hash of S
     B = 0x5C32EC7FC48CE1802D9B70DBC3FA574EAF015FCE4E99B43EBE3468D6EFB2276BA3669AFF6FFC0F4C6AE4AE2E5D74C3C0AF97DCE17147688DDA89E734B56944A2
     # not verified in this script: B is hash of T
     p = 2^224 - 2^96 + 1
     k = GF(p)
     E = EllipticCurve([k(A),k(B)])
     n = E.cardinality()
     print n != p
     print n.is_prime()
     print (2*p+2-n).is_prime()
     print Integers(n)(p).multiplicative_order() * 100 >= n-1
     print Integers(2*p+2-n)(p).multiplicative_order() * 100 >= 2*p+2-n-1
     cmdisc = ((p+1-n)^2-4*p).squarefree_part()
     if cmdisc % 4 != 1: cmdisc *= 4
     print -cmdisc > 2^100

Notes on terminology and security

The name "BADA55" (pronounced "bad-ass") is explained by the appearance of the string BADA55 near the beginning of each BADA55 curve. This string is underlined in the Sage scripts above.

We actually chose this string in advance and then manipulated the curve choices to produce this string. The BADA55-VR curves illustrate the fact that, as pointed out by Scott in 1999, "verifiably random" curves do not stop the attacker from generating a curve with a one-in-a-million weakness. The BADA55-VPR curves illustrate the fact that "verifiably pseudorandom" curves with "systematic" seeds generated from "nothing-up-my-sleeve numbers" also do not stop the attacker from generating a curve with a one-in-a-million weakness.

We do not assert that the presence of the string BADA55 is a weakness. However, with a similar computation we could have selected a one-in-a-million weakness and produced curves with that weakness. Suppose, for example, that twist attacks were not publicly known but were known to us; a random 224-bit curve has one chance in a million of being extremely twist-insecure (attack cost below 2^30), and we could have generated a curve with this property, while pretending that this was a "verifiable" curve generated for maximum security.

We view the terminology "verifiably random" as deceptive. The claimed randomness (a uniform distribution) is not being verified; what is being verified is merely a hash computation. We similarly view the terminology "verifiably pseudorandom" and "nothing up my sleeves" as deceptive.

Contributors

BADA55 is joint work by the following authors (alphabetical order):

Slides

The following presentation was given by Bernstein and Lange at the Eurocrypt 2014 rump session: (PDF)

Papers

[bada55] 18pp. (PDF) Daniel J. Bernstein, Tung Chou, Chitchanok Chuengsatiansup, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Christine van Vredendaal. How to manipulate curve standards: a white paper for the black hat. Document ID: bada55ecd325c5bfeaf442a8fd008c54. URL: http://cr.yp.to/papers.html#bada55. Date: 2014.07.22.

Acknowledgments

This work was supported by the U.S. National Science Foundation under grant 1018836. "Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation."

This work was supported by the Netherlands Organisation for Scientific Research (NWO) under grant 639.073.005.

This work was supported by the European Commission under Contract INFSO-ICT-284833 PUFFIN.

Calculations were carried out on two GPU clusters:

  • The Saber cluster at Technische Universiteit Eindhoven.
  • The K10 cluster at the University of Haifa, funded by ISF grant 1910/12.

Version: This is version 2014.07.23 of the bada55.html web page.