corCTF 2021

Here are writeups for my challenges in corCTF 2021:

fibinary

fibinary was a simple encoding challenge where each character was encoded in “base Fibonacci” - a binary number where each successive place value represented the next Fibonacci number. For example, 110100 would represent 8 + 5 + 0 + 3 + 0 + 0 = 16. To decode, we simply do the reverse of encoding, and add together the Fibonacci numbers indicated by the 1s in the binary representation. Here was my solve script:

fib = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89][::-1]

with open('flag.enc', 'r') as f:
	toks = f.read().strip().split()

for tok in toks:
	n = 0
	for i in range(len(tok)):
		if tok[i] == '1':
			n += fib[i]
	print(chr(n), end='')
print()

supercomputer

supercomputer was a challenge about a seemingly impossible math computation involving taking powers of massive 2048 bit numbers, and then taking powers of those numbers. In the end, it reduced to finding the number of powers of p that divided into a massive final number t.

from Crypto.Util.number import getPrime, long_to_bytes
from pwn import *
import random, binascii

flag = open('flag.txt').read()

def v(p, k):
	ans = 0
	while k % p == 0:
		k /= p
		ans += 1
	return ans

p, q, r = getPrime(2048), getPrime(2048), getPrime(2048)
print(p, q, r)
n = pow(p, q) * r

a1 = random.randint(0, n)
a2 = n - a1
assert a1 % p != 0 and a2 % p != 0

t = pow(a1, n) + pow(a2, n)
print(binascii.hexlify(xor(flag, long_to_bytes(v(p, t)))))

There were many interesting ways to do this problem, but I’ll cover the most direct - the Lifting the Exponent (LTE) lemma. You can read a more detailed explanation on how it works and a proof of it (involving binomial expansions, another popular way to solve this challenge) in this PDF.

In summary, what this lemma says is, for our function \(v_p\) (v with prime p),

Using this on t, we get

Therefore, v(p, t) is \(2q\) and we can plug that into the xor to recover our flag.

bank

This was a challenge relating to a quantum money scheme, where you had to determine the value of 50 qubits that made up a dollar bill to get the flag. If you aren’t familiar with quantum computing or quantum money schemes and/or would like a quick overview, I recommend you check out my writeup here on a similar challenge I solved earlier this year and read the “The Basics” and “The Problem” sections.

Analysis

Looking at this problem, unlike the one linked above, there is no “probe” qubit to use, so how can we determine the value of a qubit? Taking a closer look at the source code, we notice this section:

elif op == '8':
    actual = bill[idx]
    if actual in '01':
        measured = qubits[idx].measure('01')
    else:
        measured = qubits[idx].measure('+-')
    if actual == measured:
        print('Qubit successfully verified.')
    else:
        print('Incorrect qubit!')

What notably doesn’t happen is the code exiting if the qubit is wrong. This means we can verify the qubit as many times as we want! Now this doesn’t solve the problem on its own, since we still don’t know what basis to pick, and picking the wrong one would destroy the information in the qubit. However, now we can use some properties of qubits to our advantage.

Solution

Pick any basic single qubit gate, such as the X gate. Note that the X gate has eigenstates \(\vert+\rangle\) and \(\vert-\rangle\), in other words, if you apply an X gate to a qubit currently in either of those 2 states, nothing happens. We can use this to our advantage since we know the qubits start in the correct, verified state.

For each qubit, we apply an X gate, and then try to verify it. If it still is successfully verified, we now know it is in the \(+/-\) basis. Otherwise, the qubit did change (from \(\vert0\rangle\) to \(1\rangle\) or vice versa), and we know it is in the \(0/1\) basis. Now that we know what basis it is in, we can simply measure it (keeping in mind we first applied an X gate). Do this for all 50 qubits and you’ll get the flag!

Here is a script my teammate qopruzjf wrote to testsolve my challenge: (I was too lazy to write my own)

from pwn import *
# r = remote('crypto.be.ax', 6005)
r = process(["python3", "server.py"])

mybill = list("?"*50)

def test_X(i):
	r.sendline(b'1')
	r.recvuntil(b'9. Back')
	r.sendline(b'8')
	r.recvline()
	re = r.recvline()[:-1]
	print(re)
	if re == b'> Incorrect qubit!': # qubit was not X-eigenvector, so in 0, 1
		r.recvuntil(b'9. Back')
		r.sendline(b'1')
		r.recvuntil(b'9. Back')
		r.sendline(b'6')
		r.recvuntil(b'The qubit measured as ')
		mybill[i] = r.recvline()[:-1].decode()
		r.recvuntil(b'9. Back')
		r.sendline(b'9')
	else: # qubit is in +- basis
		r.recvuntil(b'9. Back')
		r.sendline(b'7')
		r.recvuntil(b'The qubit measured as ')
		mybill[i] = r.recvline()[:-1].decode()
		r.recvuntil(b'9. Back')
		r.sendline(b'9')

def get_qubit(i):
	r.recvuntil(b'3. Quit')
	r.sendline(b'1')
	r.recvuntil(b'index of the qubit you wish to work with: ')
	r.sendline(str(i).encode())
	r.recvuntil(b'9. Back')
	test_X(i)

r.recvuntil(b'Would you like an account? (y/n) ')
r.sendline(b'y')

for i in range(50):
	get_qubit(i)

mybill = ''.join(mybill)
print(mybill)
r.recvuntil(b'3. Quit')
r.sendline(b'2')
r.recvuntil(b'Enter your bill: ')
r.sendline(mybill.encode())
r.interactive()