# ezdsa
## DescriptionThis task has two parts to it, the first part is the signer. You can send a message to the server and it will sign it and send it back. The second part is the verifier. The verifier will take the message and the signature of the message and verify they match.
## AnalysisLets take a look at the signer code:```Pythonimport socketserverimport randomimport ecdsa
key = open("secp256k1-key.pem").read()sk = ecdsa.SigningKey.from_pem(key)
def sony_rand(n):    return random.getrandbits(8*n).to_bytes(n, "big")
def sign(data):    if data == b"admin":        raise ValueError("Not Permitted!")    signature = sk.sign(data, entropy=sony_rand)    return signature
class TCPHandler(socketserver.StreamRequestHandler):
    def handle(self):        data = self.rfile.readline().strip()        try:            signature = sign(data).hex()            self.wfile.write(b"Your token: " + data + b"," + signature.encode())        except ValueError as ex:            self.wfile.write(b"Invalid string submitted: " + str(ex).encode())
if __name__ == '__main__':    server = socketserver.ForkingTCPServer(("0.0.0.0", 10101), TCPHandler)    server.serve_forever()```Basic info we can get from it:- Every request will call `sign(our_data)`- `sign()` will check that our input is NOT "admin", and will sign- It's using some sort or rand function for the entropy of the signer- The ecdsa curve they are using is "secp256k1"- We can send it any message (besides "admin") and get the signature of the message
Now lets take a look at the verifier:```Pythonimport socketserverimport ecdsaimport pyjokesfrom flag import FLAG
key = open("pub.pem").read()vk = ecdsa.VerifyingKey.from_pem(key) 
def valid_signature(msg, sig):    try:        vk.verify(sig, msg)        return True    except ecdsa.BadSignatureError:        return False
class TCPHandler(socketserver.StreamRequestHandler):
    def handle(self):        data = self.rfile.readline().strip()        user, signature = data.split(b",")        sig = bytes.fromhex(signature.decode())        try:            if valid_signature(user, sig):                if user == b"admin":                    self.wfile.write(b"Hello admin! Here is your flag: " + FLAG)                else:                    self.wfile.write(pyjokes.get_joke().encode())            else:                self.wfile.write(b"Invalid signature!")        except Exception as ex:            self.wfile.write(b"Something went wrong!")
if __name__ == '__main__':    server = socketserver.ForkingTCPServer(("0.0.0.0", 10100), TCPHandler)    server.serve_forever()```Basic info we can get from it:- The handler will try to first `valid_signature`- `valid_signature` will use the msg and signature you provided and verify they match- Checks that the message you send equals "admin" before sending the flag
Since we cannot send "admin" to the signer I had to do some research into how ecdsa works. 
## How the algorithmAn ECDSA signature is a pair of integers `(r,s)`.
The ECDSA signature algorithm works like so:1. `e = H(m)` where H is a hashing function (i.e sha1, sha256)2. Pick a random `k` such that `0 < k < n-1`3. Compute `(x,y) = kG` where G is the prime order of curve4. `r = x mod n`5. `s = inverse(k)*(z+r*d) mod n` where d is a private key integer and z is the leftmost bits of e6. Send `(m,r,s)`
The ECDSA verification algorithm works like so:1. `e = H(m)`2. `w = inverse(s) mod n`3. `u_1 = zw mod n` and `u_2 = zw mod n`4. `(x,y) = u_1*G + u_2*Q` where Q = d x Q5. If `r` is congruent with `x mod n` we know the signature is valid
## How we can crack itWhen I send the signer different strings to sign i noticed it would always send something with the prefix "13d8f71de2338048bcddd4846ea9762fa022172b6602f269c519892d8bf7e94f".... If we think back to how the ECDSA signature looks `(r,s)` we can see that r is not changing. This means we know that `r = x mod n` has to always be the same. From this information we can figure out that they are using the same "random" `k` everytime. So now lets make two request to the server with different m's. The signer will send us back `(m1,r,s1) and (m2,r,s2)`.
Since we know k is constant we can easily solve for it with the following equation:```k = (H(m1) - h(M2)) / (s1 - s2)```We then can solve for what x was: ```x = (k*s1 - h(m1)) / r```
With k and x known we can now start writing the script to sign "admin" and send to the server.
## Solution```Python# https://crypto.stackexchange.com/questions/57846/recovering-private-key-from-secp256k1-signaturesimport ecdsa, hashlibfrom ecdsa.numbertheory import inverse_modfrom ecdsa.ecdsa import Signaturefrom ecdsa import SigningKey, VerifyingKey, derfrom pwn import *
curve          = ecdsa.SECP256k1text_to_sign   = b"admin"hash_algorithm = hashlib.sha1
def get_key_from_hash():
    m_hash1 = '21298df8a3277357ee55b01df9530b535cf08ec1'    sig1_hex = '13d8f71de2338048bcddd4846ea9762fa022172b6602f269c519892d8bf7e94f77608e0387a7ba5392bd1e2b4ded1048133fb584b7686233af00a6e7c5d427e7'    m_hash2 = 'c692d6a10598e0a801576fdd4ecf3c37e45bfbc4'    sig2_hex = '13d8f71de2338048bcddd4846ea9762fa022172b6602f269c519892d8bf7e94fdcb6d55b347bfbe8c6a37e2b7c6ca764d7bd07f52d56df2ff80df7a59cbe51ec'
    m_hash1 = int(m_hash1, 16)    r = int(sig1_hex[:len(sig1_hex)//2], 16)    sig1 = int(sig1_hex[len(sig1_hex)//2:], 16)    m_hash2 = int(m_hash2, 16)    sig2 = int(sig2_hex[len(sig2_hex)//2:], 16)
    print("m_hash1 = " + hex(m_hash1))    print("sig1 = " + hex(sig1))    print("m_hash2 = " + hex(m_hash2))    print("sig2 = " + hex(sig2))    print("r = " + hex(r))
    r_i = inverse_mod(r, curve.order)    m_h_diff = (m_hash1 - m_hash2) % curve.order
    for k_try in (sig1 - sig2, sig1 + sig2, -sig1 - sig2, -sig1 + sig2):
        k = (m_h_diff * inverse_mod(k_try, curve.order)) % curve.order
        s_E = (((((sig1 * k) % curve.order) - m_hash1) % curve.order) * r_i) % curve.order
        key = SigningKey.from_secret_exponent(s_E, curve=curve, hashfunc=hash_algorithm)
        if key.get_verifying_key().pubkey.verifies(m_hash1, Signature(r, sig1)):            print("ECDSA Private Key = " + "".join("{:02x}".format(c) for c in key.to_string())) # If we got here we found a solution            return key
def sign_text(priv_key):    sk = ecdsa.SigningKey.from_string(priv_key.to_string(), curve=curve)    vk = sk.get_verifying_key()    sig = sk.sign(text_to_sign)    signed_message = "".join("{:02x}".format(c) for c in sig)    return "{},{}".format(text_to_sign.decode("utf-8"), signed_message)
def send_message(s_m):    target = remote('chal.cybersecurityrumble.de', 10100)    print("Sending '{}'".format(s_m))    target.sendline(s_m)    target.interactive()
signed_message = sign_text(get_key_from_hash())print(send_message(signed_message))```Once you run this script the server will print "Hello admin! Here is your flag: CSR{m33333333333p}".
flag = CSR{m33333333333p}