Author. EggRoll

[TOC]

# PRaNsomG

## Overview

The ransomware first generates $32$ random $576$-bits numbers and then produces the key and initialization vector for encryptor. On the other hand, it uses a 2-bytes OTP to encrypt the $32$ random numbers and appends them to the corresponding encrpyted files.

## Exploit

Clearly, our goal is to recover the key and iv from the 32 random numbers. The straightforward approach is to crack the PRNG, which is MT19937 in this case. However, we have only $32 \times 576 < 19937$ bits.

Let's study the PRNG deeper, here is the way that MT19937 updates the internal states:

for i in range(0, 623+1):
    y = (self.MT[i] & 0x80000000) + (self.MT[(i+1) % 624] & 0x7fffffff)  
    self.MT[i] = self.MT[(i + 397) % 624] ^ (y >> 1)
    if (y % 2) != 0:
        self.MT[i] = self.MT[i] ^ (2567483615)

and the output is generated as follow:

if self.index == 0:
    self.generate_numbers()
y = self.MT[self.index]
y = y ^ (y >> 11)
y = y ^ ((y << 7) & (0x9d2c5680))
y = y ^ ((y << 15) & (0xefc60000))
y = y ^ (y >> 18)
self.index = (self.index + 1) % 624
return y

From the output, it's not hard to convery it back to the internal state and most importantly, any new internal state depends on only $3$ previous states. Therefore, we could still figure out the key and iv using less than $19937$-bits output.

from Crypto.Util.number import *
from Crypto.Cipher import AES
import random
import os

def USR(x, shift):
	res = x
	for i in range(32):
		res = x ^ res >> shift
	return res

def USL(x, shift, mask):
	res = x
	for i in range(32):
		res = x ^ (res << shift & mask)
	return res

def to_MT(v):
	v = USR(v, 18)
	v = USL(v, 15, 0xefc60000)
	v = USL(v, 7, 0x9d2c5680)
	v = USR(v, 11)
	return v

def to_random(y):
    y = y ^ (y >> 11)
    y = y ^ ((y << 7) & (0x9d2c5680))
    y = y ^ ((y << 15) & (0xefc60000))
    y = y ^ (y >> 18)
    return y

def xor(a, b):
	return b''.join([bytes([a[i] ^ b[i % len(b)]]) for i in range(len(a))])

def recover(a, b, c, otp):
	a = bytes_to_long(xor(a, otp))
	b = bytes_to_long(xor(b, otp))
	c = bytes_to_long(xor(c, otp))
	res = []
	MT_i, MT_iadd1, MT_iadd397 = to_MT(a), to_MT(b), to_MT(c)
	y = (MT_i & 0x80000000) + (MT_iadd1 & 0x7fffffff)
	MT_iadd624 = MT_iadd397 ^ (y >> 1)
	if (y % 2) != 0:
		MT_iadd624 = MT_iadd624 ^ 0x9908b0df
	return long_to_bytes(to_random(MT_iadd624))

def pad(s, L):

	return (L - len(s)) * b"\x00" + s

DEBUG = False

if not DEBUG:

	folder = "./enc_files/"
	files = os.listdir(folder)
	sorted_files = []
	for i in range(32):
		for fname in files:
			if fname.startswith(str(i) + "_"):
				sorted_files += [fname]
				files.remove(fname)
				break 

	enc, outputs = [], []
	for fname in sorted_files:
		with open(folder + fname, "rb") as f:
			tmp = f.read()
			enc += [tmp[:-72]]
			_ = tmp[-72:]
		for i in range(17, -1, -1):
			outputs += [_[4 * i: 4 * i + 4]]
else:
	# random.seed(12345678)
	outputs = []
	for _ in range(576):
		outputs += [long_to_bytes(random.getrandbits(32))]
	_key = long_to_bytes(random.getrandbits(1680))[:16]
	_iv = long_to_bytes(random.getrandbits(1680))[:16]

"""
	0, 1, ..., 575 (576)
	576, 577, ..., 627, 628 (1680 / 32 = 52.5)
	629, 630, ..., 680, 681
"""

for n in range(1 if DEBUG else 256**2):
	otp = pad(long_to_bytes(n), 2)

	key = recover(outputs[4], outputs[5], outputs[401], otp)[:2] + \
		pad(recover(outputs[3], outputs[4], outputs[400], otp), 4) + \
		pad(recover(outputs[2], outputs[3], outputs[399], otp), 4) + \
		pad(recover(outputs[1], outputs[2], outputs[398], otp), 4) + \
		pad(recover(outputs[0], outputs[1], outputs[397], otp), 4)[:2]
	
	iv = recover(outputs[57], outputs[58], outputs[454], otp)[:2] + \
		pad(recover(outputs[56], outputs[57], outputs[453], otp), 4) + \
		pad(recover(outputs[55], outputs[56], outputs[452], otp), 4) + \
		pad(recover(outputs[54], outputs[55], outputs[451], otp), 4) + \
		pad(recover(outputs[53], outputs[54], outputs[450], otp), 4)[:2]

	if not DEBUG:
		cipher = AES.new(key, AES.MODE_CBC, iv)
		for i, e in enumerate(enc):
			try:
				pt = cipher.decrypt(enc[i])
				print(pt.decode())
				print(i)
			except:
				pass
	else:
		assert key == _key and iv == _iv

## FLAG

:::success
HTB{v1t4l1um_h3r3_w3_c0m3___n0_r4ns0mw4r3_c4n_st0p_us}
:::

# Interception

## Overview

The server generates standard RSA parameters $(p, q, e, d, N)$ and the encryption key is defined to be $$ pow(ct, a^{N}, N) $$ where $ct, a$ are constants. Also, we are given three options:
1. Send the message $m$, the server returns $pow(ANS, e, N)$ if $pow(m, d, N)$ is decodable. Otherwise, it gives us $pow(random, e, N)$
2. Provide the key to the server and get the decrypted results back
3. Retrieve high bits of one prime factor of $N$ if the input is exactly the hash of $N$

## Exploit

Obviously, the steps to capture the flag are listed below.
1. Recover the value of RSA modulus $N$ using the oracle
2. Factorize $N$ with the high bits of one prime factor
3. Compute the key and send it to the server

### Step 1. Recover Modulus

Notice that by definition, $m^{e} - pow(m, e, N)$ is a multiple of $N$. If we have several such multiples, then $N$ is likely to be the GCD of them. From this observation, we should make $pow(m, d, N)$ be decodable. In my implementation, I choose $m=2^e$

### Step 2. Factorize N

We have $643$ bits of $q$, which is enough for us to factorize the modulus. See https://github.com/mimoo/RSA-and-LLL-attacks for more reference.

### Step 3. Key Computation

As we have factorization of $N$, we tends to find $$ pow(ct, a^{N}, p) \quad \text{and} \quad pow(ct, a^{N}, q) $$ By Fermat's little theorem, $$pow(ct, a^{N}, p) = pow(ct, a^{N\pmod{p-1}}, p)$$ Finally, using CRT to get the key.

## FLAG

:::success
HTB{th3y_d3f1n1t3ly_d0nt_h4v3_a_sUp3r_c0mPut3r!}
:::

# Vitrium Stash

## Overview

We are asked to forgery a DSA signature of message in a special form. Precisely, we have to provide $m ,r, s$ such that $$ r = (g^{ms^{-1}}y^{rs^{-1}} \pmod{p})\pmod{q} $$ where $y=g^{x}\pmod{p}$ and $q$ is the order of $\mathbb{F}_{p}(g)$

## Exploit

According to the function for verification, it's not hard to come up with a valid signatures $(0, y\pmod{q}, y\pmod{q})$. So it remains to find a message in the special form whose correpsonding integral value is a multiple of $q$. This could be done by LLL. A similar problem is https://github.com/Social-Engineering-Experts/SEETF-2023-Public/tree/main/challs/crypto/onelinecrypto

from Crypto.Util.number import *
import json

q = 26189572440233739420990528170531051459310363621928135990243626537967

# b'{"admin": True, "user": "xxxxxxx"}'

for k in range(30, 70):
	
	c = bytes_to_long(b'{"admin": true, "user": "' + b"\x00" * k + b'"}')
	M = Matrix(ZZ, k+2, k+2)
	M[:k+1, :k+1] = Matrix.identity(k+1)
	for i in range(k):
		M[i, -1] = 256 ** (k+1 - i)
		M[-2, i] = -80
	M[-2, -2] = 1
	M[-2, -1] = c
	M[-1, -1] = -q
	M = M.LLL()

	for r in M:
		if r[-1] == 0 and r[-2] == 1:
			try:
				print("Found")
				print(k)
				user = "".join([chr(r[i] + 80) for i in range(k)])
				# check
				message = b'{"admin": true, "user": "' + user.encode() + b'"}'
				print(bytes_to_long(message) % q)
				print(message.decode())
			except:
				pass

## FLAG

:::success
HTB{th3_l0c4t10n_0f_th3_v1t4l1um_1s_4t___37.187561,-115.885322}
:::