Ecurve it like Beckham

Solves: 0

Challenge Description

The challenge supplied a public ECDSA key and a bunch of signatures.

image alt text

Signatures

  {"message hash": "37bf488115c14bc75bd3abfba09e3a10e4b671479755165310244b31b925929a", "signature": "(9811783871763325604756417160787846138404247835194244394354131020979062723933, 55791654947192643955306007970    524722900505588307283376371034301963123114165948)"}
  {"message hash": "9442f76ff69de268bf22f98d803b52aeb289b0aa5bd55c17b3b4d3b6652ce268", "signature": "(16842672915651939019730535973185867061057860352849830024453076236449618387846, 9822948972963614614072213326    2045145654921177567834687343813459264455251940224)"}
  ...

Key

-----BEGIN PUBLIC KEY-----
MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEHwWBWR0Dfapord6Ja4/CrjlBeTHQ
I3LK5ByvYhzMzMQ2SUMcpdVC1unYbqsGbc1KwVVuavIHFqqMvLlhZMQkdA==
-----END PUBLIC KEY-----

The attack

This is a classic repeating-k-breaking of DSA. If we can find two signatures with the same r we can extract the private key.

Quick proof

s = 1/k (H + x*r) mod n, where x is the private key

Say that we have two signatures with the same r, so:

s1 = 1/k (H1 + x*r) mod n
s2 = 1/k (H2 + x*r) mod n

This means that we can recover the k value by:

s1-s2 = 1/k (H1 + x*r) mod n - 1/k (H2 + x*r) mod n
s1-s2 = 1/k (H1-H2) mod n
k = ((H1-H2) / (s1-s2)) mod n

Now we extract x by using s:
x = ((s*k)-H))/r mod n

Solution

The twist of the challenge is our unknown n. We need to find that parameter in some way. Luckily for us, the parameter is not secret nor random, it is choosen by NIST. We first need to look at our key to see which parameter to use. It requires some Google-fu

EccKey(curve='P-256', x=14031425269174631844092188919498800608183536405845297577669333727317255310532, y=24554336848573207326144613712141942513509757787905379245470080208324218070132)

Now we know that the curve is P-256, so we can search google for the parameter.

Google search: NIST fips P-256

The first hit is a document from NIST, which describes multiple curves and their parameters.

At page 89 we find the n value for P-256

n = 115792089210356248762697446949407573529996955224135760342
    422259061068512044369

Now we can implement a script to find two repating k and extract the private key

#!/usr/bin/python3
import json
import collections
import gmpy
from Cryptodome.PublicKey import ECC


f = open("publickey.pem")
key = ECC.import_key(f.read())
f.close()
print(key)

f = open("signatures.txt", "r")
signatures = f.readlines()
f.close()

sig_dict = {}
for signature in signatures:
    json_obj = json.loads(signature.rstrip())
    r = json_obj['signature'].split(",")[0][1:]
    s = json_obj['signature'].split(",")[1][1:-1]
    h = json_obj['message hash']
    sig_dict[h] = {'r':r, 's':s}

r = []
for sig in sig_dict.items():
    r.append(sig[1]['r'])

copy = ([item for item, count in collections.Counter(r).items() if count > 1])[0]

M = []
S = []
R = []
for sig in sig_dict.items():
    if sig[1]['r'] == copy:
        M.append(int("0x"+sig[0], 16))
        S.append(int(sig[1]['s']))
        R.append(int(sig[1]['r']))

# NIST P-256 n parameter
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369 

nom =(M[0]-M[1])%n
denom = (S[0]-S[1])%n
k = (nom*gmpy.invert(denom, n))%n
d = ((S[0]*k-M[0])*gmpy.invert(R[0], n))%n

print("BTH_CTF{"+str(d)+"}")

And the flag!

BTH_CTF{16859897575604388048434139223879309114446889925045767799455621888122996123340}