0xkasper

HackTM CTF 2020 Qualifiers Write-Up

· ctf, crypto, misc

Introduction

The HackTM CTF 2020 Qualifiers was a CTF where teams could qualify for the actual final at HackTM 2020 in Romania. Only the top 10 teams were invited. Unfortunately I could only participate on the second day of this two-day long CTF, as I had other plans. Nevertheless I still completed a few challenges and made it to the 95th place out of 750 actively participating teams. I only completed challenges in the cryptography and miscellaneous categories during the CTF. But as long as the challenges stay online, I will try to complete more and add them here.

This CTF was definitely harder than the previous CTF I participated in, the RiceTeaCatPanda CTF. You can read that write up here. But in the end I did learn a lot.


Cryptography


RSA Is Easy #1

rsa-is-easy-1

The challenge_files.zip contains a file called c which includes a line with ‘Public Key’ and one pair of a small number and a very large number, and a line with ‘Encrypted Flag’ and a list of very large numbers. And another file called rsa.py. As you may have guessed from the title, it has something to do with RSA. The c file contains an RSA public key, which is the encryption exponent e and the modulus n, and an encrypted flag. The rsa.py file shows the code used to encrypt the flag, it’s an implementation of RSA. Finding the decryption exponent d, i.e. the private key, is not going to happen, since the primes p and q in this implementation are both random and 512-bit, making this 1024-bit RSA. We therefore cannot factorize n and/or calculate d.

def enc(key, p):
    e, n = key
    cipher = [pow(ord(char), e, n) for char in p]
    return cipher

def dec(pk, c):
    key, n = pk
    plain = [chr(pow(char, key, n)) for char in c]
    return ''.join(plain)

The encryption and decryption methods of rsa.py

The trick lies in the actual implementation. It is important to analyze all the functions for flaws. It is the encryption function that has a flaw: it encrypts the plaintext message character by character. The amount of characters that can be used to write a flag is not large at all, at most 255 in ASCII. And since we know the public key, we can encrypt all those possible characters and check which value matches any value in the encrypted flag.

For example, the encryption exponent used is 65537 and we know that a HackTM flag starts with ‘H’. So the ASCII value of ‘H’ to the power of 65537 modulo n should yield the first flag value, and it does. This way we can easily bruteforce the flag.

import string

with open('c', 'r') as f:
    data = f.read().split('\n')
    e = int(data[1].split(', ')[0][1:])
    n = int(data[1].split(', ')[1][:-1])
    flag_enc = [int(x) for x in data[4][1:-1].split(', ')]

flag = ''
for f in flag_enc:
    for c in string.printable:
        if pow(ord(c), e, n) == f:
            flag += c
            break
print(flag)

The script I used to bruteforce the characters and obtain the flag

Flag: HackTM{why_ar3_MY_pR1va7es_pu8l1C_??}


RSA Is Easy #2

rsa-is-easy-2

This challenge is almost the same as RSA Is Easy #1, but in this case we did not get a public key. Instead we got a very long encrypted message, again character by character. The challenge_files.zip contains the c file with the encrypted message and an rsa.py with the same RSA implementation. From the implementation we can extract that an encryption exponent e of 65537 is used again, but to do the same method as the previous challenge, we need the modulus n. We might be able to calculate n from the 1111 encrypted characters, but an easier method of obtaining the flag is frequency analysis.

Since every character is encrypted one by one, we can compare different encrypted characters for equality and construct a frequency table for every character. This can be used to reconstruct the original text by using a table of all English characters ordered by frequency. The most frequent character in the encrypted text is probably the same as the most frequent character in the English language. Another easier way is to assign an ASCII character to every number and construct a text that appears to be random and let quipqiup solve it as if it is a substitution cipher.

with open('c', 'r') as f:
    data = f.read().split('\n')
    flag_enc = [int(x) for x in data[4][1:-1].split(', ')]

freq_dict = {}
for f in flag_enc:
    if not f in freq_dict:
        freq_dict[f] = 1
    else:
        freq_dict[f] += 1
freq = sorted(list(freq_dict.items()), key=lambda x: x[1])
freq.reverse()

english_freq = [' ', 'E','T','A','I','N','O','R','S','L','H',
                'C','M','D','Y','P','U','W','F','G','.','V',
                'B','X','K',',','Q', 'Z', '\'', '0', '9']
translator = {}
for i, c in enumerate(english_freq):
    translator[freq[i][0]] = c
for f in flag_enc:
    if f in translator:
        print(translator[f], end='')

The script I used to perform frequency analysis on the encrypted flag and translate it to English characters

This gives us a long story about frequency analysis and at the end it gives us the flag.

Flag: HackTM{when_it_comes_to_crypto_or_carpet_never_roll_your_own}


Prison Break

prison-break

I completed this challenge after the CTF had ended.

The challenge files contains a large list of 10 million triplets of numbers (a, b, c). As said in the description our task is to create a list of 10 million zeroes and add c to every element of the list between the indices a (inclusive) and b (exclusive) modulo 10. Then we have to take the product of every non-zero digit in the list and apply a modulus of 999999937. Implementing this is not difficult, we can just loop over every line and for every iteration loop over the range of a to b in the list. Unfortunately this range can be almost as large as the actual length of the list. So doing it the naive way will take ages. Or in CS terms, it will take O(n * k).

Luckily there is a solution, or better said a technique we can apply. The so called sliding window technique allows us to do it in O(n), which is way faster. We only loop once over all the elements in the ‘list’ (we’re not actually going to use a list), and keep the current value at that index stored. We can see the values a and b as a ‘window’ and the value c as the ‘change’ when entering or leaving the window. In order to do this, we keep a list of tuples, where one value is the index (a or b) and the change (c for a and -c for b). If we sort this list, we have an ordered list of tuples that tells us when to apply the change.

Apart from the index of the iteration, we also keep the position index of the point/changes list so we know where we are. If the iteration index reaches the next point of the list, we apply the change to the current value and increment the position index. And of course, we also keep the total product which we multiply by the current value every iteration. Don’t forget to apply a modulus of 10 to the value before multiplying and a modulus of 999999937 to the total product.

with open('given.txt', 'r') as f:
    lines = f.read().split('\n')

points = []
for line in lines:
    spl = line.split(' ')
    a = int(spl[0])
    b = int(spl[1])
    c = int(spl[2])
    points.append((a, c))
    points.append((b, -c))
points.sort()

n = 999999937
product = 1
s = 0
pos = 0
for i in range(1, 10000001):
    while pos < len(points) and i >= points[pos][0]:
        s += points[pos][1]
        pos += 1
    s %= 10
    if s > 0:
        product *= s
        product %= n
print(product)

My Prison Break implementation in Python

My implementation takes about 62 seconds, including sorting and calculating. I’m sure it can be optimized even further, but I’m content for now. The value we find is the actual flag.

Flag: HackTM{585778044}


Count On Me

count-on-me

I also completed this challenge after the CTF had ended.

In the challenge files there is a Python file called aes.py showing the encryption method, which is 256-bit AES in CBC mode. There is a text file called challenge.txt which contains the used IV during encryption, this is the initialization vector that is used for AES encryption in CBC mode, and also a ciphertext, which is probably the encrypted flag. And another file called key.png, which is of course the key that was used for encryption.

count-on-me-key

key.png

But as you can see the key is not very straightforward. This image definitely looks like some cipher, but it isn’t really. Signs are frequently repeated and seem to have an upper part and a lower part. The upper part does not exceed 3 lines and the lower part doesn’t exceed 4 lines. There is also one special character that looks like a fish. It’s actually a base-20 numeral system, where the upper lines represent 5/10/15 and the lower lines represent 1/2/3/4. The fish is zero. Now every token is a number from 0-19. I created another file called key and wrote the decimal values of every token, one on each line. There are 3 blurred tokens, so we don’t know what those values are and we will have to bruteforce it. This is not a problem however, since there are only 20 to the power of 3 different keys possible.

We have to find a key that is hexadecimal and 64 characters, which is 32 bytes and therefore matches the key length of 256-bit AES encryption. But the number of tokens is 59, so we’re not done yet. I tried to concat all the decimal values into one big decimal number and convert it to hexadecimal, but this yielded more than 64 characters. And of course that’s wrong, because it wouldn’t be equal to the base-20 value of the key. We have to treat the key as a large base-20 value, but we only have a list of each number/factor as base-10. To convert this list to one big base-20 value, we simply multiply it by 20 to the power of the order of magnitude. Now we convert this value to hexadecimal and obtain a key of the right length.

import string
from Crypto.Cipher import AES

keys = []
with open('key') as f:
    nms = f.read().split('\n')
    for i in range(0, 20 ** 3):
        key = nms
        key[31] = i % 20
        key[15] = i // 20 % 20
        key[5] = i // 400 % 20
        key = [int(x) for x in key]
        base_20 = 0
        for i, k in enumerate(key):
            base_20 += k * 20 ** (len(key) - i - 1)
        key = format(base_20, '0x')
        key = bytes.fromhex(key)
        keys.append(key)
iv = bytes.fromhex('42042042042042042042042042042042')
ciphertext = bytes.fromhex(
    '059fd04bca4152a5938262220f822ed6997f9b4d933 \
     4db02ea1223c231d4c73bfbac61e7f4bf1c48001dca \
     2fe3a75c975b0284486398c019259f4fee7dda8fec')

for key in keys:
    aes = AES.new(key, AES.MODE_CBC, iv)
    plaintext = aes.decrypt(ciphertext)
    if all([chr(c) in string.printable for c in plaintext]):
        print(plaintext)

My Python script to bruteforce the key from the token values and find the right plaintext

As you can see I just took the positions of the missing values in the key and generated 8000 keys. The IV and ciphertext were given, so from there on you only have to decrypt the ciphertext to a different plaintext for every key and check which plaintext looks like a real flag.

Flag: HackTM{can_1_h@ve_y0ur_numb3r_5yst3m_??}


Miscellaneous


Romanian Gibberish

romanian-gibberish

The Wikipedia link shows a language game called ‘Gibberish’ where you add letters to each syllable of a word. The provided text contains ‘HapackTM’ which is obviously ‘HackTM’, so the letter ‘p’ plus the vowel is added after the vowel. The same applies to every other syllable in the text. Removing these additions reveals the flag.

Flag: HackTM{Welcome_To_HackTMCTF_2020!}


The Dragon Sleeps At Night

the-dragon-sleeps-at-night

In this awesome challenge we are tasked with slaying a dragon. First we have to use netcat to connect to the given IP and port. This prompts us with a text-based game.

the-dragon-sleeps-at-night-2

Every action makes 6 hours pass and at 00:00 a day passes as well. The store sells 5 different levels of swords, from a level 1 sword with 10 damage for 10$ to a level 5 sword with 100.000 damage for $1.000.000.000. Going to work allows you to tell the boss how many hours you’ve worked, but with a maximum of 3 digits and at $1/hour that’s just $999. Going to the dragon’s cave will result in you trying to slay the dragon with your current sword. Going home allows you to sleep for as many days as you want. In the storage you can store a sword, but it will degrade one level every day.

Obviously, even if we scam the boss for $999 every time, it would take a long time to reach the amount of money needed for the level 5 sword. One way to scam the boss for a lot of money is using ‘9e9’, which is 9 billion but still 3 digits. After having bought the level 5 sword and going to the dragon cave, we realize that even this sword is not strong enough and it’s game over. We need a level 6 sword, but that’s not sold at the store.

If we store a level 1 sword in the storage, it will degrade to level 0 if we sleep at home for 1 day. But if we sleep for -1 days, it will ‘degrade’ to level 2. Using this method, we can create a level 6 sword. If we use this sword to enter the dragon’s cave, we successfully slay the dragon and obtain the flag.

Flag: HackTM{g3t_m0re_sl33p_and_dr1nk_m0re_water}


CHIP 8 /1

chip-8-1

Following the link shows a CHIP 8 emulator.

chip-8-1-2 chip-8-1-3

The instruction set of this machine can be found here. As said in the challenge description, the goal is to access the protected first 512 bits of the memory using only CHIP 8 instructions.

I read all instructions multiple times and just tried different things until I could read the protected memory. Using 1 000 to set the program counter (PC) to 0x000 is not allowed, we can only set it to a value greater than 0x200 (512). Using A 000 to set register I to 0x000 is not allowed either, so we cannot use F 0 65 which fills the registers with the data at I.

But another instruction that sets I is F 0 29 which will set I to the address of the sprite that represents the value in V0. These sprites are stored at the start of the memory and are 5 bytes each. A white pixel is a 1 bit and a black pixel is a 0 bit. 6 0 5 stores 0x5 in V0 and then F 0 29 sets I to 0x5 * 0x5 which is 0x19. The instruction D 1 1 5 would then draw the sprite located at I to (V1, V1) which is (0, 0) and with a height of 5. This will output a 5 on the screen. This instruction to set I and this drawing instruction do not check bounds.

The flag is probably stored in the memory after the sprites. So let’s set V0 to 0x10 with 6 0 10. Now F 0 29 will set I to 0x50 and D 1 1 F will then draw 15 bytes starting from 0x50. This doesn’t draw any sprites, but does draw some of the flag data in bits.

6 0 10
F 0 29
D 1 2 F
6 0 13
F 0 29
6 1 8
6 2 4
D 1 2 F

The instructions I used to draw the entire flag

chip-8-1-4

Now all that’s left is to translate the pixels to binary, 1 row of 8 pixels per byte, and then from binary to ASCII to get the flag.

Flag: HackTM{a55em8led_s0cks}


CHIP 8 /2

chip-8-2

Read part 1 of the CHIP 8 challenge first to get a better understanding.

In this challenge we have to find a way to read the last 512 bits of memory. Again, I just tried different way of settings the I register or PC to a protected memory location. I couldn’t set I to these addresses, but I was able to set the PC to a protected location using the jump instruction 1 E00. 0xE00 to 0xFFF is protected memory, but we can jump to it and just try to execute whatever is there.

Setting the PC to 0xE00 will execute a lot of A AAA instructions, which just sets I to 0xAAA. This is because the protected memory starts with a lot of 0xAA values. Nonetheless, at address 0xF40 it starts to get interesting. Seemingly random instructions and invalid instructions are found from there on. This must be the flag data. Setting the PC to 0xF40 with 1 F40 and stepping through the instructions shows in the last instruction box that it executed AA48. And 0x48 is equal to ‘H’, which is the first letter of the flag format. Stepping through the instructions and writing down the value of every last instruction will slowly reveal the flag. If the program crashes because of an invalid instruction, you just write it down and set the PC to after this instruction. Now we can obtain the flag by converting the hexadecimal values we found to ASCII.

Flag: HackTM{jud6e_jury_and_3x3cut1on}