NSA and ECC

[BurtW]

Ok, our friend Dan at SECG is really trying to dig into this and find out exactly how the random curves were generated.  He has asked me to narrow down the search to the curves we are actually interested in so he does not waste time researching curves we do not care about.

So, I need a list of the random curves that we actually care about - or maybe people have stopped caring about NIST/NSA random curves since the one we use is not a NSA/NIST curve.

Here is what he has done and found out so far in his preliminary analysis:

Yesterday, I dug a little into this:

I extracted the seeds from the LaTeX source, using a not very careful grep search, and found 22 seeds (some of which are now commented out in SEC2). I may have missed some seeds whose LaTeX did not match my criteria. 

Twelve seeds contain the ASCII string “MinghuaQu”, but in some cases they are shifted by 4 bits.  I concluded that these 12 were not NIST curves, and that the remaining 10 curves must be NIST curves.

I believe that the 12 seeds containing “MinghuaQu” are curves are mostly 163 bit or smaller, so I doubt that you are considering them.

So far, I have not detected any clear pattern in the remaining ten seeds, but I have not tried hard, mainly I suspect that they are the output of some PRNG, and therefore such tests would likely fail.  My main check so far was to compare the sorted set of byte frequencies among the 400 seed bytes to the same statistic for random sets of 400 pseudorandom bytes.  A few trials of the random sets had a higher maximum frequency, and some had a lower maximum frequency.  I did not calculate any kind of P-test.  The point of this test was to see the seeds were some byte-encoding which might favour some particular bytes.  I have done to nothing examine the order of the bytes.

Again: many of the smaller curves are now absent from SEC2 version 2.0, which has 11 random curves, 10 of which are NIST curves.

Best regards,

Dan

[1713896370]

1713896370

[1713896370]

1713896370

[1713896370]

1713896370

[niko]

So, I need a list of the random curves that we actually care about - or maybe people have stopped caring about NIST/NSA random curves since the one we use is not a NSA/NIST curve.

From all the recent revelations it appears that NSA operates also by proxies and shills in private and academic institutions who push the NSA agenda.

[jgarzik]

We care about bitcoin's curve ;p

[gmaxwell]

We care about bitcoin's curve ;p

Other than the SECP256k1 we use in Bitcoin, a lot of the internet cares about the NIST P256r and P224r curves.

[Peter Todd]

We care about bitcoin's curve ;p

Other than the SECP256k1 we use in Bitcoin, a lot of the internet cares about the NIST P256r and P224r curves.

OpenPGP ECDSA uses those curves right? (and the 512r one too)

[piotr_n]

So, I need a list of the random curves that we actually care about - or maybe people have stopped caring about NIST/NSA random curves since the one we use is not a NSA/NIST curve.

Thanks Burt for digging into it.

I don't know about others, but personally I only care about SECP256k1, and specifically about these five constants:

Code:

P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
B = 7
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

How the above values were chosen/calculated/generated?
What process a person shall follow to get to the same values?

If we know the process of calculating these values, I guess we should be able to draw our own conclusions on whether it was an honest one, or rather a backdoor driven.
B and N were rather chosen intentionally not randomly - but also here I would like to hear a fair explanation (a scientific justification) on why this values and not some others.

[fpgaminer]

and specifically about these five constants:

They've already been explained in this thread.  In summary:

The first constant we care about is p; TierNolan already explained that one.  It's the largestsmallest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024

From that we can explain b.  If we're searching for the smallest combination of a and b that results in a prime order elliptic curve, a = 0 and b = 7 is the first one.  I don't know the specifics on why a and b should be small (probably GLV optimization), but they aren't suspicious regardless.

N is just the order of the elliptic curve; no explanation needed.

The last piece of the puzzle is the choice for G.  Since the order of the elliptic curve is prime, we can pick any point on the curve (except infinity), and get a group with the same order (i.e. there are no subgroups).  Why SECG picked the particular G they did is unexplained.  However, there is no reason to believe any G is weaker or stronger than any other G (against a compliant ECDSA verifier).  I would guess that either G is totally random, or it has sentimental meaning to the author(s).

Since the curve is not weak to any publicly known attacks, and the constants are not suspicious, then what else are we looking for with regards to secp256k1?

[piotr_n]

and specifically about these five constants:

They've already been explained in this thread.  In summary:

Explained - yes.
Justified - no. At least not according to my understanding of what "science" is.

To be more specific:

The first constant we care about is p; TierNolan already explained that one.  It's the largest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024

But why 1024? What does 1024 have to do with the EC math?
Why the largest prime for t<1024, not e.g. the smallest prime for t>1024?
This explanation, instead of answering questions, only creates more.

From that we can explain b.  If we're searching for the smallest combination of a and b that results in a prime order elliptic curve, a = 0 and b = 7 is the first one.  I don't know the specifics on why a and b should be small (probably GLV optimization), but they aren't suspicious regardless.

I'd like to know "the specifics" though.
For you they aren't suspicious because they are small - but maybe B is suspicious exactly because it is small? Or maybe it is suspicious because it leads to a specific N that is suspicious...

Don't get me wrong - it's not that I believe in B being suspicious, but before we know exactly why it is 7, we cannot exclude any possibility, can we?

Since the curve is not weak to any publicly known attacks, and the constants are not suspicious, then what else are we looking for with regards to secp256k1?

If you believe that the curve is not weak to any attacks, then what are you doing in this topic? In such case it should not concern you.

But if you believe that the curve might be weak to some attacks that are not publicly known, though they are known to someone, then the statements you are making are kind of weird, since whether such weaknesses exist is exactly what we are trying to figure out here, while you are throwing your "no worries" conclusion on us.

If there is a weakness that depends on the constants (which is the thesis from the OP), the best way to find it goes through questioning the values.

[BurtW]

With regard to the selection of a and b, from Dan:

Also, I read a little more on the subject: the curve parameters (0,7) belong to the class of curves with a=0 which have an efficient endomorphism of order 3 (as listed in the GLV paper).  I am curious to know if BitCoin is using GLV method which takes advantage of this feature.

I did not know the answer to Dan's question so I asked gmaxwell and he responded to Dan, through me, with:

No, the production Bitcoin software uses a completely straight forward curve-generic implementation.

However, the possibility of high speed implementations is one of the major attractive characteristics of this curve. Bitcoin uses a zero-trust design where all participating nodes verify all signatures, so the whole network's scalability depends on the weakest full participants.

One of our core developers has created a high performance secp256k1 implementation which we may use in the future:

https://github.com/sipa/secp256k1

This implementation can do around 14k validations per second per core on a modern i7 cpu. (Which makes it about 6x faster than the generic code we use today).  One of the barriers in deploying this implementation is having more ECC experienced eyes looking at it.

Therefore we know that a=0 on purpose and b=7 is the smallest value that works given a=0.

[polarhei]

He's worried about constants that have no explanation. The SEC random curves have "random numbers" in them, but are they really random? AFAIK nobody knows how one might exploit the algorithms if they weren't, but hesitation is reasonable.

However Bitcoin does not use a random curve. It uses a Koblitz curve where there are explanations for why the constants are the way they are.

Also, the NSA is not going to crack the crypto used on Bitcoin because their goal is not to actively attack Bitcoin (I doubt the NSA care much about financial regulations). Their goal is to spy on everyone. They're much more likely to do graph analysis of the block chain than worry about the crypto.

There is no true random. Only exponential.

[BurtW]

There is no true random. Only exponential.

What?

[gmaxwell]

The first constant we care about is p; TierNolan already explained that one.  It's the largest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024

But why 1024? What does 1024 have to do with the EC math?
Why the largest prime for t<1024, not e.g. the smallest prime for t>1024?
This explanation, instead of answering questions, only creates more.

Not really, the reasons here are well understood by anyone working on this stuff in detail.

The number is a generalized mersenne prime. The reason for this is that our we are doing calculations in this field so when we multiply we must take the result mod p where p is the size of the field. If p is a freely chosen prime to compute the mod we must divide which is hideously complex. Instead, if P has special form, we can break the larger value at the word level into small fragments and compute the mod p as some sum of them with negations. The performance impact is enormous.

This is just an extension of how it's easier to compute x%16, which can be computed as x&15, then it is to compute x%13.

The reason to use largest prime is just to have the largest field size for one admitting the optimization.

The same reasonable sounding criteria has been used to select primes for many different curves, so it's unlikely that a bad prime was selected and then a complicated explanation was found. The explanation gives a real performance improvement, makes sense, and then was used many times to pick many numbers.

Likewise the efficient endomorphism selection of the a and curve formula permits using the GLV method to speed up point multiplies. This optimization is used by Pieter's libsecp256k1 to make ECDSA verification on x86_64 something like 6x faster than OpenSSL for our curve.

Maybe it turns out that these selections for performance also turn out to select for some weakness. No one knows what unknown math will bring. But the performance benefits are not small, so you don't have to hypothize some rigged process to explain this stuff. (And certainly ECDSA performance is very important to our applications.)  As a side effect, this eliminates all random parameters, save the generator. So thats a great relief for anyone concerned that our parameters were mysterious and could have been rigged via non-public selection.

I have no blinking idea where the generator comes from, but also can't come up with _any_ way it could be an attack even if I assume that our curve has a weakness of every form which I've heard of for discrete log on an abelian variety. The generator is generally irrelevant. You might be able to pick one which permits faster multiplication under some specific multiplication scheme, but I asked Pieter about that and he seemed to believe that it would take a exponentially hard search, so was unlikely to be very useful... I've only bothered expending time thinking about it because I can't figure out why, due to the irrelevance of its specific value, they didn't pick one with a more compact binary representation, and because its the only parameter thats unexplained though it is the only one which there is no real reason to care about.

This isn't to say that the curve selection couldn't be better: Ed25519 is still somewhat faster than Pieter's code. Our parameters pick a curve who's quadratic twist is not of prime order, which means that some optimizations (e.g. the ones used in Ed25519) are not available, and it also means that a single bit error during a multiply (e.g. for doing ECDH) could basically leak the private key. (Basically an off by one in the x coordinate instead gives a value on the twist, and because the twist's order is factorable, the discrete log problem can be solved on it with complexity related to its largest factor, which is only about 2^50). But the ideas behind making curves for high performance which are better in these respects all came after these parameters were selected.

[piotr_n]

The first constant we care about is p; TierNolan already explained that one.  It's the largest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024

But why 1024? What does 1024 have to do with the EC math?
Why the largest prime for t<1024, not e.g. the smallest prime for t>1024?
This explanation, instead of answering questions, only creates more.

Not really, the reasons here are well understood by anyone working on this stuff in detail.

The number is a generalized mersenne prime. The reason for this is that our we are doing calculations in this field so when we multiply we must take the result mod p where p is the size of the field. If p is a freely chosen prime to compute the mod we must divide which is hideously complex. Instead, if P has special form, we can break the larger value at the word level into small fragments and compute the mod p as some sum of them with negations. The performance impact is enormous.

This is just an extension of how it's easier to compute x%16, which can be computed as x&15, then it is to compute x%13.

Thanks for explaining.

I am not going to pretend that I am working on this stuff in detail, since honestly I have no freaking idea what all these XY vs XYZ calculations do, nor I'd dare to question your expertise in this field.
But still I didn't get it, from your explanation, why it is 1024 and not e.g. 512 or 2048?

[TierNolan]

and specifically about these five constants:

They've already been explained in this thread.  In summary:

The first constant we care about is p; TierNolan already explained that one.  It's the largest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024

It is technically the smallest prime, since it is the largest t (and t is subtracted).

I don't know where 1024 comes from.  Maybe there is something in the internals of large multipliers. 

The 2^32 is presumably linked to 32 bit words in the multipliers.

From that we can explain b.

That is past my expertise, but a check should be made that b < 7 wouldn't have given a prime order.

[BurtW]

That is past my expertise, but a check should be made that b < 7 wouldn't have given a prime order.

ask and you shall...

By the way, I ran a little experiment.  Given our finite field, and setting a to 0, 7 is the first (counting from 0) value for b that results in a prime order elliptic group.  I don't understand GLV well enough to know what restrictions it places on a and b, but if we have to pick a curve where a is 0, it seems like b being 7 would be a logical choice (again, given our finite field).

[piotr_n]

pardon me the lame question, but what is the actual formula to calculate the order (N), from the A & B?
can I calc it myself, using a python shell, or do I need a six dimensions math library?

moreover, from what I understand, it isn't really possible to check whether 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 is a real prime number, is it?
AFAIK, the algos we know only allow us to check whether such a big numbers are prime with a certain probability, but we can never be totally sure about their primness, since checking for that would have taken ages - right?

[BurtW]

I can answer the question about the prime numbers.  If you set the certainty high enough you can be certain.  For example above in this thread the call test.isProbablePrime(1024) is made.  This is asking to test if the number is prime within a certainty of 1 - 0.5¹⁰²⁴

When I try to calculate this number on my calculator I get 1.00

So pretty darn certain.

0.5¹⁰²⁴ = 5.562684646268e-309

[Etlase2]

Maybe this needs its own thread, but there are a lot of crypto-smart people in this thread who will see it and it needs some discussion I think:

"Some Lattice Attacks on DSA and ECDSA" http://eprint.iacr.org/2009/363.pdf

Abstract: In this paper, using the LLL reduction method and computing the
integral points of two classes of conics, we develop attacks on DSA and
ECDSA in case where the secret and the ephemeral key and their modular
inverse are quite small or quite large.


I wasn't able to find any papers or discussion referencing it. The authors conclude that the attacks can be "quite efficient".

[piotr_n]

I can answer the question about the prime numbers.  If you set the certainty high enough you can be certain.  For example above in this thread the call test.isProbablePrime(1024) is made.  This is asking to test if the number is prime within a certainty of 1 - 0.5¹⁰²⁴

Right - that should do

I'm just going blind here, trying to find a hole, though still hoping that there isn't any.

[TierNolan]

ask and you shall...

Ahh, thanks, missed that one.