HKCERT CTF 2021 Selected Write-ups
Last Friday to Sunday there was the HKCERT CTF competition 2021 held by HKCERT. I am not allowed to join the competition (for obvious reasons). Nonetheless I am able to play around with different challenges. On 16 Nov 2021 (Tue) I held a write-up session for this CTF, so I have prepared two write-ups to share: Long Story Short (Key backup service 1) and Braceless (Key backup service 2).
Long Story Short
Challenge Files:
import os
import random
from Crypto.Cipher import AES
from Crypto.Util.number import isPrime as is_prime
from Crypto.Util.Padding import pad
# 256 bits for random-number generator
N = 0xcdc21452d0d82fbce447a874969ebb70bcc41a2199fbe74a2958d0d280000001
G = 0x5191654c7d85905266b0a88aea88f94172292944674b97630853f919eeb1a070
H = 0x7468657365206e756d6265727320617265206f6620636f757273652073757321
# More challenge-specific parameters
E = 17 # The public modulus
CALLS = 17 # The number of operations allowed
# Generate a 512-bit prime
def generate_prime(seed):
random.seed(seed)
while True:
p = random.getrandbits(512) | (1<<511)
if p % E == 1: continue
if not is_prime(p): continue
return p
# Defines a 1024-bit RSA key
class Key:
def __init__(self, p, q):
self.p = p
self.q = q
self.n = p*q
self.e = E
phi = (p-1) * (q-1)
self.d = pow(self.e, -1, phi)
def encrypt(self, m):
return pow(m, self.e, self.n)
def decrypt(self, c):
return pow(c, self.d, self.n)
# Defines an user
class User:
def __init__(self, master_secret):
self.master_secret = master_secret
self.key = None
def generate_key(self):
id = random.getrandbits(256)
self.key = Key(
generate_prime(self.master_secret + int.to_bytes(pow(G, id, N), 32, 'big')),
generate_prime(self.master_secret + int.to_bytes(pow(H, id, N), 32, 'big'))
)
def send(self, m):
if self.key is None: raise Exception('no key is defined!')
m = int(m, 16)
print(hex(self.key.encrypt(m)))
def get_secret(self):
if self.key is None: raise Exception('no key is defined!')
m = int.from_bytes(self.master_secret, 'big')
print(hex(self.key.encrypt(m)))
def main():
flag = os.environ.get('FLAG', 'hkcert21{***REDACTED***}')
flag = pad(flag.encode(), 16)
master_secret = os.urandom(32)
admin = User(master_secret)
for _ in range(CALLS):
command = input('[cmd] ').split(' ')
try:
if command[0] == 'send':
# Encrypts a hexed message
admin.send(command[1])
elif command[0] == 'pkey':
# Refreshs a new set of key
admin.generate_key()
elif command[0] == 'backup':
# Gets the encrypted master secret
admin.get_secret()
elif command[0] == 'flag':
cipher = AES.new(master_secret, AES.MODE_CBC, b'\0'*16)
encrypted_flag = cipher.encrypt(flag)
print(encrypted_flag.hex())
except Exception as err:
raise err
print('nope')
if __name__ == '__main__':
main()
'''
Side-note: I knew this is _very_ similar to "Calm Down" in HKCERT CTF 2020, but rest assured that this is a different challenge.
https://github.com/samueltangz/ctf-archive-created/blob/master/20201006-hkcert-ctf/calm-down/env/chall.py
'''
The summarize the challenge, we have the flag that is encrypted with an 32-byte AES key master_secret. We can access the master_secret encrypted with a “random” (will get to that in Braceless) 1024-bit RSA key. The RSA key can be updated to another random key, but you do not have access to the public modulus (\(e\)=17). You can also ask the service to encrypt arbitrary integers (and get the result). You can only send 17 queries to the server in a session.
Chinese Remainder Theorem
Theorem: Suppose \(n_1,\cdots,n_k\) is pairwise coprime \((\gcd(n_i,n_j)=1\) \(\forall i \neq j)\), then the system of congruence equations
\[\begin{cases} x\equiv a_1\pmod{n_1}\\ x\equiv a_2\pmod{n_2}\\ \vdots\\ x\equiv a_k\pmod{n_k}\\ \end{cases}\]has a unique solution \(x^{*}\) mod \(n_1n_2\cdots n_k\).
Broadcast Attack
Suppose a plaintext is encrypted \(k\) times, where all the public exponent \(e\) are the same, and \(k\geq e\). i.e. the following holds:
Then by Chinese Remainder Theorem, we get \(x^{*}\) mod \(n_1n_2\cdots n_k\) that satisfies all the equations above. Then \(x^{*}\equiv a_i\pmod{n_i}\) for any \(i\), at the same time \(m^e\equiv a_i\pmod{n_i}\) obviously.
But \(m^e=\underbrace{m\cdot m\cdots m}_{e}\leq \underbrace{m\cdot m\cdots m}_{k} <n_1\cdot n_2\cdots n_k\), so \(x^{*}=m^e\) (without mod), since the solution is unique mod \(n_1\cdots n_k\). So we get \(m=\sqrt[e]{x^{*}}\) just by taking the usual \(e\)-th root of \(x^*\).
Example: 韓信點兵
The setting is like so:
今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？
Let’s translate that to maths:
What is the value of \(x\)?
By Chinese remainder theorem, we know that the solution is \(x\equiv 23\pmod{105}\). If we further assume that \(0\leq x < 105\), then we can immediately deduce that \(x=23\) (without the mod).
If there are no such assumption, then note that any \(x = 23 + 105k\) (\(k\) any integers) would satisfy the equation so you do not have a unique solution.
The Challenge
Here are the following operations that we can do (we can make a total of 17 operations):
- flag: Get the flag encrypted with an AES key master_secret
- pkey: Change the current RSA public key (No default key, and \(e=17\))
- send: Use RSA key to encrypt arbitrary integers
- backup: Use RSA key to encrypt the AES key master_secret
So the goal is to try to obtain the AES key in order to decrypt the flag.
Broadcast Attack ?
So the first idea is maybe to launch an broadcast attack, since \(e=17\) is small. However, we have a lot of obstacles ahead of us.
- We are not given the public modulus (even when changing the key)
- We do not have 17 equations. (We need some for printing the encrypted flag and for some other operations)
Obstacle 1
Note that we can send -1 to encrypt. Since \(e\) is odd (Why?), and \(-1\equiv n-1\pmod{n}\), so encrypting -1 will yield
\[E_k(-1)=(-1)^e\pmod{n}=n-1\]So we can send -1 to obtain thep ublic modulus every time we change keys!
Obstacle 2
We need 1 operation for flag; then 1 for pkey, 1 to send -1 and 1 for backup to obtain 1 ciphertext-modulus pair. Then we can only have 5 ciphertext-modulus pairs (\(3\cdot 5 + 1 = 16\) already)
Broadcast Attack Works Anyway
Now we have the secret key \(m\), which is 32 bytes in length, and the RSA uses a 1024-bit public modulus which will be larger than \(2^{511*2}=2^{1022}\).
This means that for each public modulus \(n_i\), we have that \(m \leq 2^{256}\) so \(m^{17} < 2^{256*17} = 2^{4352} < 2^{5110} = 2^{1022*5} < n^5\). So we really only need 5 ciphertext-modulus pairs (instead of 16)! This is due to the fact that the original assumption of broadcast attack only have that the size of \(m\) is less than \(n\), but our plaintext in this case is much smaller than the modulus, so we do not need as much equations.
The Attack
We use python with pwntools to aid the attack.
from pwn import *
debug = True
E = 17
if debug:
r = process(['python3', 'long_story_short.py'])
else:
server = "chalp.hkcert21.pwnable.hk"
port = 28157
r = remote(server, port)
def get_flag():
r.recvuntil(b'[cmd] ')
r.sendline(b'flag')
return int(r.recvline().decode().strip(),16)
def pkey():
r.recvuntil(b'[cmd] ')
r.sendline(b'pkey')
def send(msg):
r.recvuntil(b'[cmd] ')
r.sendline(b'send ' + msg)
return int(r.recvline().decode().strip(), 16)
def backup():
r.recvuntil(b'[cmd] ')
r.sendline(b'backup')
return int(r.recvline().decode().strip(), 16)
def round():
pkey()
_n = send(b"-1")
enc = backup()
n = _n + 1
return n, enc
enc_flag = get_flag()
N = []
ENC = []
for _ in range(5):
n, enc = round()
N.append(n)
ENC.append(enc)
print(enc_flag)
print("enc =", ENC)
print("N =", N)
This is the extraction of the ciphertext-modulus pair and the encrypted flag.
Then we feed the pairs into sage for the Chinese Remainder Theorem. We just need to take the 17-th root of the result to obtain the AES key.
enc = [...]
N = [...]
sol = CRT_list(enc, N)
secret = sol.nth_root(17)
print(int(secret).to_bytes(32, "big"))
Finally We just decrypt to get the flag.
from Crypto.Cipher import AES
enc = ...
secret = ...
cipher = AES.new(secret, AES.MODE_CBC, b'\0'*16)
dec = cipher.decrypt(enc)
print(dec)
flag: hkcert21{y0u_d0nt_n33d_e_m3ss4g3s_f0r_br0adc4s7_4t7ack_wh3n_m_i5_sm41l}
Braceless
The python file is basically the same as the one in long story short, except we are not the ones who interact with the server. Instead, we are given a transcript.log that stored a session.
13,14c13,14
< E = 65537 # The public modulus
< CALLS = 65537 # The number of operations allowed
---
> E = 17 # The public modulus
> CALLS = 17 # The number of operations allowed
99,100c99,100
< Side-note: I knew this is _very_ similar to "Long Story Short" in HKCERT CTF 2021, but rest assured that this is a different challenge.
< ...:)
---
> Side-note: I knew this is _very_ similar to "Calm Down" in HKCERT CTF 2020, but rest assured that this is a different challenge.
> https://github.com/samueltangz/ctf-archive-created/blob/master/20201006-hkcert-ctf/calm-down/env/chall.py
The session first gets the encrypted flag, then repeatedly do “send 2, send 3 and backup” for 16384 times.
Getting N
First we still do not have the modulus \(N\). However, we have the encryption of 2 and 3. Note that \(\begin{align*} 2^{e} - (2^e\pmod{n}) =& an\\ 3^{e} - (3^e\pmod{n}) =& bn\\ \end{align*}\) For some positive integers \(a\) and \(b\). The left hand side of both equations we already know. To obtain \(n\), we simply take the gcd of the two results, and the result will be \(cn\), where \(c\) is some small integers. We can just perform a trial division to get rid of the small factors.
The code for recovering the modulus and the (RSA) encryption of the master secret:
from math import gcd
e = 65537
N = []
BACKUP = []
e2 = pow(2,e)
e3 = pow(3,e)
with open("transcript.log", "r") as f:
f.readline()
flag = int(f.readline(), 16)
try:
while True:
f.readline()
f.readline()
enc_2 = int(f.readline(),16)
f.readline()
enc_3 = int(f.readline(),16)
f.readline()
backup = f.readline()
g = gcd(e2-enc_2, e3-enc_3)
for i in range(500,1,-1):
if g % i == 0:
g = g // i
N.append(g)
BACKUP.append(int(backup,16))
except Exception as e:
print(e)
with open("var.py", "w") as f:
f.write(f"flag= {flag}\n")
f.write(f"N= {N}\n")
f.write(f"BACKUP= {BACKUP}")
Now we have a bunch of \(N\)’s and encryptions. We can’t really do Chinese remainder theorem here as \(e=65537\) is too large.
Exercise: Copy the analysis for the long story short part to conclude why Chinese remainder theorem is not feasible in this case.
The Anti-Climatic
With so many moduli, what can we do? One thing is to try to check their gcd to find any common factor. If there are any common factors among the moduli, then we can already recover the private exponent and thus the master_secret!
Let’s just use a simple python script to loop through all pairs of moduli and look for any common factors.
from math import gcd
from var import flag, N, BACKUP
from itertools import combinations
from Crypto.Cipher import AES
e = 65537
flag = flag.to_bytes(64, 'big')
def decrypt(n, p, enc):
q = n // p
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
return pow(enc, d, n)
for enum1, enum2 in combinations(enumerate(N), 2):
i1, n1 = enum1
i2, n2 = enum2
g = gcd(n1, n2)
if g != 1:
break
g = gcd(N[i1],N[i2])
dec1 = decrypt(N[i1], g, BACKUP[i1])
dec2 = decrypt(N[i2], g, BACKUP[i2])
assert dec1 == dec2
secret = dec1.to_bytes(32, 'big')
cipher = AES.new(secret, AES.MODE_CBC, b'\0'*16)
dec = cipher.decrypt(flag)
print(dec)
After 8 minutes, we actually get a common factor! So the problem is already solved…
Why?
Why is there a common factor? For that we look at the code for parameter generation:
self.key = Key(
generate_prime(self.master_secret + int.to_bytes(pow(G, id, N), 32, 'big')),
generate_prime(self.master_secret + int.to_bytes(pow(H, id, N), 32, 'big'))
)
def generate_prime(seed):
random.seed(seed)
while True:
p = random.getrandbits(512) | (1<<511)
if p % E == 1: continue
if not is_prime(p): continue
return p
Since the random is seeded by the input, and master_secret is fixed, so it comes down to whether the latter part is fixed! In this case we are using the function \(f(x) = G^x\pmod{n}\) for the latter part, where id is random. id is a random 256-byte integer, and \(N\) is also a 256-byte integer, we might (wrongly) assume, that \(G\) and \(H\) are primitive roots mod \(N\), and if that is the case, the chance of two \(f(x)\) and \(f(y)\) to be equal are quite low.
However, We actually have that:
\(33554432\) is just a 25-bit number! By some math we know that the probability of at least one collision when we have \(16384\) random samples is actually \(1-\frac{33554432!}{33554432^{16384}(33554432-16384)!}\approx 98\%\). (This is the famous birthday problem)
So the primes are basically guaranteed to collide!
Unintended Solution…?
The flag of this challenge is hkcert21{y0u_d0nt_n33d_p41rw15e_9cd_1f_y0u_c4n_d0_i7_1n_b4tch}. What is batch gcd?
As it turns out, there is a fast algorithm to compute if (and which) 1 of the \(N\) have any common factor with the other remaining \(N\)’s. If there are, then we can already factor one of the modulus. The idea of the algorithm is to, for the list \(X\) of integers, to compute
We just need to precompute the product of all the integers, then invoke gcd for \(n\) times (where \(n\) is the number of integers), as opposed to the naive pairwise comparison method, which requires \(\frac{n(n-1)}{2}\) gcd calls. However as the pairwise method works it doesn’t matter.