SafeCurves: |
|
BADA55 elliptic curvesThis page has been superseded by bada55.cr.yp.to. You will be redirected there in 10 seconds. This page introduces four elliptic curves at three different security/performance levels:
BADA55-VRVerifiably 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:
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-256BADA55-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-224BADA55-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-384BADA55-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-VPRThe 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:
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-224Brainpool 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 securityThe 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. ContributorsBADA55 is joint work by the following authors (alphabetical order):
SlidesThe 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: https://cr.yp.to/papers.html#bada55. Date: 2014.07.22. AcknowledgmentsThis 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:
Version: This is version 2017.01.22 of the bada55.html web page. |