(A naive introduction to reversing ECDSA)
We are of course familiar with the millennium problems from the Clay Mathematics Institute. Seven math problems were given, for which a suitable solution of any problem would yield a one million dollar prize. This was by most accounts a lot of money back at the turn of the century.
Great math problems, and there’s lots we could say about each of them here. However we aren’t going to talk about these now, instead focusing on a problem for which the solution looks even more lucrative. A solution to this other problem we focus on now would open up the public ledgers of cryptocurrency to immediate compromise, allowing an attacker to slowly drain the accounts which have a current value of somewhere around a trillion dollars. That’s a million times larger than the Clay Math prize, and hey six orders of magnitude is a lot even among friends so maybe we should take a look, what do you think?
Obviously it can’t be as easy as it looks, as millions of people wouldn’t all be using this system as a safe store of value if breaking it were easy to do. Also the notation is deceptive, as it isn’t a standard multiplication which gives us the public key, but an elliptic curve operation more akin to modular exponentiation, making the goal of our problem more of a discrete logarithm.
The public key Q is determined by Q = d X G, where d is the private key (which is chosen a random number) and G is the generator point. The trillion dollar problem is: can we invert this and determine the private key d by solving d = Q / G ?
To see exactly what’s going on here, lets look at some python code.
Pcurve = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 -1
# The proven prime
N=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
# Number of points in the field
Acurve = 0; Bcurve = 7
# These two defines the elliptic curve. y^2 = x^3 + Acurve * x + Bcurve
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
GPoint = (Gx,Gy)
# This is our generator point.
privKey = 0xA0DC65FFCA799873CBEA0AC274015B9526505DAAAED385155425F7337704883E #replace with any private key
def modinv(a,n=Pcurve):
lm, hm = 1,0
low, high = a%n,n
while low > 1:
ratio = high/low
nm, new = hm-lm*ratio, high-low*ratio
lm, low, hm, high = nm, new, lm, low
return lm % n
def ECadd(a,b):
LamAdd = ((b[1]-a[1]) * modinv(b[0]-a[0],Pcurve)) % Pcurve
x = (LamAdd*LamAdd-a[0]-b[0]) % Pcurve
y = (LamAdd*(a[0]-x)-a[1]) % Pcurve
return (x,y)
def ECdouble(a):
Lam = ((3*a[0]*a[0]+Acurve) * modinv((2*a[1]),Pcurve)) % Pcurve
x = (Lam*Lam-2*a[0]) % Pcurve
y = (Lam*(a[0]-x)-a[1]) % Pcurve
return (x,y)
def EccMultiply(GenPoint,ScalarHex):
ScalarBin = str(bin(ScalarHex))[2:]
Q=GenPoint
for i in range (1, len(ScalarBin)):
Q=ECdouble(Q);
if ScalarBin[i] == "1":
Q=ECadd(Q,GenPoint);
return (Q)
PublicKey = EccMultiply(GPoint,privKey)
print "the private key:";
print privKey; print
print "the uncompressed public key (not address):";
print PublicKey; The first few lines here are just defining the elliptic curve parameters (in this case the ones used by bitcoin often referred to with the cute natural name of “secp256k1”, k for Koblitz), and declaring a private key which we will use to create the public key.
The function EccMultiply is the one which we need to reverse to qualify for the prize. The first thing we notice there is that it uses the “double and add” algorithm to compute the multiplication. This EC multiplication is nothing other than the repeated “adding” of GPoint to itself privKey times, as we would expect from the word “multiply”. However, privKey is a large number and so it’s better to use an algorithm that runs with fewer steps, just as we do when multiplying numbers with paper and pencil. For reversing this, we’d also better not have to do anything privKey times. It could be that another multiplication algorithm could be taken as a basis for our analysis to solve the problem, so it’s worth noting that there is no “best algo” known for mulitiplication in general. For now lets just look at reversing the double-and-add algo.
Another observation is that as we step backwards through EccMultiply we are going to need an EccHalf and an EccSubtract function. Lets just assume we have these in hand, and ignore for now the fact that these are not going to be unique (as EccDouble and EccAdd both have modular operations, their inverses are likely to be multi-valued functions). We can proceed then with our “half and subtract” approach for creating our trillion dollar EccDivide function.
The goal in the half-and-subract algo is to wind up at the end, after carefully choosing each binary digit of our reconstructed privkey, and halving or subtracting at each step accordingly, with exactly the generator point G. The trouble is that we don’t know until the end if we have chosen any digit correctly, and so it looks like we will need to perform this algo roughly privKey times which is of course untenable.
Some hope can be gained by considering that we can work from both sides of the digits of privKey at once, with a “meet in the middle” approach. We can e.g. first do half-and-subract 2^128 times, building a tree database of the results, and then work from the generator point doing double-and-add until we (hopefully) reach a match in the center as we compare our double-and-add result at depth 128 to our database of half-and-subtract results at depth 128. This is an absolutely enormous reduction in run time, however it leaves us still requiring on the order of 2^128 long memory addresses, 2*2^128 ecc operations a similar number of hashtable lookups. Still untenable with today’s hardware, even on a global collaborative scale. We are talking something like quadrillions of petabytes here.
If we step back from this problem, we see another potentially useful observation, that there is a potential mismatch in the keysize from the private key to the public key. It is entirely possible for a “key collision” to occur where more than one private key yields the same public key. This is especially true because the public key need not be the verifying item but rather the hash of the public key (as in the bitcoin address) must be matched. This potentially opens up a window for our algorithm, IF we could choose the eccHalf and eccSubtract results carefully to construct a lucky collision. Unfortunately hash functions are even more difficult to reverse or gain information from than ECDSA operations, and so it looks like we are again stuck with what amounts to a brute force method.
With that extremely naive introduction to the problem of reversing ECDSA, lets take a look at how the signatures are verified to see what insight we can gain:
print; print "******* Signature Generation *********"
xRandSignPoint, yRandSignPoint = EccMultiply(Gx,Gy,RandNum)
r = xRandSignPoint % N; print "r =", r
s = ((HashOfThingToSign + r*privKey)*(modinv(RandNum,N))) % N; print "s =", s
print; print "******* Signature Verification *********>>"
w = modinv(s,N)
xu1, yu1 = EccMultiply(Gx,Gy,(HashOfThingToSign * w)%N)
xu2, yu2 = EccMultiply(xPublicKey,yPublicKey,(r*w)%N)
x,y = ECadd(xu1,yu1,xu2,yu2)
print r==x; print
Here the functions have been redefined to accept the points individually rather than as arrays, but they are the same functions otherwise. We see here that we don’t really need to recover privKey completely to obtain our prize, as it is enough to generate a signature s which verifies according to the verification procedure… however it looks like this still requires reversing an EccMultiply. Back to square 2^128.
We can also see that there may be vulnerabilities here in the choosing of the random numbers, the one which is the privKey and the one which is used in the signature algorithm. If either of these are not random enough, one can greatly limit the search space. However that’s boring and old hat, even if it has netted quite a few folks the contents of someone else’s wallet, it isn’t enough to claim our trillion dollar prize.
It does appear at this stage that simply waiting for the dollar to be worthless, making a trillion dollars easy to obtain, is going to be far quicker than any brute force code breaking ECDSA. However, there’s no proof of this, and so a clever reader might just be the one who does figure this thing out and claim the prize. Stranger things have happened. Good luck!