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 says that it provides "verifiably pseudo-random" curves along with "data that allow to verify that the curves were pseudo-randomly generated". However, the BADA55 Research Team has discovered that none of the standard Brainpool curves below 512 bits were generated by the standard Brainpool curve-generation procedure. Apparently the public never actually tried to verify the curves. This is an inspirational example, suggesting a simple strategy for subverting subsequent standards.
A different procedure that does generate the Brainpool curves appeared a few years later in the first Brainpool RFC. Draft 00 of this RFC in 2007, and draft 01 in early 2008, did not contain a procedure; a procedure was added to draft 02 upon request from Hal Finney. The RFC procedure is written in a totally different style from the standard procedure, so the difference in content is not immediately obvious.
The failure of the Brainpool standard procedure to generate the Brainpool standard curves does not appear to be discussed, or even mentioned, anywhere in the Brainpool RFCs or on the Brainpool web pages. There also do not appear to be any updates or errata to the Brainpool standard: version 1.0 of the standard (2005.10.19) is still the latest version available from the Brainpool web pages as of this writing (2015.09.27).
An earlier discovery (Bernstein and Lange, 2013) is that there is a highly nonrandom overlap of digits between the "pseudo-random" coefficients A and B in most of the Brainpool curves y^2 = x^3+Ax+B, as illustrated by the following example (underlines added):
Curve-ID: brainpoolP256r1 p: A9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377 A: 7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9 B: 26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6
Johannes Merkle, lead author of the Brainpool TLS RFC, writes "I admit that this is unfortunate."
Both of the above Brainpool issues (the visible nonrandomness, and the failure of the standard procedure to generate the standard curves) can be blamed on a rather complicated mechanism by which Brainpool decided which SHA-1 inputs to use for various portions of A and B. See the BADA55 paper, particularly Section 5, for a detailed analysis.
Verification scripts
The BADA55 Research Team has written an implementation in the Sage computer-algebra system, emphasizing simplicity and clarity, of the prime-generation and curve-generation procedures specified in the Brainpool standard; and, for comparison, an implementation of the procedure from the Brainpool RFC. There are actually three implementations of the standard procedure:
- brain224slow.sage: Follow the standard Brainpool procedure to generate a 224-bit curve, starting from knowing the 224-bit Brainpool prime. This does not generate the standard 224-bit Brainpool curve.
- brain224.sage: Slightly more complicated but much faster. Specifically, includes an "early abort" (using "division polynomials"), improving performance by an order of magnitude without changing the output.
- brainpool.sage: Follow the standard Brainpool procedure to generate seven primes and seven curves. This generates the standard 512-bit Brainpool curve but does not generate any of the smaller curves.
There are also three analogous implementations of the RFC procedure:
- brain224fixedslow.sage. This generates the standard 224-bit Brainpool curve.
- brain224fixed.sage. This generates the standard 224-bit Brainpool curve, faster.
- brainpoolfixed.sage. This generates all of the standard Brainpool curves.
Warning: For simplicity, these implementations skip checking a few security criteria that have negligible probability of failing, such as having large CM field discriminant.
Version: This is version 2017.01.22 of the "Brainpool curves" web page.