This writeup was originally published on the author’s website and is added here for completeness.

Everbody can exploit oracles. Do you have what it takes to exploit a restricted oracle? If you do you might find a flag between all the German words I placed in there.

Category: crypto

Solver: lapesi, SchizophrenicFish2nds

Flag: GPNCTF{niC3_gUESsInG_PADDing_15_fUN}

Walkthrough

We are provided with an archive containing some source code and a command to spawn an instance:

ncat --ssl restricted-oracle.gpn23.ctf.kitctf.de 443

The source code is a Python script chall.py that uses AES.MODE_CBC to decrypt user inputs. But instead of returning the decrypted data, it returns if the padding is correct or not. This allows us to reverse the internal state of the decryption process and ultimately recovering the plaintext.

When connecting to the server we get two hex strings, the first one will be useful later, the second one is an encrypted text containing random German words. We need to decrypt this text to get the flag later.

The attack we are going to use is explained here in great detail with animations and code.

Essentially, we will use the fact that the server tells us if the padding is correct or not to iteratively guess the plaintext byte by byte. We will start with the last byte and work our way to the first byte. This works because the padding is only valid if the n padding bytes at the end of the plaintext are all equal to n. For example, if there are 3 padding bytes, the last 3 bytes of the plaintext must be 0x03 0x03 0x03.

This lets us recover the internal state of the decryption process, which we can then xor with the initialization vector (IV) to get the plaintext. For a more intuitve understanding, check the animations mentioned above.

Unfortunately, this is not sufficient to decrypt the whole text. The following code limits the number of requests we can make to the server:

while tries < MAX_TRIES:

MAX_TRIES is calculated as:

MAX_TRIES = lambda x: len(x)*40

MAX_TRIES = MAX_TRIES(text)

This means we can only make 40 requests per byte on average. Unfortunately, our attack bruteforces all bytes from 0x00 to 0xff, which is more than 40 requests per byte on average. To circumvent this, we will need to guess more intelligently.

We know that the plaintext is a string of German words, this means that the plaintext bytes are limited to certain characters. We will only guess bytes that would result in valid characters. Let byte b be valid at position i (from right to left) and v be the byte of the IV at position i, then b ^ v ^ i is equal to the plaintext byte at position i. This means b ^ v ^ i must be a valid character. We can use this to limit our guesses to only valid characters with the following code:

letter_order = "enirstadhulcgmobwfkzvpjxyqENIRSTADHULCGMOBWFKZVPJXYQ"
for candidate in [ord(c) ^ pad_val ^ initial_iv[-pad_val] for c in letter_order]:
    ...

The candidates are the bytes we guess for position pad_val. We will then check if the padding is correct for each candidate. If it is, we can use the candidate to recover the plaintext byte at position i.

This limits the number of requests significantly. Additionally, we sorted the candidates by their frequency in the German language, so we will guess the most common characters first.

This does not hold for the last block because it may contain characters that are not in the letter_order string. Because we can bruteforce all other blocks with under 40 requests per byte, we can afford to bruteforce the last block with all 256 possible bytes.

The following code implements the attack:

#!/usr/bin/env python

from pwn import remote
import operator
import string
from Crypto.Cipher import AES
import sys
from hashlib import sha512
import random
import os
import secrets
import string

BLOCK_SIZE = 16
requests = 0

def unpad( s):
    padbit = s[-1]
    padding = s[-padbit:]
    if set(padding) == {padbit}:
        return s[:-s[-1]]
    else:
        return None

def send_command(conn, msg):
    global requests
    conn.recvuntil(b'oracle: ')
    conn.sendline(msg.hex().encode() )
    requests += 1
    response = conn.recvline().strip()
    if "True" in response.decode():
        return True
    elif "False" in response.decode():
        return False
    else:
        print(f"Unexpected response: {response}")



def xor(bytes_a, bytes_b):
    return bytes(map(operator.xor, bytes_a, bytes_b))


def main():
    conn = remote('portcreek-of-outrageous-glory.gpn23.ctf.kitctf.de', 443, ssl=True)
    conn.recvline()
    encrypted_flag_flag= bytes.fromhex(conn.recvline().decode())
    print(f'Encrypted flag flag: {encrypted_flag_flag.hex()}')
    encrypted_flag =  bytes.fromhex(conn.recvline().decode())
    encrypted_flag = encrypted_flag + b"\xff"*BLOCK_SIZE*0
    target_len = len(encrypted_flag)

    def oracle(iv, ct_block):
        return send_command(conn, iv + ct_block)

    plaintext = full_attack(encrypted_flag[:BLOCK_SIZE], encrypted_flag[BLOCK_SIZE:], oracle, target_len=target_len)


    print(f'The decrypted plaintext is: {plaintext}')
    print(f'This script made {requests} requests to the encryption service.')


def all_block_attack(block, oracle):
    """Returns the decryption of the given ciphertext block"""

    # zeroing_iv starts out nulled. each iteration of the main loop will add
    # one byte to it, working from right to left, until it is fully populated,
    # at which point it contains the result of DEC(ct_block)
    zeroing_iv = [0] * BLOCK_SIZE

    for pad_val in range(1, BLOCK_SIZE+1):
        padding_iv = [pad_val ^ b for b in zeroing_iv]

        for candidate in range(256):
            padding_iv[-pad_val] = candidate
            iv = bytes(padding_iv)
            if oracle(iv, block):
                if pad_val == 1:
                    # make sure the padding really is of length 1 by changing
                    # the penultimate block and querying the oracle again
                    padding_iv[-2] ^= 1
                    iv = bytes(padding_iv)
                    if not oracle(iv, block):
                        continue  # false positive; keep searching
                break
        else:
            raise Exception("no valid padding byte found (is the oracle working correctly?)")

        zeroing_iv[-pad_val] = candidate ^ pad_val

        # print(zeroing_iv)

    return zeroing_iv

def single_block_attack(block, oracle, initial_iv):
    """Returns the decryption of the given ciphertext block"""

    # zeroing_iv starts out nulled. each iteration of the main loop will add
    # one byte to it, working from right to left, until it is fully populated,
    # at which point it contains the result of DEC(ct_block)
    zeroing_iv = [0] * BLOCK_SIZE

    for pad_val in range(1, BLOCK_SIZE+1):
        padding_iv = [pad_val ^ b for b in zeroing_iv]

        letter_order = "enirstadhulcgmobwfkzvpjxyqENIRSTADHULCGMOBWFKZVPJXYQ"
        for candidate in [ord(c) ^ pad_val ^ initial_iv[-pad_val] for c in letter_order]:
            padding_iv[-pad_val] = candidate
            iv = bytes(padding_iv)
            if oracle(iv, block):
                if pad_val == 1:
                    # make sure the padding really is of length 1 by changing
                    # the penultimate block and querying the oracle again
                    padding_iv[-2] ^= 1
                    iv = bytes(padding_iv)
                    if not oracle(iv, block):
                        continue  # false positive; keep searching
                break
        else:
            raise Exception("no valid padding byte found (is the oracle working correctly?)")

        zeroing_iv[-pad_val] = candidate ^ pad_val

        # print(zeroing_iv)

    return zeroing_iv


def full_attack(iv, ct, oracle, target_len=0):
    """Given the iv, ciphertext, and a padding oracle, finds and returns the plaintext"""
    assert len(iv) == BLOCK_SIZE and len(ct) % BLOCK_SIZE == 0

    msg = iv + ct
    blocks = [msg[i:i+BLOCK_SIZE] for i in range(0, len(msg), BLOCK_SIZE)]
    result = b''

    # loop over pairs of consecutive blocks performing CBC decryption on them
    first = False
    # loop over pairs of consecutive blocks performing CBC decryption on them
    iv = blocks[0]
    for ct in blocks[1:]:
        if (target_len - len(result)) // 16 <= 2:
            dec = all_block_attack(ct, oracle)
            first = False
        else:
            dec = single_block_attack(ct, oracle, iv)

        pt = bytes(iv_byte ^ dec_byte for iv_byte, dec_byte in zip(iv, dec))


        result += pt

        print(result, (target_len - len(result)) // 16, 'blocks left')
        iv = ct

    return result



if __name__ == '__main__':
    main()

We have now succesfully recovered the text. We can now use it to get the flag. For that let’s look at this code:

print(xor(sha512(text[:-3].encode("utf-8")).digest(),FLAG.encode()).hex())

This code takes the sha512 hash of the decrypted text without the last 3 bytes, and xors it with the flag. This means we can recover the flag by xoring the sha512 hash of the decrypted text without the last 3 bytes with the output of this code. This output is the first hex string we received when connecting to the server.

But we have to also remove 0 to 4 more bytes because of this line:

for i in range(random.randint(0,4)):
    self.chall += chr(ord("A")+(os.urandom(1)[0] % 26)).encode()

So if we use the following output of our script:

The decrypted plaintext is: b'stehendieUnfallverursachervorGerichtMelandrierzieltdenbisherletztenPodestplatzfrBMWinderSuperbikeWMLautVertragsollMilwaukeedasgleicheMaterialwieAltheaerhaltensoeinemAllradleristmanimSchneenatrlichfeinrausbeslissingmoetinverscheidenelandenbekrachtigdwordenindenationaleparlementenPAULKIERASDeshalbfolgendengeistlichenStzendeserstenTeilsauchtraditionelldieklassischenWeihnachtsliederderVorweihnachtszeithindunationalistischeBharatiyaJanataPartyBJPhattedieParlamentswahlimMaimitgroerMehrheitgewonnenEuropaundAmerikaverfgtdieIberdrolaSAberKapazittenvonMegawattLadevolumenzumBeispielwchstaufLiterundkannaufbiszuLitererweitertwerdenLitermehralsfrhersagtederSicherheitsberatervonPrsidentBarackObamaBenRhodesineinemCNNInterviewamMontagabendabsurdumfhrtedasHinundHerdanndieSPFraktionschefMarkusSpthFeuerthalenverlangtespternocheineneuerlicheAbstimmungausProtestdagegendassdieFDPgegendiegutenSittenimRatverstossewieersagteZI\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e

Encrypted flag flag: f91370530cca421b3d477f981848eb8f4f2e16bcf4b2376a13b642f165183dbeccc1756937415b1b96726ea208ceb7e159a3bf4e4eb0bc0a865553ef46665bed

We can use the following code to recover the flag (in this case we remove the last 2 bytes):

from hashlib import sha512

def xor(a:bytes,b:bytes)->bytes:

    ml  = max(len(a),len(b))
    a = a.ljust(ml, b'\x00')
    b = b.ljust(ml, b'\x00')
    return bytes(x ^ y for x, y in zip(a, b))

text = b'stehendieUnfallverursachervorGerichtMelandrierzieltdenbisherletztenPodestplatzfrBMWinderSuperbikeWMLautVertragsollMilwaukeedasgleicheMaterialwieAltheaerhaltensoeinemAllradleristmanimSchneenatrlichfeinrausbeslissingmoetinverscheidenelandenbekrachtigdwordenindenationaleparlementenPAULKIERASDeshalbfolgendengeistlichenStzendeserstenTeilsauchtraditionelldieklassischenWeihnachtsliederderVorweihnachtszeithindunationalistischeBharatiyaJanataPartyBJPhattedieParlamentswahlimMaimitgroerMehrheitgewonnenEuropaundAmerikaverfgtdieIberdrolaSAberKapazittenvonMegawattLadevolumenzumBeispielwchstaufLiterundkannaufbiszuLitererweitertwerdenLitermehralsfrhersagtederSicherheitsberatervonPrsidentBarackObamaBenRhodesineinemCNNInterviewamMontagabendabsurdumfhrtedasHinundHerdanndieSPFraktionschefMarkusSpthFeuerthalenverlangtespternocheineneuerlicheAbstimmungausProtestdagegendassdieFDPgegendiegutenSittenimRatverstossewieersagteZI'
flag = "f91370530cca421b3d477f981848eb8f4f2e16bcf4b2376a13b642f165183dbeccc1756937415b1b96726ea208ceb7e159a3bf4e4eb0bc0a865553ef46665bed"

flag_bytes = bytes.fromhex(flag)
text = text[:-2]
result = xor(sha512(text[:-3]).digest(), flag_bytes)
print(result)

This will give us the flag:

GPNCTF{niC3_gUESsInG_PADDing_15_fUN}