rsa_last_bit.sage

# This is sage script!

from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, bytes_to_long
import random

from rand_crack import RandCrack # https://github.com/tna0y/Python-random-module-cracker/blob/master/randcrack.py

TESTING = False
BLOCK_SIZE = 16

### Protocol parsing functions

if not TESTING:
    
    from pwn import *
    context(log_level='debug')
    #r = process('python server.py', shell=True)

    r = remote('crypto.chal.ctf.westerns.tokyo', 5643)
    
    def skip_menu():
        r.readuntil(' get encrypted key\n')

    # Send multiple messages at once to make exploit work faster
    
    def send_prepared(msgs):
        r.send("".join(msgs))

    def encrypt_rsa_prepare(m):
        return "1\n{}\n".format(long_to_bytes(int(m)))

    def encrypt_rsa_recv():
        skip_menu()
        r.readuntil('RSA: ')
        s = r.readline().strip()
        return bytes_to_long(s.decode('hex'))

    def get_decrypted_rsa_last_byte_prepare(c):
        return "2\n{}\n".format(long_to_bytes(c).encode('hex'))
        
    def get_decrypted_rsa_last_byte_recv():
        skip_menu()
        r.readuntil('RSA: ')
        s = r.readline().strip()
        return bytes_to_long(s.decode('hex')) % 256

    def get_encrypted_aes_key():
        skip_menu()
        r.send("4\n")
        r.readuntil('here is encrypted key :)\n')
        c = Integer(bytes_to_long(r.readline().strip().decode('hex')))
        return c

    def pad(s):
        n = 16 - len(s)%16
        return s + chr(n)*n

    def get_encrypted_flag():
        skip_menu()
        r.send("3\n")
        r.readuntil('another bulldozer is coming!\n')
        return r.readline().strip().decode('hex')

    def get_randbits_prepare():
        return "1\n\n"

    def get_randbits_recv():
        skip_menu()
        r.readuntil('AES: ')
        s = r.readline().strip()
        return s.decode('hex')
        
else:

    privkey = RSA.generate(1024)
    pubkey = privkey.publickey()
    aeskey = os.urandom(16)
    flag = 'FLAG' * 100

    def encrypt_rsa_prepare(m):
        return m

    def encrypt_rsa_recv():
        global prepared_msgs
        m = prepared_msgs[0]
        prepared_msgs = prepared_msgs[1:]
        return Integer(bytes_to_long(pubkey.encrypt(long_to_bytes(int(m)), 0)[0]))

    def get_encrypted_aes_key():
        return Integer(bytes_to_long(pubkey.encrypt(aeskey, 0)[0]))

    def get_decrypted_rsa_last_byte_prepare(c):
        return c

    def send_prepared(msgs):
        global prepared_msgs
        prepared_msgs = msgs

    def get_decrypted_rsa_last_byte_recv():
        global prepared_msgs
        c = prepared_msgs[0]
        prepared_msgs = prepared_msgs[1:]
        return Integer(bytes_to_long(privkey.decrypt(long_to_bytes(int(c)))[-1]))

    def pad(s):
        n = 16 - len(s)%16
        return s + chr(n)*n

    def get_encrypted_flag():
        iv = long_to_bytes(random.getrandbits(BLOCK_SIZE*8), 16)
        print("real iv was {}".format(iv.encode('hex')))
        aes = AES.new(aeskey, AES.MODE_CBC, iv)
        return '#' * 16 + aes.encrypt(pad(flag))

    def get_randbits_prepare():
        return None

    def get_randbits_recv():
        return long_to_bytes(random.getrandbits(BLOCK_SIZE*8), 16)


### Exploit


def recover_n():
    nums = [37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]
    preps = map(encrypt_rsa_prepare, nums)
    send_prepared(preps)
    t = None
    for pp in nums:
        c = encrypt_rsa_recv()
        nd = pp ** e - c
        if t is None:
            t = nd
        else:
            t = gcd(t, nd)

    return t

def recover_m(c):
    nums = [(Zmod(n)(c) / Zmod(n)(2)**(e * i)) for i in xrange(128)]
    preps = map(get_decrypted_rsa_last_byte_prepare, nums)
    send_prepared(preps)
    
    def get_last_bit(nn):
        return get_decrypted_rsa_last_byte_recv() % 2

    bits = map(get_last_bit, nums)
    found = 0
    nk = 0
    for i in xrange(128):
        for fb in range(2):
            assert (found + 2 ** i * fb + nk * n) % (2 ** i) == 0
            if ((found + 2 ** i * fb + nk * n) // (2 ** i)) % 2 == bits[i]:
                found = found + 2 ** i * fb
                if bits[i] == 1:
                    nk = nk + 2 ** i
                break

    return found

def recover_rand_state():
    r = RandCrack()
    send_prepared([get_randbits_prepare() for _ in xrange(200)])
    for _ in xrange(200):
        b = get_randbits_recv()[:16]
        b = bytes_to_long(b)
        for _ in xrange(4):
            r.submit(b % (2 ** 32))
            b //= 2 ** 32

    return r

if __name__ == "__main__":
    e = 65537
    n = recover_n()
    print "Recovered n={}".format(n)

    if TESTING:
        assert n == pubkey.n

    encrypted_aes_key = get_encrypted_aes_key()
    aes_key = recover_m(encrypted_aes_key)
    print "Recovered aes key={}".format(aes_key)

    if TESTING:
        assert aes_key == bytes_to_long(aeskey)

    rp = recover_rand_state()
    real_iv = long_to_bytes(rp.predict_getrandbits(BLOCK_SIZE*8), 16)
    print("predicted iv was {}".format(real_iv.encode('hex')))
    encrypted_flag = get_encrypted_flag()[16:]

    flag = AES.new(long_to_bytes(int(aes_key), 16), AES.MODE_CBC, real_iv).decrypt(encrypted_flag)
    print "Recovered flag={!r}".format(flag)


    print "n={}".format(n)
    print "encrypted aes key={}".format(encrypted_aes_key)
    print "aes key={}".format(aes_key)
    print "encrypted flag={!r}".format(encrypted_flag)
    print "flag={!r}".format(flag)