Overview

This is a writeup for the Encryptomatic challenge from the United States Cyber Games Season IV Open. In this challenge, I was tasked with breaking an encryption scheme that uses AES-ECB, a block cipher mode known for its simplicity but also for its vulnerabilities when not used properly. The challenge gives us a ciphertext generated by appending a secret flag to user-supplied input and encrypting it. By analyzing how the encrypted output changes as we modify our input, we can apply a well-known cryptographic attack technique: the Padding Oracle Attack. This attack allows us to recover the hidden flag byte by byte, exploiting the deterministic nature of AES-ECB encryption.

Challenge

Description

Our new Encryptomatic tool makes securing your messages a snap!
nc 0.cloud.chals.io 28962
Author: tsuto

Attached File

 1from Crypto.Cipher import AES
 2from Crypto.Util.Padding import pad
 3import os
 4
 5# Random Key
 6key = os.urandom(16)
 7flag = os.getenv("FLAG","SIVUSCG{t3st_fl4g}")
 8
 9cipher = AES.new(key, AES.MODE_ECB)
10
11print("****************************************")
12print("   Welcome to the USCG Encryptomatic!   ")
13print("  Please enter your message to encrypt  ")
14print("and I will add my flag for safe-keeping.")
15print("****************************************")
16
17while True:
18    try:
19        msg = input("> ")
20        msg += flag
21
22        ciphertext = cipher.encrypt(pad(msg.encode(),16))
23        print("Encrypted: "+ciphertext.hex())
24    except EOFError:
25        pass

Initial Impressions

As I reviewed the source code for the challenge, a few specific lines immediately jumped out as vulnerabilities that hinted at a padding oracle attack..

1. AES-ECB Mode:

   1cipher = AES.new(key, AES.MODE_ECB)

   Using AES-ECB mode is inherently insecure. In ECB mode, identical blocks of plaintext are encrypted to identical blocks of ciphertext, which makes patterns easily recognizable and susceptible to cryptographic attacks. ECB doesn’t randomize the encryption process, meaning that if the input is structured in a predictable way (as it is in this challenge, where the user’s input is followed by the flag), you can manipulate the input to reveal the secret.

2. Appending User Input to the Secret:

   1msg += flag

   This line is crucial because it appends the secret flag to the user-controlled input before encrypting the entire message. This setup is ideal for a byte-by-byte decryption attack—you can carefully craft your input, aligning it block-by-block with the secret flag, and by observing changes in the ciphertext, you can leak information about the flag one byte at a time.

3. Padding the Message:

   1ciphertext = cipher.encrypt(pad(msg.encode(), 16))

   The use of PKCS7 padding here is another critical factor. Since AES operates on fixed-size blocks (16 bytes in this case), padding is used to fill out the final block. If we can control the input size such that the padding shifts, we can observe how the encryption behaves when padding is added or removed, allowing us to leak information about the flag.

Developing an Exploit

With these observations, I saw a clear path to exploiting this challenge:

• Block Manipulation: Because the flag is appended to my input, I realized I could manipulate the number of characters I send to control the alignment of my input and the secret flag. By sending a string of a specific length, I could position the flag in such a way that only one new byte of the flag enters the final block with each iteration.
• Oracle Behavior: I suspected that by comparing ciphertext blocks, I could infer which byte of the flag is being encrypted and extract it one character at a time. pwn.college has a near-identical proof of concept exploit in one of the challenges in the “Cryptography” module of their Intro to Cybersecurity dojo. The code I created for that module laid the groundwork for my exploit here, as the principles and approach were nearly the same.

What is an Oracle Attack?

An Oracle Attack is a type of cryptographic attack where an attacker exploits the ability to query a system (the “oracle”) and gain useful information about the encryption or decryption process. In this scenario, the oracle responds in a way that allows the attacker to make educated guesses about secret data, often revealing sensitive information byte-by-byte. Oracle attacks are often considered a form of side-channel attack—attacks that don’t directly compromise the cryptographic algorithm itself but rather exploit weaknesses in how it’s implemented or how it interacts with the external environment.

Side-channel attacks can take many forms, such as measuring the time it takes to encrypt or decrypt data, observing power consumption during cryptographic operations, or analyzing error messages returned by the system. In the case of an oracle attack, the side channel is the feedback given by the encryption system—either in the form of altered ciphertext or changes in output when certain inputs are made. By using these subtle clues, attackers can break even secure encryption schemes like AES-ECB, as demonstrated in this challenge.

Conditions Required to Perform an Oracle Attack on AES

To successfully carry out an Oracle Attack against AES (specifically AES-ECB in this case), the following conditions are typically necessary:

1. Access to an Encryption Oracle: The attacker must be able to submit input to the encryption system and receive the corresponding encrypted output.

2. Known Prefix Structure: The attacker should have control over the input that is prepended to the secret message (or flag). In our case, we can send arbitrary data before the flag, which allows us to align blocks for byte-by-byte decryption.

3. Block-based Cipher (like AES): The encryption algorithm should use fixed-size blocks (AES uses 16-byte blocks) to make the byte-alignment strategy work.

4. Fixed Padding Scheme: If padding (such as PKCS7) is used, it must be predictable. Knowing the padding scheme helps in guessing how many bytes remain to be decrypted.

5. No Input Validation Errors: If the encryption system does not raise errors when it receives unusual input, it gives us more flexibility to try different attack strategies.

In the following sections, we will walk through the solution to breaking AES-ECB encryption using a byte-by-byte Oracle Attack.

How an Oracle Attack Can Break Stream Ciphers and AES

Stream Ciphers

Oracle attacks can also be used against stream ciphers under specific conditions, typically when there is a predictable initialization vector (IV) or key-stream reuse. If the attacker can get access to multiple ciphertexts encrypted with the same key stream, it becomes easier to extract the original plaintext. For example, if the same keystream is applied to different messages, attackers can use XOR operations to manipulate or deduce portions of the plaintext.

AES-ECB

In our scenario, we are dealing with AES-ECB mode (Electronic Codebook mode), where each block of plaintext is encrypted independently using the same key. This mode is vulnerable to Oracle Attacks because identical plaintext blocks will produce identical ciphertext blocks. This pattern can be exploited to reconstruct the secret plaintext by modifying the input in a controlled manner and observing how the output changes.

Challenge Breakdown: AES-ECB Encryption with a Hidden Flag

In this challenge, we are dealing with a service that appends a secret flag to any user input, encrypts the combined message using AES-ECB, and returns the ciphertext in hexadecimal form. Our goal is to extract the flag without knowing it.

Step 1: Understanding the Block Structure

The first thing we need to do is figure out how many blocks the ciphertext contains, which corresponds to the length of the secret flag. We can do this by sending an empty input and examining the length of the returned ciphertext.

1nc 0.cloud.chals.io port 28962
2****************************************
3   Welcome to the USCG Encryptomatic!
4  Please enter your message to encrypt
5and I will add my flag for safe-keeping.
6****************************************
7>
8Encrypted: 237d6657bbab12acc57a1d9edd0d9c31f8f04fd2a800730f61ad786958807117

By dividing the length of the ciphertext by the block size (16 bytes for AES-ECB), we determine the total number of blocks:

1>>> len('237d6657bbab12acc57a1d9edd0d9c31f8f04fd2a800730f61ad786958807117') / 2 / 16
22.0

This indicates that the ciphertext contains 2 blocks, implying that the flag is 32 bytes long. We can now start crafting our input to align with these blocks.

Step 2: Preparing for Byte-by-Byte Extraction

AES-ECB mode treats each block independently. To extract the flag byte-by-byte, we send a series of controlled inputs that align our guesses with the hidden flag. We start by sending a block full of known characters (A’s) and capture the encrypted output.

The key here is that when we send 32 A’s, the encryption system appends the secret flag at the end of our input and pads it using PKCS7 padding. This allows us to control the input and gradually reveal the flag.

Let’s look at the Python code for this step.

 1from pwn import *
 2import string
 3
 4# context.log_level = "DEBUG"
 5
 6chunk_size = 16
 7total_blocks = 2
 8
 9conn = remote("0.cloud.chals.io", 28962)
10
11def fetch_ciphertext():
12    # Fetch ciphertext from the server response
13    response = conn.recvuntil(b"\n")
14    keyword = b"Encrypted: "
15    return response[response.find(keyword) + len(keyword) : response.find(b"\n")]

Here, we set up the connection to the server and define a function fetch_ciphertext() that retrieves the ciphertext from the server’s response. We will use this function to compare ciphertexts as we iterate over possible flag values.

Step 3: Brute Forcing Character by Character

Next, we will send inputs where we reduce the number of A’s by one in each iteration, and then compare the encrypted output to our previous results to determine the next byte of the flag.

 1def execute():
 2    max_secret_length = total_blocks * chunk_size
 3    discovered_secret = b""
 4
 5    for length in range((max_secret_length - 1), -1, -1):
 6        prefix = b"A" * length
 7        conn.recvuntil(b"> ")
 8        conn.sendline(prefix)
 9        reference_blocks = fetch_ciphertext()
10
11        # Attempt to brute force the next character in the flag
12        attempt = b"A" * length + discovered_secret
13        for char in string.printable[:95]:
14            test_input = attempt + char.encode()
15            conn.recvuntil(b"> ")
16            conn.sendline(test_input)
17            trial_blocks = fetch_ciphertext()
18
19            # Check if the blocks match
20            if reference_blocks[: max_secret_length * 2] == trial_blocks[: max_secret_length * 2]:
21                discovered_secret += char.encode()
22                log.info("Discovered so far: {}".format(discovered_secret.decode()))
23                break
24
25        # Stop once we've discovered the full flag
26        if len(discovered_secret) + length <= max_secret_length - 1:
27            log.success("Flag: {}".format(discovered_secret.decode()))
28            return

In this section, the script sends a varying number of A’s (by reducing the length of the prefix) and brute forces the next character by comparing the output ciphertext with a reference block. We repeat this process until the entire flag is recovered.

Step 4: Putting It All Together

Once all the individual components have been explained, we combine them into a complete solution. After brute-forcing the flag byte-by-byte, the script finally outputs the flag:

1if __name__ == "__main__":
2    execute()

Final Script

 1from pwn import *
 2import string
 3
 4# context.log_level = "DEBUG"
 5
 6chunk_size = 16
 7total_blocks = 2
 8
 9conn = remote("0.cloud.chals.io", 28962)
10
11
12def fetch_ciphertext():
13    response = conn.recvuntil(b"\n")
14    keyword = b"Encrypted: "
15    return response[response.find(keyword) + len(keyword) : response.find(b"\n")]
16
17
18def execute():
19    max_secret_length = total_blocks * chunk_size
20    discovered_secret = b""
21
22    for length in range((max_secret_length - 1), -1, -1):
23        prefix = b"A" * length
24        conn.recvuntil(b"> ")
25        conn.sendline(prefix)
26        reference_blocks = fetch_ciphertext()
27
28        attempt = b"A" * length + discovered_secret
29        for char in string.printable[:95]:
30            test_input = attempt + char.encode()
31            conn.recvuntil(b"> ")
32            conn.sendline(test_input)
33            trial_blocks = fetch_ciphertext()
34            if (
35                reference_blocks[: max_secret_length * 2]
36                == trial_blocks[: max_secret_length * 2]
37            ):
38                discovered_secret += char.encode()
39                log.info("{}".format(discovered_secret.decode()))
40                break
41
42        if len(discovered_secret) + length <= max_secret_length - 1:
43            log.success("Flag: {}".format(discovered_secret.decode()))
44            return
45
46
47if __name__ == "__main__":
48    execute()

Output

We successfully extract the hidden flag after ~2 minutes of brute forcing:

Flag: SIVUSCG{3CB_sl1d3_t0_th3_l3ft}

<EOF>

This exploit highlights the importance of using secure encryption modes and protecting systems from side-channel attacks such as padding oracles. If you’re still unclear about how this attack works, I highly recommend watching this video, which gives an in-depth explanation of padding oracle attacks. However, bear in mind that a solid understanding of asymmetric encryption is necessary to fully grasp the video’s concepts.