UTCTF 2024 - simple signature

Write up for UTCTF 2024 - Crypto/simple signature

Challenge

The s in rsa stands for secure.

#!/usr/bin/env python3
from Crypto.PublicKey import RSA

key = RSA.generate(2048)

print('Welcome to the signature generator!')
print('This service generates signatures for nonnegative integer messages.')
print('Today\'s RSA parameters are: ')
print(f'n = {key.n}')
print(f'e = {key.e}')

admit = []
i = 0
while True:
    print('Enter a message as an integer (enter 0 to stop): ',end='')
    x = int(input())
    if x == 0 and i == 0:
        print('You must request at least one signature.')
        continue
    if x == 0:
        break
    # technically not a correct hash function, but they don't need to know that
    sig = pow((x + i) % key.n, key.d, key.n)
    print('Your signature is: ', end='')
    print(sig)
    admit.append((x, sig))
    i += 1

print('Now, come up with your own pair!')
print('Enter a message: ',end='')
x = int(input())
print('Enter a signature: ',end='')
s = int(input())

if (x, s) in admit:
    print('Cannot enter a message that you already requested.')
    exit(0)

if (pow(s, key.e, key.n) - (x + i)) % key.n == 0:
    print("Congrats! Here is the flag: utflag{a1m05t_t3xtb00k_3x3rc153}")
else:
    print('Invalid signature.')

Explain

The server receives the message and returns the RSA signature value. Each time you sign, the server calculates the signature value of the message value you entered + i (starting from i = 0).

Solve

from pwn import *

r = remote("betta.utctf.live", 4374)

r.recvuntil(b"n = ")
n = int(r.recvline()[:-1])

r.recvuntil(b"e = ")
e = int(r.recvline()[:-1])

r.recvuntil(b"Enter a message as an integer (enter 0 to stop):")
r.sendline(b"1")

r.recvuntil(b"Enter a message as an integer (enter 0 to stop):")
r.sendline(b"4")

r.recvuntil(b"Your signature is: ")
s = r.recvline()[:-1]

r.recvuntil(b"Enter a message as an integer (enter 0 to stop):")
r.sendline(b"0")

r.recvuntil(b"Enter a message: ")
r.sendline(b"3")

r.recvuntil(b"Enter a signature: ")
r.sendline(s)

r.recvuntil(b"Congrats! Here is the flag: ")
print(str(r.recvline(), "utf-8")[:-1])

❯ python3 utctf_simple-signature.py
[+] Opening connection to betta.utctf.live on port 4374: Done
utflag{a1m05t_t3xtb00k_3x3rc153}
[*] Closed connection to betta.utctf.live port 4374