# Hard to Implement

***Full disclosure***, I didn't solve **Hard to Implement** during the competition. I only managed to find the solution *a few hours* after it ended. Nevertheless, I think it was a great learning experience, so I decided to write it up anyway.

## Overview
The challenge came with a python script called `cryptor.py`. After examining it, I found out that the main logic was in the `serve` function:

attempts = 1500
...
def serve(req):
    key = get_random_bytes(16)
    while tries < attempts:
    ...
        ct = encrypt(key, req.recv(4096).strip(b'\n'))
        req.sendall(b"Response > " + ct.encode() + b'\n')

These are the notable lines. What `serve` does is *take the client request*, *encrypt the content* and *response with the ciphertext*. `key` is randomly generated each time we connect to the server, but remains the same throughout the session. Each session allows us `1500` attempts.

def encrypt(key,plaintext):
	cipher = AES.new(key, AES.MODE_ECB)
	pt = pad(plaintext + flag.encode(), 16)
	return cipher.encrypt(pt).hex()

As we dive into `encrypt`, we can see that it:
- Uses *AES* in *ECB mode* as its cipher
- Appends flag content to the user input
- Pads plaintext into blocks of 16 bytes
- Encrypts and returns the ciphertext as hex.

Since we can vary the length of our inputs, thereby change the length of the plaintext, we can gather information about the length of the flag.

Let's say our flag is `pctf{test}`, which is 10 characters long. Here's how `pt` would look for different input lengths:

Length of input: 0
b'pctf{test}\x06\x06\x06\x06\x06\0x6'

Length of input: 3
b'000pctf{test}\x03\x03\x03'

Length of input: 5
b'00000pctf{test}\x01'

Suprisingly, if the input's length is 6, we won't get `b'000000pctf{test}'`. Instead, we get:

Length of input: 6
b'000000pctf{test}\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'

That means even if our plaintext can be divided perfectly into 16-bytes block, `pad` still appends another block full of `\x10` bytes.

## Padding Exploration
My first thought was to recover the length of our input until `pt` reached the second block:

$ nc chal.competitivecyber.club 6001
Thank you for using our secure communications channel.
This channel uses top-shelf military-grade encryption.
If you are not the intended recepient, you can't read our secret.
(0/1500) Send challenge > 0
Response > ac6eefe77724860c0740be6b6b1ea80f

(1/1500) Send challenge > 00
Response > 19c5c284a43725702cac9d6f8dccb70e

(2/1500) Send challenge > 000
Response > bbd0a57d87d3ea614b4cd4b74aee5f2bac158d887d81d49f5c9d89c8ee9a2909

After three attempts, the second block's ciphertext appeared, so we could deduce that the flag is **13-character long**. That means it should look something like `pctf{xxxxxxx}`.

## The Solution
You know that moment in a story where, after much struggle, the character steps back and reflect, only to realize the answer was in front of them all along.

We start by inputting 10 characters:

(0/1500) Send challenge > 0000000000

# pt = b'0000000000pctf{xxxxxxx}\x09\x09\x09\x09\x09\x09\x09\x09\x09'

# First block: b'0000000000pctf{x'
# Second block: b'xxxxxx}\x09\x09\x09\x09\x09\x09\x09\x09\x09'

Response > 6e209b54e1660f60caa714bb32819d905dc77a9442076eeb33dde311b5d0bd79

We save the first 32 hex digits of the response. After some tinkering, we find out that `a` is a match!

(1/1500) Send challenge > 0000000000pctf{0
Response > edab14795dde5c9ad59dbbede0daad367e053fbada6a66b5766b69d49cda1ea9

(2/1500) Send challenge > 0000000000pctf{1
Response > 6f8092c353cdbf8ec2d4d837bcab1dba7e053fbada6a66b5766b69d49cda1ea9

...
(11/1500) Send challenge > 0000000000pctf{a
Response > 6e209b54e1660f60caa714bb32819d907e053fbada6a66b5766b69d49cda1ea9

We will brute-force a total of **7 characters**, skipping `pctf{` and the final `}`.

Here's the solve script:

from pwn import *
from string import printable

# Constants
BLOCK_LEN_IN_BYTES = 16
BLOCK_LEN_IN_HEX = BLOCK_LEN_IN_BYTES * 2

# Helper functions
def get_response(string_data):
    conn.recv()
    conn.sendline(string_data.encode())
    conn.recvuntil('Response >')
    response = conn.recvline().strip()
    return response

def get_first_block(bytes_data: bytes):
    return bytes_data[0:BLOCK_LEN_IN_HEX]

# Connect to server
conn = remote('chal.competitivecyber.club', 6001)

# Recover characters
recovered = 'pctf{'
for input_len in range(10, 3, -1):
    flag_enc = get_first_block(get_response('0' * input_len))
    
    # Brute-force
    for c in printable:
        enc = get_first_block(get_response('0' * input_len + recovered + c))
        if enc == flag_enc:
            recovered += c
            print('Progress:', recovered)
            break

print('FLAG:', recovered + '}')

After a while, we get our flag, `pctf{ab8zf58}`. It was a long journey, but we got there in the end.

## Afternote: Failed attempt, ECB and new line
:::warning
***WARNING:** Ramblings ahead.*
:::

As I've mentioned, `encrypt` uses **ECB mode**. If you don't know what ECB mode is yet, to simply put, it encrypts each block ***independently of the one before it***. This is different from, say, CBC mode, where the encryption result of one block affects the next one.

With `pad` and `+ flag.encode()` stripped away, this is what `cipher.encrypt(plaintext).hex()` returns:

> 0000000000000000
fa97a7f64baa043d5bea49df83e17e70
> 11111111111111110000000000000000
84c94d3d1c58e042a8c26252ae6ae939fa97a7f64baa043d5bea49df83e17e70
> 22222222222222220000000000000000 
0c7de362a7c5593d6d88170eab510330fa97a7f64baa043d5bea49df83e17e70

Notice how `0000000000000000` always yields the same result `fa97a7f64baa043d5bea49df83e17e70`, as long as it aligns with a 16-byte block?

That being said, what does any of this have to do with our challenge?

I came up with a brilliant scheme! How about we recover the ciphertext of the second block (padding and all) and recreate it in the first block to brute-force? Genius!

My plan was as follows. First I inputted five `0`s:

(0/1500) Send challenge > 00000

# pt = b'0000000pctf{xxxxxxx}\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e'

# First block: b'0000000pctf{xxxxxx'
# Second block: b'x}\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e'

Response > 9bb84f7ac880ecf3e87984f31ae0515283811ae8582f132240d6387619bc99dc

I saved the second block of the response, which is the last 32 hex digits. To find the unknown character, I started sending different characters plus the same suffix:

(1/1500) Send challenge > 0} (invisible b'\x0e's)
Response > 99cbe6b01f0af2e807ccc3c17fcedf849f6602948f7ed14dc8e903a10689b3ee

(2/1500) Send challenge > 1} (invisible b'\x0e's)
Response > 1a3aa222c141613272486972ae2082499f6602948f7ed14dc8e903a10689b3ee

...

I stopped when I found a match, which for the last character was `8`:

(9/1500) Send challenge > 8} (invisible b'\x0e's)
Response > 83811ae8582f132240d6387619bc99dc9f6602948f7ed14dc8e903a10689b3ee

The plan worked! I started getting results, but after recovering four characters, I suddenly stopped getting new matches. All I got was a sad piece of incomplete flag, `zf58}`.

As it turns out, `\0xa` is the new line character `\n`. That screwed the plan up big time since I couldn't send the full input.

I tried skipping over it and made up by brute-forcing two characters at a time instead. But O(n^2) is too many n's for me, so I scrapped the idea.