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

Johannes Merkle <johannes.merkle@secunet.com> Thu, 23 October 2014 09:47 UTC

Return-Path: <Johannes.Merkle@secunet.com>

X-Original-To: cfrg@ietfa.amsl.com

Delivered-To: cfrg@ietfa.amsl.com

Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3E9761A8A40 for <cfrg@ietfa.amsl.com>; Thu, 23 Oct 2014 02:47:10 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: 0.69

X-Spam-Level:

X-Spam-Status: No, score=0.69 tagged_above=-999 required=5 tests=[BAYES_50=0.8, J_CHICKENPOX_21=0.6, RCVD_IN_DNSWL_LOW=-0.7, T_RP_MATCHES_RCVD=-0.01] autolearn=ham

Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id z7_Db6c1K6bS for <cfrg@ietfa.amsl.com>; Thu, 23 Oct 2014 02:47:06 -0700 (PDT)

Received: from a.mx.secunet.com (a.mx.secunet.com [195.81.216.161]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8A2141A8A42 for <cfrg@irtf.org>; Thu, 23 Oct 2014 02:47:05 -0700 (PDT)

Received: from localhost (alg1 [127.0.0.1]) by a.mx.secunet.com (Postfix) with ESMTP id 812B41A008B; Thu, 23 Oct 2014 11:46:57 +0200 (CEST)

X-Virus-Scanned: by secunet

Received: from a.mx.secunet.com ([127.0.0.1]) by localhost (a.mx.secunet.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id agrQjthHGxo6; Thu, 23 Oct 2014 11:46:53 +0200 (CEST)

Received: from mail-essen-01.secunet.de (unknown [10.53.40.204]) by a.mx.secunet.com (Postfix) with ESMTP id 643981A0087; Thu, 23 Oct 2014 11:46:53 +0200 (CEST)

Received: from [10.208.1.76] (10.208.1.76) by mail-essen-01.secunet.de (10.53.40.204) with Microsoft SMTP Server (TLS) id 14.3.210.2; Thu, 23 Oct 2014 11:46:58 +0200

Message-ID: <5448CE92.6080903@secunet.com>

Date: Thu, 23 Oct 2014 11:46:58 +0200

From: Johannes Merkle <johannes.merkle@secunet.com>

User-Agent: Mozilla/5.0 (Windows NT 6.1; rv:24.0) Gecko/20100101 Thunderbird/24.6.0

MIME-Version: 1.0

To: Tanja Lange <tanja@hyperelliptic.org>

References: <D065A817.30406%kenny.paterson@rhul.ac.uk> <201410211027.13608.manfred.lochter@bsi.bund.de> <20141021090529.GA12154@LK-Perkele-VII> <201410211127.53008.manfred.lochter@bsi.bund.de> <20141021114003.GZ5502@cph.win.tue.nl>

In-Reply-To: <20141021114003.GZ5502@cph.win.tue.nl>

Content-Type: text/plain; charset="windows-1252"

Content-Transfer-Encoding: 8bit

X-Originating-IP: [10.208.1.76]

X-EXCLAIMER-MD-CONFIG: 2c86f778-e09b-4440-8b15-867914633a10

Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/yyZ8LiE8m_U243vzEcJVC7JQTmk

Cc: cfrg@irtf.org

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

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.15

Precedence: list

List-Id: Crypto Forum Research Group <cfrg.irtf.org>

List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>

List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>

List-Post: <mailto:cfrg@irtf.org>

List-Help: <mailto:cfrg-request@irtf.org?subject=help>

List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>

X-List-Received-Date: Thu, 23 Oct 2014 09:47:10 -0000

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

- Re: [Cfrg] ECC reboot (Was: When's the decision?) Paterson, Kenny
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Johannes Merkle
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Paterson, Kenny
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Ilari Liusvaara
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Alyssa Rowan
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Andy Lutomirski
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Ilari Liusvaara
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Alyssa Rowan
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Johannes Merkle
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Alyssa Rowan
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Ilari Liusvaara
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Johannes Merkle
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Hallof, Andreas
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Manuel Pégourié-Gonnard
- Re: [Cfrg] ECC reboot (Was: When's the decision?) David Leon Gil
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Hallof, Andreas
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Watson Ladd
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Michael Hamburg
- Re: [Cfrg] ECC reboot (Was: When's the decision?) David Leon Gil
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Phillip Hallam-Baker
- Re: [Cfrg] Hardware requirements, Brainpool (was:… Alyssa Rowan
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Michael Hamburg
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Stephen Farrell
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Watson Ladd
- Re: [Cfrg] ECC reboot James Cloos
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Phillip Hallam-Baker
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Benjamin Black
- Re: [Cfrg] ECC reboot Benjamin Black
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Michael Hamburg
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Watson Ladd
- Re: [Cfrg] ECC reboot Rob Stradling
- Re: [Cfrg] ECC reboot Alyssa Rowan
- [Cfrg] W3C WebCrypto WG Liasioning [was Re: ECC r… Harry Halpin
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Lochter, Manfred
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Ilari Liusvaara
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Lochter, Manfred
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Tanja Lange
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Alyssa Rowan
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Lochter, Manfred
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Alyssa Rowan
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Johannes Merkle
- Re: [Cfrg] ECC reboot Rob Stradling
- Re: [Cfrg] ECC reboot (Was: When's the decision?) Ilari Liusvaara
- Re: [Cfrg] ECC reboot Watson Ladd
- Re: [Cfrg] ECC reboot Phillip Hallam-Baker
- Re: [Cfrg] ECC reboot Phillip Hallam-Baker
- Re: [Cfrg] ECC reboot Alyssa Rowan
- Re: [Cfrg] ECC reboot Andy Lutomirski
- Re: [Cfrg] ECC reboot Phillip Hallam-Baker
- Re: [Cfrg] ECC reboot Andy Lutomirski
- Re: [Cfrg] ECC reboot Ilari Liusvaara
- Re: [Cfrg] ECC reboot Michael Hamburg
- Re: [Cfrg] ECC reboot Rob Stradling
- Re: [Cfrg] ECC reboot Phillip Hallam-Baker
- Re: [Cfrg] ECC reboot Andy Lutomirski
- Re: [Cfrg] ECC reboot Watson Ladd
- Re: [Cfrg] ECC reboot Samuel Neves
- Re: [Cfrg] ECC reboot Michael Hamburg
- Re: [Cfrg] ECC reboot Michael Hamburg
- Re: [Cfrg] ECC reboot Ilari Liusvaara