This post discusses the security of NIST prime curves (i) given the compromised status of Dual_EC_DRBG, (ii) and in light recent announcements from the NSA’s IAD which can be found here:

https://www.nsa.gov/ia/programs/suiteb_cryptography/

Interestingly, the agency has also stated that “With respect to IAD customers using large, unclassified PKI systems, remaining at 112 bits of security (i.e. 2048-bit RSA) may be preferable (or sometimes necessary due to budget constraints) for the near-term in anticipation of deploying quantum resistant asymmetric algorithms upon their first availability”.

The intent of this post is to try and question some theories around deliberate specification of weak curves  by selection of “weak seed” inputs to the SHA-1 function as part of the ANSI / NIST curve generation process. The reasoning presented expands on implied requirements around the number of weak curves that must exist over 256 bit prime fields in order for such theories to hold.

Weak Curves:

It is widely known that certain classes of “weak curves” exist where the standard ECDLP problem is reduced to a simpler problem. For example, attacks on curves which leverage pairings are documented in the literature. Such attacks leverage bilinear maps \langle \cdot,\cdot\rangle: \mathbb{G}_{1}\times \mathbb{G}_{2} \rightarrow \mathbb{J} from abelian groups \mathbb{G}_{1} and \mathbb{G}_{2} that evaluate to elements in some other abelian group \mathbb{J}. For the Weil and Tate pairings, we map from groups in E(\mathbb{F}_{p^{k}}) to a multiplicative group \mathbb{F}^{*}_{p^{k}} where  \mathbb{F}_{p^{k}} is some finite extension of \mathbb{F}_{p} with k > 1. Pairings, when applied to so called supersingular curves with embedding degree less than 6, reduce standard ECDLP to the sub exponential DLP in multiplicative groups. Another case of weak curves are the so called prime field anomolous curves with \sharp E(\mathbb{F}_{p}) = p, though in general we don’t expect such an equality to hold (On the other hand, the so called Hasse bound tells us that the most that \sharp E(\mathbb{F}_{p}) can differ from p + 1 is by the trace of Frobenius t where \mid t \mid \le 2 \sqrt{p})

Koblitz and Menezes (KM2015):

For the rest of this post, we’ll dissect some parts of a post Snowden defense of ECC authored by Koblitz and Menezes, two mathematicians of high repute (Koblitz in particular is the co-inventor of elliptic curve cryptography, author of the landmark text “A Course in Number Theory and Cryptography”, and noted sceptic of reductionist methods / provable security) . The ECC defense is entitled “An Riddle Wrapped in an Enigma” published here –

Click to access 1018.pdf

The line of thought we’re concerned with traces lineage of the NIST prime curves to NSA  involvement in the ANSI X9F1 committee, the exact nature of NSA involvement is not well outlined in the paper, but the implication is that NSA was willing to generate curves on behalf of the ANSI effort, and at the time, had the technology to enumerate orders of the resulting groups.

In order to ensure that known weak curves (known to the NSA, that is) were not selected, it was decided that curve co-efficients be selected by passing a seed to the SHA-1 function. The security of this method would be assured given the fact that it’s hard to invert SHA-1, i.e., in the event that NSA was aware of certain weak curves, it would be hard to find the SHA-1 pre-image that would result in the required co-efficients for the weak curve.

So this brings us to one of the primary arguments against security of the prime curves, and it’s centered on the provenance / legitimacy of the SHA-1 seeds used for curve generation. In the vein of classic conspiracy theories, the argument goes that the NSA could have known about “many” weak curves, and repeatedly picked random seeds until one of the seeds resulted in a weak curve. Koblitz and Menezes in the referenced paper refute this line of thought by arguing that in order to find a seed for a weak prime curve in 2^{48} SHA-1 trials, there would have to be approximately 2^{209} weak curves over 256 bit prime fields. The argument is as follows:

For a field \mathbb{F}_{p}, the number the number of “isomorphism classes” of curves over the field is 2p. Therefore, for a 256 bit prime there are about 2^{257} isomorphism classes of elliptic curves over \mathbb{F}_{p}.  Also, for a given curve, we would prefer \sharp E(\mathbb{F}_{p}) to be as close to a prime as possible since complexity of ECDLP is based on the largest prime subgroup of E(\mathbb{F}_{p}) – put another way, an attacker can use the group order to solve ECDLP in subgroups whose orders are co-prime and then map back to the full group through Chinese Remainder Theorem (CRT) – therefore, it’s important to know the group order, which circa 1997 was purportedly a computation only within reach of the NSA – Koblitz and Menezes (KM2015) imply this as one of the reasons behind involvement of NSA in the ANSI process.

With E(\mathbb{F}_{p}) we’re interested primarily in groups of prime order (given CRT derived weaknesses), so to pick up the analysis of KM2015 from where we left off, for p being a 256 bit number p, the prime number theorem tells us that there are around p/ln \ p = 2^{256}/ln(2^{256}) = 2^{256}/256 \ ln2 \approx 2^{248} primes. Put another way, a proportion 2^{-8} of 256 bit numbers are prime, this tells us that the proportion of strong curves over the field is about 2^{-8} of 2^{257} (since there are 2^{257} isomorphism classes of curves over a 256 bit field) which puts the number of strong curves at about 2^{249}. Now the argument goes that if NSA knew how to break a proportion 2^{-40} of the strong curves, then there would be 2^{249} / 2^{40} = 2^{209} curves that NSA could break, but that the rest of the world believes to be secure.  In this case, 2^{209}/2^{257} = 1/2^{48} is the proportion of total curves that are known to be insecure only to the NSA. So if you go with the math presented, the argument goes that NSA could have found a known weak curve after 2^{48} seed input trials to SHA-1.

KM2015 then proceed to argue that for a 256 bit prime, 2^{209} is an extremely large number of weak curves to have gone undetected by the community for 18 years. The argument goes – assume the NSA could conduct week seed searches in 2^{48} work – if we take this to be true, we can then work backward with the prime number theorem etc. to arrive at the number of required weak curves for NSA to have “plausibly” searched for seeds producing desired weak curves in 2^{48} trials.

Deep Crack: Bespoke Silicon Circa 1998

Though KM2015 go on to cite other possible reasons for dropping p-256, including adaptations of Bernstein and Lange’s so called n^{1/3}  pre-computation based attacks, our focus here was to understand the capping of possible NSA SHA-1 trials / hashing power at 2^{48}, and the derived requirement around 2^{209} weak curves.  Should such a bound on available hashing power be considered high or low given the state of 1997 technology? Alas, we must draw our own conclusions, but we present one important benchmark around the state of bespoke silicon in that era. Specifically, we cite the case of the EFF 1998 DES Cracker, colloquially called “Deep Crack”. This was a machine that brute forced the 2^{56} DES key space in a matter of days. Deep Crack was designed and built by Kocher et. al. at CRI with 1856 custom ASICS. The cost of the DES cracker is stated at $250,000 in 1998 dollars.

Conclusions:

It is not the intent of the author to promote the view that there are a large number of weak curves nor that the NSA exploited this fact to pre-determine SHA-1 seeds in order to ensure selection of weak curves and their eventual standardization through NIST. The situation with weak curves is quite different from that of Dual_EC_DRBG, since in some sense, eventual knowledge of such weak curves would confer an “equal opportunity” advantage to anyone with cryptanalytic ability, rather than bestowing an asymmetric advantage to any one party.  Rather, the point of this post is to merely trace reasoning around existence of weak curves and provide more insight around quantifying the size of classes of purported weak curves. If one allows NSA to have about 2^{80} hashing power in 1997 rather than 2^{48}, by the reasoning outlined above, this would imply the existence of about 2^{257}/2^{80} = 2^{177} weak curves which is a very large number and seems unlikely. In concluding, we echo the remarks of KM2015:

“Although there is no plausible reason to mistrust the NIST curves, there are two reasons why it is nevertheless preferable to use other curves .. The first reason is public perception — even though it is unlikely that the NIST curves are unsafe, there has been enough speculation to the contrary that to keep everybody happy one might as well avoid the NIST curves. The second reason is that the other curves do have some advantages … It is no discredit to the NIST curves that more efficient alternatives are now available — after all, it has been 18 years, and it would be surprising if no one had come up with anything better by now”