# BabyEncoder - reverse

We're basically a simple program that does this:

* Reads 64 bytes from `/dev/urandom` into a variable called `buf`
* Runs the following encryption loop

for ( i = 0; i <= 63; ++i )
    *((_BYTE *)buf + i) = *((_BYTE *)buf + i) % 0x5Fu + 32;

* This basically turns every value in `buf` into a value from 32 to 126 inclusive.
* Runs another encoding function `sub_13C7` over a chunk of 8 bytes from `buf` eight times (ie `buf[0:8]`, `buf[8:16]`, etc.
* The return value from `sub_13C7` is a double that's stored into the `v6` array as 128 bytes

for ( j = 0; j <= 7; ++j )
    sub_13C7(
      (unsigned int)&v6[128 * j],
      buf[j],
      BYTE1(buf[j]),
      BYTE2(buf[j]),
      BYTE3(buf[j]),
      BYTE4(buf[j]),
      BYTE5(buf[j]),
      BYTE6(buf[j]),
      HIBYTE(buf[j]));

* We are given the output of `v6`
* If we guess the `buf` array correctly we get the flag (after the encoding loop from the second bullet point)

## sub_13C7
* Generate initial random value $\text{v32}$ between 0 and 254 inclusive
* Generate 8 random numbers $r_j$, $0 \le r_j \le 254$
* Generate 128 values in an array as such ($0 \le i \le 127$):
$$\text{arr[i]} = \sum_{j=1}^8 \left(\text{buf[j]}*\cos\left(\frac{2\pi}{128}*j*i + \frac{\pi}{64}*r_j\right)\right) + \text{v32} + x_i\\
= \sum_{j=1}^8 \left(\text{buf[j]}*\cos\left(\frac{\pi}{64}*(i*j + r_j)\right)\right) + \text{v32} + x_i$$

## Fourier Series and DFT
* According to https://en.wikipedia.org/wiki/Fourier_series#Table_of_common_Fourier_series, this formula is very similar to the formula for a Fourier Series
$${\displaystyle s_{\scriptscriptstyle N}(x)={\frac {A_{0}}{2}}+\sum _{n=1}^{N}A_{n}\cdot \cos \left({\tfrac {2\pi }{P}}nx-\varphi _{n}\right)}$$
* The $x_i$ above is a random integer from 0 to 2 inclusive, it can be thought of as random noise added to the fourier series.
* In exponential form (which helps when we're going to calculate the DFT)
$${\displaystyle s_{_{N}}(x)=\sum _{n=-N}^{N}c_{n}\cdot e^{i2\pi nx/P}}$$
* Equating the variables from the 2 equations we have
$$\frac{A_0}{2} = \text{v32}\\
A_n = \text{buf[j]}\\
x = i\\
n = j\\
N = 8\\
P = 128\\
\varphi _{n} = -\frac{\pi}{64}r_j\\
c_n = \frac {A_{n}}{2}e^{-i\varphi _{n}}$$

* The DFT (Discrete Fourier Transform) will give us a set of coeffcients $X_k$. The random noise is small and won't affect the coeffcients.
* We can use these coefficients to define a new Fourier Series (https://en.wikipedia.org/wiki/Discrete_Fourier_transform#math_Eq.2)
* Note $N = 128$ here, not to be confused in the above series where we defined $N = 8$.

$${\displaystyle x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}\cdot e^{i2\pi kn/N},\quad n\in \mathbb {Z} ,}$$
* Note that this Fourier Series is different than the one we have from the `sub_13C7` function
* First, we have 128 terms in this expression, compared to the 9 we had in the other Fourier Series.
* However, we can still recover the original coefficients by only looking at the first nine $X_k$ values.
* This works because if we look at the exponential form of the Fourier Series and equate it to the Fourier Series the DFT defines for us, then $c_n = \frac{X_k}{128}$
* This basically means that the only relevant terms from the new Fourier Series are $k = 0$ to $k = 8$, accounting for the 8 cosine terms we have and the initial $A_0/2$ term from the Fourier Series of `sub_13C7`.
* The DFT will still give us values for $X_k$ beyond $k = 8$, but they will be very small and negligible, which makes sense since our original series only has 9 terms.
* We are going to use `numpy` to calculate the DFT, which gives us complex values, in order to get the amplitude and phase (which gives us $\text{buf[j]}$ and $r_j$), we have to convert from complex to polar notation. This is trivial with `np.abs` and `np.angle`.

## Code

from pwn import *
import struct
import numpy as np

#context.log_level = 'debug'

def proof_of_work(tube):
    tube.recvline()
    poww = tube.recvline().strip(b"\n")
    p = int(poww[poww.index(b"mod ") + 4:poww.index(b" =")])
    tube.recvuntil("Your answer: ")
    # calculate 2^(2^x) mod p
    x = int(poww[5:poww.index(b") mod ")])
    tube.sendline(str(pow(2, pow(2, x), p)))
    #tube.interactive()

def get_doubles(tube):
    v6 = []
    tube.recvuntil("========START=======\n")
    doubles = tube.recvuntil("=========END========\n", drop=True)
    #print(len(doubles))
    assert len(doubles) == 8192
    for i in range(1024):
        v6.append(struct.unpack('<d', doubles[8*i:8*(i + 1)])[0])
    
    correct_bufs = []
    for xx in range(1024//128):
        fft = np.fft.fft(v6[128*xx:128*(xx + 1)])/128
        amp = np.abs(fft)
        phase = np.angle(fft)
        #print(list(fft))
        #print("v32", round(amp[0]))
        for i in range(1, 9):
            #print("buf[j]", round(amp[i]*2))
            correct_bufs.append(int(round(amp[i]*2)))
            #print("r_j", round(phase[i]*64/np.pi))
        #print(correct_bufs)
        #print(list(np.fft.fft(v6[:128])/128))
        #print(list(np.fft.rfft(v6[:128])/128))

    tube.send(bytes(correct_bufs))
    print(tube.recv(1024))

r = remote("202.120.7.212", 20001)
proof_of_work(r)
get_doubles(r)

## Flag
`flag{R34l1y_3aSy_R3ve7s3_W31C000m3_T0_0CTF/TCTF_2022_G000d_Luck}`