HackMDHKCert23 CTF : Cipher Bridging Service
Description
The challenge is pretty simple. In each connection, the server will initialize an AES-CBC cipher and a RSA cipher. The server will first send us the encrypted secret with the AES-CBC cipher solely, then we got infinite query on the functions \(Enc_{RSA}(Dec_{AES}(c))\), or \(Enc_{AES}(Dec_{RSA}(c))\), finally we need to submit the secret to get the flag.
Getting Started
The server has a fixed AES and RSA cipher in each connection. Here, we define 4 operations:
- \(c = Enc_{RSA}(m)\) - The enryption function using the RSA cipher, notice that we know that \(e=65537\), and \(n\) is 2048-bit, but we don't know \(n\) at this point.
- \(m = Dec_{RSA}(c)\) - The decryption function using the RSA cipher.
- \(iv, c = Enc_{AES}(pad(m))\) - The enryption function using the AES-CBC cipher, notice that it is AES-128 and the \(iv\) generation is not controllable. The pad function is just using the PKCS #7 padding such that \(m\) would be in multiple of 16 bytes.
- \(m = unpad(Dec_{AES}(iv, c))\) - The decryption function using the AES-CBC cipher, notice that the \(iv\) is controllable. The unpad function may raise error if unpadding fails and ends the connection.
First, when we make a connection to the server, we can get \(iv_s, enc_s^{AES} = Enc_{AES}(secret)\) from the server, where \(secret\) is a hex number of 128 bytes (i.e. 128 characters of \(0, 1, ..., 9, a, b, ..., f\)). Then, we got infinite query on the given 2 functions:
- \(c = Enc_{RSA}(Dec_{AES}(iv, c))\) - A function that decrypts in AES-CBC, then encrypts in RSA.
- \(iv, c = Enc_{AES}(Dec_{RSA}(m))\) - A function that decrypts in RSA, then encrypts in AES-CBC.
Here I will demonstrate my solution on the challenge which is totally unintened according to Mystiz (lul.
Idea of the solution
The idea is fairly simple, we notice that the AES chops the message into pieces. In other words, let \(iv, c = Enc_{AES}(b_1 || b_2 || ... || b_n)\), with \(b_i\) having block size of 256 bits, we can get \(c = c_1 || c_2 || ... || c_n\), where \(m_i = Dec_{AES}(c_{i-1}, c_i)\) (thanks to the property of AES-CBC)!
Therefore, the idea is that, if we can shift the message \((b_1 || b_2 || ... || b_n)\) by right for few bits (e.g. 16 bits), then a new block \(c'_{n+1}\) will form when doing AES encryption, with the lowest 16 bits of \(b_n\), which is \(b_n^{lsb_{16}} = Dec_{AES}(c'_n, c'_{n+1})\). Then maybe we can do some bruteforce to the lowest 16 bits since the search space is small, and this repeats for the next 16 bits again, until the whole message is leaked.
Implementing the idea
Now the problem is, how can we shift the \(secret\) to the right? Don't forget about the homomorphic property of RSA! First, we transform the encrypted secret into RSA form, \(enc_s^{RSA} = Enc_{RSA}(Dec_{AES}(iv_s, enc_s^{AES}))\). Then, we calculate \(k_0 \equiv (2^{16} + 1)^e \cdot enc_s^{RSA}\ (\text{mod } n)\) locally (getting \(n\) will be explained later), what will happen when we do \(Enc_{AES}(Dec_{RSA}(k_0))\)?
When \(Dec_{RSA}(k_0)\) is performed, it will be decrypted as \((2^{16} + 1) \cdot secret = 2^{16} \cdot secret + secret\). One can see \((2^{16} \cdot secret)\) is effectively padding \(0\)s to the end of \(secret\), and adding \(secret\) to it implies we have extended the last 16 bits of \(secret\)! Therefore, denote \(iv^0, c^0_1 || c^0_2 || ... || c^0_{n+1} = Enc_{AES}(Dec_{RSA}(k_0))\), then \(Dec_{AES}(c^0_n, c^0_{n+1})\) would be the last 16 bits of \(secret\).
Finally, when we perform \(Enc_{RSA}(Dec_{AES}(c^0_n, c^0_{n+1}))\), we can get \((secret_{lsb_{16}})^e\ (\text{mod } n)\) from the server, since there are only \(2^{16}\) possibility of \(secret_{lsb_{16}}\) (actually fewer since each byte can only be hexidecimal character), we can bruteforce the value of \(secret_{lsb_{16}}\) locally (if we get the value of \(n\)).
Final details
Getting \(n\) is easy actually, think what the server will return if we perform \(Enc_{RSA}(Dec_{AES}(Enc_{AES}(Dec_{RSA}(2^{2048} - 1))))\), it will return \(r_0 = 2^{2048} - 1\ (\text{mod } n)\)! Therefore, we can get \(n = (2^{2048} - 1) - r_0\).
Also as mentioned above, since each byte can only hexidecimal character, we can right shift 32 bits each time since the search space of 4 bytes is just \(16^4 = 65536\), repeat the above algorithm again by shifting right by \(64, 96, ...\), one can leak the whole \(secret\).
Solve script
import signal
import base64
import os
from gmpy2 import is_prime
from Crypto.Cipher import AES as _AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import long_to_bytes, bytes_to_long
import sys
from pwn import *
from tqdm import tqdm
r = remote('chal.hkcert23.pwnable.hk', 28221)
def dec_rsa_enc_aes(m):
r.recvuntil('🤖 ')
r.sendline(f'rsa {long_to_bytes(m).hex()}')
r.recvuntil('🔑 ')
return bytes.fromhex(r.recvuntil(b'\n', drop=True).decode())
def dec_aes_enc_rsa(m):
r.recvuntil('🤖 ')
r.sendline(f'aes {m.hex()}')
r.recvuntil('🔑 ')
return int(r.recvuntil(b'\n', drop=True).decode(), 16)
def main():
r.recvuntil('🔑 ')
c0 = bytes.fromhex(r.recvuntil(b'\n', drop=True).decode())
# Get n
test_d = 2**2048 - 1
mod_d = dec_aes_enc_rsa(dec_rsa_enc_aes(test_d))
n = test_d - mod_d
c0_rsa = dec_aes_enc_rsa(c0)
saved_buffer = b''
for b_idx in range(8):
for ite in range(1, 5):
multi = pow(2**(32*ite + 128 * b_idx) + 1, 0x10001, n)
homo = (multi * c0_rsa) % n
homo_enc_aes = dec_rsa_enc_aes(homo)
blocks = [homo_enc_aes[i*16:(i+1)*16] for i in range(len(homo_enc_aes)//16)]
iv, ct = blocks[-((b_idx * 4 + ite) // 4) - 2], b''.join(blocks[-((b_idx * 4 + ite) // 4) - 1 : ])
plain_enc_rsa = dec_aes_enc_rsa(iv + ct)
for i in tqdm(range(16**4)):
trying = f'{hex(i)[2:]}'.rjust(4, '0').encode() + saved_buffer
trying = bytes_to_long(trying)
try_plain = pow(trying, 0x10001, n)
if try_plain == plain_enc_rsa:
saved_buffer = f'{hex(i)[2:]}'.rjust(4, '0').encode() + saved_buffer
print(saved_buffer)
break
else:
raise Exception("No solution found!")
r.sendline(f'easy {saved_buffer.hex()}')
r.interactive()
