pwn2win 2020 writeup

2020-06-01 02:31:11 Author: furutsuki.hatenablog.com 阅读量: 164
觉得文章还不错?,点我收藏



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.

f:id:Furutsuki:20200601014755p:plain

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


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

    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):
    # noise
    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.




觉得文章还不错?,点我收藏



如果文章侵犯到您的版权,请联系我:buaq.net[#]pm.me