RSA Civilization

Overview

The ZIP contains three sub-problems — Digital Trace, HADES, and Pagar Betis. We only solved HADES, which is enough to obtain the final RSA flag for the series.

HADES ships three main files: hades.py, main.py, and utils.py. It is an AES-like block cipher, but with a crucial modification: there is no S-box (no SubBytes).

from utils import *
import os

class HADES:
    def __init__(self, key1: bytes, key2: bytes):
        self.Nb = 4
        self.Nk = len(key1) // 4
        self.Nr = {16: 10, 24: 12, 32: 14}[len(key1)]
        self.k1 = expand_key(key1, self.Nr)
        self.k2 = expand_key(key2, self.Nr)

    def encrypt_block(self, block: bytes) -> bytes:
        state = bytes2matrix(block)
        state = add_round_key(state, self.k1[0])
        state = matrix_mul(self.k2[0], state)

        for round in range(1, self.Nr):
            state = matrix_mul(self.k2[round], state)
            state = shift_rows(state)
            state = mix_columns(state)
            state = add_round_key(state, self.k1[round])

        state = matrix_mul(self.k2[self.Nr], state)
        state = shift_rows(state)
        state = add_round_key(state, self.k1[self.Nr])
        return matrix2bytes(state)

utils.py contains:

• GF(2⁸) operations — matrix multiplication and inversion over the Galois field.
• Matrix operations — multiplication and Gauss–Jordan inversion.
• AES utilities — ShiftRows, MixColumns, and key expansion, but crucially without SubBytes.

main.py:

• The encrypt function only accepts a 16-byte plaintext with a bit count ≤ 1 (i.e. all-zero, or exactly one bit set).
• The decrypt function returns the flag when its output equals b"Hwelp Pweaseeeee".

Analysis: the cipher is fully linear

Removing SubBytes removes the only non-linear component of AES. Every remaining operation (AddRoundKey = XOR, MixColumns / matrix multiply = GF(2⁸) linear maps, ShiftRows = permutation) is linear over GF(2). That means the whole encryption can be written as an affine transformation:

C = A · P + B

where:

• A = the linear transformation matrix,
• B = the ciphertext of the all-zero plaintext,
• P = the plaintext,
• C = the ciphertext.

Because the encryption oracle only accepts plaintexts with at most one active bit, we can recover the whole affine map bit by bit:

1. Get B by encrypting the all-zero plaintext:

   def get_encrypted(pt):
       r.recvuntil(b">> ")
       r.sendline(b"1")
       r.recvuntil(b"Enter your plaintext: ")
       r.sendline(pt.hex().encode())
       resp = r.recvline().decode()
       ct_hex = resp.split("Encrypted: ")[1].strip()
       return bytes.fromhex(ct_hex)
   
   B = get_encrypted(bytes(16))

2. Get the basis of A by encrypting the 128 plaintexts that each have exactly one active bit, and XOR-ing out B:

   A_basis = []
   for i in range(128):
       pt = bytearray(16)
       byte_idx = i // 8
       bit_idx = i % 8
       pt[byte_idx] = 1 << bit_idx
       ct = get_encrypted(pt)
       A_i = xor_bytes(ct, B)
       A_basis.append(A_i)

3. Build the target ciphertext. Since encryption is linear, the ciphertext of any plaintext is B XOR-ed with the basis vectors of its set bits. We want the plaintext that decrypts to b"Hwelp Pweaseeeee", i.e. we build the ciphertext that corresponds to that target:

   target_pt = b"Hwelp Pweaseeeee"
   target_bits = bytes_to_bits(target_pt)
   
   ct_target = bytearray(B)
   for i, bit in enumerate(target_bits):
       if bit:
           ct_target = xor_bytes(ct_target, A_basis[i])

4. Send the crafted ciphertext to the decrypt option and read the flag.

Solution script

from pwn import *
import os
from Crypto.Util.number import bytes_to_long, long_to_bytes

def bytes_to_bits(data):
    bits = []
    for byte in data:
        for i in range(8):
            bits.append((byte >> i) & 1)
    return bits

def xor_bytes(a, b):
    return bytes([x ^ y for x, y in zip(a, b)])

r = remote("20.198.224.34", 8222)

def get_encrypted(pt):
    r.recvuntil(b">> ")
    r.sendline(b"1")
    r.recvuntil(b"Enter your plaintext: ")
    r.sendline(pt.hex().encode())
    resp = r.recvline().decode()
    ct_hex = resp.split("Encrypted: ")[1].strip()
    return bytes.fromhex(ct_hex)

def send_decrypted(ct):
    r.recvuntil(b">> ")
    r.sendline(b"2")
    r.recvuntil(b"Enter your plaintext: ")
    r.sendline(ct.hex().encode())
    return r.recvline()

# Step 1: Get B
B = get_encrypted(bytes(16))

# Step 2: Get A basis vectors
A_basis = []
for i in range(128):
    pt = bytearray(16)
    byte_idx = i // 8
    bit_idx = i % 8
    pt[byte_idx] = 1 << bit_idx
    ct = get_encrypted(pt)
    A_i = xor_bytes(ct, B)
    A_basis.append(A_i)

# Step 3: Build the target ciphertext
target_pt = b"Hwelp Pweaseeeee"
target_bits = bytes_to_bits(target_pt)

ct_target = bytearray(B)
for i, bit in enumerate(target_bits):
    if bit:
        ct_target = xor_bytes(ct_target, A_basis[i])

# Step 4: Send to decrypt
print(send_decrypted(ct_target))

This yields the HADES flag:

RSA{ye_sbox_is_kinda_important_isnt_it_ye_really_its_very_important_actually_hades_help_me_pwease_pwease_pwease}

Getting the final flag

Finally, we send that RSA{...} flag to the host 20.198.224.34 on port 8333, which rewards us with the challenge's final flag.