PRaNsomG
PRaNsomG
Following the mole’s dismissal, the nation suffered from an onslaught of relentless phishing campaigns. With little time to spare during this chaotic and tense period, warnings and safeguards for staff members were inadequate. A few individuals fell victim to the phishing attempts, leading to the encryption of sensitive documents by ransomware. You were assigned the mission of reverse engineering the ransomware and ultimately recovering the classified files, restoring order and safeguarding the nation’s sensitive information.
Files
Download: crypto_pransomg.zip
Overview
This is a crypto challenge built around a ransomware sample. The ransomware first generates 32 random 576-bit numbers and then derives the key and initialization vector for the AES encryptor from them. On top of that, it uses a 2-byte OTP (one-time pad) to “protect” the 32 random numbers and appends them to each corresponding encrypted file.
Our goal is therefore to recover the AES key and IV from those 32 appended random numbers so we can decrypt the files.
Analysis
The straightforward approach would be to crack the PRNG, which is MT19937 (the Mersenne Twister) in this case. The classic state-recovery attack needs 624 consecutive 32-bit outputs (19937 bits) to fully reconstruct the internal state. Here we only have 32 × 576 = 18432 bits, which is less than 19937, so a naive full state recovery will not work.
The trick discussed during the event was simpler than full state recovery: you can feed zero bytes in to obtain enough input data, and although the output is not 100% correct, the specific bits used to derive the AES key and IV come out correct. The 2-byte OTP only has 16 bits of entropy, so it can simply be brute forced. Concretely, if you have two secrets s1 = (output1 ^ otp) and s2 = (output2 ^ otp), then for the correct seed/state new_out1 ^ s1 and new_out2 ^ s2 both yield the same OTP, which acts as a consistency check.
The real insight is in how MT19937 updates its internal state. Here is the state update step:
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 here is how a single 32-bit output is produced via the tempering transform:
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
The tempering transform is invertible, so we can convert any output back to its internal state value. More importantly, each new internal state MT[i+624] depends on only three previous states: MT[i], MT[i+1], and MT[i+397]. That means we can compute the key and IV bits we need using far fewer than 19937 bits of output.
Exploitation
The exploit below inverts the tempering on the relevant outputs, reconstructs the specific future states that feed the AES key and IV, brute forces the 16-bit OTP, and decrypts the files. The helper functions implement the invertible tempering (to_MT / to_random), the single-step state recovery (recover), and the OTP XOR.
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
Brute forcing all 256**2 OTP candidates and decrypting the files with the recovered key and IV yields the classified contents and the flag.
HTB{v1t4l1um_h3r3_w3_c0m3___n0_r4ns0mw4r3_c4n_st0p_us}