Rating:

Both challenges are quite similar, so I only write a single writeup for them.

## Understanding the basics
In both cases, we have a single brainfuck file. (I recommend to __not__ run it with the interpreter given in the description, but I found an interpreter / visualizer that is safer to use: [BF Visualizer](https://fatiherikli.github.io/brainfuck-visualizer/). Let's put the first program into it and watch it (Check the *Optimize* box and reduce the delay for a deccent speed). The program will eventually crash because of the limited tape, but looking at the values, they look like ASCII values:
![BF1](https://raw.githubusercontent.com/DerBaer0/CTF-writeups/main/2021-imaginaryctf/bf1.jpg)
So, there is the flag, but it is truncated in the end. We could modify the sourcecode for a wider tape, or we look into the source code (which we'll need for the second challenge anyway.) I structured the code to be more readable: Before and after [] is a newline, so loops are in a line by themselfs. The beginning constists of blocks of this form:

>>+++++++++++
[<+++++++++++>-]
--
[<-------->+]

What is happening here? The first two lines:

We increment a cell X = 11 times
We have a small loop that: Goes to the left, increment by Y = 11, go right, decrement by 1. Repeat

This is a multiplication X * Y: The left cell used as the result starting with 0, the right cell is the loop counter starting with Y (set in the first line). For each iteration, the left cell is incremented by X, and this is done Y times, so X*Y.
The lines 3 and 4 are basically the same, but instead of adding it to the left cell, it subtracts. So, this whole block computes:
cell = X * Y - A * B, where the 4 variables can be determined by the number of + or - in the four lines. In our example: cell = 11 * 11 - 2 * 8 = 105 = ascii('i')
For the first challenge, I appended to every block <.> which prints the value we just built and removed the first few blocks of code for the remaining part of the flag to fit into memory. This solves No Thoughts, Head Empty.

But for the second challenge, it is more complicated. The description suggests that we have a similar challenge and looking at the source, we can identify the same 4-line blocks of code, but the numbers are larger. This stops us from running it: It is very slow and the numbers are not ascii values anymore. At this point, I wrote a small function to parse and print the values:
python
def get_num(ls): # takes 4 lines as strings
pms = [0] * 4
for i in range(4): # count the number of plus and minus for each line
pms[i] = (ls[i].count('+'), ls[i].count('-'))
# Some lines add, some lines substract.
# With max(), I get the number, no matter which of the two options is used,
# because the loop counter always only appears once
val = max(pms[0]) * max(pms[1]) # this is X*Y
mul = 1
if ls[3][2] == '-': # detect if we add or subtract the second part
mul = -1
val += mul * max(pms[2]) * max(pms[3]) # this is A*B
return val

Note that this fails for the easier challenge because there were some blocks with only two lines.
## Reversing Brainfuck
Now, we get the numbers: 105 5664 5066 6888 5376 7742. The first one is i, but the others are too large for ASCII. Now, I went onto reversing the tail part of the Brainfuck Code. I did this using a sheet of paper and stepping the online interpreter to visualize as much as possible what is happening. I start by picking out some important parts (and added line numbers for the explanation). (H) marks the position of the head, _ a value not relevant for the current aspect
#### The Doubler

1 [->+>++<<] # This is a loop that transforms: X 0 0 into 0 X 2*X
2 >>
3 [-<<+>>] # This loop moves a value two cells to the left: 0 _ X to X _ 0
# Together, they change X(H) 0 0 to 2*X X 0(H)

Followed by some moving stuff we look at later, follwed by a loop doing the important stuff:

1 [<
2 [->>-<<] # A _ B to 0 _ B-A
3 >-
4 [-<+<+>>]<<[->>+<<] # similar to 3-5: transform 0 0 X to 0 X 2*X
5 >>] # from X Y(HEAD) Z, to 0 Y Z-X, to 0 Y-1 Z-X, to Y 2*(Y-1) Z-X
6 >>
7 [>]
8 >-]


#### The Gauss Subtraction

1 [<
2 [->>-<<]
3 >-
4 [-<+<+>>]
5 <<
6 [->>+<<]
7 >>]


(0) initial setup
0 X X D E (when the loop runs, both X have the same value)
--------------
(1) go left
v
0 X X D E
--------------
(2) subtraction
v
0 0 X D-X E
--------------
(3) go right, decrement
v
0 0 X-1 D-X E
--------------
(4) double
v
X-1 X-1 0 D-X E
--------------
(4) left, copy, right
v
0 X-1 X-1 D-X E

We are back at the initial state with a two differences:
D was decremented by X, X got reduced by 1 (in both positions). As this happens inside a loop, we continue substracting X-1 from D-X and reduce X-1 to X-2 and so forth. In The end, we subtracted all numbers between X and 1 from D. The sum of values between 1 and X is (X + 1) * X / 2 (Gauss Sum), so D is reduced by this value in total.
#### The repeating Printer

<
[
[<]<[<]> # go to the leftmost non-zero cell (a bit complicated, because it needs to skip a zero cell in the middle)
. # print it
[>]>[>]< # go to the rightmost on-zero cell
-] # decrement and repeat

So, this function prints left leftmost most as many times as the rightmost cell indicates

#### The big loop
Putting our snippets together with some *glue* code, the big loop in the end reads as this (Note that there is a 0 between B and K. B is a normal character, and K is the number of characters in the flag. It is set similar to all other values, but there is an additional > beforehead to create the zero space.). In this case, it is assumed the flag only has two characters A and B.

Setup 0 0 A B 0 K(H) X 0 0
The Doubler 0 0 A B 0 K 2X X 0(H)
The repeating Printer 0 0 A B 0 K 2X 0(H) 0
Move to the far left 0 0 A(H) B 0 K 2X 0 0
Duplicate the value 0 A A(H) B 0 K 2X 0 0
The Gauss Subtraction 0 0 0(H) B-Gauss(A) 0 K 2X 0 0
Go right, decrement and Repeat 0 0 0(H) B-Gauss(A) 0 K-1(H) 2X 0 0

So, basically, we have a value X starting with 1 (directly before the big loop begins). We double X, print the current character X times, decrement the value of the second character by the gauss sum of the first character and go back to repeat by doubling X. This prints the first character once, the second character twice, the thid character 4 times and and so forth.

## The Script
python
import sys

def get_num(ls):
pms = [0] * 4
for i in range(4):
pms[i] = (ls[i].count('+'), ls[i].count('-'))
val = max(pms[0]) * max(pms[1])
mul = 1
if ls[3][2] == '-':
mul = -1
val += mul * max(pms[2]) * max(pms[3])
return val

def gauss(x):
return (x+1) * x // 2

bf = open(sys.argv[1]).readlines() # open the (formatted! file)
ls = [x.strip() for x in bf[:128]] # take all characters (the value 124 is taken by looking at the source)
ls = [get_num(ls[i:i+4]) for i in range(0, len(ls), 4)] # compute all values
for i in range(1, len(ls)): # apply the gaussian subtraction
ls[i] = ls[i] - gauss(ls[i-1])
print("".join(map(chr, ls)))

The flag: ictf{th3_l3s5_th0ugh+_+he_b3teR}

Original writeup (https://github.com/DerBaer0/CTF-writeups/blob/main/2021-imaginaryctf/Misc-FewerToughs.md).