# ångstromCTF 2021 Writeups

## Relatively Simple Algorithm

n = 113138904645172037883970365829067951997230612719077573521906183509830180342554841790268134999423971247602095979484887092205889453631416247856139838680189062511282674134361726455828113825651055263796576482555849771303361415911103661873954509376979834006775895197929252775133737380642752081153063469135950168223
p = 11556895667671057477200219387242513875610589005594481832449286005570409920461121505578566298354611080750154513073654150580136639937876904687126793459819369
q = 9789731420840260962289569924638041579833494812169162102854947552459243338614590024836083625245719375467053459789947717068410632082598060778090631475194567
e = 65537
c = 108644851584756918977851425216398363307810002101894230112870917234519516101802838576315116490794790271121303531868519534061050530562981420826020638383979983010271660175506402389504477695184339442431370630019572693659580322499801215041535132565595864123113626239232420183378765229045037108065155299178074809432

The goal of this challenge is to provide a basic introduction to RSA and ASCII encoding. Using the Wikipedia link provided in the hint, we may calculate $\lambda=\text{lcm}(p-1,q-1)$ and $d$ as the modular inverse of $e\mod\lambda$. Then we may find $m=c^d\mod n$. Code below (py3.8 needed):

from math import gcd
n = 113138904645172037883970365829067951997230612719077573521906183509830180342554841790268134999423971247602095979484887092205889453631416247856139838680189062511282674134361726455828113825651055263796576482555849771303361415911103661873954509376979834006775895197929252775133737380642752081153063469135950168223
p = 11556895667671057477200219387242513875610589005594481832449286005570409920461121505578566298354611080750154513073654150580136639937876904687126793459819369
q = 9789731420840260962289569924638041579833494812169162102854947552459243338614590024836083625245719375467053459789947717068410632082598060778090631475194567
e = 65537
c = 108644851584756918977851425216398363307810002101894230112870917234519516101802838576315116490794790271121303531868519534061050530562981420826020638383979983010271660175506402389504477695184339442431370630019572693659580322499801215041535132565595864123113626239232420183378765229045037108065155299178074809432
l = (p-1)*(q-1) // gcd(p-1,q-1)
d = pow(e, -1, l)
m = pow(c, d, n)
print(m)

This program outputs `77829732531886017666421465369706368622254927240332446949265849761777437379574153694975519245766808162296991738636674224619780544798026515410227980157`. To convert this into the flag, we first convert it to hexadecimal, and then convert the hex string into ASCII. Below are two ways to do this in Python:

print(bytes.fromhex(hex(m)[2:]))
length = (m.bit_length()+7) // 8
print(m.to_bytes(length,'big'))

Both of these give us the flag: `actf{old_but_still_good_well_at_least_until_quantum_computing}`.

## Follow the Currents

import os
import zlib
def keystream():
	key = os.urandom(2)
	index = 0
	while 1:
		index+=1
		if index >= len(key):
			key += zlib.crc32(key).to_bytes(4,'big')
		yield key[index]
ciphertext = []
with open("plain","rb") as f:
	plain = f.read()
	assert b"actf{" in plain
	k = keystream()
	for i in plain:
		ciphertext.append(i ^ next(k))
with open("enc","wb") as g:
	g.write(bytes(ciphertext))

This is a simple stream cipher created by XORing the plain text with a keystream. The weakness here is that the initial key is generated with `key = os.urandom(2)`, which only provides 2 bytes = 16 bits of security. As such we only need to bruteforce $2^{16}=65536$ keystreams, and on each iteration we check if the resulting plaintext contains `actf{`. Code below (notice how it looks very similar to the source):

import os
import zlib
def keystream(key):
	index = 0
	while 1:
		index+=1
		if index >= len(key):
			key += zlib.crc32(key).to_bytes(4,'big')
		yield key[index]

with open("enc","rb") as f:
	enc = f.read()
	for key in range(65536):
		plain = []
		k = keystream(key.to_bytes(2,'big'))
		for i in enc:
			plain.append(i ^ next(k))
		if b"actf{" in bytes(plain): print(bytes(plain))

This outputs several lines, all of which contain the flag (crc32 is not very collision resistant). The one which is entirely ASCII is `there are like 30 minutes left before the ctf starts so i have no idea what to put here other than the flag which is actf{low_entropy_keystream}`. And thus our flag is `actf{low_entropy_keystream}`.

## Oracle of Blair

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os

key = os.urandom(32)
flag = open("flag","rb").read()

while 1:
	try:
		i = bytes.fromhex(input("give input: "))
		if not i:
			break
	except:
		break
	iv = os.urandom(16)
	inp = i.replace(b"{}", flag)
	if len(inp) % 16:
		inp = pad(inp, 16)
	print(
		AES.new(key, AES.MODE_CBC, iv=iv).decrypt(inp).hex()
	)

This source code implements a simple AES-CBC decryption oracle, where any instances of `{}` are replaced with the flag. Let's look at the CBC decryption diagram from Wikipedia.
Note that although the IV is randomized, it only affects the first plaintext block, which means the rest of the oracle will give the same output for any input, which really sounds a lot like ECB.

Remember that the weakness in ECB is that the same input will always give the same output anywhere in the message, which means collisions in the output mean collisions in the input. Here, the weakness is similar -- an output block is completely determined by two adjacent ciphertext blocks. Essentially, it's ECB with 32-byte blocks of input and 16-byte blocks of output (we'll ignore every other block starting from the second one).

From here, we can conduct a standard attack on an ECB oracle, where we bruteforce the flag one character at a time. Code below:

from pwn import *
r = remote('crypto.2021.chall.actf.co', 21112)
def query(inp):
	r.readuntil(': ')
	r.sendline(inp.hex())
	return bytes.fromhex(r.readline(False).decode())

# find flag length
num_blocks = len(query(b'{}'))//16
flag_length = (num_blocks - 1) * 16
for i in range(1,16):
	if len(query(b'{}' + b'A'*i))//16 > num_blocks:
		flag_length += (i-1) + 2
		break
flag_blocks = (flag_length+15)//16
known_flag = b''
for i in range(flag_length):
	if known_flag[-1:] != b'{': # testing actf{} screws it up lol
		charset = [*range(32,127)]
	else:
		charset = [i for i in range(32,127) if chr(i) != '}']
	padding = b'A' * (32-len(known_flag)-1)
	q = b''.join(padding+known_flag[-31:]+bytes([c]) for c in charset)
	flag_padding = b'A' * (flag_blocks*16 - len(known_flag) - 1)
	q += flag_padding
	q += b'{}'
	out = query(q)
	test_offset = len(charset)*2 + (len(flag_padding)+len(known_flag)+15)//16 - 1
	enc_test = out[test_offset*16:][:16]
	known_flag += bytes([charset[out.find(enc_test)//32]])
	print(known_flag)

This outputs the flag: `actf{cbc_more_like_ecb_c}`

## Cache Money
You can make encryption stop early by sending an invalid number such as a string or a list. This way, the timing differences caused by cache hits/misses become much more noticeable. We can leak some of the round keys by doing a byte-by-byte bruteforce against the server, and then a bit of bruteforcing to resolve any ambiguities. This is enough to recover the first 192 bits of the key. To recover the last 64 bits, we have to use the decrypt function.

At least two teams solved this with a cool method involving floats, which didn't use timing at all. By inputting a float and checking for errors (`int ^ float` causes an error), you can tell with 100% certainly whether something is in the cache.

i'm too lazy to add details so have two unreadable scripts kthxbye
This script performs the timing attack and whatever.

from requests import Session
from random import shuffle
import json, itertools
enc = "https://cachemoney.2021.chall.actf.co/api/enc"
dec = "https://cachemoney.2021.chall.actf.co/api/dec"
r = Session()
def getTime(inp):
    res = r.post(enc,data=json.dumps({
        'a':inp,
        'secret':'secret192' # change this to secret128 or secret256, but if using secret256 dont forget to change to dec
    }),headers={
        'content-type':'application/json'
    }).json()
    return res['time']
cur = []
for block in range(3,-1,-1):
    cached = []
    subcur = [3,3,3,3]
    for index in range(4):
        arr = cur + subcur + list(range(17-4*block,17))
        arr[len(cur)+index+1] = 'a'
        times = [[] for i in range(256)]
        for j in range(4):
            order = list(range(256))
            shuffle(order)
            for i in order:
                arr[len(cur)+index] = i
                times[i].append(getTime(arr))
        mintimes = sorted((min(times[i]),i) for i in range(256))
        print(mintimes[:6])
        n = input(f'how many outliers? ') # ok look i'm too lazy to detect outliers with math
        n = int(n)
        cached.append(list(map(lambda x:x[1],mintimes[:n])))
        subcur[index] = mintimes[0][1]
    combos = list(itertools.product(*cached))
    times = [[] for i in range(len(combos))]
    for i in range(5):
        order = list(range(len(combos)))
        shuffle(order)
        for index in order:
            arr = cur + list(combos[index]) + list(range(17-4*block,17))
            arr[len(cur)+4] = "a"
            times[index].append(getTime(arr))
    mintimes = sorted((min(times[i]),combos[i]) for i in range(len(combos)))
    print(mintimes[:4])
    cur += list(mintimes[0][1])

This script recovers the key (or at least the first 24 bytes, last 8 bytes is left as exercise to the reader)

from Crypto.Cipher import AES
from tqdm import tqdm
from string import *
import itertools

sbox = bytes.fromhex("637c777bf26b6fc53001672bfed7ab76ca82c97dfa5947f0add4a2af9ca472c0b7fd9326363ff7cc34a5e5f171d8311504c723c31896059a071280e2eb27b27509832c1a1b6e5aa0523bd6b329e32f8453d100ed20fcb15b6acbbe394a4c58cfd0efaafb434d338545f9027f503c9fa851a3408f929d38f5bcb6da2110fff3d2cd0c13ec5f974417c4a77e3d645d197360814fdc222a908846eeb814de5e0bdbe0323a0a4906245cc2d3ac629195e479e7c8376d8dd54ea96c56f4ea657aae08ba78252e1ca6b4c6e8dd741f4bbd8b8a703eb5664803f60e613557b986c11d9ee1f8981169d98e949b1e87e9ce5528df8ca1890dbfe6426841992d0fb054bb16")
sboxinv = bytes.fromhex("52096ad53036a538bf40a39e81f3d7fb7ce339829b2fff87348e4344c4dee9cb547b9432a6c2233dee4c950b42fac34e082ea16628d924b2765ba2496d8bd12572f8f66486689816d4a45ccc5d65b6926c704850fdedb9da5e154657a78d9d8490d8ab008cbcd30af7e45805b8b34506d02c1e8fca3f0f02c1afbd0301138a6b3a9111414f67dcea97f2cfcef0b4e67396ac7422e7ad3585e2f937e81c75df6e47f11a711d29c5896fb7620eaa18be1bfc563e4bc6d279209adbc0fe78cd5af41fdda8338807c731b11210592780ec5f60517fa919b54a0d2de57a9f93c99cefa0e03b4dae2af5b0c8ebbb3c83539961172b047eba77d626e169146355210c7d")

key = [0]*32

k3 = (40, 67, 82, 56)
k3_tmp = [i^j for i,j in zip(k3,[1,0,0,0])]
k3_tmp = [sboxinv[i] for i in k3_tmp]
k3_tmp = k3_tmp[-1:] + k3_tmp[:-1]
key[12:16] = bytes(k3_tmp)
print(bytes(key))

j4 = (78, 4, 33, 119)
key[0:4] = bytes(i^j for i,j in zip(j4,k3))
print(bytes(key))

j5 = (23, 61, 121, 21)
key[4:8] = bytes(i^j for i,j in zip(j5,j4))
print(bytes(key))

a = bytes.fromhex("8e8b9e099afad3aac6312e9b37079853985e08883b14d7e2f25ce1b7627b5bc0")
alpha = (ascii_lowercase+ascii_uppercase+digits).encode()
for i in itertools.product(alpha,repeat=4):
	key[8:12] = i
	cipher = AES.new(bytes(key[:16]), AES.MODE_ECB)
	if cipher.encrypt(a).hex() == "a2dd699fa8297463c6f94c59a9d85a36fcc50f2e9382cb5ea335356923cb5503":
		print(bytes(key))
		break


k5 = (25, 209, 56, 214)
k5_tmp = [i^j for i,j in zip(k5,[1,0,0,0])]
k5_tmp = [sboxinv[i] for i in k5_tmp]
k5_tmp = k5_tmp[-1:] + k5_tmp[:-1]
key[20:24] = bytes(k5_tmp)
print(bytes(key))

# unused
j6 = (127, 150, 75, 153)
j7 = (38, 175, 19, 251)

a = bytes.fromhex("8e8b9e099afad3aac6312e9b37079853985e08883b14d7e2f25ce1b7627b5bc0")
alpha = (ascii_lowercase+ascii_uppercase+digits).encode()
for i in itertools.product(alpha,repeat=4):
	key[16:20] = i
	cipher = AES.new(bytes(key[:24]), AES.MODE_ECB)
	if cipher.encrypt(a).hex() == "dfeac0bbfc07cd7302333409e978aef0ea5e7aa0c868b7232f8ef9e593afdb00":
		print(bytes(key))
		break

## Watered Down Watermark as a Service

The big idea is to construct a BSON object that also doubles as a BMP file. Because loading images does not count as frame navigation, the request will not be blocked. Also, BMP is ideal because it does not do any compression, so we do not have to worry about fitting a specific compression format.

btw everyone who used the devtools thing is lame

### Construction of a BSON/BMP Polyglot
BMP reference: http://www.ece.ualberta.ca/~elliott/ee552/studentAppNotes/2003_w/misc/bmp_file_format/bmp_file_format.htm
BSON reference: http://bsonspec.org/spec.html

Note that the first four bytes of a BSON file represent the size. Also note that the first two bytes of a BMP file have to be `b'BM'`, which means optimistically the minimum file size would have to be `b'BM\x00\x00'` as an integer, or `19778`. Not too bad. The next four bytes after the header are supposed to be the file size, but Chrome doesn't check this so we can set it to whatever we want.

On the BSON side of things, we must now create an element. Since the rest of the BMP header is probably going to be nasty unprintable data, the `binary` type (`0x05`) is probably going to be best here. We'll use a simple key here such as `AAAA`, and we'll need a 4-byte length which we'll determine later. We also need a subtype, but BSON doesn't care if it's invalid so we again can put whatever we want.

After the BMP file size, we have four bytes for a reserved value (which means we can put anything), and then four bytes for `DataOffset`. The header will end up being `0x3e` bytes so that is what we will put here. This also coincides with the size of the current BSON element, so we'll need to make sure that works out. The next value is the size of the `InfoHeader`, which comes out to `0x28` bytes. At this point, we can just fill in the rest of the header, and then some garbage until we reach the end of the BSON data.

After the end of the BSON binary data, we construct a string that will hold a bunch of dummy values that take us to the end of the file. Construction below:

At the end of the file we leave some space for the flag key that the server will add. We don't know the length of the flag, but this can be easily bruteforced. Since the flag is in the BMP data and we are using 1 bit per pixel, it will show up encoded as binary, with black and white pixels representing 0 and 1.

After bruteforcing flag length, we eventually find that a webpage with this content works:

<style>img{float:right}</style>
<img src="http://wdwaas.2021.chall.actf.co/add-flag?object=eJztzLEJgjEUhdFrwAksbC3%2F2gGE9LqAyzpa8gIRLB3gnMdX3nd9Jede8khyVLeqX5JT3dd913bLGCNr%2BKO9Sz7PegAAAAAAAAAAAAAAAAAAAAAAAADwl2QCla6JTg%3D%3D&compressed=1">

Result:

At the very top you can see some data, here it is zoomed in:

We can clip this out with MS Paint or a similar tool and run a simple Python script to extract the flag from these pixels.

from PIL import Image
a = Image.open("lo.png")
p = a.load()
for row in range(11,-1,-1):
	for i in range(0,32,8):
		print(chr(int(''.join([str(int(p[i+j,row]==(255,255,255))) for j in range(8)]),2)),end='')
print()

This outputs the flag: `actf{a_cross_origin_catastrophe}`.