This challenge was about signature forgery. In this one we have server and it allows to

  1. Get public key
  2. Create signature
  3. Verify signature

Signature creation uses secret d and number c

\[ s = (k + c * d) % p \]

And signature verification uses message m, R and signature s

\[ gen * s == R + Q * H(R, m) \]

This is Blind Schnorr signature scheme: by design, in order to sign message server should

  1. generate random nonce, in our case it’s k and R=g*k
  2. return R to client
  3. Receive blind c to sign
  4. generates signature $$ s = (k+c*d) \mod p $$
  5. Send signature as pair (R, s)

But in our case it behaves little bit different: generates nonce k and sends to client R, and then signs all messages using same k

The randomness of nonce is crucial in this and many other signature schemes.

In this case, non random nonce allows to restore secret value d

To do this we need to generate 2 signatures of different messages

\[ \begin{aligned} &s_1 = (k + c_1 * d) \mod p\\ &s_2 = (k + c_2 * d) \mod p\\ &{s_1-s_2} = (c_1-c_2)*d \mod p \\ &d = (s_1-s_2)*{(c_1-c_2)}^{-1} \mod p \end{aligned} \]

After getting secret d we can generate as many signatures we want. Here is my script:

import hashlib
from pwn import * 
import json
from ecdsa.curves import NIST256p
from ecdsa.ellipticcurve import Point, PointJacobi

curve = NIST256p
gen = curve.generator
p = gen.order()


def point2bytes(P):
    return P.to_bytes()


def hash_func(Rp, m):
    if isinstance(m, str):
        m = m.encode()
    return int(
        int.from_bytes(hashlib.sha256(point2bytes(Rp) + m).digest(), byteorder="big")
        % p
    )

io = remote('127.0.0.1',1337)

io.sendline(json.dumps({"cmd": "GETKEY"}).encode())
key = json.loads(io.recvline())
Q = PointJacobi.from_affine(
                    Point(curve.curve, key["Q"][0], key["Q"][1])
                )

io.sendline(json.dumps({"cmd": "REQUEST"}).encode())
req = json.loads(io.recvline())
R = PointJacobi.from_affine(
                    Point(curve.curve, req["R"][0], req["R"][1])
                )
def sign_message(message):
    c = hash_func(R, message) % p
    challenge_data = {"cmd": "CHALLENGE", "c": int(c)}
    io.sendline(json.dumps(challenge_data).encode())
    signed = json.loads(io.recvline())['s']
    return signed, c
def forge(k,d, R, msg):
    c = hash_func(R, msg)
    return int((k+c*d) % p)

s1, c1 = sign_message(b'1')
s2, c2 = sign_message(b'2')
d = ((s1 - s2) * pow(c1-c2, -1, p)) % p

k = (s1 - c1*d) % p
forged = forge(k, d, R, b'3')

def verify(msg, R, s):
    verify_data = {"cmd": "VERIFY", "msg": msg, "sig": [[int(R.x()), int(R.y())], s]}
    io.sendline(json.dumps(verify_data).encode())
    res = io.recvline()
    return res
verify('1', R, s1)
verify('2', R, s2)
verify('3', R, forged)
print(io.recvline())
io.close()