t00 rare (pwn2win 2021)

solve.sage

from tqdm import tqdm

debug = False

p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
E = EllipticCurve(Zmod(p), [a, b])
G = E(0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296,
      0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5)

q = 115792089210356248762697446949407573529996955224135760342422259061068512044369

if not debug:
    q1 = 2 * 2 * 2 * 2 * 3 * 71 * 131 * 373 * 3407
    q2 = 17449 * 38189 * 187019741 * 622491383 * 1002328039319 * 2624747550333869278416773953
else:
    q1 = 2 * 2 * 2 * 2 * 3 * 71
    q2 = 131 * 373 * 3407 * 17449 * 38189 * 187019741 * 622491383 * 1002328039319 * 2624747550333869278416773953


# order of P < 2^256
def precompute_table(P):
    if debug: return P

    # finish the coming operations in 16 additions!
    T = []
    for i in tqdm(range(0, 256, 16)):
        row = []
        Q = 0*G
        step = (2**i) * P
        for _ in range(1<<16):
            row.append(Q)
            Q += step
        T.append(row)
    return T

# faster multiplication
def faster_mul(TP, r):
    if debug: return TP*r
    
    R = 0*G
    for i in range(16):
        R += TP[i][r&0xffff]
        r >>= 16
    return R
       
r = Integer(input())
s = Integer(input())

# There exists x such that pow(7, x*q2, q) * G == H
H = int(pow(r, -1, q) * s) * E.lift_x(r)

rq1 = int(sqrt(q1))
print(f'[ ] {rq1 = }')

# 25s
TG = precompute_table(G)

# 25s
TH = precompute_table(H)

# 5 minutes (2h without optimization :))
lhs = {}
step = pow(7, rq1*q2, q)
cur = 1
for k in tqdm(range(rq1)):
    P = faster_mul(TG, int(cur))
    u = P.xy()[0]
    lhs[u] = k
    cur *= step

print('[ ] LHS done!')

step = pow(7, -q2, q)
cur = 1
for k in tqdm(range(rq1)):
    P = faster_mul(TH, int(cur))
    u = P.xy()[0]
    l = lhs.get(u)
    cur *= step
    if l is not None: break
else:
    assert False, "Not found"

y = l * rq1 + k
print(f'[ ] {y = }')
x = int(pow(7, q2*y, q))

print(f'[*] {x = }')

t00-rare.py

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

import os
from pwn import *
import requests
import base64
from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
import hashlib
from gmpy2 import powmod
import json

from ctfools import Challenge as BaseChallenge
from ctfools import work # work(alg, check[, prefix, suffix, length, charset, threads])
from ctfools import discord_notify # discord_notify(url, content)

class Challenge(BaseChallenge):
    def __init__(self, local, *args, **kwargs):
        super().__init__(local=local, *args, **kwargs)

        # Do proof-of-work
        if not local:
            t = self.r.recvline().decode().strip().split(' ')
            assert t[0] == 'hashcash'
            assert t[1] == '-mb25'
            with os.popen(f'hashcash -mb25 {t[2]}') as f:
                soln = f.read()
            self.r.sendline(soln)

        self.r.recvuntil(b'4- Exit\n')

    def sign(self, h):
        self.r.sendline('1')
        self.r.sendlineafter(b'hash (hex): ', format(h, 'x'))
        self.r.recvuntil(b'(')
        r, s = list(map(int, self.r.recvuntil(b')')[:-1].decode().split(',')))
        return r, s
    
    def verify(self, h, r, s):
        self.r.sendline('2')
        self.r.sendlineafter(b'hash (hex): ', format(h, 'x'))
        self.r.sendlineafter(b'r: ', str(r))
        self.r.sendlineafter(b's: ', str(s))
        self.r.recvline()
        return self.r.recvline().strip().decode() == 'Correct!'

    def flag(self, password):
        self.r.sendline('3')
        self.r.sendline(str(password))
        self.r.recvuntil(b'Signing ')
        h = int(self.r.recvuntil(b'.')[:-1].decode(), 16)
        self.r.recvline()
        return h, self.r.recvline().strip().decode()

class Solver:
    def __init__(self):
        self.r = process(['sage', 'solve.sage'])
    
    def recover_x(self, _r, _s):
        self.r.sendline(str(_r))
        self.r.sendline(str(_s))
        while True:
            l = self.r.recvline().strip().decode()
            print(l)
            if not l.startswith('[*] x = '): continue
            return int(l[8:])

def main():
    local = 'local' in os.environ
    log = 'log' in os.environ

    r = Challenge(
        conn='nc t00-rare.pwn2win.party 1337',
        proc=['sage', 'challenge/chall.sage'],
        local=local,
        log=log)
    solver = Solver()
   
    # Vulnerability 1: Although sign(flag_digest) is banned, sign(flag_digest + order) is not.
    fh, _ = r.flag(0)
    fr, fs = r.sign(fh + 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551)
    assert r.verify(fh, fr, fs)

    # Vulnerability 2: x is poorly generated (has a small order)
    zr, zs = r.sign(0)
    x = solver.recover_x(zr, zs)

    q = 115792089210356248762697446949407573529996955224135760342422259061068512044369
    password = fs * pow(fh + fr*x, -1, q) % q
    _, flag = r.flag(password)
    print(flag)
    # CTF-BR{__0f_course_sucH_4_W3ak_k3y_w0uld_be_rare...}

    r.interactive()

if __name__ == '__main__':
    main()

# The x recovered may be incorrect (50%). Just reroll until success.