Breaking ECDSA

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:

BRXVEpTGwCo1HsaTNmhJ5NynvUsdhFzvc1ilypdV4aDLRLIlVaCCkHsuN6EAet0+ BRXVEpTGwCo1HsaTNmhJ5NynvUsdhFzvSvNuLoc421+3BZMMFukNTOztlpj9kf4e

Solving the challenge

xkcd sony

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.

BRXVEpTGwCo1HsaTNmhJ5NynvUsdhFzv

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:

  1. Calculate the curve point (x1, y1) = k x G
  2. 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.

Reflection

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)