Rev / Snail Farmer John

Author : Marvin

Challenge Description

Farmer John has moved on from cows to snails.

Please ignore any potential integer overflow (i.e. pretend that the program can handle arbitrarily large numbers).

Challenge Files
input.txt and slow.cpp

#include <cstdint>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

vector<int> comb(vector<int> in) {
    vector<int> out;
    vector<uint64_t> prefix ; 
    for(int i = 0 ; i < in.size(); i++){
    	
    }
    for (int i = 0; i < in.size(); i++) {
        for (int j = i + 1; j < in.size(); j++) {
            out.push_back(in[i] * in[j]);
        }
        out.push_back((in[i] * (in[i] - 1) / 2));
    }
    return out;
}
int main() {
    ifstream fin("input.txt");
    ofstream fout("slow.out");
    int n, k;
    fin >> n >> k;
    vector<int> score;
    for (int i = 0; i < k; i++) {
        int temp;
        fin >> temp;
        score.push_back(temp);
    }
    for (int i = k; i < n; i++) {
        score.push_back(1);
    }
    uint64_t output = 0;
    for (int j = n; j >= k; j -= 3) {
        vector<int> part = vector<int>(score.begin(), score.begin() + j);
        vector<int> res = comb(comb(part));
        for (int i = 0; i < res.size(); i++) {
            output += res[i];
        }
    }
    fout << "bcactf{" << output << "}" << endl;
}

The above script does some calculations to print out a number and our goal was to speed up the above script to find the flag

Solution

In input.txt we are given two numbers n and h whose values are 500000 and 200000 respectively, and an array of length 200000.

The first step was to figure out the working of comb function, if you look carefully the script is actually adding the sum of return value of comb(comb(part)) to the actual output.

output += sum(comb(comb(part)))

Let and array be ${a_1, a_2, a_3}$, so $$ comb({a_1, a_2, a_3}) = [a_1(a_2+a_3), a_2a_3, \frac{a_1(a_1-1)}{2}, \frac{a_3(a_3-1)}{2}, \frac{a_3(a_3-1)}{2}] $$

$$ sum(comb({a_1, a_2, a_3})) = (a_1 * (a_2 + a_3) + a_2 * a_1 + a_1) + \frac{a_1(a_1-1)}{2} + \frac{a_2(a_2-1)}{2} + \frac{a_3(a_3-1)}{2} $$

$$ sum(comb({a_1, a_2, a_3})) = \frac{2a_1a_2 + 2a_2a_3 + 2a_1a_3 + {a_1}^2 + {a_2}^2 + {a_3}^2 - (a_1 + a_2 + a_3)}{2} $$

$$ sum(comb({a_1, a_2, a_3})) = \frac{(a_1 + a_2 + a_3)^2 - (a_1 + a_2 + a_3)}{2}
$$

In general: $$ sum(comb({a_1, a_2, a_3, …a_n})) = \frac{\sum{a_i}* (\sum{a_i}-1)}{2} $$

or,

$$ sum(comb(comb({a_1, a_2, a_3, …a_n}))) = \frac{\sum{a_i} * (\sum{a_i}-1) * (\sum{a_i}-2) * (\sum{a_i}+1)}{8} $$

Thus we have reduced the operation to a single linear time function of sum. The program is looping from the end of final array (appended with 1’s) to start of initial array, thus we can pre-calculate the sum of array and then we’ll have to add to number of 1’s which will be the sum of each part.

So the final script can be reduced to :

def optimised_comb(S):
    return (S*(S-1)*(S-2)*(S+1))//8

vals, data = open("input.txt").read().split("\n")
n, k = list(map(int, vals.split(" ")))
array = list(map(int, data.split(" ")))
final_array = array + [1] * (n-k) 

output = 0 
arr_sum = sum(final_array)
for j in range(n, k-1, -3):
    part_sum = arr_sum + (j-k) #Adding number of ones to total sum 
    output += optimised_comb(part_sum)
print("bcactf{" + str(output) + "}") 

Flag

bcactf{1256717047406103274281000233490626854133493566253}

Rev/XOR

Challenge Description

The executable below outputs an encrypted flag using the XOR operator. Can you decompile and reveal the flag?

Hint

What is symmetric encryption?

Resources

xor

Solution

On checking the binary, we see a XOR function.

and the string aClkvkor8jqa1jb is ClkvKOR8JQA1JB731LeGkU7J4d2khDvrOPI63mM7.

nc challs.bcactf.com 32411
Encrypted flag: 21 0F 0A 15 3F 29 29 6B 13 1C 2C 74 7D 30 5E 50 6E 29 2B 24 19 0C 67 7D 05 54 7C 34 5C 13 32 42 29 62 7B 0F 4E 

So we XOR the encrypted flag by key to get back the flag.

encrypted = "21 0F 0A 15 3F 29 29 6B 13 1C 2C 74 7D 30 5E 50 6E 29 2B 24 19 0C 67 7D 05 54 7C 34 5C 13 32 42 29 62 7B 0F 4E"
key = "ClkvKOR8JQA1JB731LeGkU7J4d2khDvrOPI63mM7"

encrypted_bytes = bytes.fromhex(encrypted.replace(" ", ""))

decrypted_bytes = bytes(encrypted_byte ^ key_byte for encrypted_byte, key_byte in zip(encrypted_bytes, key.encode()))

print(decrypted_bytes)

Flag

bcactf{SYMmE7ric_eNcrYP710N_4WD0f229}