Category: Crypto
Difficulty: Medium/Hard
1. Challenge Overview
The challenge provides a network service that accepts hex-encoded ciphertexts. Upon connection, the server presents a large RSA modulus $N$ and an initial encrypted blob. This blob follows a specific structure:
- 4 bytes: Length of the AES ciphertext.
- 16 bytes: Initialization Vector (IV).
- L bytes: AES-CBC encrypted message.
- Remainder: An RSA-encrypted AES key.
The server’s behavior is simple: it tries to decrypt the RSA key, uses it to decrypt the AES message, and checks the PKCS#7 padding. If the padding is incorrect, it explicitly tells you: invalid padding.
chall.py
import os
from Crypto.Cipher import AES
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes
BIT_LENGTH = 1337
class PaddingError(Exception):
pass
def pad(msg : bytes):
padbyte = 16 - (len(msg) % 16)
msg += padbyte.to_bytes(1) * padbyte
return msg
def unpad(msg : bytes):
pad_byte = msg[-1]
if pad_byte == 0 or pad_byte > 16: raise PaddingError
for i in range(1, pad_byte+1):
if msg[-i] != pad_byte: raise PaddingError
return msg[:-pad_byte]
def decrypt(cipher : bytes, privkey, opt = True):
l = bytes_to_long(cipher[:4])
iv = cipher[4:20]
enc_msg = cipher[20:20+l]
enc_key = bytes_to_long(cipher[20+l:])
if opt:
c_p = enc_key % privkey.p
m_p = pow(c_p, privkey.dp, privkey.p)
c_q = enc_key % privkey.q
m_q = pow(c_q, privkey.dq, privkey.q)
h = privkey.invq * (m_p - m_q) % privkey.q
key = (m_q + h*privkey.q) % privkey.n
else:
key = pow(enc_key, privkey.d, privkey.n)
if key > 1<<128:
raise Exception('Error in key decryption')
key = key.to_bytes(16)
if len(enc_msg) % 16 > 0: raise PaddingError
decrypter = AES.new(key, AES.MODE_CBC, iv = iv)
msg_raw = decrypter.decrypt(enc_msg)
return unpad(msg_raw)
def encrypt(message : str, pubkey):
key = bytes(8) + os.urandom(8)
encrypter = AES.new(key, AES.MODE_CBC)
enc_message = encrypter.encrypt(pad(message.encode()))
enc_key = pow(bytes_to_long(key), pubkey.e, pubkey.n)
return len(enc_message).to_bytes(4) + encrypter.iv + enc_message + long_to_bytes(enc_key)
if __name__ == '__main__':
flag = open('flag.txt','r').read().strip()
RSA_key = RSA.generate(BIT_LENGTH)
print(RSA_key.n)
cipher = encrypt(flag, RSA_key)
print(cipher.hex())
while True:
try:
cipher_hex = input('input cipher (hex): ')
if cipher_hex == 'exit': break
cipher = bytes.fromhex(cipher_hex)
message = decrypt(cipher, RSA_key)
if message[:3] == b'ENO':
print('That\'s the right start')
except PaddingError:
print('invalid padding')
except Exception as err:
print('something else went wrong')2. Vulnerability Analysis
The challenge contains two distinct cryptographic layers, but only one is the weak point.
The RSA Layer (The Red Herring)
The code uses a 1337-bit RSA key. A specific check exists after RSA decryption:
if key > 1 << 128:
raise Exception('Error in key decryption')While the challenge name “Factoring Oracle” hints at RSA, the actual vulnerability lies in the server’s response to the AES decryption process. We don’t need to factor $N$ if we can manipulate the AES ciphertext directly.
The AES Layer (The Real Vulnerability)
The server uses AES-CBC and performs PKCS#7 unpadding:
def unpad(msg : bytes):
pad_byte = msg[-1]
if pad_byte == 0 or pad_byte > 16: raise PaddingError
for i in range(1, pad_byte+1):
if msg[-i] != pad_byte: raise PaddingError
return msg[:-pad_byte]If unpad raises a PaddingError, the server replies with “invalid padding”. If the padding is correct (even if the resulting plaintext is gibberish), it proceeds or gives a different error. This is a classic Padding Oracle Attack.
3. Developing the Exploit
Since we have an oracle that tells us if the last bytes of a decrypted block form a valid padding sequence (e.g., 01, 02 02, 03 03 03), we can recover the plaintext byte-by-byte.
The Strategy
- Block Isolation: We take the original RSA-encrypted key and the target ciphertext block ($C_i$).
- IV Manipulation: We create a “dummy” IV ($C’_{i-1}$). By changing the last byte of this IV and sending it to the server, we observe the oracle.
- Byte Recovery: When the server does not return “invalid padding,” we know that: $$P’i[15] \oplus C’{i-1}[15] = \text{0x01}$$ Where $P’_i$ is the intermediate state of the block.
- Chain Reaction: Once one byte is found, we adjust the IV to target the next byte (seeking
02 02padding), eventually recovering the entire 16-byte block.
The Payload Structure
Each probe sent to the server looks like this:
[ 00 00 00 10 ] (Length 16) + [ 16-byte Modified IV ] + [ 16-byte Target Cipher Block ] + [ Original RSA Enc Key ]
4. The Solution Script
The following Python script uses pwntools to automate the byte-flipping and synchronize with the server’s prompts.
from pwn import *
import sys
# Set to 'info' to see connection status
context.log_level = "info"
def solve():
# Connect to the server
io = remote("52.59.124.14", 5104)
# 1. Parse initial data
n_str = io.recvline().strip().decode()
cipher_hex = io.recvline().strip().decode()
cipher = bytes.fromhex(cipher_hex)
# Clear the initial prompt from the buffer
io.recvuntil(b"input cipher (hex): ")
l = int.from_bytes(cipher[:4], "big")
iv = cipher[4:20]
enc_msg = cipher[20 : 20 + l]
enc_key_bytes = cipher[20 + l :]
# Blocks to decrypt (IV + Ciphertext blocks)
blocks = [iv] + [enc_msg[i : i + 16] for i in range(0, len(enc_msg), 16)]
print(f"[+] Message length: {l} bytes ({len(blocks) - 1} blocks)")
print(f"[+] RSA Key extracted ({len(enc_key_bytes)} bytes)")
def is_padding_valid(test_iv, test_block):
# We send: Length 16 | Test IV | Target Block | Original RSA Key
payload = (16).to_bytes(4, "big") + test_iv + test_block + enc_key_bytes
io.sendline(payload.hex().encode())
# Wait for the prompt to ensure the server finished processing
resp = io.recvuntil(b"input cipher (hex): ")
if b"invalid padding" in resp:
return False
return True
plaintext = b""
for b_idx in range(1, len(blocks)):
prev_block = blocks[b_idx - 1]
curr_block = blocks[b_idx]
intermediate = [0] * 16
decoded = [0] * 16
print(f"\n[*] Decrypting Block {b_idx}...")
for byte_idx in range(15, -1, -1):
pad_val = 16 - byte_idx
suffix = bytes([intermediate[k] ^ pad_val for k in range(byte_idx + 1, 16)])
found = False
for val in range(256):
# Progress indicator
if val % 32 == 0:
sys.stdout.write(f"\r Byte {byte_idx:02}: Testing {val}/256...")
sys.stdout.flush()
test_iv = bytes([0] * byte_idx) + bytes([val]) + suffix
if is_padding_valid(test_iv, curr_block):
# Double check for false positives (especially for the first byte)
if pad_val == 1:
test_iv_check = bytes([test_iv[0] ^ 1]) + test_iv[1:]
if not is_padding_valid(test_iv_check, curr_block):
continue
intermediate[byte_idx] = val ^ pad_val
decoded[byte_idx] = intermediate[byte_idx] ^ prev_block[byte_idx]
char = (
chr(decoded[byte_idx])
if 32 <= decoded[byte_idx] <= 126
else "?"
)
sys.stdout.write(
f"\r [+] Byte {byte_idx:02} found: {hex(decoded[byte_idx])} ('{char}')\n"
)
found = True
break
if not found:
print(
f"\n[!] Error: Could not find valid padding for block {b_idx} byte {byte_idx}"
)
return
plaintext += bytes(decoded)
print(f"[*] Recovered so far: {plaintext}")
# Final cleanup (strip PKCS7 padding)
print(f"\n[!] FULL RECOVERED DATA: {plaintext}")
try:
pad_len = plaintext[-1]
print(f"[!] FLAG: {plaintext[:-pad_len].decode()}")
except:
print("[!] Could not decode flag, check for errors.")
if __name__ == "__main__":
solve()5. The Winning *
The “Winning Factor” here was Synchronization. In many oracle challenges, sending payloads too fast causes the server to buffer multiple responses, leading the script to misinterpret a “valid” response for the wrong byte. By using io.recvuntil(b"input cipher (hex): "), we ensured the script waited for the server to “reset” before every single probe.
6. Result
After successfully recovering two blocks of ciphertext:
- Block 1:
ENO{Y4y_a_f4ctor - Block 2:
1ng_0rac13}\x05\x05\x05\x05\x05
[+] Opening connection to 52.59.124.14 on port 5104: Done
[+] Message length: 32 bytes (2 blocks)
[+] RSA Key extracted (167 bytes)
[*] Decrypting Block 1...
[+] Byte 15 found: 0x72 ('r')
[+] Byte 14 found: 0x6f ('o')
[+] Byte 13 found: 0x74 ('t')
[+] Byte 12 found: 0x63 ('c')
[+] Byte 11 found: 0x34 ('4')
[+] Byte 10 found: 0x66 ('f')
[+] Byte 09 found: 0x5f ('_')
[+] Byte 08 found: 0x61 ('a')
[+] Byte 07 found: 0x5f ('_')
[+] Byte 06 found: 0x79 ('y')
[+] Byte 05 found: 0x34 ('4')
[+] Byte 04 found: 0x59 ('Y')
[+] Byte 03 found: 0x7b ('{')
[+] Byte 02 found: 0x4f ('O')
[+] Byte 01 found: 0x4e ('N')
[+] Byte 00 found: 0x45 ('E')
[*] Recovered so far: b'ENO{Y4y_a_f4ctor'
[*] Decrypting Block 2...
[+] Byte 15 found: 0x5 ('?')
[+] Byte 14 found: 0x5 ('?')
[+] Byte 13 found: 0x5 ('?')
[+] Byte 12 found: 0x5 ('?')
[+] Byte 11 found: 0x5 ('?')
[+] Byte 10 found: 0x7d ('}')
[+] Byte 09 found: 0x33 ('3')
[+] Byte 08 found: 0x31 ('1')
[+] Byte 07 found: 0x63 ('c')
[+] Byte 06 found: 0x61 ('a')
[+] Byte 05 found: 0x72 ('r')
[+] Byte 04 found: 0x30 ('0')
[+] Byte 03 found: 0x5f ('_')
[+] Byte 02 found: 0x67 ('g')
[+] Byte 01 found: 0x6e ('n')
[+] Byte 00 found: 0x31 ('1')
[*] Recovered so far: b'ENO{Y4y_a_f4ctor1ng_0rac13}\x05\x05\x05\x05\x05'
[!] FULL RECOVERED DATA: b'ENO{Y4y_a_f4ctor1ng_0rac13}\x05\x05\x05\x05\x05'
[!] FLAG: ENO{Y4y_a_f4ctor1ng_0rac13}
[*] Closed connection to 52.59.124.14 port 5104Flag:
ENO{Y4y_a_f4ctor1ng_0rac13}