Re: [Cfrg] ECC reboot (Was: When's the decision?)

Dear Tanja,

please allow me to answer your question. I have repeatedly expressed my feeling that the discrediting of the Brainpool
curves by the BAD55 paper is wrongful and unfair.

First of all, I would like to emphasize that I was not involved in the generation of the Brainpool curves, as I started
participating in the Brainpool group not before end of 2005. (I don't need to tell you that, as you had been a Brainpool
member in that time but others on this list will not know.)

In your paper, you explain, how you were able to create an elliptic curve with a BADA55 string in the coefficient a: As
you put it, the basic idea was "to try all possible combinations of hash functions, seed length, initial seed constant,
and so on, until he [Jerry] finds a curve that exhibits the desired vulnerability." Thus, you chose a general with
design variations that result in almost 20 bits of freedom or, equivalently, almost 2^20 combinations. According to your
paper, the following variations were used:
- 73 natural constants
- 10 different hash functions.
- 6 block size configurations of the hash function
- 2 endian-formats for the seed
- 5 counter lengths for the seed update function
- 2 orders for the concatenation of counter and seed
- 2 methods of shortening the seed to the right length
- 8 "different ways to update the counter between generation of a and b and to choose the order of generating a and b"

While your approach is scientifically sound and ingenious, I object to the conclusion that it is comparable to the
approach taken for the Brainpool curves. In this case, the number of plausible variations is much smaller:

1. Choice of the natural constants.  Brainpool curves used Pi to generate the primes and e to generate the curve
coefficients. Apart from 0, 1 and 2, or i, these are by far the most prominent mathematical constants. Period. It
doesn't matter what constants are used in some hash or symmetric encryption functions (where mathematical theory is much
less prevalent than in asymmetric crypto); when it comes to rigidity and trust, you have to choose the most natural
looking, obvious seeds.
If you ask a random mathematician about which constant is most prominent, you will get Pi as an answer with overwhelming
probability, and on second place, there will almost certainly be e. For instance,
http://en.wikipedia.org/wiki/Mathematical_constant lists these two as the first in the list of mathematical constants,
and only two others (sqrt(2) and i) as "Common mathematical constants". Nobody would answer  zeta(3), zeta(5), sin(1),
sin(2), cos(1), cos(2), tan(1), tan(2), sqrt(3), sqrt(5), sqrt(7), log(2), or any of their reciprocals, very few would
respond with the Euler–Mascheroni gamma (or any other like listed in Wikipedia as "Constants in advanced mathematics").
The golden ratio phi = (1 + sqrt(5))/2 is certainly quite prominent, but without doubt, the numbers Pi and e are by far
more "fundamental" in that they appear in so many important results. Leaves only sqrt(2) as an alternative choice;
however, sqrt(2) is algebraic, and transcendental numbers are widely felt as being less comprehensible and structured.
(Also, one could argue that deriving seeds from algebraic numbers may give it a "bad small" for the generation of
algebraic curves, but this is a weak argument as the hash function should destroy any algebraic relation.)
The conclusion is that even if you are willing to accept sqrt(2) and the golden ratio as comparably prominent and
eligible as e, Pi is outstanding and, thus, I could only imagine Pi alone, Pi+e, Pi+phi, Pi+sqrt(2), as well as reversed
orders of the combinations as being an acceptably obvious choice. This makes 7 choices, as compared to 73.

2. Choice of hash function. The Brainpool members used the approach of ANSI X9.62 to derive integers from the seeds.
This was (and is) by far the most relevant standard for elliptic curves, and I can see no reason to deviate from that
method; for a PRNG, SHA-1 was (and still is) sufficiently secure [1]. Thus, although SHA-2 was already standardized in
that time, there was no reason to change the hash function. Beside from deviating from the existing standard, using
SHA-2 would have implied additional options w.r.t the output length, which is undesirable for rigidity. IMHO, anything
else than SHA-1 would have looked less plausible. Thus, I do not really see any freedom here.

3. Seed length. ANSI X9.62 requires the seeds to be at least 160 bits long. This requirement is implied by the output
length of SHA-1. In fact, all seeds used for the NIST curves had exactly 160 bits. Again, there as no reason to deviate
from this existing example, thus, using 160 bit was the most natural choice. In addition, where there is no maximum, the
minimum is the only distinguished value.

4. Block size configurations of the hash function. This configuration option is not available for SHA-1 (and, BTW, not
for SHA-2 either).

5. Endian-formats for the seed. The Brainpool group used the same integer representation as ANSI X9.62 and all other
relevant standards for elliptic curves. IMO, any deviation would have looked suspicious.

6. Counter lengths for the seed update function. I don't know, if the option of a dedicated counter had been considered
by the Brainpool group, but for me using a counter in addition to the seeds adds unnecessary flexibility and is, thus,
undesirable.

7. Orders for the concatenation of counter and seed. No counter, no order.

8. Methods of shortening the seed to the right length. To me, the idea of rounding sounds quite unusual in the context
of cryptographic derivation functions. But to be fair, I admit that the expansion of the constants by 1120 bits, e.g.,
setting Seed = 2^1120*Pi, and the subsequent truncation of one nibble at the right hand side gives a few options. They
could have set Seed = 2^1118*Pi, which would have eliminated the need for truncation. Or they could have truncated on
the left hand side. If we add the two options of ordering the seeds according to the individual bit lengths (Seed_160 on
the left side and Seed_512 on the ride hand side, or vice-versa), we get 6 options.

9. Method to update the counter between generation of a and b and to choose the order of generating a and b. The natural
order of a and b is given by the alphabet, and, IMO, reversing this in the generation method would look a bit
artificial. For updating the seed after generation of b, the Brainpool method simply uses the seed update function. This
is the simplest approach, which is generally preferable for rigidity. But lets assume that applying the hash function s
-> h(s) was also an option, which makes 2 options.

10. There is an additional source of flexibility: It has been observed (initially in RFC 5639) that the derivation
method differs from that in ANSI X9.62 in that both coefficients are derived directly from the seeds, whereas ANSI
derives just r = a^3/b^2 mod p and leaves definition of a and b open. As explained in RFC 5639, the objective of the
Brainpool members was to generate for each bit length two isomorphic curves, one with random a and one with a=-3. The
motivation behind this was that random coefficients may facilitate avoiding patents in implementations. Since the ANSI
method does not specify how to obtain a verifiably pseudo-random a, a deviation seems unavoidable to achieve this
objective. And the most simple approach is to generate a and b using the same method as specified by ANSI for r. And by
the way, the same method (with different seed) was also used to generate the prime p.

When I multiply all the options, I get 7*6*2=84 options. Even if you don't agree with all my statements above and add
some options at one aspect or the other, there is a big difference to the estimation of 1.4 million possibilities
estimated in your paper. Furthermore, in all aspects where flexibility was possible, the choice of the Brainpool group
was among the simplest and most plausible. Of course, any assessments of plausibility is subjective and can be
controversially discussed - presumably without reaching consensus.

On the other hand, the approach taken for the Curve25519, i.e. to choose minimal coefficients, is also not 100% rigid.
In his Curve25519 paper, Dan writes:
> I rejected A = 358990 because one of its primes is slightly smaller
> than 2^252, raising the question of how standards and implementations should
> handle the theoretical possibility of a user's secret key matching the prime;
> discussing this question is more difficult than switching to another A. I rejected
> 464586 for the same reason. So I ended up with A = 486662.

These are valid arguments but, nevertheless, the conclusion is subjective. Furthermore, Bos, Costello, Longa, and
Naehrig, took quite the same approach and arrived at different curves (the NUMS curves), even at different primes. As
they write, "Full rigidity is virtually impossible in practice" [2]. I fully agree with that.

The best approach to address this is to openly discuss (with open outcome) the generation method in a large audience of
interested parties. This exactly was done in the ECC Brainpool, which is an open group which everybody (even private
persons) can join without registration, feed, or restrictions, and which includes virtually all stakeholders of ECC
standardization in Germany. In this open forum, the generation method was presented and discussed, and there was a
consensus that it is eligible. Actually, you know that better than me, because you had been an active member at that
time and you participated these discussions.

All the more, I was surprised to find you among the authors of the BADA55 paper, which, IMHO, casts a damning light of
suspicion on the Brainpool curves. And Dan's statement on this list is even more explicit in that:

> However, the following recent analysis shows that the Brainpool curves,
> which were advertised as "generated in a systematic and comprehensive
> way" covering several different security levels, actually gave the curve
> generator the flexibility to secretly choose from among more than
> 1000000 curves for any particular prime:

I have already met users (with limited knowledge in cryptology) telling me they have read that the Brainpool curves are
not trustworthy. Considering the process that had been taken by the Brainpool group, this statement is unjustified and
misleading, and considering that the curves are already rolled out in more than 50 million national ID cards and
passports, this damage of reputation is very serious.

I fully respect your scientific work in the area of elliptic curves and your contribution to the current standardization
effort, but consider the impact of your paper to the reputation of the Brainpool curves as very unfortunate.

Best regards,
Johannes

[1] NIST Special Publication 800-57. Recommendation for Key Management – Part 1: General (Revision 3). 2012
[2] J. Bos, C. Costello, P. Longa, and M. Naehrig: Selecting Elliptic Curves for Cryptography - A presentation for the
Crypto Forum Research Group (CFRG).
http://patricklonga.webs.com/Presentation_CFRG_Selecting_Elliptic_Curves_for_Cryptography.pdf

Tanja Lange wrote on 21.10.2014 13:40:
> Dear Manfred,
> 
> On Tue, Oct 21, 2014 at 11:27:52AM +0200, Lochter, Manfred wrote:
>> b) The original Brainpool curves have falsely been discredited  in the 
>> BADA55-paper.
>>
> 
> What do you claim to be false in that paper?
> 
> We show -- and as far as I know are the first to show -- that the
> approach to generate the BP curves allows the designer of that
> approach to hide a one-in-a-million weakness in the resulting 
> curve, should he or she have found such a weakness.
> 
> Regards
> 	Tanja
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
> 
> 
-- 
Viele Grüße,
Johannes Merkle