ReMeeting the Wheel — HackTheBox

Description

While Alice was daydreaming, she thought of using RSA to transfer an AES key for faster encryption, what an innovative idea! However, Bob warned her that if she made a mistake, Eve could potentially split the AES key into two equal-sized pieces. Would it cause any trouble?

Hybrid RSA+AES encryption. RSA (1024-bit, e=65537) encrypts AES key k = key1 * key2 where each factor is ~20 bits. AES-ECB encrypts the flag with KEY = sha256(str(k)).

Analysis

AES key k is a product of two small numbers in [2^20, 2^21). Textbook RSA is multiplicatively homomorphic: E(key1 * key2) = E(key1) * E(key2) mod N. This enables a meet-in-the-middle attack splitting the 2^42 search space into two 2^21 passes.

Solution

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from hashlib import sha256

N = 72741423208033405403492275698762968936514657314823442485453559870105200118330405900858299998747406127848670334407387228444029070060538220448699667905891284937839901536444798774307744865631349770845980738192442639071823803272283670943732769371979418893953521892212745135191661138195973757608889180051128601323
e = 65537

enc_aes_key_hex = "4da0230d2b8b46e3a7065f32c46df019739cc002a208cc37767a82c3e94edfc3440fa4b24a32274e35d5ddceaa33505c4f2a57281c3a5d6d4db3a0dbdbb30dbf373241319ce4a7fdd1780b6bafc86e37d283c9f9787c567434e2fc29c988fb05fd411fe4453ea40eb45fc41a423839b485e238dd2530fba284e9b07a0bba6546"
enc_secret_hex = "ce8f36aa844ab00319bcd4f86460a10d77492c060b2c2a91615f4cd1f2d0702e76b68f1ec0f11d15704ba52c5dacc60018d5ed87368464acd030ce6230efdbff7b18cba72ccaa9455a6fe6021b908dd1"

c = int(enc_aes_key_hex, 16)
enc_secret = bytes.fromhex(enc_secret_hex)

# Step 1: Build lookup table key2^e mod N -> key2
lookup = {}
for key2 in range(1 << 20, 1 << 21):
    lookup[pow(key2, e, N)] = key2

# Step 2: For each key1, check c * inv(key1^e) mod N in lookup
for key1 in range(1 << 20, 1 << 21):
    target = (c * pow(pow(key1, e, N), -1, N)) % N
    if target in lookup:
        k = key1 * lookup[target]
        KEY = sha256(str(k).encode()).digest()
        flag = unpad(AES.new(KEY, AES.MODE_ECB).decrypt(enc_secret), 16)
        print(f"FLAG: {flag.decode()}")
        break