Justice

Another nice chall by the great bebo07 in ASCWG 2025

Handouts

from hashlib import sha1,sha256
from Crypto.Util.number import bytes_to_long, long_to_bytes,inverse
from random import randint
from sage.all import *


FLAG = b'ASCWG{TESTTEST}'
a = 'redacted'
b = 'redacted'
q= 11722926242306411491117245929733953191095935082498997045653937809623622288511133179535069277231629076589496415875947858138184916449452869671412741618610351

E = EllipticCurve(GF(q), (a,b))

p = E.order
G = E.gen()
d=bytes_to_long(FLAG)
pub = d * G   

def sign(msg,d):
	hsh=bytes_to_long(sha1(msg).digest())
	while True:
		k=randint(1,2**450); print(f"🔑 Random k: {k}")
		r=int((k*G)[0])
		if r== 0:
			continue
		s=inverse(k,p)*(hsh+r*d)
		s=s%p
		if s==0:
			continue
		break
	return r,s
def verify(msg,r,s):
	hsh = bytes_to_long(sha1(msg.encode()).digest())
	u1=int((hsh*inverse(s,p))%p)
	u2 = int((r*inverse(s,p))%p)
	P=u1*G+u2*pub
	if P == E(0):
		return False
	return r == int(P[0])%p




def banner():
    print("="*50)
    print("🔐 ECDSA Signing & Verification Tool 🔐")
    print("="*50)
    x, y = G.xy()
    print(f"📍 Generator Point G:\n  x = {x}\n  y = {y}")
    print("-" * 50)
    px, py = pub.xy()
    print(f"🔑 Public Key Point P = d * G:\n  x = {px}\n  y = {py}")
    print("="*50)


def menu():
    print("\n1. Sign a message")
    print("2. Verify a signature")
    print("3. Exit")
    return input("> ")

def main():
    banner()
    while True:
        choice = menu()
        if choice == '1':
            msg = input("Enter the message to sign: ").encode()
            r, s = sign(msg, d)
            print(f"✅ Signature:\n r = {r}\n s = {s}")
        elif choice == '2':
            msg = input("Enter the message: ")
            
            r = int(input("Enter r: "))
            s = int(input("Enter s: "))
            if verify(msg, r, s):
                    print("✅ Signature is valid.")
            else:
                    print("❌ Invalid signature.")
            
        elif choice == '3':
            print("👋 Bye!")
            break
        else:
            print("❗ Invalid choice. Try again.")

if __name__ == "__main__":
    main()

This was originally a sage script but I made it into a python one.

Analysis & Solver

First thing, we don't have params, but we get 2 points and we got the prime, so easily recoverable.

def recover_curve_params(P1, P2, q):
    (x1, y1), (x2, y2) = P1, P2


    rhs1 = (y1 * y1 - x1**3) % q
    rhs2 = (y2 * y2 - x2**3) % q

    # Solve the system:
    # rhs1 ≡ a*x1 + b mod q
    # rhs2 ≡ a*x2 + b mod q
    # Subtract to eliminate b:
    # (rhs1 - rhs2) ≡ a*(x1 - x2) mod q

    dx = (x1 - x2) % q
    dy = (rhs1 - rhs2) % q

    if dx == 0:
        raise ValueError("x1 and x2 must be different")

    inv_dx = inverse(dx, q)
    a = (dy * inv_dx) % q
    b = (rhs1 - a * x1) % q

    return a, b

HOST = ''
PORT = 

r = remote(HOST,PORT)

r.recvuntil(b"x =")

Gx  = int(r.recvline().strip().decode())
r.recvuntil(b"y =")
Gy  = int(r.recvline().strip().decode())

print(f"Generator Point G: ({Gx}, {Gy})")

r.recvuntil(b"x =")

Px  = int(r.recvline().strip().decode())
r.recvuntil(b"y =")
Py  = int(r.recvline().strip().decode())

print(f"Public Key Point P: ({Px}, {Py})")
G = (Gx, Gy)
P = (Px, Py)
a, b = recover_curve_params(G, P, q)
print(f"Recovered curve parameters: a = {a}, b = {b}")

# a = 4815856414273485008521009886158662377580908498051619172603873224815096892137442624802691170396892528556560135585222543889597791900006981343938433088594317
# b = 924137159683085407146266459099732051517989098018879140512217132800587918075090017890860584703284825990148993308623712217273700206154098706100311821627788

I also hardcoded the order and G cz it takes a while to find each run.

Essentially, the vuln is in the bias of the generation of the nonce, we can assume zero MSB because it,s generated between 1 and 2^450 and both prime and order are 512 bits long giving us 62 bits of 0 MSB, reducing it to HNP given enough signatures and large enough zero MSB.

$s_ik_i = z_i + r_id \pmod p$

$k_i − (s ^{−1}_i r_i)d + (−s^{ −1}_ i z_i) = 0 \pmod p$

Lattice Construction

We collect ( N ) ECDSA signatures $((r_i, s_i))$ on messages $( m_i )$, and define:

• ( $h_i = \text{SHA1}(m_i)$)

• ( $s_i^{-1} \equiv s_i^{-1} \mod p$ )

• ( $u_i = r_i \cdot s_i^{-1} \mod p$ )

• ( $t_i = h_i \cdot s_i^{-1} \mod p$ )

From the ECDSA signature equation:

$$s_i = k_i^{-1}(h_i + d \cdot r_i) \mod p \quad \Rightarrow \quad k_i = s_i^{-1}(h_i + d \cdot r_i) \mod p$$

Assuming the nonces ( k_i ) are biased and thus small, we construct a lattice ( \mathcal{L} \in \mathbb{Z}^{(N+1) \times (N+1)} ) with basis matrix:

$$\mathbf{M} = \begin{bmatrix} p & 0 & 0 & \cdots & 0 & 0 \\\\ 0 & p & 0 & \cdots & 0 & 0 \\\\ 0 & 0 & p & \cdots & 0 & 0 \\\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\\\ 0 & 0 & 0 & \cdots & p & 0 \\\\ u_0 & u_1 & u_2 & \cdots & u_{N-1} & 1 \\ \end{bmatrix}$$

We define the target vector:

$$\mathbf{t} = \begin{bmatrix} t_0 \\\\ t_1 \\\\ \vdots \\\\ t_{N-1} \\\\ 0 \\ \end{bmatrix}$$

After applying the LLL algorithm to ( \mathbf{M} ), we obtain a short vector ( \mathbf{v} \in \mathcal{L} ) such that:

$$\mathbf{v} = \mathbf{t} + d \cdot \mathbf{b}$$

for some ( \mathbf{b} \in \mathbb{Z}^{N+1} ). The private key ( d ) is then recovered from:

$$d = -(\mathbf{v} - \mathbf{t})_{N}$$

from hashlib import sha1
from sage.all import *
from Crypto.Util.number import long_to_bytes, bytes_to_long
from pwn import *


q = 11722926242306411491117245929733953191095935082498997045653937809623622288511133179535069277231629076589496415875947858138184916449452869671412741618610351
a = 4815856414273485008521009886158662377580908498051619172603873224815096892137442624802691170396892528556560135585222543889597791900006981343938433088594317
b = 924137159683085407146266459099732051517989098018879140512217132800587918075090017890860584703284825990148993308623712217273700206154098706100311821627788
HOST = '34.34.134.114'
PORT = 1337
E = EllipticCurve(GF(q), [a, b])
p = 11722926242306411491117245929733953191095935082498997045653937809623622288511151884678862566759672851603429907204670408548428966919710305541766273397617937
G = (7728378601654153848669314158385164180059522302967914677970583993232650765945138463345363849283938899967491342470187529185442397630334781849953517323614916, 7874571890936525485550181333243163244163050157268353433706170605567272679624536152919087771798043729293387274615830878727295364267072336018937872547532829)
G_real = E(G[0], G[1])
conn = remote(HOST, PORT)
def sign_oracle(msg):
    conn.recvuntil(b"> ")
    conn.sendline(b'1')
    conn.recvuntil(b"to sign: ")
    conn.sendline(msg)
    conn.recvuntil(b"r =")
    r_val = int(conn.recvline().strip().decode())
    conn.recvuntil(b"s =")
    s = int(conn.recvline().strip().decode())
    return r_val, s 
    
num_signatures = 40
signatures = []
for i in range(num_signatures):
    msg = f"message {i}".encode()
    signatures.append(sign_oracle(msg))

N = num_signatures
u_list, t_list = [], []
for i in range(N):
    r, s = signatures[i]
    h = bytes_to_long(sha1(f"message {i}".encode()).digest())
    s_inv = inverse_mod(ZZ(s), ZZ(p))
    u_list.append((r * s_inv) % p)
    t_list.append((h * s_inv) % p)

M = Matrix(ZZ, N + 1, N + 1)
for i in range(N):
    M[i, i] = p
for i in range(N):
    M[N, i] = u_list[i]
M[N, N] = 1 

B = M.LLL()

T = vector(ZZ, t_list + [0])

B_inv = B.inverse()
coeffs_rational = vector(QQ, T) * B_inv
coeffs_rounded = vector(ZZ, [round(c) for c in coeffs_rational])

v = coeffs_rounded * B

difference_vector = v - T

d_recovered = -difference_vector[-1]

print(f"d: {d_recovered}")

if d_recovered != 0:
    try:
        flag = long_to_bytes(int(d_recovered))
        if b'ASCWG' in flag:
            print(f'FLAG: {flag.decode()}')
    except Exception as e:
        print(f"Error during conversion: {e}")
# ASCWG{b1453d_n0nc3_m4d3_d54_vuln3r4bl3}

Feedback

Tbh? amazing challenge, learned alot about HNP.