My writeups for the HTB 2023 Cyber Apocalypse CTF Crypto Category. Full solver codes can be found on my github 🙂
Information
These are all the Crypto challenges I managed to solve. Here’s the link to my github repo that has the full solving scripts.
Challenges
Ancient Encodings
Difficulty: very easy
Description: Your initialization sequence requires loading various programs to gain the necessary knowledge and skills for your journey. Your first task is to learn the ancient encodings used by the aliens in their communication.
Code Analysis
The encode function is the only function performed on the flag:
def encode(message):
return hex(bytes_to_long(b64encode(message)))
The flag is base64 encoded, converted to a long integer, and then converted to a hexadecimal number in string format.
Decryption
We need to convert the hex to bytes, and then base64 decode it:
import base64
flag = '0x53465243657a467558336b7764584a66616a4231636d347a655639354d48566664326b786246397a5a544e66644767784e56396c626d4d775a4446755a334e665a58597a636e6c33614756794d33303d'[2:]
flag = bytes.fromhex(flag)
flag = base64.b64decode(flag)
print(flag.decode())
#HTB{1n_y0ur_j0urn3y_y0u_wi1l_se3_th15_enc0d1ngs_ev3rywher3}
Flag: HTB{1n_y0ur_j0urn3y_y0u_wi1l_se3_th15_enc0d1ngs_ev3rywher3}
Small StEps
Difficulty: very easy
Description:
As you continue your journey, you must learn about the encryption method the aliens used to secure their communication from eavesdroppers. The engineering team has designed a challenge that emulates the exact parameters of the aliens’ encryption system, complete with instructions and a code snippet to connect to a mock alien server. Your task is to break it.
Code Analysis
This is RSA encryption, with a small exponent, and large-ish primes:
class RSA:
def __init__(self):
self.q = getPrime(256)
self.p = getPrime(256)
self.n = self.q * self.p
self.e = 3
def encrypt(self, plaintext):
plaintext = bytes_to_long(plaintext)
return pow(plaintext, self.e, self.n)
The main vulnerability to exploit, is that it’s a small exponent, with a small message. The fourth line of the script confirms this. It checks that the length of the message is less than 20. Considering this is textbook RSA, if m^e < n , meaning if the message raised to the power of the exponent is less than the modulus, then we can do a cube root attack.
Exploit
We can use the gmpy2 library to find the cube root of the encrypted flag:
from pwn import *
import gmpy2
host,port = '165.232.98.59',31758
conn = remote(host,port)
conn.sendlineafter(b'> ', b'E')
conn.recvuntil(b'N: ')
N = int(conn.recvline().strip().decode())
conn.recvuntil(b'The encrypted flag is: ')
enc = int(conn.recvline().strip().decode())
dec = gmpy2.iroot(enc,3)[0]
assert dec**3 < N
flag = bytes.fromhex(hex(dec)[2:])
print(flag.decode())
#HTB{5ma1l_E-xp0n3nt}
The assertion, ‘assert dec[0]**3 < int(N)’, verifies that the message raised to 3 is indeed smaller than N.
Flag: HTB{5ma1l_E-xp0n3nt}
Perfect Synchronization
Difficulty: easy
Description:
The final stage of your initialization sequence is mastering cutting-edge technology tools that can be life-changing. One of these tools is quipqiup, an automated tool for frequency analysis and breaking substitution ciphers. This is the ultimate challenge, simulating the use of AES encryption to protect a message. Can you break it?
Unfortunately for me, I need to learn to read descriptions! This was actually quite simply in the end. The class cipher reuses the same key, and salt and is using AES-ECB. Key and nonce reuse are insecure in ECB, because if you encrypt the same message twice, then the ciphertexts will be equal.
Code Analysis
class Cipher:
def __init__(self):
self.salt = urandom(15)
key = urandom(16)
self.cipher = AES.new(key, AES.MODE_ECB)
def encrypt(self, message):
return [self.cipher.encrypt(c.encode() + self.salt) for c in message]
#The main function shows exactly how this vulnerability is executed:
def main():
cipher = Cipher()
encrypted = cipher.encrypt(MESSAGE)
encrypted = "\n".join([c.hex() for c in encrypted])
with open("output.txt", 'w+') as f:
f.write(encrypted)
Each character of the message is encrypted separately. For example, let’s say we have message ‘Hello’. The ciphertext for l will be the same each time. This is where the hint for frequency analysis comes in. We aren’t meant to break the cipher, but rather identify the frequency of each characters. Honestly, I took way longer to solve this than I should have. The longer version will be posted on my blog.
Most importantly, we get a hint about the ciphertext in the fifth line of the script:
assert all([x.isupper() or x in '{_} ' for x in MESSAGE])
So the pattern of string we are looking for is all capital ascii letters + ‘{_} ‘, which will help to replace the values. With frequency analysis, we need to generate a dictionary from the most used ascii letters. Therefore, we first need to get a list of most frequently used letters. I used the one from Wikipedia and used pandas/requests/beautiful soup to parse it, following this tutorial.
Solution
Step 1: Generating a dictionary from Wikipedia:
import pandas as pd
import requests
from bs4 import BeautifulSoup
wikiurl="https://en.wikipedia.org/wiki/Letter_frequency"
table_class="wikitable sortable jquery-tablesorter"
def get_dict(wikiurl,table_class):
response=requests.get(wikiurl)
soup = BeautifulSoup(response.text, 'html.parser')
indiatable=soup.find('table',{'class':"wikitable"})
df=pd.read_html(str(indiatable))
df=pd.DataFrame(df[0])
df.columns=df.columns.droplevel(0)
df=df.reset_index(drop=True)
df['Texts']=df['Texts'].apply(lambda x: float(x.replace('%','')))
out_dict = list(df.sort_values('Texts',ascending=False)['Letter'])
return out_dict
dict_map = get_dict(wikiurl,table_class)
Step 2: Frequency Analysis
So now that we have our dictionary, we can start parsing the values by frequency. The Wikipedia dictionary didn’t include the strings ‘{_} ‘. So we will need to add them ourselves. Realistically, the space string (’ ‘) is probably the most used, so we can place it at the beginning of the list.
from collections import Counter
with open('files/output.txt','r') as inf:
data = inf.readlines()
def parse_data(data, dict_map):
data = [i.strip() for i in data]
unique_vals = list(set(data))
#len(unique_vals) == 30
plain_vals = [' '] + dict_map + [i for i in '{_}']
assert len(plain_vals) == len(unique_vals)
counts = Counter(data)
dict_items = {k: v for k, v in sorted(dict(counts).items(), key=lambda item: item[1],reverse=True)}
dict_items.update(zip(dict_items, plain_vals))
new_data =[]
for val in data:
c = dict_items[val]
new_data.append(c)
return ''.join(new_data)
cipher = parse_data(data,dict_map)
with open('files/cipher.txt','w') as outf:
outf.write(cipher)
Now, all we need to do is paste the cipher into quipqiup. It returns this, which we can see has the HTB flag, but it’s not exactly perfect:
The string we get is ‘HTB_AJSIMPLEJSUBSTITUTIONJISJWEAK}’, it’s not too complicated to see that J is meant to be ‘’, and ‘’ is meant to be ‘{’, giving us: HTB{A_SIMPLE_SUBSTITUTION_IS_WEAK}.
Flag: HTB{A_SIMPLE_SUBSTITUTION_IS_WEAK}
Multipage Recyclings
Difficulty: easy
Description: As your investigation progressed, a clue led you to a local bar where you met an undercover agent with valuable information. He spoke of a famous astronomy scientist who lived in the area and extensively studied the relic. The scientist wrote a book containing valuable insights on the relic’s location, but encrypted it before he disappeared to keep it safe from malicious intent. The old man disclosed that the book was hidden in the scientist’s house and revealed two phrases that the scientist rambled about before vanishing.
Walkthrough
Another AES challenge. Again, the cipher mode is ECB, with the same key being reused. The main encryption function is as follows:
def encrypt(self, message):
iv = os.urandom(16)
ciphertext = b''
plaintext = iv
blocks = self.blockify(message, 16)
for block in blocks:
ct = self.cipher.encrypt(plaintext)
encrypted_block = self.xor(block, ct)
ciphertext += encrypted_block
plaintext = encrypted_block
return ciphertext
Basically, the iv is encrypted with AES-ECB, then it is xored with the plaintext block. This new block is then reused as an iv. The main vulnerabilities are in the main/leak functions:
The message is repeated four times, given that it gets xored at some point, it will be easy to recover the flag.
message = pad(FLAG * 4, 16)
More importantly, the script performs a leak after encrypting the flag:
def leak(self, blocks):
r = random.randint(0, len(blocks) - 2)
leak = [self.cipher.encrypt(blocks[i]).hex() for i in [r, r + 1]]
return r, leak
[...]
ciphertext = aes.encrypt(message)
ciphertext_blocks = aes.blockify(ciphertext, 16)
r, leak = aes.leak(ciphertext_blocks)
The leak encrypts the block with AES-ECB again. Remember that in the encrypt function, each encrypted blocks is encrypted with AES-ECB, and is xored with the next block of plaintext. We can simply split the ciphertext into blocks and xor it with the leaked blocks.
Solution
from pwn import xor
ct = bytes.fromhex('bc9bc77a809b7f618522d36ef7765e1cad359eef39f0eaa5dc5d85f3ab249e788c9bc36e11d72eee281d1a645027bd96a363c0e24efc6b5caa552b2df4979a5ad41e405576d415a5272ba730e27c593eb2c725031a52b7aa92df4c4e26f116c631630b5d23f11775804a688e5e4d5624')
r = 3
phrases = ['8b6973611d8b62941043f85cd1483244', 'cf8f71416111f1e8cdee791151c222ad']
leaks = [bytes.fromhex(i) for i in phrases]
ciphertext_blocks = [ct[i:i + 16] for i in range(0, len(ct), 16)]
plaintext_blocks = [xor(i,c) for i,c in zip(ciphertext_blocks[r+1:r+3], leaks)]
#[b'_w34k_w17h_l34kz', b'}HTB{CFB_15_w34k']
#we can reverse it to get the correct string
flag = b''.join(plaintext_blocks[::-1])
print(flag.decode())
#}HTB{CFB_15_w34k_w34k_w17h_l34kz
Flag: HTB{CFB_15_w34k_w34k_w17h_l34kz}
Inside The Matrix
Difficulty: medium
Description:
As you deciphered the Matrix, you discovered that the astronomy scientist had observed that certain stars were not real. He had created two 5×5 matrices with values based on the time the stars were bright, but after some time, the stars stopped emitting light. Nonetheless, he had managed to capture every matrix until then and created an algorithm that simulated their generation. However, he could not understand what was hidden behind them as he was missing something. He believed that if he could understand the stars, he would be able to locate the secret tombs where the relic was hidden.
First, I recommend sage to run this challenge appropriately (I always test out challenges before trying to solve them).
Code Analysis
class Book:
class Book:
def __init__(self):
self.size = 5
self.prime = None
def parse(self, pt: bytes):
pt = [b for b in pt]
return matrix(GF(self.prime), self.size, self.size, pt)
def generate(self):
key = os.urandom(self.size**2)
return self.parse(key)
def rotate(self):
self.prime = random_prime(2**6, False, 2**4)
def encrypt(self, message: bytes):
self.rotate()
key = self.generate()
message = self.parse(message)
ciphertext = message * key
return ciphertext, key
Main function:
First, everything is initialised like this:
#assert len(FLAG) == 25
#[...]
book = Book()
ciphertext, key = book.encrypt(FLAG)
page_number = 1
Menu Options:
Then, we are given three options:
Then, we are given three options:
1. [L]ook at page:
This prints the ciphertext, the key and the page_number. The ciphertext and the key are printed as matrices.
print(ciphertext, key, page_number)2. [T]urn page
This will encrypt the flag again, but won’t print anything:
ciphertext, key = book.encrypt(FLAG)
page_number += 23. [C]heat
This will print the ciphertext and the key as lists:
print(f"\n{list(ciphertext)}\n{list(key)}\n")Each time the book.encrypt function is passed:
- the prime is reset
- a new key consisting of 25 random bytes is generated and passed to a matrix over FiniteField of the prime
- the message is passed to a matrix over FiniteField of the prime
- the cipher text is calculated as key*message
Solution
I used a bruteforce attack in Sage, because for the life of me I cannot understand how the math behind it works.
1. We ask the server to re-generate ciphertexts, so that we have enough values to compare and brute-force.
import string
from pwn import *
allprimes = [17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
host,port='159.65.81.51',int(31121)
valid = ['H','T','B','{','}']
def parse_res(res):
res = [eval(i) for i in res[1:-2].decode().split('\n')]
return res[0],res[1]
all_tests=[]
p=remote(host,port)
for _ in range(200):
p.recvuntil("> ")
p.sendline("T")
p.recvuntil("> ")
p.sendline("C")
res = p.recvuntil("\n\n")
ct,key = parse_res(res)
all_tests.append((list(ct),list(key)))
2. Functions for bruteforce
There are three functions I used to bruteforce the values.
The main one is check_matrix_quick:
def check_matrix_quick(ct,k):
all_mats_test=[]
for prime in allprimes:
matrixct = matrix(GF(prime), 5, 5, ct)
matrixk = matrix(GF(prime), 5, 5, k)
if tuple(list(matrix(ct)[0])) == tuple(list(matrixct)[0]):
if tuple(list(matrix(k)[0])) == tuple(list(matrixk)[0]):
try:
mat_out = matrixct/matrixk
pp = check_prime(list(mat_out)[0])
if pp == prime:
bruted = brute_mat(prime,list(mat_out))
if bruted:
good=0
zippio=list(zip(valid,bruted[0:4]+bruted[-1:]))
for i,c in zippio:
if i in c:
good +=1
if good == 5:
all_mats_test.append(bruted)
except:
pass
return all_mats_test
This function takes each ciphertext-key pair, and assigns to a matrix for each possible primes. If the first round of check passes, we divide the ciphertext with the key, so that we get the original matrix.
Then, for the divided matrix, we re-check the prime (function check_prime), by comparing to known plaintext values (the integer representation of ‘HTB{’):
def check_prime(divided_mat):
check_crs = divided_mat[0:4]
pt_chrs = (72, 84, 66, 123)
primex = 0
for i,c in zip(check_crs,pt_chrs):
for prime in allprimes:
if c%prime == i:
primex=prime
else:
pass
return primex
If this check returns true, and matches the prime we previously checked, we then brute force the matrix again, this time checking every integer representation of ‘ascii.printable’ characters mod prime, and comparing it to the value in the divided matrix. If it matches, then it will append the char as a potential value. It’s essential to check every possible option, because more than one value can be true.
def brute_mat(primex,divided_mat):
divided_mat = [item for sublist in divided_mat for item in sublist]
found = []
for c in divided_mat:
cmap=[]
for i in [ord(i) for i in string.printable]:
if i%primex == c:
cmap.append(chr(i))
found.append(cmap)
return found
Finally, if the brute_mat function comes back True (ie – it’s not empty), we check the output a final time: if the first fourth characters match ‘HTB{’, and the last character matches ‘}’, then we can safely say that we checked all potential options.
Every single output of the ‘check_matrix_quick’ function, which essentially is a bunch of steps to arrive to the the ‘brute_mat’ function, will be appended to a list.
The brute_mat function returns a list of list of potential characters at each position of the matrix. I found that the fastest way to retrieve the flag was to make a new list, at every position.
Basically, we brute-forced 200 ciphertext-key pairs. Every single combination tested returned a list of list of potential characters for each position in the matrix. This is an example of one of the brute-forced outputs:
[['H', 'w'], ['%', 'T'], ['B', 'q'], ['L', '{'], ['=', 'l'], ['0', '_'], ['0', '_'], ['\r', '<', 'k'], ['0', '_'], ['@', 'o'], ['E', 't'], ['0', '_'], ['7', 'f'], ['\n', '9', 'h'], ['3', 'b'], ['0', '_'], ['D', 's'], ['E', 't'], ['4', 'c'], ['C', 'r'], ['D', 's'], ['!', 'P'], ['!', 'P'], ['!', 'P'], ['N', '}']]So the first item in each of these lists is the first character of the flag, etc etc… To clean things up, we can group all bruteforced lists by character position, then check each position for the characters that occurs the most. With around 200 values, it’s a precise way of doing it. Thus, the final code is:
def brute_all_matrices(all_tests):
valid_brutes=[]
plain_text = []
for i in range(len(all_tests)):
testct=all_tests[i][0]
testk=all_tests[i][1]
x = check_matrix_quick(testct,testk)
if len(x) == 1:
valid_brutes.append(x[0])
for i in range(25):
flat_vals = [item for sublist in [val[i] for val in valid_brutes] for item in sublist]
max_char = max(flat_vals,key=flat_vals.count)
plain_text.append(max_char)
return ''.join(plain_text)
flag = brute_all_matrices(all_tests)
print(flag)
#HTB{l00k_@t_7h3_st4rs!!!}
Flag: HTB{l00k_@t_7h3_st4rs!!!}
Elliptic Labyrinth
Difficulty: medium
Description: As you navigate through the labyrinth inside the tomb, you encounter GPS inaccuracies that make it difficult to determine the correct path to the exit. Can you overcome the technical issues and use your instincts to find your way out of the maze?
First, I recommend sage to run this challenge appropriately (I always test out challenges before trying to solve them).
Code Analysis
This is an Elliptic Curve challenge, with a random prime and random parameters. The function ‘get_random_point’ is the only thing really going on, and it returns a random point on the curve.
There are three choices in the menu:
- Retrieve the values of p, a, b. Except the bits of a and b are truncated. The amount by which it is truncated is ‘random’, it’s any number in range (170,341).
- Print a random point on the curve
- Get the encrypted flag. The flag is encrypted with AES-CBC. The key is the sha256 hash of ( a^b%p ) in bytes. So to decrypt the flag, we need to find the values of a, b, and p.
Exploit
This is actually a very straight forward challenge. If we have the coordinates of two points on the curve, and the value of p, we can retrieve the values of a and b.
import json
from hashlib import sha256
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from pwn import *
host,port = '188.166.152.84',int(32079)
conn = remote(host,port)
conn.sendlineafter(b"> ", b'1')
params = conn.recvline()
p = eval(json.loads(params.strip())['p'])
conn.sendlineafter(b"> ", b'2')
p1 = conn.recvline()
A = json.loads(p1.strip())
conn.sendlineafter(b"> ", b'2')
p2 = conn.recvline()
B = json.loads(p2.strip())
conn.sendlineafter(b"> ", b'3')
ciph = conn.recvline()
ciph = json.loads(ciph.strip())
With those values, we can do a parameter recovery attack.
def attack(p, x1, y1, x2, y2):
"""
Recovers the a and b parameters from an elliptic curve when two points are known.
:param p: the prime of the curve base ring
:param x1: the x coordinate of the first point
:param y1: the y coordinate of the first point
:param x2: the x coordinate of the second point
:param y2: the y coordinate of the second point
:return: a tuple containing the a and b parameters of the elliptic curve
"""
a = pow(x1 - x2, -1, p) * (pow(y1, 2, p) - pow(y2, 2, p) - (pow(x1, 3, p) - pow(x2, 3, p))) % p
b = (pow(y1, 2, p) - pow(x1, 3, p) - a * x1) % p
return int(a), int(b)
x1,y1 = eval(A['x']),eval(A['y'])
x2,y2 = eval(B['x']),eval(B['y'])
a,b=attack(p, x1, y1, x2, y2)
Now, we just need to decrypt the ciphertext to get the flag!
enc,iv = bytes.fromhex(ciph['enc']),bytes.fromhex(ciph['iv'])
key = sha256(long_to_bytes(pow(a, b,p))).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
pt = unpad(cipher.decrypt(enc),16)
print(pt.decode())
#HTB{d3fund_s4v3s_th3_d4y!}
Flag: HTB{d3fund_s4v3s_th3_d4y!}
Converging Visions
Difficulty: hard
Description: As you hold the relic in your hands, it prompts you to input a coordinate. The ancient scriptures you uncovered near the pharaoh’s tomb reveal that the artifact is capable of transmitting the locations of vessels. The initial coordinate must be within proximity of the vessels, and an algorithm will then calculate their precise locations for transmission. However, you soon discover that the coordinates transmitted are not correct, and are encrypted using advanced alien techniques to prevent unauthorized access. It becomes clear that the true coordinates are hidden, serving only to authenticate those with knowledge of the artifact’s secrets. Can you decipher this alien encryption and uncover the genuine coordinates to locate the vessels and destroy them?
First, I recommend sage to run this challenge appropriately (I always test out challenges before trying to solve them).
Code Analysis
This is another Elliptic Curve challenge. First thing to notice, the values of p, a and b are imported. Meaning, they will remain constant wether we close the connection or not.
class Relic:
class Relic:
def __init__(self, p, a, b):
self.E = EllipticCurve(GF(p), [a, b])
self.P = None
self.EP = None
self.p = p
self.prng = PRNG(p, a, b)
def setupPoints(self, x):
if x >= self.p:
return 'Coordinate greater than curve modulus'
try:
self.P = self.E.lift_x(Integer(x))
self.EP = self.P
except:
return 'Point not on curve'
return ('Point confirmed on curve', self.P[0], self.P[1])
def nextPoints(self):
seed, enc_seed = self.prng.rotate()
self.P *= seed
self.EP *= enc_seed
return ('New Points', self.EP[0], self.EP[1], self.P[0], self.P[1])
The prng is initialized with the PRNG class:
class PRNG:
class PRNG:
def __init__(self, p, mul1, mul2):
self.mod = p * 6089788258325039501929073418355467714844813056959443481824909430411674443639248386564763122373451773381582660411059922334086996696436657009055324008041039
self.exp = 2
self.mul1 = mul1
self.mul2 = mul2
self.inc = int.from_bytes(b'Coordinates lost in space', 'big')
self.seed = randint(2, self.mod - 1)
def rotate(self):
self.seed = (self.mul1 * pow(self.seed, 3) + self.mul2 * self.seed +
self.inc) % self.mod
return self.seed, pow(self.seed, self.exp, self.mod)
Essentially, each time we ask for a new point, the seed is multiplied.
inc = 423298202838516040093965914645844180330692880951980532523877
seed = (a*seed^3 + b*seed + inc) % prng.mod
enc_seed = seed^2 % prng.mod
which can be re-written as:
x = seed
enc_seed = (ax^3 + bx + inc % prng.mod)^2%prng.modMain function
The menu gives us three choices:
- Setup Point
Enter coordinate x. The coordinate is passed to the class Relic, and if the point is on the curve, then point P will be initialised. If it’s not on the curve, it will tell us ‘Point not on curve’, if it’s bigger than p, it will return ‘Coordinate greater than curve modulus’. So we have ways to recover P through this option.
- Receive new point
The function nextPoints in the class Relic returns four values, the coordinates of point EP multiplied by the enc_seed and the coordinates of point P multiplied by the seed (both seeds are initialised by the PRNG class).
- Find true point
Here, we are asked to enter coordinates x, and y. The server will call the nextPoints() function, and compare our values to its output. Important thing to keep in mind, the points being verified are the points of P, aka the value multiplied by the normal seed, not the encrypted seed. The points we receive in option 2 are encrypted with the enc_seed.
Our options are limited, we can only chose to place the original point P on the curve, and then ask for the point EP, which is at first EP = point P * enc_seed, and then becomes EP = EP * enc_seed.
The first thing we need to do, is to recover the parameters.
Exploit
1. Modulus Recovery
The last line of code called before executing main, which I unfortunately missed, is to make sure that p.bit_length() == 256. I took SOOO Long to find it during the CTF, but now I found a code that basically does what I was doing manually snif snif.
host,port='161.35.168.118',int(31942)
conn = remote(host,port)
def recover_modulus(conn):
def is_leq(m):
conn.sendlineafter(b'> ',b'1')
conn.sendlineafter(b'x: ', str(m).encode())
res = conn.recvline().decode().strip()
return res == 'Coordinate greater than curve modulus'
l, u = 0, 2**256
m = 2**255
while l + 1 != u:
if is_leq(m): u = m
else: l = m
m = (u + l) // 2
return m
p = recover_modulus(conn)
We can quickly check if its correct by sending values in range p-2,p+2
for i in range(p-2,p+2):
conn.sendlineafter(b'> ',b'1')
conn.sendlineafter(b'x: ', str(i).encode())
res = conn.recvline().decode().strip()
print(res)
p+1 is the ‘alarm’ value, aka, the value that tells us that it’s greater than the modulus, so that’s our modulus!
2. Parameter Recovery
To recover the parameters, we just need to ask for a couple of points, then it will be easy to recreate the curve. The code is from here.
def get_points(conn):
points = []
for i in range(1,100):
conn.sendlineafter(b'> ',b'1')
conn.sendlineafter(b'x: ', str(i).encode())
res = conn.recvline().decode().strip()
if 'Point confirmed on curve' not in res:
pass
else:
res = eval(res)
points.append((res[1],res[2]))
if len(points) == 2:
break
return points
def parameter_recovery(p, x1, y1, x2, y2):
a = pow(x1 - x2, -1, p) * (pow(y1, 2, p) - pow(y2, 2, p) - (pow(x1, 3, p) - pow(x2, 3, p))) % p
b = (pow(y1, 2, p) - pow(x1, 3, p) - a * x1) % p
return int(a), int(b)
p = p+1
points = get_points(conn)
x1,y1,x2,y2=points[0][0],points[0][1],points[1][0],points[1][1]
a,b = parameter_recovery(p,x1,y1,x2,y2)
Now that we have our parameters, and the modulus, we can reconstruct the curve and some of the PRNG variables.
3. Curve Reconstruction
Checking the Curve:
E = EllipticCurve(GF(p), [0, 0, 0, a, b])
E.order()
#91720173941422125335466921700213991383508377854521057423162397714341988797837
When the order of a curve is equal to the modulus (which is the case here), then we have an anomolous curve. These curves are vulnerable to Smart’s Attack, and we can easily recover the multiplied values.
Having identified the vulnerability, we can now move on to getting the next point – aka the encrypted point. It’s important to remember that the server calculates everything according to the point we send first. For the purpose of this, I’m going to resend point the coordinate for x=4, and get the next values.
conn.close()
conn = remote(host,port)
def get_vals(conn):
conn.sendlineafter(b'> ',b'1')
conn.sendlineafter(b'x: ', str(4).encode())
res = conn.recvline().decode().strip()
P = (eval(res)[1],eval(res)[2])
conn.sendlineafter(b'> ',b'2')
conn.recvline().decode().strip()
res = conn.recvline().decode().strip()
Q = (eval(res)[1],eval(res)[2])
return P,Q
Pv,Qv=get_vals(conn)
assert E.lift_x(ZZ(Pv[0]))[1] == ZZ(Pv[1])
assert E.lift_x(ZZ(Qv[0]))[1] == ZZ(Qv[1])
P = E(Pv)
Q = E(Qv)
If the assertion fails, then we need to re-call the get_vals function.
4. Smart’s Attack
Here is the code I used, copied from here
def _lift(E, P, gf):
x, y = map(ZZ, P.xy())
for point_ in E.lift_x(x, all=True):
_, y_ = map(gf, point_.xy())
if y == y_:
return point_
def attack(G, P):
E = G.curve()
gf = E.base_ring()
p = gf.order()
assert E.trace_of_frobenius() == 1, f"Curve should have trace of Frobenius = 1."
E = EllipticCurve(Qp(p), [int(a) + p * ZZ.random_element(1, p) for a in E.a_invariants()])
G = p * _lift(E, G, gf)
P = p * _lift(E, P, gf)
Gx, Gy = G.xy()
Px, Py = P.xy()
return int(gf((Px / Py) / (Gx / Gy)))
enc_seed = attack(P,Q)
So, at first, I tripped out, because the size of enc_seed was 255, whereas when I tried out the PRNG by myself, it was around the size of the modulus (767 bits). But thennnnnnn, I realized, that since the curve where this seed is used is on a way smaller field, it doesn’t matter whether we recover the full encrypted seed or not, as the seed will automatically be modular to p. So this first seed we recovered, is the value of encrypted seed, meaning, it’s the value of the modified seed^2 % mod.
Finding the inverse of the enc_seed returned by smart attack mod prng.mod, and multiplying that with point Q gives us point P, which confirms the whole order/finite field thing.
mod = p*6089788258325039501929073418355467714844813056959443481824909430411674443639248386564763122373451773381582660411059922334086996696436657009055324008041039
inc = int.from_bytes(b'Coordinates lost in space', 'big')
invdx = pow(enc_seed, -1,mod)
assert Q==P*enc_seed
assert P==Q*invdx
To retrieve the original seed, we can use sage, and reconstruct the prng rotate function. With sage, we can find the value of x by constructing a polynomial. For every root found, we test it against the original point, if they all have the same result, then we are safe.
def seedmult(seed):
return (a * pow(seed, 3) + b * seed +inc) % mod
R = PolynomialRing(Zmod(p),'x')
fx=R((a * pow(x, 3) + b * x +inc)**2) - enc_seed
rvals = fx.roots()
testroots=[i[0] for i in rvals]
recovered_vs = []
for i in testroots:
xv=int(i)
fxio=seedmult(xv)
Recovered=(P*fxio)
recovered_vs.append(Recovered)
potential_points = list(set(recovered_vs))
assert len(potential_points) == 1
Now, we need to recover the value of the next seed. The points we recovered (potential_points) are point E. The point the server is asking is this point E multiplied by the next seed. We re-do the attack on the original point, and the recovered point to find this specific seed. Then, we just need to apply the seed multiplication function to get the new seed, and the next point:
potential_seeds = []
for recovered_point in potential_points:
enc_seed_2=attack(P, recovered_point)
if P*enc_seed_2 == Recovered:
potential_seeds.append((enc_seed_2,recovered_point))
if len(potential_seeds) == 1:
needed_point = potential_seeds[0][1]*seedmult(potential_seeds[0][0])
Normally, there should be only one value in potential_seeds. We can send it to the server to get the flag:
conn.sendlineafter(b'> ',b'3')
conn.sendlineafter(b'x: ', str(needed_point[0]).encode())
conn.sendlineafter(b'y: ', str(needed_point[1]).encode())
res = conn.recvline().decode().strip()
print(res)
#You have confirmed the location. It's dangerous however to go alone. Take this: HTB{0Racl3_AS_a_f3A7Ur3_0n_W3aK_CURV3_aND_PRN9??_7H3_s3cur17Y_0F_0uR_CRyP70Sys73M_w1LL_c0LLAp53!!!}
