NSA and ECC

[gmaxwell]

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?

You need a six dimensions math library.

For curves of particular structure there are simple formulas, but the general case is hard. Fancy math packages just have functions to implement fancy techniques.

There is an overview of techniques in section 5 here: http://cdn.intechopen.com/pdfs/29703/InTech-Elliptic_curve_cryptography_and_point_counting_algorithms.pdf

moreover, from what I understand, it isn't really possible to check whether 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 is a real prime number, is it?

The optimality testing we can do has exponential confidence with additional testing... so you can be arbitrarily confident. 2^256 is also small enough that you can try factoring numbers to increase your confidence (though you may need to take care to defeat initial primality testing in your factoring software).

(E.g. I successfully factored the order of secp256k1's twist just using the factor command on my Fedora system:
$ time factor 1286578769603068245382716924545379906921918859152521322839515520912848165551
1286578769603068245382716924545379906921918859152521322839515520912848165551: 3 3 3 197 1511 1559 96769 146849 2587814237219 375925338294461779 7427691663837602734654241
real    6m35.889s)

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

I've seen this paper before.

It's "quite efficient", at least relative to recovering the key the exponential time way by computing the discrete log of the public key, under their assumptions that you've signed messages with either a pair of very small (or large) K values, or a single message with a permitted combination large and small K and signature. The definition of small/large depends which of their cases you're concerned with, but picking one at random, requires (K1 * K2) < (order^(1/2))/6^(3/4).  So e.g. <2^61. The probability of picking a single 256 bit K less than 2^61 is 1e-59. So the probability is negligible even if you sign many times (and I think there were additional constraints as well— it certainly would have been nice if the authors had given concrete figures rather than requiring the readers to fuddle through the math themselves…). (Though I suppose if you want to be extra paranoid you can use this kind of thing as yet another argument for not reusing keys, at if we didn't already have enough). (And even in this case, it's not clear to me that the solution is actually tractable, just exponentially better than the DLP solving way)

[1713304727]

1713304727

[1713304727]

1713304727

[1713304727]

1713304727

[fpgaminer]

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

Well, you put in the work to check p for us, so here's my contribution:

secp256k1_parameter_proof.py

Code:

from sage.all import *


# Find the smallest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024.
def find_prime ():
for t in xrange (1023, -1, -1):
p = 2**256 - 2**32 - t

if p in Primes ():
return p

return None


# Find the smallest b, where b results in an elliptic curve of prime order, of the form y^2 = x^3 + a*x + b.
# p specifies the modulus of the underlying finite field.
def find_elliptic_curve (p, a, max_b):
K = FiniteField (p)

for b in xrange (max_b + 1):
if a == 0 and b == 0:
continue

E = EllipticCurve ([K (a), K (b)])
order = E.order ()

if order in Primes ():
return b

return None


p = find_prime ()

# Searches all combinations of a and b, where a and b < 7, until a prime order group is found.
for a in xrange (7, -1, -1):
print "Testing", a
b = find_elliptic_curve (p, a, 7)

if b is not None:
break

print ""
print "p = 0x%064X" % p
print "a = %d" % a
print "b = %d" % b
print "N = 0x%064X" % EllipticCurve (FiniteField (p), [0, b]).order ()
print ""

This requires sagemath, and can be executed by running "sage -python secp256k1_parameter_proof.py"  Here is my output:

Code:

Testing 7
Testing 6
Testing 5
Testing 4
Testing 3
Testing 2
Testing 1
Testing 0

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

real 3m1.191s
user 3m0.716s
sys 0m0.148s

I built the test to not only show that b = 7 results in the first prime order, given a = 0, but also that a = 0 and b = 7 is the first result when searching all combinations of a and b < 7.  So, if one was looking for a curve, and didn't know about GLV, (0,7) would still be a reasonable choice.

[piotr_n]

I built the test to not only show that b = 7 results in the first prime order, given a = 0, but also that a = 0 and b = 7 is the first result when searching all combinations of a and b < 7.  So, if one was looking for a curve, and didn't know about GLV, (0,7) would still be a reasonable choice.

Thanks. That's a decent and quite convincing explanation of why they chose B to be 7, though don't you feel like doing someone's else job here by explaining it to us?

I guess we can narrow down our investigation to the G point and the P (since we still don't seem to know what is so great about 1024 aka 2^10).

[Etlase2]

(and I think there were additional constraints as well— it certainly would have been nice if the authors had given concrete figures rather than requiring the readers to fuddle through the math themselves…).

Super math geeks, what do you expect? Hopefully the more cryptography enters into the public eye, cryptographers will be more apt to write papers that are digestible by a wider audience. Is it possible to simply avoid getting into the situations described by the paper? Or would doing so effectively reduce the security by the same amount?

[fpgaminer]

I guess we can narrow down our investigation to the G point and the P (since we still don't seem to know what is so great about 1024 aka 2^10).

An explanation on G would be nice to have, yes.  As for p, someone would need to dig into the implementation of optimized reduction algorithms to explain why t being less than 1024 is helpful.  I've implemented a secp256k1 specific reduction algorithm before (link to source), but it's been awhile and I didn't take the time to intuitively understand exactly which Mersenne-like primes make the method work effectively.  Nor do I understand why they chose the smallest p, and not the largest.  Perhaps that particular p allowed a small (a,b) for the curve?  I recall there being better (less code required) Mersenne-like primes to choose.

[fpgaminer]

Here's another interesting data point.  If we search all primes of the form 2**256 - 2**32 - t, starting from t = 0 to t = infinity, the first prime order curve with a = 0 and b < 1000 is the secp256k1 curve.  Code:

Code:

from sage.all import *


def find_group (prime):
K = FiniteField (prime)

for b in xrange (1, 1000):
E = EllipticCurve (K, [0, b])

if E.order () in Primes ():
return b, E.order ()

return None


p = 2**256 - 2**32 + 1

while True:
p -= 1
if not p in Primes ():
continue

result = find_group (p)

if result is not None:
break


print "Found curve: "
print "p = %X" % p
print "a = 0"
print "b = %d" % result[0]
print "N = %X" % result[1]

That helps to explain p a bit more. (In other words, we have an alternative explanation that doesn't involved 2^10).

[someone42]

I guess we can narrow down our investigation to the G point and the P (since we still don't seem to know what is so great about 1024 aka 2^10).

An explanation on G would be nice to have, yes.  As for p, someone would need to dig into the implementation of optimized reduction algorithms to explain why t being less than 1024 is helpful.  I've implemented a secp256k1 specific reduction algorithm before (link to source), but it's been awhile and I didn't take the time to intuitively understand exactly which Mersenne-like primes make the method work effectively.  Nor do I understand why they chose the smallest p, and not the largest.  Perhaps that particular p allowed a small (a,b) for the curve?  I recall there being better (less code required) Mersenne-like primes to choose.

I'm not sure if this is the optimisation you're after, but section 2.2.6 of http://www.springeronline.com/sgw/cda/pageitems/document/cda_downloaddocument/0,11996,0-0-45-110359-0,00.pdf (from here: http://cacr.uwaterloo.ca/ecc/) describes the property as: the prime must be a sum or difference of powers of 2^32. secp256k1 doesn't have this property exactly, which is why your code has all that shifting in it.

[TierNolan]

An explanation on G would be nice to have, yes.  As for p, someone would need to dig into the implementation of optimized reduction algorithms to explain why t being less than 1024 is helpful.

The thing is that they went for largest t less than 1024.  They could have gone for largest prime less than 2^256 or (2^256 - 2^32), but they went for smallest prime greater than (2^256 - 2^32 - 2^10).

Perhaps that particular p allowed a small (a,b) for the curve?  I recall there being better (less code required) Mersenne-like primes to choose.

That might be worth checking.  It might have nothing to do with 2^10.  

2^256 - 2^32 has some advantage when dealing with a 32 bit words.

If you multiply two 256 bit numbers together, you get a 512 bit number.  They can be broken down into x and y with a base (b) of 2^256.

x * b + y

Taking mod p

x * b + y mod p

b can be replaced by b mod p

x * (b mod p) + y mod p

If p = 2^256 - 2^32 - t, then (b mod p) is 2^32 + t

x * [2^32 + t] + y mod p

x * 2^32 + x * t + y mod p

(x * 2^32) is easy to compute, since it is just move all the words over by 1
(x * t) is a little harder, since you have to handle carry, but it is still a small number [ * ]
y is unchanged

Assuming t is a 10 bit number, this gives

288 bit number + 266 bit number + 256 bit number

= 289 bit number

This gives a much smaller number than originally.  x is at most 33 bits and the process can be repeated.

65 bit number + 43 bit number + 256 bit number

= 257 bit number

This could be handled "manually" by subtracting p until it is less than p.

I would suggest checking all primes of the form

2^256 - t
2^256 - 2^32 - t

for t < 2048

and then seeing what the lowest a and b are for each prime.  If there are no good values for 2^256 - t, then that might explain why they switched to 2^256 - 2^32 - t.

[ * ] this is like multiplying 123456 by 7, it is easier than if both numbers are multiple digits.

That helps to explain p a bit more. (In other words, we have an alternative explanation that doesn't involved 2^10).

Can you run the same check for 2^256 - t.

[runeks]

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?

You can use sage. They have an online version of their shell here. Here's how you calculate the order of secp256k1:

Code:

sage: F = FiniteField(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
sage: F
Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663
sage: C = EllipticCurve(F, [ 0, 7 ])
sage: C
Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663
sage: print(C.cardinality())
115792089237316195423570985008687907852837564279074904382605163141518161494337
sage: hex(C.cardinality())
'fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'
sage: G = C.point((0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8))
sage: G
(55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)
sage: G.order()
115792089237316195423570985008687907852837564279074904382605163141518161494337
sage: hex(G.order())
'fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'

[Roy Badami]

If you're asking about BIP32,  BIP32 is specific to SECP256k1 (as its results are well defined), but it supports both public and private derivation. The private derivation could be applied to any cryptosystem, though that wouldn't be BIP32 anymore. The public derivation could be applied to at least any ECDSA cryptosystem.

Is it still the intention for Bitcoin-QT to move to BIP 32 in the future?

roy

[maaku]

If you write the code.

[Roy Badami]

If you write the code.

?

My point is that previously the core devs have suggested an intention to migrate from bag-of-keys to heirarchical deterministic wallets.  The argument, AIUI, is that it simplifies backup, but such a decision would seem to negate the argument given in this thread that Bitcoin is largely safe from ECDSA attacks as long as we avoid address reuse.

So, in the light of the concerns over NSA activity in this area, I'm wondering whether it's still the intention to trust our coins (more than at present) to the security of ECDSA.

roy

[gmaxwell]

I've finally come up with a way to exploit ECDSA given control of only the generator.

Basically, you set the generator to some random multiple of an existing "public key". Then you can effectively use the "public key" as the secret for signing arbitrary messages from that "public key".

In quotes because the whole idea of a public key is ill defined if you don't yet have a generator.

Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")!  So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins.

I don't think this exposes us to any particular risk, since it only works for one key, and we have no nothing up my sleeve pubkeys, and the parameters for our system were fixed before Bitcoin existed.

But if some nice man from the NSA or Certicom claims to have a nothing up his sleeve pubkey for some protocol or another... perhaps you'd be wise to not believe him.

[Wipeout2097]

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.

Yes, and perhaps set up "rogue" full nodes.

[maaku]

Yes, and perhaps set up "rogue" full nodes.

What the heck is a "rogue" full node?

[BurtW]

Yes, and perhaps set up "rogue" full nodes.

What the heck is a "rogue" full node?

Obvioiusly a node that "runs wild" and logs every single transaction.  No, wait...

Maybe it just takes in transactions but does not send them out!  No, wait...

Maybe it makes up a lot of bogus transactions?  No, wait...

Hmmm.  I guess I don't know.

What is a "rogue" full node?  Anyone?

[niko]

Yes, and perhaps set up "rogue" full nodes.

What the heck is a "rogue" full node?

Obvioiusly a node that "runs wild" and logs every single transaction.  No, wait...

Maybe it just takes in transactions but does not send them out!  No, wait...

Maybe it makes up a lot of bogus transactions?  No, wait...

Hmmm.  I guess I don't know.

What is a "rogue" full node?  Anyone?

A node which serves, as part of a pool of similar nodes, to identify originating IPs of every transaction?

[chriswilmer]

I've finally come up with a way to exploit ECDSA given control of only the generator.

Basically, you set the generator to some random multiple of an existing "public key". Then you can effectively use the "public key" as the secret for signing arbitrary messages from that "public key".

In quotes because the whole idea of a public key is ill defined if you don't yet have a generator.

Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")!  So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins.

I don't think this exposes us to any particular risk, since it only works for one key, and we have no nothing up my sleeve pubkeys, and the parameters for our system were fixed before Bitcoin existed.

But if some nice man from the NSA or Certicom claims to have a nothing up his sleeve pubkey for some protocol or another... perhaps you'd be wise to not believe him.

Interesting!

So G could be a secret multiple of some number. You say this only works for one key... could it work for a set of related keys? Presumably you could derive an entire set of public/private keys deterministically from the private key you got by choosing G.

[oleganza]

Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")!  So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins.

G cannot be SHA256 * N because both SHA256 and N are scalar numbers in your example. You need a 2D point somewhere in this equation.

[chriswilmer]

Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")!  So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins.

G cannot be SHA256 * N because both SHA256 and N are scalar numbers in your example. You need a 2D point somewhere in this equation.

I think this is just a matter of encoding. You can map integers to 2D integer-valued points in a 1-to-1 way.