# pwn2win 2020 writeup

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:

```#!/usr/bin/python3 -u
# *-* coding: latin1 -*-
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))

while True:
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:
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

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
# from secrets import flag
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)

@staticmethod
def send_message(message, dest):
classical_channel(message, dest)

@staticmethod

class LocalQuantumComputer(IQuantumComputer):
def __init__(self, *args, **kwargs):
super().__init__(*args, **kwargs)

@staticmethod
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)

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):

output = qiskit.ClassicalRegister(self.nbits)
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()]

for i in range(0, len(self.received_qubits), 9):

circ = self.encrypt_flag(circ)
self.decrypt_flag(circ)

def classical_channel(message, dest):

def quantum_channel(qcirc, dest):
# noise

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.