TBTL CTF 2024

TBTL CTF 2024 was a 48-hour long CTF Event organised by employees of Blockhouse Technology in Zagreb, Croatia from 11 May, 06:00AM SGT to 13 May, 06:00AM SGT. There were 7 crypto challenges, 5 misc challenges, 6 pwn challenges, 5 rev challenges and 4 web challenges. My team G04T3DP30PL3 solved 3 crypto challenges, 2 misc challenges, 1 pwn challenge, 1 rev challenge and 1 web challenge. This got us 47th place amongst 792 teams, earning us 6.996 rating points on ctftime.

This writeup includes my workings for the 3 crypto challenges, 1 pwn challenge and 1 rev challenge which I solved.

crypto

Fence Building (100 points)

We are given a scrambled flag, and the challenge description hints that a fence cipher is being used.

We can use online tools such as planetcalc to decrypt the ciphertext. This gives us the flag if we use 4 rails: TBTL{G00d_F3nce5_m4k3_g00D_n31ghb0ur5}

School Essay (100 points)

We are given the following Python script:

from Crypto.Util.number import *
from redacted import FLAG

ESSAY_TEMPLATE = """
My Favorite Classmate
=====================

My favorite person in this class has a beautiful smile,
great sense of humour, and lots of colorful notebooks.

However, their most distinctive feature is the fact that
you can represent their name as an integer value, square
it modulo %d,
and you'll get %d.

Additionally, When you compute the greatest integer not exceeding
the cube root of their squared name, you get %d.

By now, all of you have probably guessed who I'm talking about.
"""


def invpow3(x):
    lo, hi = 1, x
    while lo < hi:
        mid = (lo + hi) // 2 + 1
        if (mid**3) <= x:
            lo = mid
        else:
            hi = mid - 1
    return lo


N = 59557942237937483757629838075432240015613811860811898821186897952866236010569299041278104165604573

name_int = bytes_to_long(FLAG)

assert 1 < name_int < N

value_1 = (name_int**2) % N
value_2 = invpow3(name_int**2)

print(ESSAY_TEMPLATE % (N, value_1, value_2))

We also know the result of the modulo operation and the smallest integer whose cube root does not exceed the message squared.

On checking using factordb, we find that N is a prime number. Hence we can use the Tonelli-Shanks algorithm to find the value of m.

I cloned this GitHub repository and proceeded to input the value of \(a\) and \(p\).

Now that we have the roots, we can make a simple solve script to get the flag (I tried both roots):

from Crypto.Util.number import *

print(long_to_bytes(703032588627510822704619969444615719158069204277139920487471397235396114708359092304587909772157))

This gives us the flag: TBTL{J0hn_J4c0b_J1n6LeH31mer_Schmid7_<3}

Wikipedia Signatures (100 points)

We are told that the problem involves digital signatures. We are also given the following script server.py:

#!/usr/bin/python3

from redacted import FLAG

from Crypto.Util.number import bytes_to_long
from Crypto.Math.Numbers import Integer
from Crypto.PublicKey import RSA

import signal


TARGET = b'I challenge you to sign this message!'


def myprint(s):
    print(s, flush=True)


def handler(_signum, _frame):
    myprint("Time out!")
    exit(0)


def rsa(m, n, x):
    if not 0 <= m < n:
        raise ValueError("Value too large")
    return int(pow(Integer(m), x, n))

# Alice signs a message—"Hello Bob!"—by appending to the original
# message a version encrypted with her private key.
# Does m ^ d mod n
def wikipedia_sign(message, n, d):
    return rsa(message, n, d)

# Bob receives both the message and signature. He uses Alice's public key
# to verify the authenticity of the message, i.e. that the encrypted copy,
# decrypted using the public key, exactly matches the original message.
# compute c ^ e mod n
def wikipedia_verify(message, signature, n, e):
    return rsa(signature, n, e) == bytes_to_long(message)

def main():
    signal.signal(signal.SIGALRM, handler)
    signal.alarm(300)

    rsa_key = RSA.generate(1024)
    public_key = (rsa_key.n, rsa_key.e)

    myprint(f"RSA public key: {public_key}")
    myprint("Options:")
    myprint(f"1 <sig> -- Submit signature for {TARGET} and win")
    myprint("2 <msg> -- Sign any other message using wikipedia-RSA")

    for _ in range(10):
        line = input("> ")
        action, data = map(int, line.split())
        if action == 1:
            if wikipedia_verify(TARGET, data, rsa_key.n, rsa_key.e):
                myprint(f"{FLAG}")
                exit(0)
            else:
                myprint(f"Nope. Keep trying!")
        elif action == 2:
            if data % rsa_key.n == bytes_to_long(TARGET):
                myprint(f"Nope. Won't sign that!")
            else:
                sig = wikipedia_sign(data, rsa_key.n, rsa_key.d)
            myprint(sig)
        else:
            break


if __name__ == "__main__":
    main()

Essentially, we are given a known plaintext, and challenged to sign it with the help of a signing oracle. The signing oracle, however, will not directly sign the plaintext for us. It will also not sign any multiples of the plaintext.

As it turns out, this is victim to an existential forgery attack.

Let the RSA signing function be \(S\). If we can factorise the message \(m\) into two factors, say \(m = m_1m_2\), then we would want \(S(m) = S(m_1m_2)\). Expanding the signing function, \(S(m_1m_2) = (m_1m_2)^e mod\space n = (m_1^e mod\space n\times m_2^e mod\space n)mod\space n = (S(m_1)\times S(m_2))mod\space n\)

So all we need to do is find at least 2 factors of \(m\), get the oracle to sign the factors, then multiply the signed factors and perform modulo n. I used factordb to factorise \(m\) into 3 factors: \(m_1\), \(m_2\) and \(m_3\), then found their signed values \(s_1\), \(s_2\) and \(s_3\), multiplied them and applied modulo \(n\). I then submitted this as a signature and it was accepted. Below is the solve script:

from Crypto.Util.number import bytes_to_long

TARGET = b'I challenge you to sign this message!'
'''
IDEA
We wish to forge the signature of TARGET, i.e. find S(TARGET)
S(TARGET) = pow(TARGET, d, N)
If we can factorise TARGET, i.e. TARGET = m1 * m2 * m3, we can get the signing oracle to compute
S(m1), S(m2) and S(m3).
S(TARGET) = S(m1 * m2 * m3) = pow(m1 * m2 * m3, d, N) = (pow(m1, d, N) * pow(m2, d, N) * pow(m3, d, N)) % N
= (S(m1) * S(m2) * S(m3)) % N
'''
# long_value = bytes_to_long(TARGET)
long_value = 36367516023080771443785382206537484078500891673043385026763929849792665821597708151383329
N = 127615371505899714748358555201998931254929502359253245229424569729239718780210844446558789786766059471803952759610656583794654107320850664393116761223331387904289729943871097833192197546370764701312416767047567421287604868926635024110875678814007665786944777150322932068355980747916352029641295223560432083433
e = 65537
m1, m2, m3 = 29, 7917141825001291, 158397096373570792429398106246416860700170897291328086627072903632668511
s1 = 42925480254329893841360510946264677222139271434878871312036959358581658006747416959841489378501224193508887531180473105954161795834130630913463524574004116728756398969624610278957327203355380259086265648167881271086530612233921941271153121739718158789931126539413302493672747921557494198359359192204593923916
s2 = 111372255355264247421531499661246618384487152239168359914670832866093942140391928549307016854372646835918866377205085171701615258128550842976231629146107439589335514353514666312979242381730907063406267045008117560779401433490416883777764146426159824479278927884633632503832187986277297713652911026960155394513
s3 = 70217238417599767352767243055184151556163016776972441396430968905579566943223853967357306705455434587052206193993308349603629120437089169957293088249912697514822831042161050400774951888223276295788434416283023816782004351059072131075912903589935221512630781262595202731025649838905157846279720843604819537653
print((s1 * s2 * s3) % N)

Submitting this as the signature gives us the flag: TBTL{r3p347_4f73r_m3-d16174l_516n47ur3_15_n07_3ncryp710n}

pwn

Enough with the averages

We are given the following source code chall.c:

// gcc -o chall chall.c -Wextra
#include <stdio.h>
#include <stdlib.h>

void read_flag() {
  FILE* in;
  char flag[64];
  in = fopen("flag.txt", "rt");
  fscanf(in, "%s", flag);
  fclose(in);
}

void vuln() {
  int score[20];
  int total = 0;
  for (int i=0; i<20; i++) {
    printf("Enter score for player %d:\n", i);
    scanf("%d", &score[i]);
    total += score[i];
  }
  printf("Average score is %lf.\n", total/20.);
  printf("Type q to quit.");
  while (getchar() != 'q');
}

int main() {
  setbuf(stdin, NULL);
  setbuf(stdout, NULL);
  read_flag();
  vuln();
  return 0;
}

When analysing the binary using checksec, we find that all protections are enabled on the binary. The architecture is amd64-64-little.

Basically the main() function is calling read_flag() which reads the flag file into an array of chars, and then calls vuln(). vuln() uses scanf to take in 20 integers which represent the player scores, then prints the average score before prompting the user to exit the program.

The main problem with this code is that if we enter a character to scanf("%d", &score[i]) instead of an integer, the value at &score[i] is not changed. Entering a character will also cause subsequent scanf calls taking in an integer to be “skipped”, until we read a character.

Analysing the code using Ghidra, we observe that the local_58 variable which stores the flag’s characters in the read_flag() function occupies the stack from Stack[-0x58] to Stack[-0x11] inclusive.

We also observe that the local_68 variable in the vuln() function occupies the stack from Stack[-0x68] to Stack[-0x11] inclusive.

We also know that the stack base pointers for read_flag() and vuln() are the same, since vuln() is called right after read_flag().

For the first 4 players, we always give them a score of 0. This is because the first 16 bytes (or 4 integers) which the vuln() function accepts were not used to store the flag’s characters. The remaining 16 integers, or 64 bytes (which is also 64 characters), in the stack were previously used to store the flag’s characters.

The vuln() function will read ‘blocks’ of 1 integer (4 bytes) when calculating the average. In total, we have 16 ‘blocks’ we want to find the characters of. We number these blocks from 0 to 15. Our strategy is as follows:

1. Maintain a cumulative sum of block values. I call this cum.
2. We set all blocks 0 to 14 to have an integer value of 0, and enter a character as the integer value of block 15. This causes scanf to “skip” the replacement of the characters at block 15.
3. Obtain the average of the 20 blocks, and multiply it by 20 to obtain the integer value of block 15 res.
4. Since the binary is little endian, the first character of the block is stored at the lowest byte while the last character of the block is stored at the highest byte. So the first character is the last 8 bits of res, the second character is the next 8 bits of res, the third character is the next 8 bits of res and the last character is the first 8 bits of res. This helps us obtain the last 4 characters of the flag which are located in block 15.
5. Increment the value of cum by res.
6. This time we set all blocks 0 to 13 to have an integer value of 0, and enter a character as the integer value of block 14. This causes scanf to “skip” the replacement of the characters at blocks 14 and 15.
7. Obtain the average of the 20 blocks, and multiply it by 20 to obtain the combined integer value of blocks 14 and 15.
8. The integer value of block 14, res, is this integer value with cum subtracted (recall that cum now has the value of block 15).
9. Increment cum by res.
10. Repeat step 4 to obtain the characters in block 14.
11. Repeat steps 6 - 10, successively decrementing the block at which we enter a character into scanf("%d", &score[i]). Doing so, we obtain the characters in all blocks.

Below is the Python script which implements this:

from pwn import *

cum = 0
flag = ""
# iterate through "chunks" of 4 characters
for i in range(16):
    # p = process('./stats')
    p = remote('0.cloud.chals.io', 10198)
    # first 4 chunks do not contain the flag so set to 0 so
    # we don't include their value
    for _ in range(4):
        p.sendlineafter(b":\n", b'0')
    num_zeroes = 16 - i - 1
    for _ in range(num_zeroes):
        p.sendlineafter(b":\n", b'0')
    p.sendlineafter(b":\n", b'a')
    p.recvuntil(b'is ')
    res = p.recvuntil(b'.\n')
    info(res)
    p.close()
    res = res[:-2].decode()
    res = int(float(res) * 20)
    res -= cum
    cum += res
    a = chr(res % 256)
    res >>= 8
    b = chr(res % 256)
    res >>= 8
    c = chr(res % 256)
    res >>= 8
    d = chr(res % 256)
    flag = a + b + c + d + flag

print(f"flag: {flag}")

The script prints the flag for us, and the output is: flag: TBTL{e4t_Y0ur_vegG13s_1n1714l1z3_y0ur_d4rn_v4r14bl35}\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00

rev

Flagcheck (100 points)

We are provided a simple binary file which tells us if our input is the correct flag. Inspecting the file with Ghidra, we see the following:

undefined8 main(void)
{
  int iVar1;
  size_t flag_length;
  long in_FS_OFFSET;
  uint seed;
  int i;
  int j;
  char input [72];
  long local_20;
  char elem;

  local_20 = *(long *)(in_FS_OFFSET + 0x28);
  printf("Let me check your flag: ");
  __isoc99_scanf(&DAT_0010213d,input);
  flag_length = strlen(input);
  if (flag_length != 63) {
    no();
  }
  seed = 1;
  i = 0;
  while( true ) {
    flag_length = strlen(input);
    if (flag_length <= (ulong)(long)i) break;
    seed = (int)input[i] * seed;
    i = i + 1;
  }
  srand(seed);
  j = 0;
  while( true ) {
    flag_length = strlen(input);
    if (flag_length <= (ulong)(long)j) break;
    elem = input[j];
    iVar1 = rand();
    if (((int)elem ^ iVar1 % 0x100) != *(uint *)(target + (long)j * 4)) {
      no();
    }
    j = j + 1;
  }
  puts("Correct!");
  if (local_20 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return 0;
}

We can infer that the flag length is 63. The program computes a seed using the product of all the characters in our input, and feeds the seed into srand. Then, for each integer in the input, we generate a random integer using rand(), then perform XOR with the integer and take the least significant 8 bits. We then compare this to the corresponding element in target. We can verify that this is legitimate because every integer in target only has non-zero bits in its least significant 8 bits.

Following this, in order to find the flag, we have no choice but to find out what the seed is. Since srand uses a Linear Congruential Generator, and we know that the first 4 characters should be TBTL, we can determine what the seed should be. However, I opted to use a brute-force approach starting from the maximum possible value of the seed (0xffffffff) and reducing its value. At each seed value I would check if the first four xor values produced by the seed were correct. Below is my brute-force script:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main() {
    unsigned int target[63] = {0x33, 0x84, 0x3d, 0x3f, 0x2a, 0x93, 0x7b, 0x82, 0x1a, 0xac, 0x8e, 0xf4, 0xb1, 0xcb, 0x8d, 0x21, 0x0e, 0xb7, 0x67, 0x96, 0x2c, 0x81, 0xd3, 0xbc, 0x29, 0x6c, 0x4b, 0x0d, 0x00, 0xed, 0xfd, 0xee, 0x56, 0x40, 0x52, 0xd5, 0x05, 0x6d, 0x90, 0x3e, 0x7a, 0x1b, 0x69, 0x23, 0x1f, 0xb6, 0x1d, 0xbc, 0x98, 0xd1, 0xa6, 0x83, 0xe9, 0xeb, 0x13, 0x21, 0x3d, 0xf8, 0x2b, 0x79, 0x53, 0x4f, 0xa1};
    unsigned int seed = 0xffffffff;

    while (1) {
        // apply the seed to srand
        srand(seed);
        int a = rand();
        int b = rand();
        int c = rand();
        int d = rand();
        // check if the produced xor values are correct
        if (((0x54 ^ a % 0x100) == target[0]) && ((0x42 ^ b % 0x100) == target[1]) && ((0x52 ^ c % 0x100) == target[2]) && ((0x46 ^ d % 0x100) == target[3])) {
            printf("Seed found: %u\n", seed);
        }

        seed--;
        if (seed == 0) break;
    }
}

After a few minutes, I get the seed value which is 3797176037. I can then make a solve script to solve for the flag:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main() {
    unsigned int target[63] = {0x33, 0x84, 0x3d, 0x3f, 0x2a, 0x93, 0x7b, 0x82, 0x1a, 0xac, 0x8e, 0xf4, 0xb1, 0xcb, 0x8d, 0x21, 0x0e, 0xb7, 0x67, 0x96, 0x2c, 0x81, 0xd3, 0xbc, 0x29, 0x6c, 0x4b, 0x0d, 0x00, 0xed, 0xfd, 0xee, 0x56, 0x40, 0x52, 0xd5, 0x05, 0x6d, 0x90, 0x3e, 0x7a, 0x1b, 0x69, 0x23, 0x1f, 0xb6, 0x1d, 0xbc, 0x98, 0xd1, 0xa6, 0x83, 0xe9, 0xeb, 0x13, 0x21, 0x3d, 0xf8, 0x2b, 0x79, 0x53, 0x4f, 0xa1};
    unsigned int seed = 3797176037;

    for (int i = 0; i < 63; i++) {
        int a = rand();
        int nxt = (target[i] ^ a % 0x100);
        char c = nxt;
        printf("%c", c);
    }
}

This gives us the flag: TBTL{l1n3a4_C0ngru3n7i41_6en3r4t0r_b453d_Fl4G_Ch3ckEr_G03z_8rr}