BADA55 Crypto
Introduction Scripts New VR curves Brainpool curves New VPR curves Papers and slides
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:

There are also three analogous implementations of the RFC procedure:

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.