Back to writeups
FlagYardcryptosolved

Crypto CTF

1 Jan 2025 · by 0xIDA

Solvers

Crypto CTF

Author: 0xIDA
Platform: FlagYard · Category: crypto · Difficulty: N/A

Flag: FlagY{462af29a4bf35f08ade8393c7d6cf3a9}

Challenge: tcp.flagyard.com:26998 — Easy — Crypto

Solvers

Summary

The server provides three operations on a fresh 1024-bit RSA key per connection:

  • Sign a message using d mod (p-1) (CRT exponent for p).
  • Verify a signature against n.
  • Encrypt a message modulo q.

The signing and encryption paths are each correct modulo only one factor, while verification uses the full n. This lets us recover the two primes separately from a single connection and then forge a valid signature for the privileged message give_me_flag.

Vulnerability chain

  1. Key-per-connection: p and q are regenerated every time the service starts a new TCP session, so all oracle queries must be made on the same connection.
  2. Signature path uses only p: sig = sha256(msg)^d mod p. Therefore sig^e ≡ sha256(msg) (mod p), i.e. p | sig^e − h.
  3. Encryption path uses only q: enc = msg^e mod q. Therefore q | msg^e − enc.
  4. Recover p and q from two queries each:
    • p = gcd(s_a^e − h_a, s_b^e − h_b) (up to a small cofactor).
    • q = gcd(2^e − enc_2, 3^e − enc_3) (up to a small cofactor).
  5. Forge a full signature: with p and q known, compute d = e^{-1} mod (p-1)(q-1) and sign give_me_flag.
  6. Submit in the same session to get the flag.

Exact exploit steps

from pwn import remote
from Crypto.Util.number import bytes_to_long, GCD
from hashlib import sha256
import gmpy2

e = 65537
HOST, PORT = 'tcp.flagyard.com', 26998

io = remote(HOST, PORT)

# 1. Two signatures under the same p
io.sendlineafter(b'> ', b'1'); io.sendlineafter(b'Message to sign: ', b'a')
s1 = int(io.recvline().split(b' ')[-1])
io.sendlineafter(b'> ', b'1'); io.sendlineafter(b'Message to sign: ', b'b')
s2 = int(io.recvline().split(b' ')[-1])

# 2. Two encryptions under the same q
io.sendlineafter(b'> ', b'3'); io.sendlineafter(b'Message to encrypt: ', b'\x02')
t2 = int(io.recvline().split(b' ')[-1])
io.sendlineafter(b'> ', b'3'); io.sendlineafter(b'Message to encrypt: ', b'\x03')
t3 = int(io.recvline().split(b' ')[-1])

# 3. Recover q (cheap)
q = GCD(2**e - t2, 3**e - t3)

# 4. Recover p (expensive ~25 s because s_i is ~512 bits, exponent e=65537)
ha = bytes_to_long(sha256(b'a').digest())
hb = bytes_to_long(sha256(b'b').digest())
b = gmpy2.mpz(s2)**e - hb
a = pow(gmpy2.mpz(s1), e, b) - ha
p = int(gmpy2.gcd(a, b))

# 5. Remove small cofactors from both primes
for prime in [p, q]:
    for f in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]:
        while prime % f == 0 and prime.bit_length() > 512:
            prime //= f

n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

# 6. Forge signature for the privileged message
htarget = bytes_to_long(sha256(b'give_me_flag').digest())
sig = pow(htarget, d, n)

# 7. Submit in the same connection
io.sendlineafter(b'> ', b'2')
io.sendlineafter(b'Message: ', b'give_me_flag')
io.sendlineafter(b'Signature: ', str(sig).encode())
print(io.recvline())  # Here is your flag: FlagY{...}

Key pitfall

  • The server creates a new key per connection. Early attempts failed because the solve script closed the first connection, computed p/q, and then opened a new connection to submit — but the new connection had a different n, so the forged signature was invalid against a fresh key. All four oracle queries plus the final submission must be performed in the same remote() session.
  • Send raw bytes, not ASCII digits. The encryption menu expects the message as bytes; sending b'2' encrypts the ASCII value 50 instead of the integer 2. Use b'\x02' and b'\x03'.

Remediation

  • Do not leak CRT-reduced signatures. The signing operation should compute the signature modulo n = p*q (or correctly combine CRT and verify against the same n). Returning h^d mod p is equivalent to disclosing a factor of n through two signatures.
  • Do not expose encryption under a single factor. The encryption operation should use the full modulus n, not q.
  • Use a single, consistent key and fixed public exponent for the entire service lifetime (or at least for the lifetime of a client session), so that these cross-modulus relationships cannot be exploited.