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$):
  
  $$\begin{gathered} \text{arr[i]}=\sum _{j=1}^8(\text{buf[j]}\ast \cos (\frac{2\pi }{128}\ast j\ast i+\frac{\pi }{64}\ast r_j))+\text{v32}+x_i \\ =\sum _{j=1}^8(\text{buf[j]}\ast \cos (\frac{\pi }{64}\ast (i\ast j+r_j)))+\text{v32}+x_i \end{gathered}$$

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_N(x)=\frac{A_0}{2}+\sum _{n=1}^N{A}_n\cdot \cos (\frac{2\pi }{P}nx-{\phi }_n)}$$

• 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
  

  $$\begin{gathered} \frac{A_0}{2}=\text{v32} \\ {A}_n=\text{buf[j]} \\ x=i \\ n=j \\ N=8 \\ P=128 \\ {\phi }_n=-\frac{\pi }{64}{r}_j \\ {c}_n=\frac{A_n}{2}{e}^{-i{\phi }_n} \end{gathered}$$

• 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},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}