0xkasper

## Introduction

The Cybersecurity Challenge Belgium (CSCBE) is a CTF for students at Belgian universities. Although I'm not Belgian, I do study in Belgium, so I was able to participate. I did not have a team and played by myself, so I couldn't score as many points and unfortunately did not qualify for the finals in Brussels. Nonetheless, there was one interesting challenge of which I want to share my solution with you.

---
## Cryptography

---
### A Pirate's Life For Me

For this challenge we were given a [challenge.py](/static/files/cscbe-2020-qualifiers-write-up/challenge.py) and a valid hash. Our task was to forge a signature for this specific hash, such that the server could verify it and give us the flag. The signature is supposed to be generated from a few specific bytes and the ASN.1 byte sequence as header, followed by the hash and then encrypted with RSA.

RSA is public-key cryptography, which means that someone can generated a new public and private key pair and where something encrypted with this public key can only be decrypted with its paired private key. It's practically impossible to calculate the private key from the public key, which makes it secure. The person who generated the keys has to keep the private key secret (hence the name private key) and distribute the public key. Now people can encrypt something using the public key and safely send it to the person with the private key. With digital signatures it's the other way around. To verify that something, e.g. a message, is originated from me, I have to encrypt it with my private key and append that ciphertext to the message. This ciphertext is my signature, since anyone can decrypt with my freely available public key, resulting in the message and thus people can confirm that I signed it.

Now, for this challenge we are given the modulus and the public key. As you can see in `challenge.py`, this public key exponent is only 3. An exponent of 3 works, but it's not always secure. As I explained, we have to generate the signature for the given hash. But to generate the signature we need to encrypt the hash with the private key, since the server will use the public key to decrypt it. However, since the public key is only 3, we might be able to first construct a signature that adheres to the server's requirements and then send the cube root of this number. This won't give us a perfect signature, but because of a mistake in the signature verification function in the server, this doesn't matter.

To verify the signature, the server first decrypts the given signature using the public key exponent (which is just taking a power of 3). It then checks if the result is 256 bytes and if the first two bytes are equal to 0x00 and 0x01. After that it looks for the next 0x00 byte and checks if all bytes before this zero byte are equal to 0xFF. Now, normally the number of 0xFF bytes matters, but this server doesn't actually check the length, it just looks for the 0x00 byte. We can therefore just send one (or even zero) 0xFF byte. After that, it checks if the ASN.1 byte sequence is present and finally the actual hash.

So two bytes (0x00 and 0x01), one 0xFF byte, one 0x00 byte, the given ASN.1 sequence of 15 bytes and the hash of 20 bytes gives us a signature of 39 bytes. So that leaves 217 bytes for garbage because if doesn't check the length of the 0xFF sequence. Now we can use a cube root, because we don't care if some of the garbage bytes won't be preserved.

```python
from gmpy2 import mpz, iroot
from base64 import b64encode, b64decode

def cube_root(n):
    return int(iroot(mpz(n), 3)[0])

H = bytes.fromhex('3F34564B0A1FB3AFE3676911FF990B3127BEC0C2')
ASN = b'0!0\t\x06\x05+\x0e\x03\x02\x1a\x05\x00\x04\x14'
MODULUS = 0xE4D114A8D6BDA750718DC4865391DEAF71CDA4624DC92FC720B7C27A1E254F1F73F86888FFB37816ABB2BEDF98DFD35EDB10C40A05C7BE6D881E4C3F1C881E71026B5386E60A76AD5273B446D79901E5557BF1850C726EAEABCF7212F0C6173A61B8C1EF197DA2ACFA3A083FAA7F6246948E263F8F8CEA77562AC990090BB8F80C891ED8732AEE829D4850D8BE54C40F6051FDE7F6A8BA1A0E598EE67582E9FCD998480C23B7B987B830D94B6D054FC98DBD5E77620742524A876FBC7F189987600ABB7BE222C6700AFAE8E6DA3FB442BB772D5ECE4356C552293C2C102A14A2B59434941453E54E1D2F0E677E6E05F2CFA6BDEF8F794DED7F6477CD014C7A8D
EXPONENT = 3

prefix = b'\x00\x01\xff\x00' + ASN + H
garbage = (256 - len(prefix)) * b'\xfe'
signature = prefix + garbage
cbrt = cube_root(int.from_bytes(signature, 'big'))
decrypted = pow(cbrt, EXPONENT, MODULUS).to_bytes(256, 'big')

print(f'The signature is preserved: {prefix == decrypted[:len(prefix)]}')
print(b64encode(cbrt.to_bytes(256, 'big')).decode())
```

So we first construct the prefix that will pass us through the signature verification on the server. Then we fill it up to 256 bytes with garbage. After that we take the cube root and check if the first 39 bytes of the cube root decrypted with the public key exponent of 3 is equal to the prefix. If so, the server will accept the signature and give us the flag. And guess what, it did.

---
## Comments

---

A short write-up of a challenge of the CSCBE 2020 Qualifiers.

This is a short write-up of one interesting challenge of the CSCBE 2020 Qualifiers. This CTF had quite a lot of challenges, with a great range of difficulties.


CSCBE 2020 Qualifiers Write-Up

A short but detailed write-up of some challenges of the Nullcon HackIM CTF 2020.

This article is a write-up for the challenges of the Nullcon HackIM CTF 2020 that I completed. The amount of challenges I completed is not a lot, so I try to explain everything more in-depth. This CTF was quite hard for me.


Nullcon HackIM CTF 2020 Write-Up

## 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](/articles/rtcp-ctf-2020-write-up). But in the end I did learn a lot.

---
## Cryptography

---
### RSA Is Easy \#1
![rsa-is-easy-1](/static/images/hacktm-ctf-2020-qualifiers-write-up/rsa-is-easy-1.png)

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`.

```python
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.

```python
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](/static/images/hacktm-ctf-2020-qualifiers-write-up/rsa-is-easy-2.png)

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](https://quipqiup.com/) solve it as if it is a substitution cipher.

```python
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](/static/images/hacktm-ctf-2020-qualifiers-write-up/prison-break.png)

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.


```python
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](/static/images/hacktm-ctf-2020-qualifiers-write-up/count-on-me.png)

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](/static/images/hacktm-ctf-2020-qualifiers-write-up/count-on-me-2.png)
> 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.

```python
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](/static/images/hacktm-ctf-2020-qualifiers-write-up/romanian-gibberish.png)

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](/static/images/hacktm-ctf-2020-qualifiers-write-up/the-dragon-sleeps-at-night.png)

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](/static/images/hacktm-ctf-2020-qualifiers-write-up/the-dragon-sleeps-at-night-2.png)

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](/static/images/hacktm-ctf-2020-qualifiers-write-up/chip-8-1.png)

Following the link shows a CHIP 8 emulator.

![chip-8-1-2](/static/images/hacktm-ctf-2020-qualifiers-write-up/chip-8-1-2.png)
![chip-8-1-3](/static/images/hacktm-ctf-2020-qualifiers-write-up/chip-8-1-3.png)

The instruction set of this machine can be found [here](https://github.com/mattmikolay/chip-8/wiki/CHIP%E2%80%908-Instruction-Set). 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.

```python
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](/static/images/hacktm-ctf-2020-qualifiers-write-up/chip-8-1-4.png)

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](/static/images/hacktm-ctf-2020-qualifiers-write-up/chip-8-2.png)

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}

---
## Comments

---

A thorough write-up of the HackTM CTF 2020 challenges I completed.

In this article I explain all the challenges I completed during the HackTM CTF 2020 Qualifiers. This CTF was way harder than the previous one, but I still managed to complete some of the cryptography and all but one of the miscellaneous challenges. The challenges were very interesting and creative.


HackTM CTF 2020 Qualifiers Write-Up

A detailed write-up of challenges of the RiceTeaCatPanda CTF 2020.

A write-up of the challenges I completed during the RiceTeaCatPanda CTF of 2020. It had numerous categories, including cryptography, web, reverse engineering, exploitation, AI and more. There were challenges of various difficulties, ranging from very easy to hard. One of the less serious CTFs out there, but very enjoyable and fun to play.
