May 21, 2017
Breaking Elliptic Curve Digital Signature Algorithm
ECDSA CTF Challenge
Recently a video on breaking ECDSA encryption was posted to YouTube by LiveOverflow. LiveOverflow is a great channel and I would definitely recommend subscribing to it. The video is about “breaking ECDSA encryption” from the rhme2 embedded security challenge. In fact, the “breaking” is more like “exploiting poor implementation”, which is almost always the case for issues with modern crypto.
The video reminded me of a very similar CTF challenge I completed last summer. I thought I would finally do a writeup, and realised I still had the solution script lying around, perfect.
What is ECDSA?
Elliptic Curve Digital Signature Algorithm is a digital signature algorithm that makes use of elliptic curve cryptography. A good primer on how ECC works can be found over at cloudflare. The math that explains elliptic curves is quite complicated. When implemented correctly ECDSA is infeasible to break. A much shorter ECDSA key provides the same security as a much longer RSA key. In RSA the public key is the product of 2 primes, plus some small number, the private key is a mathematically related prime. In ECC, the public key is an equation for and a point on an elliptic curve, the private key is a number. Elliptic curve crypto is also much faster than traditional RSA. Examples of the use of ECDSA includes the technology that underpins Bitcoin.
What was the challenge?
Elliptic curve digital signature algorithm (ECDSA) is used to authenticate users of the BitPub web code repository. Each user has his own private key that they use to sign a random nonce from server in order to authenticate. The protocol seems to be secure, however, one of the users of BitPub, namely EvilCompany, does not follow precisely all guidelines related to secure usage of ECDSA. You are provided with a traffic dump containing two successful logins of EvilCompany to BitPub. For a good hacker this can be enough to get EvilCompany’s private key and authenticate to BitPub on their behalf.
As the challenge brief suggests, a pcap containing two successful logins was given. Additionally an example, unusable, private key was given in PEM format. The “two successful logins” consisted of two nonces and two signatures that resulted from signing the nonces with a valid key.
The signatures were as follows:
Solving the challenge
Right off the bat, it should be obvious that something is not-so-random in this setup. You would expect that the two generated signatures would be unique, however a quick glance tells us that this is not exactly the case. As can be seen, the first half of the signatures appear identical.
If we look at the wikipedia page, we find out that the signature is comprised of the pair of numbers (r, s). It looks like we have found a common r value. The other halves of the signatures are the two s values.
The part of the process where r is derived involves the following calculations:
- Calculate the curve point (x1, y1) = k x G
- Calculate r = x1 mod n. If r=0, go back to step 3.
We can see that r relies on obtained curve point, which directly relies on the value of k.
Some research reveals that the whole security of this system is underpinned by the randomness of the value k. In fact in 2010, fail0verflow disclosed that they had obtained Sony’s ECDSA private key used to sign PS3 software. The problem with Sony’s implementation was that their k value was static, and not randomly generated.
It looks like EvilCompany may have had some of the same engineers working for them as Sony did, as this indeed looks to be the same issue.
Tools for the job
After messing around with a few libraries, I settled on the python ecdsa package. At the time I wasn’t so familiar with python, so working with the library actually took some getting used to. Over the last year, I’ve been using Python extensively for a lot of natural language processing and machine learning, and as a result I am much more comfortable with the language.
Writing the script
The last question that really remained for this challenge, now that the weakness in the scheme had been identified, was – what curve was being used? ECDSA can be used with a large number of different curves (check with
openssl ecparam -list_curves if you don’t believe me).
Fortunately, part of the given information was an example private key. The python ecdsa library had a convenient method for reading such a key into an object (from pem format). Afterwards we could easily obtain the curve used, and subsequently the order.
private_key_pem = ''' -----BEGIN EC PRIVATE KEY----- MF8CAQEEGKyFd/8lBEkufLbV+HFtTBk3KNhZK29CJaAKBggqhkjOPQMBAaE0AzIA BB1ZB2byaoiLjGw46KCr2hYJtAlV0ZlmIIvRH4fo+HrgYH9Yv2gyffLlGG19l/LD 9w== -----END EC PRIVATE KEY----- ''' private_key = SigningKey.from_pem(private_key_pem.strip()) curve_order = private_key.curve.order
Then it was a matter of solving for k, which is conveniently explained on the wikipedia page! Followed by solving for the private key dA.
def recover_key(c1,sig1,c2,sig2): n = curve_order # cut up the strings before we convert to number s1 = string_to_number(sig1[-24:]) s2 = string_to_number(sig2[-24:]) r = string_to_number(sig1[-48:-24]) z1 = string_to_number(sha1(c1)) z2 = string_to_number(sha1(c2)) # solve sdelta_inv = inverse_mod(((s1-s2)%n),n) k = ( ((z1-z2)%n) * sdelta_inv) % n inverse_r = inverse_mod(r,n) da = (((((s1*k) %n) -z1) %n) * inverse_r) % n
Once we have dA, the python ecdsa package exposes a convenient function for creating a
SigningKey from the secret exponent, which we go ahead and do.
We can then use this
SigningKey to sign a new challenge given by EvilCompany’s portal. Once we do we’re in! We can see EvilCompany’s BitPub code repository and their algorithm for world domination. The full solution script is at the end of the post, you can run it yourself and check it out. Re-reading my solution the code could be a lot better, but it works.
This challenge was a lot harder to figure out than to write about after the fact. Now, a year on, it seems that the solution is blindingly obvious, but last year it gave me a real run for my money. I haven’t done many crypto-related problems since this, as my focus has been on binary exploitation. I still find crypto really interesting and it is undoubtedly one of the key pillars of security, so I hope there’ll be cool future CTF challenges which I can use to learn more about it.
Full solution script
from ecdsa import SigningKey from ecdsa import VerifyingKey from ecdsa.numbertheory import inverse_mod import hashlib import binascii import base64 # get order from given priv key private_key_pem = ''' -----BEGIN EC PRIVATE KEY----- MF8CAQEEGKyFd/8lBEkufLbV+HFtTBk3KNhZK29CJaAKBggqhkjOPQMBAaE0AzIA BB1ZB2byaoiLjGw46KCr2hYJtAlV0ZlmIIvRH4fo+HrgYH9Yv2gyffLlGG19l/LD 9w== -----END EC PRIVATE KEY----- ''' private_key = SigningKey.from_pem(private_key_pem.strip()) curve_order = private_key.curve.order def string_to_number(tstr): return int(binascii.hexlify(tstr), 16) def sha1(content): sha1_hash = hashlib.sha1() sha1_hash.update(content) hash = sha1_hash.digest() return hash def recover_key(c1, sig1, c2, sig2): n = curve_order # cut up the strings before we convert to number! s1 = string_to_number(sig1[-24:]) s2 = string_to_number(sig2[-24:]) r = string_to_number(sig1[-48:-24]) z1 = string_to_number(sha1(c1)) z2 = string_to_number(sha1(c2)) # solve sdelta_inv = inverse_mod(((s1-s2)%n),n) k = ( ((z1-z2)%n) * sdelta_inv) % n inverse_r = inverse_mod(r,n) da = (((((s1*k) %n) -z1) %n) * inverse_r) % n recovered_private_key = SigningKey.from_secret_exponent(da) return recovered_private_key.to_pem() if __name__ == "__main__": challenge1 = "iSsuZJOq1FNKMuK4wm88UEkr21wgsypW" sig1 = ''' BRXVEpTGwCo1HsaTNmhJ5NynvUsdhFzvc1ilypdV4aDLRLIlVaCCkHsuN6EAet0+ '''.strip() challenge2 = "x3wqOnaetBPO66TrBaMyr3NQIDbhvK0w" sig2 = ''' BRXVEpTGwCo1HsaTNmhJ5NynvUsdhFzvSvNuLoc421+3BZMMFukNTOztlpj9kf4e '''.strip() key = recover_key(challenge1,base64.b64decode(sig1),challenge2,base64.b64decode(sig2)) print key #create the signature sk = SigningKey.from_pem(key) challenge = "DkHV48UYq10wj8SuOYrGsp65S0BrBHdc" vk = sk.get_verifying_key() signature = sk.sign(challenge) try: # because who trusts python vk.verify(signature, challenge) print "good signature" except BadSignatureError: print "BAD SIGNATURE" encoded_signature = base64.b64encode(signature) print(signature) print(encoded_signature)