I played this year's pwn2win CTF as a member of zer0pts. We reached 6th place and got 2842 points. I mostly solved crypto challenges which were fun. and tried to solve some weird misc challenges and ppc challenges.
challenge files and my solution scripts are available from here
[crypto] Androids Encryption
challenge script:
import sys import base64 from Crypto.Cipher import AES from secrets import flag, key1, iv1 def to_blocks(txt): return [txt[i*BLOCK_SIZE:(i+1)*BLOCK_SIZE] for i in range(len(txt)//BLOCK_SIZE)] def xor(b1, b2=None): if isinstance(b1, list) and b2 is None: assert len(set([len(b) for b in b1])) == 1, 'xor() - Invalid input size' assert all([isinstance(b, bytes) for b in b1]), 'xor() - Invalid input type' x = [len(b) for b in b1][0]*b'\x00' for b in b1: x = xor(x, b) return x assert isinstance(b1, bytes) and isinstance(b2, bytes), 'xor() - Invalid input type' return bytes([a ^ b for a, b in zip(b1, b2)]) BUFF = 256 BLOCK_SIZE = 16 iv2 = AES.new(key1, AES.MODE_ECB).decrypt(iv1) key2 = xor(to_blocks(flag)) def encrypt(txt, key, iv): global key2, iv2 assert len(key) == BLOCK_SIZE, f'Invalid key size' assert len(iv) == BLOCK_SIZE, 'Invalid IV size' assert len(txt) % BLOCK_SIZE == 0, 'Invalid plaintext size' bs = len(key) blocks = to_blocks(txt) ctxt = b'' aes = AES.new(key, AES.MODE_ECB) curr = iv for block in blocks: ctxt += aes.encrypt(xor(block, curr)) curr = xor(ctxt[-bs:], block) iv2 = AES.new(key2, AES.MODE_ECB).decrypt(iv2) key2 = xor(to_blocks(ctxt)) return str(base64.b64encode(iv+ctxt), encoding='utf8') def enc_plaintext(): print('Plaintext: ', end='') txt = base64.b64decode(input().rstrip()) print(encrypt(txt, key1, iv1)) def enc_flag(): print(encrypt(flag, key2, iv2)) def menu(): while True: print('MENU') options = [('Encrypt your secret', enc_plaintext), ('Encrypt my secret', enc_flag), ('Exit', sys.exit) ] for i, (op, _) in enumerate(options): print(f'{i+1} - {op}') print('Choice: ', end='') op = input().strip() assert op in ['1', '2', '3'], 'Invalid option' options[ord(op)-ord('1')][1]() def main(): print('Let\'s see if you are good enough in symmetric cryptography!\n') try: menu() except Exception as err: sys.exit(f'ERROR: {err}') if __name__ == '__main__': main()
We can see there are two keys: one is a fixed key for encrypting our input, and another one is modified each in encrypt for encrypting the flag. On focusing the last line in the encrypt, we found that key2 is determined by our last ciphertext key2 = xor(to_blocks(ctxt)). As we can get the result of encryption, we can get the key2 too.
So we can get the pair of iv, ciphertext, and its key. Just write the decryption with taking care of encryption mode.
from ptrlib import * from base64 import b64encode, b64decode from Crypto.Util.Padding import * from Crypto.Cipher import AES BLOCK_SIZE = 16 def to_blocks(txt): return [txt[i*BLOCK_SIZE:(i+1)*BLOCK_SIZE] for i in range(len(txt)//BLOCK_SIZE)] def xor(b1, b2=None): if isinstance(b1, list) and b2 is None: assert len(set([len(b) for b in b1])) == 1, 'xor() - Invalid input size' assert all([isinstance(b, bytes) for b in b1]), 'xor() - Invalid input type' x = [len(b) for b in b1][0]*b'\x00' for b in b1: x = xor(x, b) return x assert isinstance(b1, bytes) and isinstance(b2, bytes), 'xor() - Invalid input type' return bytes([a ^ b for a, b in zip(b1, b2)]) plaintext = pad(b"the quick brown fox jumps over the lazy dog", AES.block_size) sock = Socket("encryption.pwn2.win", 1337) sock.sendlineafter("Choice: ", "1") sock.sendlineafter("Plaintext: ", b64encode(plaintext)) c = b64decode(sock.recvline()) iv, c = c[:16], c[16:] key = xor(to_blocks(c)) sock.sendlineafter("Choice: ", "2") c = b64decode(sock.recvline()) iv, c = c[:16], c[16:] blocks = to_blocks(c) aes = AES.new(key=key, mode=AES.MODE_ECB) curr = iv ctxt = b'' for i in range(len(blocks)): ctxt += xor(aes.decrypt(blocks[i]), curr) curr = xor(blocks[i] , ctxt[-16:]) print(ctxt)
[crypto] Omni Crypto
enc.py
import gmpy2 import random from Crypto.Util.number import bytes_to_long def getPrimes(size): half = random.randint(16, size // 2 - 8) rand = random.randint(8, half - 1) sizes = [rand, half, size - half - rand] while True: p, q = 0, 0 for s in sizes: p <<= s q <<= s chunk = random.getrandbits(s) p += chunk if s == sizes[1]: chunk = random.getrandbits(s) q += chunk p |= 2**(size - 1) | 2**(size - 2) | 1 q |= 2**(size - 1) | 2**(size - 2) | 1 if gmpy2.is_prime(p) and gmpy2.is_prime(q): return p, q e = 65537 p, q = getPrimes(1024) N = p*q phi = (p-1)*(q-1) d = gmpy2.invert(e, phi) m = bytes_to_long(open("flag.txt", "rb").read()) c = pow(m, e, N) print("N =", hex(N)) print("c =", hex(c))
It seems to be an RSA challenge whose p and q shares some MSB and LSB. MSB can be extracted from N by a naive square root. LSB can also be extracted from the modular square root of mod [tex: 2n].
def sqrt_power_of_2_mod(a, n): """find x^2 = a mod 2^n""" assert a % 8 == 1 res = [] for x in [1, 3]: for k in range(3, n): i = ((x*x - a) // pow(2, k)) % 2 x = x + i * pow(2, k-1) res.append(x) res.append(2**n - x) return res
Though we cannot find out sizes of MSB and LSB, just pray for MSB + LSB >= half of p and q bits and apply coppersmith.
from sage.all import * from modsqrt import sqrt_power_of_2_mod import gmpy2 N = 0xf7e6ddd1f49d9f875904d1280c675e0e03f4a02e2bec6ca62a2819d521441b727d313ec1b5f855e3f2a69516a3fea4e953435cbf7ac64062dd97157b6342912b7667b190fad36d54e378fede2a7a6d4cc801f1bc93159e405dd6d496bf6a11f04fdc04b842a84238cc3f677af67fa307b2b064a06d60f5a3d440c4cfffa4189e843602ba6f440a70668e071a9f18badffb11ed5cdfa6b49413cf4fa88b114f018eb0bba118f19dea2c08f4393b153bcbaf03ec86e2bab8f06e3c45acb6cd8d497062f5fdf19f73084a3a793fa20757178a546de902541dde7ff6f81de61a9e692145a793896a8726da7955dab9fc0668d3cfc55cd7a2d1d8b631f88cf5259ba1 c = 0xf177639388156bd71b533d3934016cc76342efae0739cb317eb9235cdb97ae50b1aa097f16686d0e171dccc4ec2c3747f9fbaba4794ee057964734835400194fc2ffa68a5c6250d49abb68a9e540b3d8dc515682f1cd61f46352efc8cc4a1fe1d975c66b1d53f6b5ff25fbac9fa09ef7a3d7e93e2a53f9c1bc1db30eed92a30586388cfef4d68516a8fdebe5ebf9c7b483718437fcf8693acd3118544249b6e62d30afa7def37aecf4da999c1e2b686ca9caca1b84503b8794273381b51d06d0dfb9c19125ce30e67a8cf72321ca8c50a481e4b96bbbc5b8932e8d5a32fa040c3e29ced4c8bf3541e846f832a7f9406d263a592c0a9bce88be6aed043a9867a7 size = 1024 for lsb_len in range(100, 400, 5): print(lsb_len) for msb_len in range(100, 400, 5): msb, _ = gmpy2.iroot(N, 2) shift = int(msb).bit_length() - msb_len msb = int(msb) >> shift ls = sqrt_power_of_2_mod(N, lsb_len) for l in ls: lsb = l _, x = PolynomialRing(Zmod(N), name='x').objgen() f = msb * (2 ** (size - msb_len)) + (x * (2 ** lsb_len)) + lsb f = f.monic() xs = f.small_roots(X=2**(size - msb_len - lsb_len), beta=0.3) for s in xs: print( msb * (2 ** (size - msb_len)) + (s * (2 ** lsb_len)) + lsb)
the flag was found around lsb=300.
[crypto/rev] S1 Protocol
The reversing part writeup will be written by @ptr-yudai. The binary works like the following script.
from Crypto.Util.number import * pattern = 0x1000000000000000000000000000000000000000001000000000000000000000000000000000000000001000000000000000000000000000000000000000001000000000000000000000000000000000000000001000000000000000000000000000000000000000001 while True: x = getRandomNBitInteger(21 * 8) p = (0b11 << 1022) + (pattern * x << 16) + getRandomNBitInteger(16) | 1 if isPrime(p): break q = getStrongPrime(1024) n = p * q r = getRandomRange(2, n) flag = long_to_bytes(open("flag.txt", "rb").read()) print(n+1) print(pow(r, n, n**3)) print(pow(1 + n, flag, (n+1)*(n**3)))
Obviously, the flag is encrypted with modified paillier crypto, and the factor of modulus has some pattern. There was an analogy challenge in the google CTF 2019. Luckily, its solver can be applied as-is. So I don't know how it works.
from sage.all import * n = 24873956958658402268767683103493059896705299540675048547193795288445376056675974746836994045550208950377561438045299653683756857105762284046700057257044778523863095409390382049154376271272054943837723148622450408029389494774175445756568213417919195725130474727174628849316519649758004047082836095165350139241058167015090602339726250580015660699904551403507821949156006918652616841989957152257987416669296535546243917804424508781976452089018525704521989449529550926409771357879685458344231307480394377651973499196053459100169309910822372188138310059463352985798139208816853247052829533726918240148879918230116779685881 pattern_size = 21*8 prime_size = 1024 x = 2**pattern_size d0 = 2**pattern_size - 1 w = 2**prime_size u, v = divmod(n, w) M = matrix([[x, 0, u * d0 % w], [0, x, v * d0 % w], [0, 0, w]]) for vec in M.LLL(): bx, ax = vec[0], -vec[1] p = gcd(ax * w + bx, n) if 1 < p < n: q = n // p break print(p) print(q)
[crypto] Lost qKeys
import qiskit import os from Crypto.Util.number import bytes_to_long flag = b"hogepiyo" class IQuantumComputer: def __init__(self, nbits): self.nbits = nbits self.nbytes = (self.nbits - 1)//8 + 1 def string_to_bits(self, m): if isinstance(m, str): m = m.encode() return self.decode(self.encode(bytes_to_long(m))) def encode(self, m): return '{:0{}x}'.format(m, self.nbytes) def decode(self, m): return '{:0{}b}'.format(int(m, 16), self.nbits)[-self.nbits:] def send_qubits(self, msg, dest): qbit_config = self.decode(msg) q = qiskit.QuantumRegister(9*len(qbit_config)) circ = qiskit.QuantumCircuit(q) for j, c in enumerate(qbit_config): if c=='1': circ.x(q[9*j]) circ.cx(q[9*j],q[9*j+3]) circ.cx(q[9*j],q[9*j+6]) circ.h(q[9*j]) circ.h(q[9*j+3]) circ.h(q[9*j+6]) circ.cx(q[9*j],q[9*j+1]) circ.cx(q[9*j],q[9*j+2]) circ.cx(q[9*j+3],q[9*j+4]) circ.cx(q[9*j+3],q[9*j+5]) circ.cx(q[9*j+6],q[9*j+7]) circ.cx(q[9*j+6],q[9*j+8]) return quantum_channel(circ, dest) def read_qubits(self, circ): raise NotImplemented('read_qubits') @staticmethod def send_message(message, dest): classical_channel(message, dest) @staticmethod def read_message(message): raise NotImplemented('read_message') class LocalQuantumComputer(IQuantumComputer): def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) @staticmethod def read_message(message): print(message) class RemoteQuantumComputer(IQuantumComputer): def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) self.key = self.decode(self.encode(bytes_to_long(os.urandom(self.nbytes)))) self.encoded_flag = self.string_to_bits(flag) def encrypt_flag(self, circ): self.qbuffer = qiskit.QuantumRegister(self.nbits) circ.add_register(self.qbuffer) for i, c in enumerate(self.encoded_flag): if c=='1': circ.x(self.qbuffer[i]) for i in range(len(self.key)): if self.key[i]=='1': circ.h(self.qbuffer[i]) return circ def decrypt_flag(self, circ): for i in range(self.nbits): circ.ch(self.received_qubits[9*i], self.qbuffer[i]) output = qiskit.ClassicalRegister(self.nbits) circ.add_register(output) circ.measure(self.qbuffer, output) bk = qiskit.Aer.get_backend('qasm_simulator') job = qiskit.execute(circ, bk, shots=1) res = job.result() if not res.success: raise MemoryError('You should use a real quantum computer...') res = res.get_counts(circ) self.res = [self.encode(int(k,2)) for k in res.keys()] def read_qubits(self, circ): self.received_qubits = circ.qubits for i in range(0, len(self.received_qubits), 9): circ.cx(self.received_qubits[i], self.received_qubits[i+1]) circ.cx(self.received_qubits[i], self.received_qubits[i+2]) circ.ccx(self.received_qubits[i+1], self.received_qubits[i+2], self.received_qubits[i]) circ.h(self.received_qubits[i]) circ.cx(self.received_qubits[i+3], self.received_qubits[i+4]) circ.cx(self.received_qubits[i+3], self.received_qubits[i+5]) circ.ccx(self.received_qubits[i+4], self.received_qubits[i+5], self.received_qubits[i+3]) circ.h(self.received_qubits[i+3]) circ.cx(self.received_qubits[i+6], self.received_qubits[i+7]) circ.cx(self.received_qubits[i+6], self.received_qubits[i+8]) circ.ccx(self.received_qubits[i+7], self.received_qubits[i+8], self.received_qubits[i+6]) circ.h(self.received_qubits[i+6]) circ.cx(self.received_qubits[i], self.received_qubits[i+3]) circ.cx(self.received_qubits[i], self.received_qubits[i+6]) circ.ccx(self.received_qubits[i+3], self.received_qubits[i+6], self.received_qubits[i]) circ = self.encrypt_flag(circ) self.decrypt_flag(circ) def classical_channel(message, dest): dest.read_message(message) def quantum_channel(qcirc, dest): dest.read_qubits(qcirc) def connect(local, remote): remote.send_message('passwd:', local) pwd = input() local.send_qubits(pwd, remote) remote.send_message(', '.join(remote.res), local) def main(nbits): local = LocalQuantumComputer(nbits) remote = RemoteQuantumComputer(nbits) connect(local, remote) if __name__=='__main__': nbits = 8*len(flag) main(nbits=nbits)
The server encrypts the flag with quantum computing. But practically, it is no needed to know about quantum computing. After some local experiments and observations, I noticed that the flag is masked by key and our input. So we should input 0 as the password to reduce the bit size of the mask.
Connect to the server many times and get statistics of the masked flag, then the flag can be recovered.