Castors CTF is a jeopardy style capture the flag competition that was held last weekend. It started on Friday 29th May 2020 and ended on Sunday 31st May 2020.

I found the Bagel Bytes challenge in the cryptography category very interesting, so I decided to make this post as a writeup of how I managed to solve it.

Challenge: Bagel Bytes
Category: Cryptography

Bagel Bytes Challenge

Analysis

We are given a netcat command to connect to the server hosting the challenge. Executing the command yields the following :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
$ nc chals20.cybercastors.com 14420

 ______  ______  ______  ______  __           ______  __  __  ______ ______  ______    
/\  == \/\  __ \/\  ___\/\  ___\/\ \         /\  == \/\ \_\ \/\__  _/\  ___\/\  ___\   
\ \  __<\ \  __ \ \ \__ \ \  __\\ \ \____    \ \  __<\ \____ \/_/\ \\ \  __\\ \___  \  
 \ \_____\ \_\ \_\ \_____\ \_____\ \_____\    \ \_____\/\_____\ \ \_\\ \_____\/\_____\ 
  \/_____/\/_/\/_/\/_____/\/_____/\/_____/     \/_____/\/_____/  \/_/ \/_____/\/_____/ 
                                                                                       
Welcome to Bagel Bytes!
Our ovens are known for baking ExtraCrispyBagels!
We bake 16 bagels per rack and the last rack is always full!
Today's special is flag bagels!

Select:
    1) Bake your own bagels!
    2) Bake the flag!
Your choice: 1
Add your bagels:
> test

Thank you for baking with us! Here are your baked bytes:
3fd9c2c89afd741438ed587345551d03

Select:
    1) Bake your own bagels!
    2) Bake the flag!
Your choice: 2
Add your bagels:
> 

Thank you for baking with us! Here are your baked bytes:
27f52db3a63a15a5bfe82640c24d3e4252f48b901f1ce735ab007f4b7b105ef1b8a42ba9f97bbdbfbb2f6bd4251bff22

The server gives us two options : we can either bake our own bagel or the flag. In both options, the server asks for an input, and gives an output of what appears to be a hexadecimal string.

The challenge also provides us with the python script of the running server :

server.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
from Crypto.Cipher import AES
import socketserver
from secret import FLAG, KEY

BANNER = b"""
 ______  ______  ______  ______  __           ______  __  __  ______ ______  ______    
/\  == \/\  __ \/\  ___\/\  ___\/\ \         /\  == \/\ \_\ \/\__  _/\  ___\/\  ___\   
\ \  __<\ \  __ \ \ \__ \ \  __\\\ \ \____    \ \  __<\ \____ \/_/\ \\\ \  __\\\ \___  \  
 \ \_____\ \_\ \_\ \_____\ \_____\ \_____\    \ \_____\/\_____\ \ \_\\\ \_____\/\_____\ 
  \/_____/\/_/\/_/\/_____/\/_____/\/_____/     \/_____/\/_____/  \/_/ \/_____/\/_____/ 
                                                                                       """
MESSAGE = b"""
Welcome to Bagel Bytes!
Our ovens are known for baking ExtraCrispyBagels!
We bake 16 bagels per rack and the last rack is always full!
Today's special is flag bagels!
"""

MENU = b"""
Select:
    1) Bake your own bagels!
    2) Bake the flag!
Your choice: """

aes = AES.new(KEY, AES.MODE_ECB)

def pad(s):
    if len(s) % 16 == 0:
        return s
    else:
        pad_b = 16 - len(s) % 16
        return s + bytes([pad_b]) * pad_b

def bake_your_own(s, c):
    return c.encrypt(pad(s))

def bake_flag(s, c):
    return len(s), c.encrypt(pad(s + FLAG))

def challenge(req):
    while True:
        req.sendall(MENU)
        choice = req.recv(1024).strip()
        if choice == b'1':
            req.sendall(b'Add your bagels:\n> ')
            inp = req.recv(1024).strip()
            enc = bake_your_own(inp, aes)
            req.sendall(b"\nThank you for baking with us! Here are your baked bytes:\n" + enc.hex().encode() + b"\n")
        elif choice == b'2':
            req.sendall(b"Add your bagels:\n> ")
            inp = req.recv(1024).strip()
            n, enc = bake_flag(inp, aes)
            req.sendall(b"\nThank you for baking with us! Here are your baked bytes:\n" + enc.hex().encode() + b"\n")
        else:
            req.sendall(b"\nThat's not on the menu!\n")

class TaskHandler(socketserver.BaseRequestHandler):
    def handle(self):
        self.request.sendall(BANNER)
        self.request.sendall(MESSAGE)
        challenge(self.request)

if __name__ == '__main__':
    socketserver.ThreadingTCPServer.allow_reuse_address = True
    server = socketserver.ThreadingTCPServer(('0.0.0.0', 8080), TaskHandler)
    server.serve_forever()

Analysing the provided script shows that the action of baking they are referring to is actually AES encryption.

The script also reveals that the server is using the pycrypto implementation of AES with ECB mode.

The encryption key and the flag are secrets and are not given in the shared script. The padding function reveals that the length of the blocks is indeed 16 bytes or 128 bits.

In option 1, the server takes our plaintext input, adds a padding (AES input length must be a multiple of 16 bytes), encrypts it using the secret key, then give us the hexadecimal representation of the result.

In option 2, the server does the same, but this time around it concatenates the plaintext input and the secret flag before moving forward with the remaining actions.

When we provide an empty string in option 2, we get a ciphertext made of 3 blocks. So we know that the flag is made of 3 blocks, with eventual padding at the end.

To get the flag, we would need to decrypt the ciphertext we get from option 2. But to do that, we would need the secret key (since AES is symmetric, meaning that encryption_key = decryption_key)

Using option 1, we can get as many plaintext/ciphertext pairs as we want. But we also know that AES is resistant to known-plaintext attacks.

So how can we get the flag?

Solution

At this stage, we know that there’s no way to retrieve the secret key needed for decryption.

Well, our goal is not to retrieve the secret key, all we need is the secret flag and we have to recover it without decryption! To do so we are going to exploit the weakness of ECB mode.

In fact, when we provide AES-ECB with the same plaintext, and use the same key, we always get the same ciphertext. Since AES is a block cipher, the same observation applies to each of the 16 bytes blocks.

The trick is to recover the flag one byte at a time, using option 2.

We are going to forge our input payload as follows :

  • Provide the first 15 bytes, for instance 15 times the character A : AAAAAAAAAAAAAAA
  • The first block that will be encrypted will be made of our 15 bytes + the first character of the flag :
    AAAAAAAAAAAAAAA + f
  • Store the first block of the encryption result for later comparison
  • For every printable character c :
    • We provide our 15 bytes + c : AAAAAAAAAAAAAAA + c
    • Get the first block of the encryption result and compare it to the reference block we got earlier
    • If the blocks are the same then we have successfully brute-forced the first character of the flag!

We can now repeat this process for the first 16 characters, and do the same for the next blocks until we recover the full flag.

Here’s a python script I wrote that retrieves the flag using the algorithm explained above.

I’m using the pwntools module to connect to the server and the strings module to brute-force all printable characters.

get_flag.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#!/usr/bin/env python3

from pwn import *
from string import printable

# The block size is 16 bytes represented by 32 hex characters
block_size = 32


def get_blocks(ciphertext):
    '''
    This function takes a hex ciphertext and returns a list of the blocks composing it
    '''
    new = []
    for i in range(0, len(ciphertext), block_size):
        new.append(ciphertext[i:i+block_size])
    return new

host = 'chals20.cybercastors.com'
port = 14420

# Initiate the connection to the server
p = remote(host , port)

# List of retrieved characters
known_data = []

# We know that the flag is made of 3 blocks
for i in range(3):

    # For each block we get the 16 characters of the flag
    while len(known_data) < 16 * (i+1):

        # We forge our payload and send it
        payload = "A" * (15 + (16*i) - len(known_data))
        p.recv()
        p.sendline(b'2')
        p.recv()
        p.sendline(payload.encode())
        result = p.recv().decode("utf-8")
        ciphertext = result.split("\n")[2]
        blocks = get_blocks(ciphertext)

        # We save the reference block for later comparison
        reference_block = blocks[i]

        # Brute-forcing the character
        for c in printable:
            print("Trying string = " + "".join(known_data) + c)
            payload = "A" * (15 + (16*i) - len(known_data)) + ''.join(known_data) + c
            p.recv()
            p.sendline(b'2')
            p.recv()
            p.sendline(payload.encode())
            result = p.recv().decode("utf-8")
            ciphertext = result.split("\n")[2]
            blocks = get_blocks(ciphertext)

            # We compare the blocks
            if blocks[i] == reference_block:
                print('Character retrieved: ' + c)
                known_data.append(c)
                break

print("The flag: " + ''.join(known_data))

# Close the connection to the server
p.close()

Running this script gives the following output :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
$ python3 get_flag.py

. . .

Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY@
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY[
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY\
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY]
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY^
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY_
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY`
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY{
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY|
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY}
Character retrieved: }
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY}0
Character retrieved: 0
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY}00
Character retrieved: 0
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY}000
Character retrieved: 0
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY}0000
Character retrieved: 0
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY}00000
Character retrieved: 0
Trying string = castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY}000000
Character retrieved: 0
The flag: castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY}000000

We successfully retrieved the flag with its padding.

The flag is : castorsCTF{I_L1k3_muh_b4G3l5_3x7r4_cr15pY}