I heard bulldozer is on this channel, be careful!
nc crypto.chal.ctf.westerns.tokyo 5643

  • Download the chal: here.

How to solve

To decrypt the flag, we need two things: the AES key and the IV when the flag is generated.

IV

IV is generated by random.getrandbits(). Python random uses Mersenne Twister, and it is able to recover the state of the Python random generator with 624 32-bit integers. See this link for detail.

You can check that MT::untemper works normally with this code.

from pwn import *

r = remote('crypto.chal.ctf.westerns.tokyo', 5643)
menu_str = '4: get encrypted key'
r.recvuntil(menu_str)

rand_values = []
def encrypt(t):
    r.sendline('1')
    r.sendline(t)
    l = r.recvuntil(menu_str)

    # Store random values to restore MT
    iv = int(l.split('AES: ')[1][:32], 16)
    for i in range(4):
        rand_values.append( (iv >> (32 * i)) & ((1 << 32) - 1) )

    rsa = int(l.split('RSA:')[1].split('AES:')[0], 16)
    return rsa

for i in xrange(256):
    encrypt('\x00')

# MT Untemper: http://mslc.ctf.su/wp-content/uploads/files/svalka/mt.py
from mt import untemper
mt_state = tuple(map(untemper, rand_values[:624]) + [0])
random.setstate((3, mt_state, None))

for i in xrange(1024):
    rnd = random.getrandbits(128)
    assert rnd == rand_values[i], "Failed"

AES Key

  • This part is unintended.

We can get $aeskey^e \pmod N$ by the option 4, and we can decrypt $x^e \pmod N$ with the option 2, but it only gives the length and the last one byte of the plain message.

The problem is that they give the length. AES key is 16byte, and the RSA is 1024bit. It is possible to get $(aeskey \times t)^e \pmod N$ for any $t$. So we can recover the AES key one bit by one bit, from the MSB to the LSB, by multiplying a value $t$ that makes a difference in the length of the decrypted message.

from pwn import *
# Using encrypt() defined above

# Calculate N of RSA
N = None
for i in range(2, 8): # 2 ~ 7, total 
    enc = encrypt( chr(i) )
    if N is None:
        N = pow(i, 0x10001) - enc
    else:
        N = GCD(N, pow(i, 0x10001) - enc)

# Get encrypted AES key
r.sendline('4')
l = r.recvuntil(menu_str)
aeskey_enc = l.split('here is encrypted key :)\n')[1][:256]
aeskey_enc = int(aeskey_enc, 16)

# Check whether the length is 128 bytes, or not.
def decrypt(t):
    r.sendline('2')
    r.sendline(t)
    l = r.recvuntil(menu_str)
    lsb = l.split('RSA: ')[1].split('\n')[0]
    return lsb

recovered = 0
two_1016 = 2 ** 1016
for i in xrange(127, -1, -1):
    threshold = recovered + 2 ** i
    tmp = (two_1016 + threshold - 1) // threshold
    assert tmp * (threshold - 1) < two_1016, "Failed"

    val = aeskey_enc * pow(tmp, 0x10001, N) % N
    res = decrypt( long_to_bytes(val).encode('hex') )
    if len(res) // 2 == 128:
        recovered += 2 ** i

aeskey = recovered
print('aeskey', aeskey)

Full exploit

from pwn import *
from Crypto.Util.number import long_to_bytes, GCD
from Crypto.Cipher import AES
import random

r = remote('crypto.chal.ctf.westerns.tokyo', 5643)
menu_str = '4: get encrypted key'
r.recvuntil(menu_str)

# === Stage 1: Recover Python MT ===

rand_values = []
def encrypt(t):
    r.sendline('1')
    r.sendline(t)
    l = r.recvuntil(menu_str)

    # Store random values to restore MT
    iv = int(l.split('AES: ')[1][:32], 16)
    for i in range(4):
        rand_values.append( (iv >> (32 * i)) & ((1 << 32) - 1) )

    rsa = int(l.split('RSA:')[1].split('AES:')[0], 16)
    return rsa

# Calculate N of RSA
N = None
for i in range(2, 8): # 2 ~ 7, total 
    enc = encrypt( chr(i) )
    if N is None:
        N = pow(i, 0x10001) - enc
    else:
        N = GCD(N, pow(i, 0x10001) - enc)

for i in xrange(156 - 6):
    encrypt('\x00')

# From http://mslc.ctf.su/wp/confidence-ctf-2015-rsa2-crypto-500/
# MT Untemper: http://mslc.ctf.su/wp-content/uploads/files/svalka/mt.py
from mt import untemper
mt_state = tuple(map(untemper, rand_values[:624]) + [0])
random.setstate((3, mt_state, None))

for i in xrange(156):
    rnd = random.getrandbits(128)

iv = random.getrandbits(128)
print('next iv', iv)

r.sendline('3')
l = r.recvuntil(menu_str)
flag = l.split('coming!\n')[1].split('\n')[0][32:]
print('flag', flag)

# === Stage 2: Recover AES key ===

def decrypt(t):
    r.sendline('2')
    r.sendline(t)
    l = r.recvuntil(menu_str)
    lsb = l.split('RSA: ')[1].split('\n')[0]
    return lsb

r.sendline('4')
l = r.recvuntil(menu_str)
aeskey_enc = l.split('here is encrypted key :)\n')[1][:256]
aeskey_enc = int(aeskey_enc, 16)

# Check whether the length is 128 bytes, or not.
recovered = 0
two_1016 = 2 ** 1016
for i in xrange(127, -1, -1):
    threshold = recovered + 2 ** i
    tmp = (two_1016 + threshold - 1) // threshold
    assert tmp * (threshold - 1) < two_1016, "Failed"

    val = aeskey_enc * pow(tmp, 0x10001, N) % N
    res = decrypt( long_to_bytes(val).encode('hex') )
    if len(res) // 2 == 128:
        recovered += 2 ** i

aeskey = recovered
print('aeskey', aeskey)

r.close()

# === Stage 3: Decrypt ===

flag = flag.decode('hex')
aeskey = long_to_bytes(aeskey, 16)
iv = long_to_bytes(iv, 16)

def unpad(s):
    n = ord(s[-1])
    return s[:-n]

aes = AES.new(aeskey, AES.MODE_CBC, iv)
print(unpad(aes.decrypt(flag)))

The flag is TWCTF{L#B_de#r#pti#n_ora#le_c9630b129769330c9498858830f306d9}. I need to study the LSB decryption oracle. 🙁