## Trunc
### Challenge> I wish I could say more, but I don't want to!> `nc 02.cr.yp.toc.tf 23010`> [TRUNC.txz](https://cr.yp.toc.tf/tasks/TRUNC_dd1e2d91b790125fdfc7596f0076fa476446d2fb.txz)
```python#!/usr/bin/env python3
from Crypto.Util.number import *from hashlib import sha256import ecdsafrom flag import FLAG
E = ecdsa.SECP256k1G, n = E.generator, E.order
cryptonym = b'Persian Gulf'
def keygen(n, G):    privkey = getRandomRange(1, n-1)    pubkey = privkey * G    return (pubkey, privkey)
def sign(msg, keypair):    nbit, dbit = 256, 25    pubkey, privkey = keypair    privkey_bytes = long_to_bytes(privkey)    x = int(sha256(privkey_bytes).hexdigest(), 16) % 2**dbit    while True:        k, l = [(getRandomNBitInteger(nbit) << dbit) + x for _ in '01']        u, v = (k * G).x(), (l * G).y()        if u + v > 0:            break    h = int(sha256(msg).hexdigest(), 16)    s = inverse(k, n) * (h * u - v * privkey) % n    return (int(u), int(v), int(s))
def verify(msg, pubkey, sig):    if any(x < 1 or x >= n for x in sig):        return False    u, v, s = sig    h = int(sha256(msg).hexdigest(), 16)    k, l = h * u * inverse(s, n), v * inverse(s, n)    X = (k * G + (n - l) * pubkey).x()    return (X - u) % n == 0
def die(*args):    pr(*args)    quit()
def pr(*args):    s = " ".join(map(str, args))    sys.stdout.write(s + "\n")    sys.stdout.flush()
def sc():    return sys.stdin.readline().strip()
def main():    border = "+"    pr(border*72)    pr(border, " hi all, welcome to the high secure elliptic curve signature oracle!", border)    pr(border, " Your mission is to sign the out cryptonym, try your best :)        ", border)    pr(border*72)
    keypair = keygen(n, G)    pubkey, privkey = keypair
    while True:        pr("| Options: \n|\t[P]rint the pubkey \n|\t[S]ign \n|\t[V]erify \n|\t[Q]uit")        ans = sc().lower()        if ans == 'p':            pr("| pubkey =", pubkey.x(), pubkey.y())        elif ans == 's':            pr("| send your hex message to sign: ")            msg = sc()            try:                msg = bytes.fromhex(msg)            except:                die("| your message is not valid! Bye!!")            if msg == cryptonym:                die('| Kidding me? Bye')            msg = msg[:14]            sig = sign(msg, keypair)            pr("| sign =", sig)        elif ans == 'v':            pr("| send your hex message to verify: ")            msg = sc()            try:                msg = bytes.fromhex(msg)            except:                die("| your message is not valid! Bye!!")            pr("| send the signature separated with comma: ")            sig = sc()            try:                sig = [int(s) for s in sig.split(',')]            except:                die("| your signature is not valid! Bye!!")            if verify(msg, pubkey, sig):                if msg == cryptonym:                    die("| Good job! Congrats, the flag is:", FLAG)                else:                    pr("| your message is verified!!")            else:                die("| your signature is not valid! Bye!!")        elif ans == 'q':            die("Quitting ...")        else:            die("Bye ...")
if __name__ == '__main__':    main()```
### SolutionHere we have a ECDSA-like signature scheme: nonces $k$ and $l$ are generated in such a way, that they always have their 25 LSBs dependent only on private key, thus always the same, then $u$ and $v$ are obtained as $x$-coordinates of $kG$ and $lG$ respectively, where $G$ is a generator on the curve `secp256k1`, then $h$ = `sha256(msg)` and $s \equiv k^{-1}(hu - vd) \mod n$ are computed, where $d$ is the private key and $n$ is the order of the curve. $(u, v, s)$ is a signature for $h$.
Verification works as follows: again, $h$ = `sha256(msg)` is computed, then $k \equiv hus^{-1} \mod n$ and $l \equiv vs^{-1} \mod n$ are computed, after that $X$ is derived as $x$-coordinate of $kG - lP$, where $P = G * d$ is the public key. Signature verifies iff $X \equiv u \mod n$.During interaction with the service we can obtain the public key by sending `p`, sign any message (except `Persian Gulf`) by sending `s`, verify a signature for a message with `v`, and if the signature for `Persian Gulf` verifies, we are given the flag, and quit with `q`.
This is an unintended solution, which doesn't exploit odd nonce generation during signature creation.If $h_1$ is a hash of some message $m$, and $h_2$ is the hash for `Persian Gulf`, we can write $h_2 \equiv m h_1 \mod n$, and if $(u_1, v_1, s_1)$ is a valid signature for $h_1$, then $(u_1, v_1m, s_1m)$ is a valid signature for $h_2$.
Proof: during verification of $h_1$ we have $k \equiv h_1u_1s_1^{-1} \mod n$ and $l \equiv v_1s_1^{-1} \mod n$. During verification of $h_2$ we have $k \equiv h_1mu_1(ms_1)^{-1} \equiv h_1mu_1m^{-1}s_1^{-1} \equiv h_1u_1s_1^{-1}\mod n$ and $l \equiv v_1m(s_1m)^{-1} \equiv v_1ms_1^{-1}m^{-1} \equiv v_1s_1^{-1}\mod n$, so $k, l$ are the same, thus $X$ is the same. And since $u$ is also the same, this signature will also verify.
#### Implementation
```python#!/usr/bin/env python3from pwn import remotefrom ecdsa import SECP256k1from hashlib import sha256
n = SECP256k1.orderm1 = b'lol' # any other message is finem2 = b'Persian Gulf'h1 = int(sha256(m1).hexdigest(), 16)h2 = int(sha256(m2).hexdigest(), 16)m = h2 * pow(h1, -1, n) % nr = remote("02.cr.yp.toc.tf", 23010)for _ in range(9):    r.recvline()r.sendline('s')r.recvline()r.sendline(m1.hex())u1, v1, w1 = eval(r.recvline()[8:])u2, v2, w2 = u1, v1 * m % n, w1 * m % nfor _ in range(5):    r.recvline()r.sendline('v')r.recvline()r.sendline(m2.hex())r.recvline()r.sendline(','.join(map(str, [u2, v2, w2])))print(r.recvline().decode().strip().split()[-1])r.close()```##### Flag
`CCTF{__ECC_Bi4seD_N0nCE_53ns3_LLL!!!}`