angstromCTF 2020 | RSA-OTP

from Crypto.Util.number import bytes_to_long
from Crypto.Random.random import getrandbits # cryptographically secure random get pranked
from Crypto.PublicKey import RSA
from secret import d, flag
# 1024-bit rsa is unbreakable good luck
n = 136018504103450744973226909842302068548152091075992057924542109508619184755376768234431340139221594830546350990111376831021784447802637892581966979028826938086172778174904402131356050027973054268478615792292786398076726225353285978936466029682788745325588134172850614459269636474769858467022326624710771957129
e = 0x10001
key = RSA.construct((n,e,d))

f = bytes_to_long(bytes(flag,'utf-8'))
print("Encrypted flag:")
print(key.encrypt(f,0)[0])

def otp(m):
    # perfect secrecy ahahahaha
    out = ""
    for i in bin(m)[2:]:
        out+=str(int(i)^getrandbits(1))
    return out

while 1:
    try:
        i = int(input("Enter message to sign: "))
        assert(0 < i < n)
        print("signed message (encrypted with unbreakable otp):")
        print(otp(key.decrypt(i)))
    except:
        print("bad input, exiting")
        break

RSAの好きな暗号文を平文にしてくれるけど、その後でランダムなbit列とXORを取るので本当に情報が手に入らない。手に入るのは平文のbit数くらいなので、これに着目してやると LSBLeakAttackができる

from ptrlib import *

n = 136018504103450744973226909842302068548152091075992057924542109508619184755376768234431340139221594830546350990111376831021784447802637892581966979028826938086172778174904402131356050027973054268478615792292786398076726225353285978936466029682788745325588134172850614459269636474769858467022326624710771957129
e = 0x10001

sock = Socket("crypto.2020.chall.actf.co", 20600)
sock.recvuntil("flag:\n")
c = int(sock.recvline().decode())

last_bit = 1000000
def oracle(c):
    global last_bit
    sock.recvuntil("sign: ")
    sock.sendline(str(c))
    print(sock.recvline())
    current_bit = len(sock.recvline())
    oracle_v = 1 if current_bit <= last_bit else 0
    last_bit = current_bit
    return oracle_v

oracle(c)
print(lsb_leak_attack(oracle, n, e, c))