[SECCON Beginners CTF 2020] RSA Calc

F(1337)=FLAG!

from Crypto.Util.number import *
from params import p, q, flag
import binascii
import sys
import signal

N = p * q
e = 65537
d = inverse(e, (p-1)*(q-1))

def input(prompt=''):
    sys.stdout.write(prompt)
    sys.stdout.flush()
    return sys.stdin.buffer.readline().strip()

def menu():
    sys.stdout.write('''----------
1) Sign
2) Exec
3) Exit
''')
    try:
        sys.stdout.write('> ')
        sys.stdout.flush()
        return int(sys.stdin.readline().strip())
    except:
        return 3

def cmd_sign():
    data = input('data> ')
    if len(data) > 256:
        sys.stdout.write('Too long\n')
        return

    if b'F' in data or b'1337' in data:
        sys.stdout.write('Error\n')
        return

    signature = pow(bytes_to_long(data), d, N)
    sys.stdout.write('Signature: {}\n'.format(binascii.hexlify(long_to_bytes(signature)).decode()))

def cmd_exec():
    data = input('data> ')
    signature = int(input('signature> '), 16)

    if signature < 0 or signature >= N:
        sys.stdout.write('Invalid signature\n')
        return

    check = long_to_bytes(pow(signature, e, N))
    if data != check:
        sys.stdout.write('Invalid signature\n')
        return

    chunks = data.split(b',')
    stack = []
    for c in chunks:
        if c == b'+':
            stack.append(stack.pop() + stack.pop())
        elif c == b'-':
            stack.append(stack.pop() - stack.pop())
        elif c == b'*':
            stack.append(stack.pop() * stack.pop())
        elif c == b'/':
            stack.append(stack.pop() / stack.pop())
        elif c == b'F':
            val = stack.pop()
            if val == 1337:
                sys.stdout.write(flag + '\n')
        else:
            stack.append(int(c))

    sys.stdout.write('Answer: {}\n'.format(int(stack.pop())))

def main():
    sys.stdout.write('N: {}\n'.format(N))
    while True:
        try:
            command = menu()
            if command == 1:
                cmd_sign()
            if command == 2:
                cmd_exec()
            elif command == 3:
                break
        except:
            sys.stdout.write('Error\n')
            break

if __name__ == '__main__':
    signal.alarm(60)
    main()

解説

cmd_exec()で1337,Fを実行させられればflagを得ることが出来ます
cmd_execで計算を実行するには署名が必要になりますが、署名を発行するcmd_sign()は1337およびFの入った入力を禁止しています
また、Nは1024bitあるため秘密鍵を大会期間中に解析するのは現実的ではありません

RSAでは公開鍵N以上の情報を暗号化すると、Nで剰余を取る際にデータの損失が発生します
しかし、cmd_sign()では署名するデータを256B(=2048bit)まで受けつけています
これを利用して署名の衝突を発生させます

RSAの署名の計算式は signature = plain ^ d mod n です
ここで (plain + n) ^ d mod n にしても先の式と同じ値を得ることが出来、署名の衝突を発生させられます

あとは先ほど出した値をサーバーに投げて署名を生成し、その署名を使って1337,Fを実行するだけです

ソルバーはこちら

#!/usr/bin/env python3
from Crypto.Util.number import *
from pwn import *

target = ('nc rsacalc.quals.beginners.seccon.jp 10001'.split(' '))

io = process(target)

N = 104452494729225554355976515219434250315042721821732083150042629449067462088950256883215876205745135468798595887009776140577366427694442102435040692014432042744950729052688898874640941018896944459642713041721494593008013710266103709315252166260911167655036124762795890569902823253950438711272265515759550956133

payload = b'1'
io.sendlineafter('> ', payload)
payload = long_to_bytes(bytes_to_long(b'1337,F') + N)
io.sendlineafter('> ', payload)
o = io.readline()

sig = o[len("Signature: "):len(o)-1]
print(sig)

payload = b'2'
io.sendlineafter('> ', payload)
payload = b'1337,F'
io.sendlineafter('data> ', payload)
payload = sig
io.sendlineafter('signature> ', payload)
print(io.readline())

metarin@archdesk ../seccon_beg/crypto/rsacalc % ./sol.py                            
[+] Starting local process '/usr/bin/nc': pid 209384
b'4e06f717e17244d00ab84deedf099e9badbbd5395536ccb5ec733640c2ac199dcbddb1191b1ad93b2748faafca56e394965d7bacf69dd2a5493ccfb7df0556ceeb44245911b457f39f14110d233f23f17798ee9b2af9dc9d52bcbd9ba51957f2e4c5de28b39c356ce03dc5aa4d731fea8367c5bfda3345800316ddea4e985d15'
b'ctf4b{SIgn_n33ds_P4d&H4sh}\n'

ctf4b{SIgn_n33ds_P4d&H4sh}