I'm trying to solve the CTF challenge called ProSign 3 at Cryptohack platform which involves exploiting an ECDSA signing service that allows us to sign a fixed message being padded with the time ... or verify a signature given a message, a value of r, and a value of s. Successful verification yields in the flag returned. Now the main objective is to spoof a signature and I've been struggling to do that.

As a start I'm aware of a potential exploit with the sign_time() function which takes the current time in seconds as the value n used within randrange(1,n) for the secret integer to be used in the calculation of r and s -> so we can exploit this to send only when time in seconds = 2 ... yielding randrange(1,2) to only return 1 everytime and causing the value of r to be the x coordinate of generator point G of the curve.

That's pretty much where I am right now so further assistance will be appreciated.

Here is the challenge source code for your reference:

#!/usr/bin/env python3

import hashlib
from Crypto.Util.number import bytes_to_long, long_to_bytes
from ecdsa.ecdsa import Public_key, Private_key, Signature, generator_192
from utils import listener
from datetime import datetime
from random import randrange

FLAG = "crypto{?????????????????????????}"
g = generator_192
n = g.order()

class Challenge():
    def __init__(self):
        self.before_input = "Welcome to ProSign 3. You can sign_time or verify.\n"
        secret = randrange(1, n)
        self.pubkey = Public_key(g, g * secret)
        self.privkey = Private_key(self.pubkey, secret)

    def sha1(self, data):
        sha1_hash = hashlib.sha1()
        return sha1_hash.digest()

    def sign_time(self):
        now = datetime.now()
        m, n = int(now.strftime("%m")), int(now.strftime("%S"))
        current = f"{m}:{n}"
        msg = f"Current time is {current}"
        hsh = self.sha1(msg.encode())
        sig = self.privkey.sign(bytes_to_long(hsh), randrange(1, n))
        return {"msg": msg, "r": hex(sig.r), "s": hex(sig.s)}

    def verify(self, msg, sig_r, sig_s):
        hsh = bytes_to_long(self.sha1(msg.encode()))
        sig_r = int(sig_r, 16)
        sig_s = int(sig_s, 16)
        sig = Signature(sig_r, sig_s)

        if self.pubkey.verifies(hsh, sig):
            return True
            return False

    # This challenge function is called on your input, which must be JSON
    # encoded
    def challenge(self, your_input):
        if 'option' not in your_input:
            return {"error": "You must send an option to this server"}

        elif your_input['option'] == 'sign_time':
            signature = self.sign_time()
            return signature

        elif your_input['option'] == 'verify':
            msg = your_input['msg']
            r = your_input['r']
            s = your_input['s']
            verified = self.verify(msg, r, s)
            if verified:
                if msg == "unlock":
                    self.exit = True
                    return {"flag": FLAG}
                return {"result": "Message verified"}
                return {"result": "Bad signature"}

            return {"error": "Decoding fail"}

  • $\begingroup$ This is a dump of a CTF, thus off-topic. But we can give a hint: in ECDSA, the first component of the signature is the $x$ coordinate of $k\,G$ where $k$ must be secret. Otherwise uh, assuming the message or it's hash is public, as well as the signature, the private key leaks! In fact, $k$ should be essentially uniformly random in $[0,n)$. $\endgroup$
    – fgrieu
    Apr 17 at 10:02