HTB CyberApocalypse CTF 2022
This week, my team the Crusaders of Rust along with some guest players playing under the alias InCrusadersWeRust participated and won the HTB Cyber Apocalypse CTF 2022 after some close competition with other teams! I felt like doing some writeups for the crypto challenges. I skipped some of them because I don’t feel like explaining them in great detail.
| Challenge Name | Tags | Category/Difficulty |
|---|---|---|
| Android-In-The-Middle | man in the middle diffe-hellman |
crypto/⭐ |
| Jenny from the Block | block cipher |
crypto/⭐ |
| How The Columns Have Turned | lcg twisted columnar |
crypto/⭐ |
| Memory Acceleration | meet in the middle hash function |
crypto/⭐⭐ |
| Down the Rabinhole | rabin gcd polynomial gcd |
crypto/⭐⭐ |
| Mind in the Clouds | ecdsa nonce leakage coppersmith |
crypto/⭐⭐⭐ |
| One Step Closer | rsa polynomial gcd franklin-reiter |
crypto/⭐⭐⭐ |
| Secret Codes | salae 433Mhz manchester code |
hardware/⭐⭐ |
[crypto] Android-In-The-Middle
challenge
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import hashlib
import random
FLAG = "HTB{--REDACTED--}"
DEBUG_MSG = "DEBUG MSG - "
p = 0x509efab16c5e2772fa00fc180766b6e62c09bdbd65637793c70b6094f6a7bb8189172685d2bddf87564fe2a6bc596ce28867fd7bbc300fd241b8e3348df6a0b076a0b438824517e0a87c38946fa69511f4201505fca11bc08f257e7a4bb009b4f16b34b3c15ec63c55a9dac306f4daa6f4e8b31ae700eba47766d0d907e2b9633a957f19398151111a879563cbe719ddb4a4078dd4ba42ebbf15203d75a4ed3dcd126cb86937222d2ee8bddc973df44435f3f9335f062b7b68c3da300e88bf1013847af1203402a3147b6f7ddab422d29d56fc7dcb8ad7297b04ccc52f7bc5fdd90bf9e36d01902e0e16aa4c387294c1605c6859b40dad12ae28fdfd3250a2e9
g = 2
def decrypt(encrypted, shared_secret):
key = hashlib.md5(long_to_bytes(shared_secret)).digest()
cipher = AES.new(key, AES.MODE_ECB)
message = cipher.decrypt(encrypted)
return message
print(DEBUG_MSG + "Generating The Global DH Parameters")
print(DEBUG_MSG + f"g = {g}, p = {p}")
print(DEBUG_MSG + "Calculation Complete\n")
print(DEBUG_MSG + "Generating The Public Key of CPU...")
c = random.randrange(2, p - 1)
C = pow(g, c, p)
print(DEBUG_MSG + "Calculation Complete")
print(DEBUG_MSG + "Public Key is: ???\n")
M = input("Enter The Public Key of The Memory: ")
M = int(M)
print(DEBUG_MSG + "The CPU Calculates The Shared Secret")
shared_secret = pow(M, c, p)
print(DEBUG_MSG + "Calculation Complete")
encrypted_sequence = input("Enter The Encrypted Initialization Sequence: ")
encrypted_sequence = bytes.fromhex(encrypted_sequence)
sequence = decrypt(encrypted_sequence, shared_secret)
if sequence == b"Initialization Sequence - Code 0":
print(DEBUG_MSG + "Reseting The Protocol With The New Shared Key")
print(DEBUG_MSG + f"{FLAG}")
We’re given access to a server which implements the Diffe-Hellman Key Exchange protocol.
The server sends us the Diffe-Hellman parameters $g, p$, and generates a private key $c$ and its corresponding public key $C = g^{c} \bmod p$. We are then allowed to send a public key $M$, from which the shared secret is derived as $M^{c} \bmod p$. Our goal is to recover the shared secret, from which we can send the server a message which will get us the flag.
solution
We have free choice over $M$, and we would like to make it so that for any $c$, we know the value of $M^{c}$, as this is the shared secret.
Since 1 to the power of anything is 1, we can set $M=1$, and then we know the shared secret will always be 1.
After this, we can use the shared secret to encrypt the chosen message, and recover the flag.
from pwn import *
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import hashlib
s = remote("134.209.178.167", 31149)
s.sendlineafter("Enter The Public Key of The Memory:", "1") # choose 1 to be M
target_message = b"Initialization Sequence - Code 0"
key = hashlib.md5(long_to_bytes(1)).digest() # shared secret will always be 1
cipher = AES.new(key, AES.MODE_ECB)
message = cipher.encrypt(target_message)
s.sendlineafter("Enter The Encrypted Initialization Sequence:", message.hex())
print(s.recvall().decode())
Flag: HTB{7h15_p2070c0l_15_pr0tec73d_8y_D@nb3er_c0pyr1gh7_1aws}
[crypto] Jenny From The Block
challenge
from hashlib import sha256
from Crypto.Util.Padding import pad, unpad
import subprocess
import os
allowed_commands = [b'whoami', b'ls', b'cat secret.txt', b'pwd']
BLOCK_SIZE = 32
def encrypt_block(block, secret):
enc_block = b''
for i in range(BLOCK_SIZE):
val = (block[i]+secret[i]) % 256
enc_block += bytes([val])
return enc_block
def encrypt(msg, password):
h = sha256(password).digest()
if len(msg) % BLOCK_SIZE != 0:
msg = pad(msg, BLOCK_SIZE)
blocks = [msg[i:i+BLOCK_SIZE] for i in range(0, len(msg), BLOCK_SIZE)]
ct = b''
for block in blocks:
enc_block = encrypt_block(block, h)
h = sha256(enc_block + block).digest()
ct += enc_block
return ct.hex()
def run_command(cmd):
if cmd in allowed_commands:
try:
resp = subprocess.run(
cmd.decode().split(' '), capture_output=True)
output = resp.stdout
return output
except:
return b'Something went wrong!\n'
else:
return b'Invalid command!\n'
print('This is Jenny! I am the heart and soul of this spaceship.\nWelcome to the debug terminal. For security purposes I will encrypt any responses.')
while True:
command = input("> ").encode()
output = run_command(command)
response = b'Command executed: ' + command + b'\n' + output
password = os.urandom(32)
ct = encrypt(response, password)
print(ct)
We are given access to a server that will allow us to run some commands, however the responses are all encrypted using some custom block cipher.
The block cipher is a simple addition cipher, which derives a key for the next block using the plaintext and ciphertext of the current block.
Here is a diagram that might make things easier to visualise:
solution
The key idea here is to notice that if we can get the plaintext and the ciphertext of a block, we can recover the key for the next block, and therefore we can get keys for all future blocks. The block size is 32 bytes, so we’ll need a full block of 32 bytes to be successful.
The server responds with messages of the form:
Command executed: {command} {output}
and we would like to run the command cat secret.txt. This means the encryption will be of the form:
Command executed: cat secret.txt {output}
and luckily for us:
len("Command executed: cat secret.txt")
>> 32
this is exactly 32 bytes! We can therefore now recover the key for the next block, and then decrypt all subsequent blocks.
from pwn import *
from hashlib import sha256
BLOCK_SIZE = 32
s = remote("46.101.25.63", 31949)
s.sendlineafter(">", "cat secret.txt")
ciphertext = bytes.fromhex(s.recvline().decode())
def decrypt_block(enc_block, secret):
block = b''
for i in range(BLOCK_SIZE):
val = (enc_block[i]-secret[i]) % 256
block += bytes([val])
return block
blocks = [ciphertext[i:i+BLOCK_SIZE] for i in range(0, len(ciphertext), BLOCK_SIZE)]
plaintextblock = b'Command executed: cat secret.txt'
ciphertextblock = blocks[0]
output = b''
for block in blocks[1:]:
key = sha256(ciphertextblock + plaintextblock).digest() # derive key for next block
plaintextblock = decrypt_block(block, key) # set blocks so we can derive key after that
output += plaintextblock
ciphertextblock = block
print(output.decode())
Flag: HTB{b451c_b10ck_c1ph3r_15_w34k!!!
[crypto] How The Columns Have Turned
challenge
import os
with open('super_secret_messages.txt', 'r') as f:
SUPER_SECRET_MESSAGES = [msg.strip() for msg in f.readlines()]
def deriveKey(key):
derived_key = []
for i, char in enumerate(key):
previous_letters = key[:i]
new_number = 1
for j, previous_char in enumerate(previous_letters):
if previous_char > char:
derived_key[j] += 1
else:
new_number += 1
derived_key.append(new_number)
return derived_key
def transpose(array):
return [row for row in map(list, zip(*array))]
def flatten(array):
return "".join([i for sub in array for i in sub])
def twistedColumnarEncrypt(pt, key):
derived_key = deriveKey(key)
width = len(key)
blocks = [pt[i:i + width] for i in range(0, len(pt), width)]
blocks = transpose(blocks)
ct = [blocks[derived_key.index(i + 1)][::-1] for i in range(width)]
ct = flatten(ct)
return ct
class PRNG:
def __init__(self, seed):
self.p = 0x2ea250216d705
self.a = self.p
self.b = int.from_bytes(os.urandom(16), 'big')
self.rn = seed
def next(self):
self.rn = ((self.a * self.rn) + self.b) % self.p
return self.rn
def main():
seed = int.from_bytes(os.urandom(16), 'big')
rng = PRNG(seed)
cts = ""
for message in SUPER_SECRET_MESSAGES:
key = str(rng.next())
ct = twistedColumnarEncrypt(message, key)
cts += ct + "\n"
with open('encrypted_messages.txt', 'w') as f:
f.write(cts)
dialog = "Miyuki says:\n"
dialog += "Klaus it's your time to sign!\n"
dialog += "All we have is the last key of this wierd encryption scheme.\n"
dialog += "Please do your magic, we need to gather more information if we want to defeat Draeger.\n"
dialog += f"The key is: {str(key)}\n"
with open('dialog.txt', 'w') as f:
f.write(dialog)
A key is randomly generated and is used to seed an LCG, from which keys for a “Twister Columnar” cipher is derived. Notably, the $a$ parameter for the LCG is equal to the modulus $p$.
solution
Observe that if $a = p$, then any time we do $ax + b \bmod p$, $ax$ is a multiple of $p$, and will get reduced to 0 when taken $\bmod p$. Therefore, the output of the LCG will always be $b$. Conveniently, we are given an output of the LCG, which we know is equal to $b$, and is the key used for every encryption.
Now that we know the key, we just need to write a decrypt function for the Twisted Columnar encryption, which is quite simple to do:
def decrypt(ct, key):
derived_key = deriveKey(key)
width = len(key)
w = len(ct) // width
ct = [list(ct[i:i + w]) for i in range(0, len(ct), w)]
pt = [ct[derived_key[i]-1][::-1] for i in range(width)]
blocks = transpose(pt)
pt = flatten(blocks)
return pt
and finally we can decrypt all the encrypted messages.
def deriveKey(key):
derived_key = []
for i, char in enumerate(key):
previous_letters = key[:i]
new_number = 1
for j, previous_char in enumerate(previous_letters):
if previous_char > char:
derived_key[j] += 1
else:
new_number += 1
derived_key.append(new_number)
return derived_key
def transpose(array):
return [row for row in map(list, zip(*array))]
def flatten(array):
return "".join([i for sub in array for i in sub])
def decrypt(ct, key):
derived_key = deriveKey(key)
width = len(key)
w = len(ct) // width
ct = [list(ct[i:i + w]) for i in range(0, len(ct), w)]
pt = [ct[derived_key[i]-1][::-1] for i in range(width)]
blocks = transpose(pt)
pt = flatten(blocks)
return pt
messages = """VEOAOTNRDCEEIFHIVHMVOETYDEDTESTHTCHLSRPDAIYAATOSTEGIIIOCIPYLTNOTLRTRNLEEUNBEOSFNANDHTUFTEETREEEEOEDHNRNYA
AAVPDESEETURAFFDUCEDAEECNEMOROCEANHPTTGROITCYSSSETTSKTTRLRIUAVSONOISECNJISAFAATAPATWORIRCETYUIPUEEHHAIHOG
NABPSVKELHRIALDVEHLORCNNOERUNGTAEEEHEHDORLIEEAOTITUTEAUEARTEFISESGTAYAGBTHCEOTWLSNTWECESHHBEIOYPNCOLICCAF
NIRYHFTOSSNPECMPNWSHFSNUTCAGOOAOTGOITRAEREPEEPWLHIPTAPEOOHPNSKTSAATETTPSIUIUOORSLEOAITEDFNDUHSNHENSESNADR
NUTFAUPNKROEOGNONSRSUWFAFDDSAAEDAIFAYNEGYSGIMMYTAANSUOEMROTRROUIIOODLOIRERVTAMNITAHIDNHRENIFTCTNLYLOTFINE
""".splitlines()
[print(decrypt(message, "729513912306026")) for message in messages]
THELOCATIONOFTHECONVOYDANTEISDETERMINEDTOBEONTHETHIRDPLANETAFTERVINYRYOUCANUSELIGHTSPEEDAFTERTHEDELIVERYS
THECARGOISSAFEWENEEDTOMOVEFASTCAUSETHERADARSAREPICKINGUPSUSPICIOUSACTIVITYAROUNDTHETRAJECTORYOFTHEPLANETA
BECAREFULSKOLIWHENYOUARRIVEATTHEPALACEOFSCIONSAYTHECODEPHRASETOGETINHTBTHELCGISVULNERABLEWENEEDTOCHANGEIT
DONTFORGETTOCHANGETHEDARKFUELOFTHESPACESHIPWEDONTWANTANYUNPLEASANTSURPRISESTOHAPPENTHISSERIOUSMISSIONPOPO
IFYOUMESSUPAGAINILLSENDYOUTOTHEANDROIDGRAVEYARDTOSUFFERFROMTHECONSTANTTERMINATIONOFYOURKINDAFINALWARNINGM
from which we can extract the flag:
Flag: HTB{THELCGISVULNERABLEWENEEDTOCHANGEIT}
[crypto] Memory Acceleration
challenge
from hashlib import md5
from Crypto.Util.number import long_to_bytes, bytes_to_long
sbox = [
0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
]
def rotl(n, b):
return ((n << b) | (n >> (32 - b))) & 0xffffffff
def sub(b):
b = long_to_bytes(b)
return bytes([sbox[i] for i in b])
def phash(block, key1, key2):
block = md5(block.encode()).digest()
block = 4 * block
blocks = [bytes_to_long(block[i:i+4]) for i in range(0, len(block), 4)]
m = 0xffffffff
rv1, rv2 = 0x2423380b4d045, 0x3b30fa7ccaa83
x, y, z, u = key1, 0x39ef52e9f30b3, 0x253ea615d0215, 0x2cd1372d21d77
for i in range(13):
x, y = blocks[i] ^ x, blocks[i+1] ^ y
z, u = blocks[i+2] ^ z, blocks[i+3] ^ u
rv1 ^= (x := (x & m) * (m + (y >> 16)) ^ rotl(z, 3))
rv2 ^= (y := (y & m) * (m + (z >> 16)) ^ rotl(x, 3))
rv1, rv2 = rv2, rv1
rv1 = sub(rv1)
rv1 = bytes_to_long(rv1)
h = rv1 + 0x6276137d7 & m
key2 = sub(key2)
for i, d in enumerate(key2):
a = (h << 1) & m
b = (h << 3) & m
c = (h >> 4) & m
h ^= (a + b + c - d)
h += h
h &= m
h *= u * z
h &= m
return h
DEBUG_MSG = "DEBUG MSG - "
WELCOME_MSG = """Virgil says:
Klaus I'm connecting the serial debugger to your memory.
Please stay still. We don't want anything wrong to happen.
Ok you should be able to see debug messages now..\n"""
MEMORIES = ["lol", "lol2"]
block = ""
counter = 0
print(WELCOME_MSG)
while True:
block += MEMORIES[counter]
print(DEBUG_MSG + f"You need to validate this memory block: {block}")
first_key = int(input(DEBUG_MSG + "Enter first key: "))
second_key = int(input(DEBUG_MSG + "Enter second key: "))
proof_of_work = phash(block, first_key, second_key)
if proof_of_work == 0:
block += f" ({first_key}, {second_key}). "
print("Virgil says: \nWow you formed a new memory!!")
counter += 1
print(f"Let's try again {4 - counter} times just to be sure!\n")
else:
print(f"Incorect proof of work\n"
"\nVirgil says: \n"
"You calculated something wrong Klaus we need to start over.")
exit()
if counter == 4:
print("It seems that everything are working fine.\n"
"Wait what is that...\n"
"Klaus this is important!!\n"
"This can help you find your father!!\n"
f"{MEMORIES[-1]}")
exit()
We are given a custom hash function, which takes in 2 keys and a message block, and outputs a 32 bit hash. Our goal is, for 4 rounds, find 2 keys $k_1, k_2$ such that the hash of a known message block is equal to 0.
solution
The hash function has a suspiciously small output of 32 bits. This means that, if we try $2^{32}$ combinations for $k_1, k_2$, we would expect to find at least one pair such that the hash of the block will be equal to zero.
However, $2^{32}$ is a little large to bruteforce, especially in something like python. Ideally we’d like to optimize this a bit.
The key to this challenge is to notice that the hash function can be split into two individual parts, each which uses only one of the keys. This means that, since we know the “start” and “end”, we can potentially turn this into a Meet In the Middle attack. I won’t go into too much detail here, you can find a slightly more detailed explanation in my writeup for another challenge, but the general idea is that you save time by using more space, by bruteforcing the keys individually and finding where they meet, i.e. the “middle”
The only thing we need to do is figure out how to “invert” the second half of the hash function, so that we can get to the middle from the end.
key2 = sub(key2)
for i, d in enumerate(key2):
a = (h << 1) & m
b = (h << 3) & m
c = (h >> 4) & m
h ^= (a + b + c - d)
h += h
h &= m
Hmm, this looks really annoying to invert, as it combines addition with bit shifting and XOR, which are hard to represent algebraically. Luckily, there’s a good cheat for this, we can use the power of z3! z3 is a SMT solver, which we can plug in our conditions, and then hopefully we can get a value of $h$, which for a given $k_2$, results in $h_{out} = 0$.
from z3 import *
from tqdm import tqdm
m = 0xffffffff
def invert(htarget, d):
s = Solver()
h = BitVec('h', 33)
a = (h << 1) & m
b = (h << 3) & m
c = (h >> 4) & m
p = a + b + c - d
_h = ((h ^ p) << 1) & m
s.add(_h == int(htarget))
prevsol = 0
sols = []
while True: # ideally we want as many unique h's as possible, therefore we try find all solutions
try:
s.add(h != int(prevsol))
s.check()
prevsol = s.model()[h].as_long()
if check(prevsol&m, d) == htarget:
sols.append(prevsol)
except Exception as e:
break
return sols
def check(h, d):
a = h << 1 & m
b = h << 3 & m
c = h >> 4 & m
p = a + b + c - d
_h = ((h ^ p) << 1) & m
return _h
Z3 inversion takes a little while, so I only chose to generate about $2^{15}$ of these values. From a bit of local testing, we then need about $2^{19}$ $k_1$’s in order to find a collision.
Finally, after generating these collisions, we generate $2^{19}$ possible values for the given block, and hopefully we find a $h$ which is found in the data of key2, in which case we have successfully found $k_1, k_2$. This takes about 1 minute to generate a zero-hash on my laptop.
from tqdm import tqdm
from pofwork import *
from hashlib import md5
from Crypto.Util.number import long_to_bytes, bytes_to_long
data = eval(open("allsols4.txt").read())
set2 = {}
for i, x in data:
if not set2.get(x, 0):
set2[x] = i
set2key = set(set2.keys())
m = 0xffffffff
def fakephash(key1):
rv1, rv2 = 0x2423380b4d045, 0x3b30fa7ccaa83
x, y, z, u = key1, 0x39ef52e9f30b3, 0x253ea615d0215, 0x2cd1372d21d77
for i in range(13):
x, y = blocks[i] ^ x, blocks[i+1] ^ y
z, u = blocks[i+2] ^ z, blocks[i+3] ^ u
rv1 ^= (x := (x & m) * (m + (y >> 16)) ^ rotl(z, 3))
rv2 ^= (y := (y & m) * (m + (z >> 16)) ^ rotl(x, 3))
rv1, rv2 = rv2, rv1
rv1 = sub(rv1)
rv1 = bytes_to_long(rv1)
h = rv1 + 0x6276137d7 & m
return h
origblock = "put your block here"
block = md5(origblock.encode()).digest()
block = 4 * block
blocks = [bytes_to_long(block[i:i+4]) for i in range(0, len(block), 4)]
set1 = dict({(fakephash(i), i) for i in tqdm(range(2**19))})
set1key = set(set1.keys())
intersections = list(set1key.intersection(set2key)) # find if there are any collisions
middle = intersections[0]
# generate the keys
key1 = set1[middle]
key2 = bytes_to_long(bytes([sbox.index(x) for x in long_to_bytes(set2[middle])[::-1]]))
print(f"key1: {key1}, key2: {key2}")
assert phash(origblock, key1, key2) == 0
Flag: HTB{K14u5_h45_z3_h42d_c0d3d_1n_m3m02y}
[crypto] Down The Rabinhole
challenge
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from Crypto.Util.Padding import pad
import os
FLAG = b"HTB{--REDACTED--}"
def getPrimes(coefficient):
while True:
a = getPrime(512)
p = 3 * coefficient * a + 2
if isPrime(p):
break
while True:
b = getPrime(512)
q = 3 * coefficient * b + 2
if isPrime(q):
break
return p, q
def encrypt(message, coefficient):
p, q = getPrimes(coefficient)
n = p * q
padded_message = bytes_to_long(pad(message, 64))
message = bytes_to_long(message)
c1 = (message * (message + coefficient)) % n
c2 = (padded_message * (padded_message + coefficient)) % n
return (n, c1, c2)
coefficient = getPrime(128)
message = FLAG[0:len(FLAG)//2]
n1, c1, c2 = encrypt(message, coefficient)
print(n1)
print(c1)
print(c2)
message = FLAG[len(FLAG)//2:]
print(n2)
print(c3)
print(c4)
out.txt:
59695566410375916085091065597867624599396247120105936423853186912270957035981683790353782357813780840261434564512137529316306287245132306537487688075992115491809442873176686026221661043777720872604111654524551850568278941757944240802222861051514726510684250078771979880364039814240006038057748087210740783689350438039317498789505078530402846140787188830971536805605748267334628057592989
206131769237721955001530863959688756686125485413899261197125641745745636359058664398433013356663394210624150086689905532
14350341133918883930676906390648724486852266960811870561648194176794020698141189777337348951219934072588842789694987397861496993878758159916334335632468891342228755755695273096621152247970509517996580512069034691932835017774636881861331636331496873041705094768329156701838193429109420730982051593645140188946
56438641309774959123579452414864548345708278641778632906871133633348990457713200426806112132039095059800662176837023585166134224681069774331148738554157081531312104961252755406614635488382297434171375724135403083446853715913787796744272218693049072693460001363598351151832646947233969595478647666992523249343972394051106514947235445828889363124242280013397047951812688863313932909903047
429546912004731012886527767254149694574730322956287028161761007271362927652041138366004560890773167255588200792979452452
29903904396126887576044949247400308530425862142675118500848365445245957090320752747039056821346410855821626622960719507094119542088455732058232895757115241568569663893434035594991241152575495936972994239671806350060725033375704703416762794475486000391074743029264587481673930383986479738961452214727157980946
The flag is split into halves, and encrypted using a variation of the Rabin cryptosystem.
Firstly, a random 128 bit prime $c$ is generated, and remains constant for both encryptions.
For each encryption, two 641-ish bit primes $p, q$ are generated of the form $(3 * c * x) + 2$. These primes are multiplied to give a modulus $n$. Then, we are given two ciphertexts:
\[c_1 = m^2 + cm \bmod n\\ c_2 = p(m)^2 + cp(m) \bmod n\]where $p(m)$ is the padded version of the message to 64 bytes.
solution (unintended)
Firstly, there’s a very big unintended with this challenge. Notice that the padded message will be 64*8 = 512 bits. Notice then that the ciphertext will only be a maximum of:
\[(2^{512})^2 + (2^{128} * 2^{512}) = 2^{1024}\]and notice that the bit length of $n$ is approximately 1282.
This means that, during encryption, the $\bmod n$ is effectively irrelevant. The hardness of the Rabin cryptosystem relies on the fact that taking a square root $\bmod n$, i.e. finding $a$ such that $a^2 \equiv x \bmod n$ for any given $x$ without knowing the factorization of $n$ is hard.
However, since the $\bmod n$ is not used, we can simply try and find roots of this polynomial over the integers. One thing we need to take care of is not knowing what $c$ is, and there is a way to do that, but actually, since $cp(m)$ is so small compared to $p(m)^2$, we can just approximate $c_2 \approx p(m)^2$ and we should be able to recover $p(m)$ well enough that we have the flag.
Indeed, if we try it with the values given in the output:
long_to_bytes(iroot(14350341133918883930676906390648724486852266960811870561648194176794020698141189777337348951219934072588842789694987397861496993878758159916334335632468891342228755755695273096621152247970509517996580512069034691932835017774636881861331636331496873041705094768329156701838193429109420730982051593645140188946, 2)[0])
>>> b"HTB{gcd_+_2_*_R@6in_.|5_t'''''''''''''''''''''''\x8a\x1b=\x84x\x1e\xe9\x17\x8a\x01J\x1c\x08w\x95b"
long_to_bytes(iroot(29903904396126887576044949247400308530425862142675118500848365445245957090320752747039056821346410855821626622960719507094119542088455732058232895757115241568569663893434035594991241152575495936972994239671806350060725033375704703416762794475486000391074743029264587481673930383986479738961452214727157980946, 2)[0])
>>> b"hi5_@_cro55over_epi5ode?}'''''''''''''''''''''''\x8a\x1b=\x84x\x1e\xe9\x17\x8a\x01J\x1c\x08w\x95b"
we get the entire flag.
solution (intended)
The intended solution for this challenge is a bit more complex. We’ll start by trying to recover the unknown coefficient $c$.
The primes are of the form $(3 * c * x) + 2$. If we multiply two of them together and expand it out:
\[\begin{eqnarray} (3cx + 2)(3cx + 2) = 9c^2x^2 + 12cx + 4 \end{eqnarray}\]Notice that $n - 4$ is therefore a multiple of $c$. We could try and factor it out, but it’s 128 bits, and would probably take too long.
Remember though, we have 2 of these moduli, so what we can do instead is take the GCD of these two multiples of $c$, and hopefully we should get some small multiple of $c$.
from math import gcd
n1 = 59695566410375916085091065597867624599396247120105936423853186912270957035981683790353782357813780840261434564512137529316306287245132306537487688075992115491809442873176686026221661043777720872604111654524551850568278941757944240802222861051514726510684250078771979880364039814240006038057748087210740783689350438039317498789505078530402846140787188830971536805605748267334628057592989
n2 = 56438641309774959123579452414864548345708278641778632906871133633348990457713200426806112132039095059800662176837023585166134224681069774331148738554157081531312104961252755406614635488382297434171375724135403083446853715913787796744272218693049072693460001363598351151832646947233969595478647666992523249343972394051106514947235445828889363124242280013397047951812688863313932909903047
print(gcd(n1 - 4, n2 - 4))
>>> 2367570917280473441342864832287881019439
and if we plug this into FactorDB or whatever, we can see that we have indeed recovered the coefficient.
Now that we have the coefficients, we have two polynomials where the only unknowns are $m, p(m)$:
\[x^2 + cx - c_1\\ p(x)^2 + cx - c_2\\\]Firstly, we’ll ideally want to reduce this to only one unknown, such that we get two polynomials with roots of $m$. We’ll do this by writing $p(m)$ in terms of $m$, and we can do so by writing $p(m)$ as:
\[p(m) = 2^{(64 - 25) * 8} * m + 0x10101\dots * (64 - 25)\]where 25 is the length of the flag half (which you would bruteforce if it was not known)
Then, since we have two polynomials with roots of $m$, we can take their polynomial GCD, as due to the factor theorem, they should share the common factor of $(x - m)$. Repeating this twice should get us the flag.
from math import gcd
from Crypto.Util.number import long_to_bytes
n1 = 59695566410375916085091065597867624599396247120105936423853186912270957035981683790353782357813780840261434564512137529316306287245132306537487688075992115491809442873176686026221661043777720872604111654524551850568278941757944240802222861051514726510684250078771979880364039814240006038057748087210740783689350438039317498789505078530402846140787188830971536805605748267334628057592989
c1 = 206131769237721955001530863959688756686125485413899261197125641745745636359058664398433013356663394210624150086689905532
c2 = 14350341133918883930676906390648724486852266960811870561648194176794020698141189777337348951219934072588842789694987397861496993878758159916334335632468891342228755755695273096621152247970509517996580512069034691932835017774636881861331636331496873041705094768329156701838193429109420730982051593645140188946
n2 = 56438641309774959123579452414864548345708278641778632906871133633348990457713200426806112132039095059800662176837023585166134224681069774331148738554157081531312104961252755406614635488382297434171375724135403083446853715913787796744272218693049072693460001363598351151832646947233969595478647666992523249343972394051106514947235445828889363124242280013397047951812688863313932909903047
c3 = 429546912004731012886527767254149694574730322956287028161761007271362927652041138366004560890773167255588200792979452452
c4 = 29903904396126887576044949247400308530425862142675118500848365445245957090320752747039056821346410855821626622960719507094119542088455732058232895757115241568569663893434035594991241152575495936972994239671806350060725033375704703416762794475486000391074743029264587481673930383986479738961452214727157980946
poly_gcd = lambda g1, g2: g1.monic() if not g2 else poly_gcd(g2, g1%g2)
coeff = gcd(n1-4, n2-4)//9
P.<m1> = PolynomialRing(Zmod(n1))
pm1 = 2^((64 - 25)*8)*m1 + 0x010101010101010101010101010101010101010101010101010101010101010101010101010101 * (64-25)
poly1 = m1^2 + coeff*m1 - c1
poly2 = pm1^2 + coeff*pm1 - c2
P.<m2> = PolynomialRing(Zmod(n2))
pm2 = 2^((64 - 25)*8)*m2 + 0x010101010101010101010101010101010101010101010101010101010101010101010101010101 * (64-25)
poly3 = m2^2 + coeff*m2 - c3
poly4 = pm2^2 + coeff*pm2 - c4
print(b"".join([long_to_bytes(int(poly_gcd(p1, p2).small_roots()[0])) for p1, p2 in [(poly1, poly2), (poly3, poly4)]]))
Flag: HTB{gcd_+_2_*_R@6in_.|5_thi5_@_cro55over_epi5ode?}
[crypto] Mind in the Clouds
challenge
import json
from hashlib import sha1
from random import randint
from Crypto.Util.number import bytes_to_long
from ecdsa.ecdsa import generator_256, Public_key, Private_key, Signature
fnames = [b'subject_kolhen', b'subject_stommb', b'subject_danbeer']
nfnames = []
class ECDSA:
def __init__(self):
self.G = generator_256
self.n = self.G.order()
self.key = randint(1, self.n - 1)
self.pubkey = Public_key(self.G, self.key * self.G)
self.privkey = Private_key(self.pubkey, self.key)
def sign(self, fname):
h = sha1(fname).digest()
nonce = randint(1, self.n - 1)
sig = self.privkey.sign(bytes_to_long(h), nonce)
return {"r": hex(sig.r)[2:], "s": hex(sig.s)[2:], "nonce": hex(nonce)[2:]}
def verify(self, fname, r, s):
h = bytes_to_long(sha1(fname).digest())
r = int(r, 16)
s = int(s, 16)
sig = Signature(r, s)
if self.pubkey.verifies(h, sig):
return retrieve_file(fname)
else:
return 'Signature is not valid\n'
ecc = ECDSA()
def init_storage():
i = 0
for fname in fnames[:-1]:
data = ecc.sign(fname)
r, s = data['r'], data['s']
nonce = data['nonce']
nfname = fname.decode() + '_' + r + '_' + s + '_' + nonce[(14 + i):-14]
nfnames.append(nfname)
i += 2
def retrieve_file(fname):
try:
dt = open(fname, 'rb').read()
return dt.hex()
except:
return 'The file does not exist!'
print('This is a cloud storage service.\n' +
'You can list the files inside and also see their contents if your signatures are valid.')
while True:
print('\nOptions:\n1.List files\n2.Access a file')
payload = json.loads(input())
if payload['option'] == 'list':
payload = json.dumps(
{'response': 'success', 'files': nfnames})
print(payload.encode())
elif payload['option'] == 'access':
fname = payload['fname']
r, s = payload['r'], payload['s']
dt = ecc.verify(fname.encode(), r, s)
if ('not exist' in dt) or ('not valid' in dt):
payload = json.dumps({'response': 'error', 'message': dt})
else:
payload = json.dumps({'response': 'success', 'data': dt})
print(payload.encode())
We’re given access to a server which stores files and their ECDSA signature. We can get signatures for 2 files, and notably, we are leaked the middle bits of the nonces used to sign those files. Our goal is to produce a valid signature for the file subject_danbeer
solution
The server removes the first and last 14 hex digits of the nonces (except for one of them, where it removes 15 hex digits), and we have 2 of them. Therefore, we have $(14 + 14 + 14 + 15) * 4$ = a total of 228 unknown bits, which can be considered “small” compared to the curve order of 256 bits. Time for Coppersmith!
We’ll form two equations based on the ECDSA equations, with unknowns $k_1, k_2, d$
\[\begin{eqnarray} s_1k_1 = h_1 + r_1d\\ s_2k_2 = h_2 + r_2d\\ \end{eqnarray}\]Firstly, we’d ideally like to get rid of $d$. We can do this by combining 2 samples. Since I’m too lazy to write out the equations, we’ll ask Sage to compute the resultant for us. joseph has a nice trick for this in one of his writeups, which involves computing the Sylvester matrix and then taking the determinant:
P.<k1, k2, d, h1, h2, r1, r2, s1, s2> = PolynomialRing(GF(115792089210356248762697446949407573529996955224135760342422259061068512044369))
def resultant(f1, f2, var):
return Matrix(f1.sylvester_matrix(f2, var)).determinant()
poly1 = h1 + r1*d - s1*k1
poly2 = h2 + r2*d - s2*k2
poly3 = resultant(poly1, poly2, d)
print(poly3)
>>> k1*r2*s1 - k2*r1*s2 + h2*r1 - h1*r2
We’ve now gotten rid of $d$. Now we’ll rewrite $k_1, k_2$ with our known bit values:
\[\begin{eqnarray} k_1 = 2^{196}a_1 + 2^{56}b_1 + c_1\\ k_2 = 2^{188}a_2 + 2^{56}b_2 + c_2\\ \end{eqnarray}\]where $b_1, b_2$ are known, and $a_1, c_1, a_2, c_2$ are our small unknowns, and then we can substitute these back into our new multivariate polynomial.
Now we can chuck Coppersmith at it, and hopefully we should be able to recover $k_1$ and $k_2$, from which we can easily recover $d$ by finding roots of one of our original polynomials. defund has a great implementation of multivariate Coppersmith for this.
import itertools
from hashlib import sha1
# from https://github.com/defund/coppersmith/blob/master/coppersmith.sage
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
R = f.base_ring()
N = R.cardinality()
f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m+1):
base = N^(m-i) * f^i
for shifts in itertools.product(range(d), repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1/factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B*monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []
def resultant(f1, f2, var):
return Matrix(f1.sylvester_matrix(f2, var)).determinant()
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
fname1 = "subject_kolhen_cf93b80a0507f25712f7d248a6966e32d8779a1a29920e27b29aca2975f28df3_210c480f2578635a569c906990dcf65791b0a844622028ae12ed55b0dbffa4c6_f7448810c770c148d7a5dea7ca8a58ee2376"
fname2 = "subject_stommb_b2f0179d444fe16a8257f4cd300c29b1924228e17163a8b0e8a994ba4523e20b_eb82f558439607261d47f217a26922325a324b2252da2cd1c1ef178fca71b0f5_a84e1ab9aedafa43605e508febb33543ea"
f1 = fname1.split("_")
h1 = int(sha1(("_".join(f1[:2])).encode()).hexdigest(), 16)
r1 = int(f1[2], 16)
s1 = int(f1[3], 16)
b1 = int(f1[4], 16)
f2 = fname2.split("_")
h2 = int(sha1(("_".join(f2[:2])).encode()).hexdigest(), 16)
r2 = int(f2[2], 16)
s2 = int(f2[3], 16)
b2 = int(f2[4], 16)
P.<a1, c1, a2, c2, d> = PolynomialRing(GF(order))
k1 = a1*2^196 + b1*2^56 + c1
k2 = a2*2^188 + b2*2^56 + c2
poly1 = h1 + r1*d - s1*k1
poly2 = h2 + r2*d - s2*k2
poly3 = resultant(poly1, poly2, d)
P.<a1, c1, a2, c2> = PolynomialRing(GF(order)) # there is probably a much better way to do this...
poly3 = eval(str(poly3))
bounds = (2^56, 2^56, 2^64, 2^56)
roots = small_roots(poly3, bounds, m=2, d=2)[0]
a1, c1, a2, c2 = roots
P.<d> = PolynomialRing(GF(order))
k1 = a1*2^196 + b1*2^56 + c1
poly1 = h1 + r1*d - s1*k1
print("d:", poly1.roots()[0][0])
Finally, with the private key recovered, we can sign the filename and get the flag.
import json
from hashlib import sha1
from Crypto.Util.number import bytes_to_long
from ecdsa.ecdsa import generator_256, Public_key, Private_key
fname = 'subject_danbeer'
d = 39577127242457828829693909487476334496443112013102308760621879538920726198563
pubkey = Public_key(generator_256, d * generator_256)
privkey = Private_key(pubkey, d)
h = sha1(fname.encode()).digest()
sig = privkey.sign(bytes_to_long(h), 1337)
signature = {
"option": "access",
"fname": fname,
"r": hex(int(sig.r)),
"s": hex(int(sig.s))
}
print(json.dumps(signature))
Flag: HTB{y0u_4r3_th3_m4st3r_0f_LLL}
[crypto] One Step Closer
challenge
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime, inverse
import random
FLAG = b'HTB{--REDACTED--}'
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 257
def encrypt_flag():
a = random.getrandbits(1024)
b = random.getrandbits(1024)
flag = bytes_to_long(FLAG)
msg = a*flag + b
ct = pow(msg, e, n)
return {'ct': format(ct, 'x'), 'n': format(n, 'x'), 'e': format(e, 'x'), 'a': format(a, 'x'), 'b': format(b, 'x')}
We are given access to a website which will call the encrypt_flag function every time the page is reloaded and return the result. The flag is encrypted using the RSA cryptosystem, where each time the flag is encrypted as:
solution
Similar to Down The Rabinhole, we can form two polynomials with the same roots of $m$ and take their polynomial GCD, where the common factor will once again be $(x - m)$ . Since the only unknown is $m$, this is very straightforward.
This is also known more commonly as the Franklin-Reiter related message attack.
import requests as r
from Crypto.Util.number import long_to_bytes
url = "http://165.227.224.55:32107/api/get_flag"
r1, r2 = r.get(url).json(), r.get(url).json()
n = int(r1["n"], 16)
e = int(r1["e"], 16)
a1 = int(r1["a"], 16)
b1 = int(r1["b"], 16)
c1 = int(r1["ct"], 16)
a2 = int(r2["a"], 16)
b2 = int(r2["b"], 16)
c2 = int(r2["ct"], 16)
poly_gcd = lambda g1, g2: g1.monic() if not g2 else poly_gcd(g2, g1%g2)
P.<m> = PolynomialRing(Zmod(n))
poly1 = (a1*m + b1)^e - c1
poly2 = (a2*m + b2)^e - c2
m = poly_gcd(poly1, poly2).small_roots()
print(long_to_bytes(int(m[0])))
Flag: HTB{f1n1t3_d1ff3r3nc35_134d_70_r31473d_m355493_4774ck5}
[hardware] Secret Codes
challenge
We are presented with a .sal file, which is named Capture433.sal. One of the channels is a digital channel, while the other is analog. The digital channel cuts off after the first transmission, but the analog channel remains fine.
solution
Immediately the first thing we would like to do is convert the analog data to digital data. This is not too hard, in fact we can simply do this manually. Doing so gives us 10 bitstreams of length 66:
101001101001101010100110011001101010011010101001101001010101100101
101001011010100101101001011010101010010110100110101010010110100101
101010010110011001100110010101010110010110100101101010010110101001
101010010110101010101001011001101010100101100101011010010110101001
101001011001010110101001010110100110011001010101011010010110010101
101001011001101010101001011010011010100101101010101001010110011001
101010010101101001100101100110101010011001010101011010010110011001
101001010110101010101001011001101010010110101001011010010110100101
101001100101010110101001011001010110100101100101101001010101011001
The next step is figuring out how to decode these. From the filename, we can guess that this is a 433 Mhz signal, and after doing a bit of googling, we can find that this is Manchester Code. The basic idea is that every two bits codes for one bit, and is either “10” = 0, or “01” = 1. We also note there is an initial extra bit.
So, we can write a simple decoder with python:
from Crypto.Util.numbrt import long_to_bytes
def decode(stream):
code = {"10": "0", "01": "1"}
blocks = [code[stream[i:i+2]] for i in range(0, len(stream), 2)][1:]
return long_to_bytes(int("".join(blocks), 2))
streams = """101001101001101010100110011001101010011010101001101001010101100101
101001011010100101101001011010101010010110100110101010010110100101
101010010110011001100110010101010110010110100101101010010110101001
101010010110101010101001011001101010100101100101011010010110101001
101001011001010110101001010110100110011001010101011010010110010101
101001011001101010101001011010011010100101101010101001010110011001
101010010101101001100101100110101010011001010101011010010110011001
101001010110101010101001011001101010010110101001011010010110100101
101001100101010110101001011001010110100101100101101001010101011001""".splitlines()
print(b"".join([decode(stream) for stream in streams]))
which gives us our flag