GrabCON CTF 2021 - The Ancient Temple

"The Ancient Temple" is a crypto challenge in GrabCON CTF 2021. You can download the challenge file here and the auxiliary file here.

Details

The challenge file seems overwhelming at first glance. But let's unravel its complexity by examining the function one by one. Let's first understand what's the deal with the variable k

k = [list(map(int, list(' '.join(bin(ord(i))[2:]).split()))) for i in flag]

We could analyze this statically (no running code) or dynamically (by just printing out what's k). Let's talk about how to analyze it statically (in case we can't actually run the code). One method I like to use is to work backwards from the outermost layer, starting with the [ ]. Let's simplify it:

k = [ list( f0(i) ) for i in flag ]
f0(i) = map( int, list( f1(i) ) )
f1(i) = ' '.join( f2(i) )
f2(i) = bin( ord(i) )[2:].split()

Now, we slowly understand each of the ‘functions' applied to i, let's start with f2(i). It feeds ord(i) into bin(). In python, the ord function returns the integer representation of a character. It basically works like an ASCII lookup table, so for instance ord('A') would give us 65, which is the decimal number for the character ‘A' in ASCII. bin will take an integer input and output its binary representation, much like what hex in python does. So, bin(ord(i)) will output the binary representation of an ASCII character as a string. However, bin actually prepends ‘0b' in front of the output string, like how hex prepends ‘0x' in front of the hex output, thus the [2:] syntax ‘cuts-off' 2 character of the output. The split in this case does nothing, because the output contains no white space. So, f2 is just fancy code for converting an ASCII to its binary representation with the result stored in an array of 1 element.

f1 joins the output of f2. However, the output of f2 is just a list with 1 element, f1 basically converts f2 from a list of 1 string into a string. So, f1 basically takes an ASCII and convert it to a string that is the binary representation of it. Finally, f0 maps each element of the string produced by f1 to the function int, this means if the string is "0010", we will get the array [0, 0, 1, 0]. We have statically analyzed what is k: its just a list of lists that are binary representation of each characters in the flag.

While analyzing the function like this seems tedious, if we have no access to a run-time, this is the only way to understand the code. Luckily for those of us with python installed on our local machine, analyzing this is a breeze. What we could do is simply print out k and see what it looks like given an input.

[[1, 0, 1, 0, 0, 1, 0], [1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 0, 1, 0, 0], [1, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 1, 1], [1, 0, 1, 0, 1, 0, 0], [1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 0, 1, 0, 0]]

This confirms out static analysis. Thus, we know that each character of the flag is converted to an array containing its binary representation. Now let's understand the operations performed on k:

def num_gen(first, last):
   o = [[1]]
   cnt = 1
   while cnt <= last:
       if cnt >= first:
           yield o[-1][0]
       row = [o[-1][-1]]
       for b in o[-1]:
        row.append(row[-1] + b)
       cnt += 1
       o.append(row)

for i in num_gen(7, 13):
       s.append(i)

The first 2 blocks of code seems to be building up the variable s. However, when we inspect the auxiliary file given, s is provided. To save time, let's make a fair assumption: we don't have to care about s because not only is it given to us, its generation also contain no elements of randomness, meaning what we have should be the same as what the author of this challenge have.

Let's look at the other blocks of code.

for i in range(len(s)):
    ni = ((l*s[i]) % M)
    n.append(ni)


for p in k:
    C_curr = []
    for (x,y) in zip(p, n):
        C_ = x*y
        C_curr.append(C_)
    C += [sum(C_curr)]

In the first loop, each element in s is multiplied modulo M and appended to n. By the same reasoning as s, we don't have to give this too much thought because n is also provided in the auxiliary file. The second loop is interesting to us, because it performs operation with the binary representation of each characters of the flag, or k.

For every binary representation, each bit is multiplied by a corresponding element in n, then appended to an array C_curr. Then after all bits have been multiplied, C_curr is summed and appended on to C. We conclude here that the values in C found in the auxiliary file is actually the encoding of the flag.

For an array n of size 7, which is the same number of bits sufficient to represent an ASCII character, the encoding of a character i in the flag is as follows:

C = i[0] * n[0] + i[1] * n[1] + ... + i[6] * n[6]

Where i[0] is the most significant bit (MSB) of i, while i[1] is the bit to the right of the MSB and so on. This gives a fairly straight-forward way to break this: Brute-forcing.

Rationale: There are only 7-bits used for each character, which gives us 128 possibility for each characters. Let's assume the flag is 50 characters long (pessimistic assumption), this will require 128 50 attempts to guess the plaintext. 128\50 = 6400 is a very small search space, which makes this attack feasible.

Note: I am well aware that the author claim that this isn't the "intended" way of solving this challenge. But it is to me, the most simplest approach. Besides, I believe brute-forcing is fair game in a crypto challenge given real-world crypto is designed to withstand against brute-forcing anyways.

Enough said, let's break this thing already!

C = [15051976, 12005794, 3916945, 6470614, 7771050, 19992202, 17519217, 19419005, 13883825, 18691766, 13988655, 6979140, 14478779, 13988655, 8943599, 13883825, 25527382, 6384186, 13988655, 16461640, 25527382, 16224525, 6707729, 21488294, 25527382, 14392351, 6707729, 16733051, 12005794, 25527382, 6470614, 3916945, 7771050, 12711276, 21673277]

dflag = []
for c in C:
    print('cracking', c)
    for i in range(128):
        pm = list(map(int, bin(i)[2:]))
        if len(pm) < 7:
            pm = [0] * (7-len(pm)) + pm

        curr = []
        for (x, y) in zip(pm, n):
            e = x*y
            curr.append(e)

        if sum(curr) == c:
            dflag.append(curr)
            break

binlist = [''.join(['1' if ci else '0' for ci in c]) for c in dflag]
intlist = [int(bi, 2) for bi in binlist]
chrlist = [chr(i) for i in intlist]
print(''.join(chrlist))

In our loop, we iterate from 0 to 128 (though we can eliminate 0, since none of any element in C is 0) for each integer in C. We used the same encoding function to compute the sum of curr, which is then compared with the element in C. If there is a match, we have found our binary sequence, and append it to a dflag array. This code will run AT MOST 24*(length of C = 35) = 840 iterations. Even if 1 iteration takes 1 second (which is a ridiculously pessimistic assumption), we would be done by at most 14 minutes. Besides, this is MUCH faster than actively trying to "solve" the linear equations that computes C.

<me@cj-basepc:ancient>>$ python solve.py
cracking 15051976
cracking 12005794
cracking 3916945
cracking 6470614
cracking 7771050
cracking 19992202
cracking 17519217
cracking 19419005
cracking 13883825
cracking 18691766
cracking 13988655
cracking 6979140
cracking 14478779
cracking 13988655
cracking 8943599
cracking 13883825
cracking 25527382
cracking 6384186
cracking 13988655
cracking 16461640
cracking 25527382
cracking 16224525
cracking 6707729
cracking 21488294
cracking 25527382
cracking 14392351
cracking 6707729
cracking 16733051
cracking 12005794
cracking 25527382
cracking 6470614
cracking 3916945
cracking 7771050
cracking 12711276
cracking 21673277
GrabCON{kn4ps4ck_h45_g07_y0ur_baCK}

Bingo, we got the flag.