23rd Goulash Programming Nights
2025
RestrictedOracle
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.
Crypto
172 points
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 a 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
xor
s it with the flag. This means we can recover the flag by xor
ing 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}
Was this helpful?