Cyber Apocalypse 2023: Crypto

Mar 23, 2023 9293 words 44 minutes

Contents

https://i.imgur.com/zjySC02.jpg — Cyber Apocalypse 2023

For the past five days, I have been competing solo in the Cyber Apocalypse CTF 2023. During this time, I was able to solve all of the pwn challenges and 10 out of the 11 crypto challenges. In this writeup, I will be sharing my solutions for some of the crypto challenges that I solved. If you’re interested in reading about the pwn challenges, check out my other post.

https://i.imgur.com/0Fe0Nyw.png — I was able to solve 10 out of 11 crypto challenges

Crypto

Multipage Recyclings

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.

Initial Analysis

For this challenge, we were given two file called source.py and output.txt. Let’s take a look at the source.py first.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import random, os

FLAG = b'HTB{??????????????????????}'


class CAES:

    def __init__(self):
        self.key = os.urandom(16)
        self.cipher = AES.new(self.key, AES.MODE_ECB)

    def blockify(self, message, size):
        return [message[i:i + size] for i in range(0, len(message), size)]

    def xor(self, a, b):
        return b''.join([bytes([_a ^ _b]) for _a, _b in zip(a, b)])

    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

    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


def main():
    aes = CAES()
    message = pad(FLAG * 4, 16)

    ciphertext = aes.encrypt(message)
    ciphertext_blocks = aes.blockify(ciphertext, 16)

    r, leak = aes.leak(ciphertext_blocks)

    with open('output.txt', 'w') as f:
        f.write(f'ct = {ciphertext.hex()}\nr = {r}\nphrases = {leak}\n')


if __name__ == "__main__":
    main()

Based on the given source code, the main logic for the code is as follows:

Concatenate the flag with itself 4 times.
Pad the flag so that it can be split into multiple 16-bytes block
Encrypt it with AES
Provide some leaks

Let’s try to understand the encrypt method first. If you read it, it is actually an implementation of AES-CFB.

So, now we know the AES type, let’s take a look at what the leak that the source generates is. It turns out that the given leak was two decrypted blocks that exist in the ciphertext. Therefore, given the leaks, our target is to somehow recover our flag.

Solution

Please refer to the image above. As you can see, to decrypt the plaintext, what AES-CFB does is actually like this,

$$ p_i = C(c_{i-1}) \oplus c_{i} $$

where $C$ is the block cipher encryption, $c$ is the ciphertext, and $p$ is the plaintext. Notice that the leak is actually the $C(c_{i-1})$ result, where $i$ is random. Additionally, the given leak is always two consecutive blocks, and if we have the $C(c_{i-1})$ and $C(c_{i})$, we can actually get the plaintext block for at least two blocks. After testing to XOR the blocks one by one, I found that the leak is $C(c_3)$ and $C(c_4)$. By XORing them with $c_4$ and $c_5$, respectively, we were able to obtain the flag.

Full Script

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


from pwn import *

def blockify(message, size):
    return [message[i:i + size] for i in range(0, len(message), size)]

ct = bytes.fromhex('bc9bc77a809b7f618522d36ef7765e1cad359eef39f0eaa5dc5d85f3ab249e788c9bc36e11d72eee281d1a645027bd96a363c0e24efc6b5caa552b2df4979a5ad41e405576d415a5272ba730e27c593eb2c725031a52b7aa92df4c4e26f116c631630b5d23f11775804a688e5e4d5624')
ct_blocks = blockify(ct, 16)

leak_3 = bytes.fromhex('8b6973611d8b62941043f85cd1483244')
leak_4 = bytes.fromhex('cf8f71416111f1e8cdee791151c222ad')
print(xor(ct_blocks[4], leak_3))
print(xor(ct_blocks[5], leak_4))

Flag: HTB{CFB_15_w34k_w34k_w17h_l34kz}

Inside the Matrix

Description

As you deciphered the Matrix, you discovered that the astronomy scientist had observed that certain stars were not real. He had created two 5x5 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.

Initial Analysis

For this challenge, we were given a file called server.py. Let’s check that.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


from sage.all_cmdline import *
# from utils import ascii_print
import os

FLAG = b"HTB{????????????????????}"
assert len(FLAG) == 25


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


def menu():
    print("Options:\n")
    print("[L]ook at page")
    print("[T]urn page")
    print("[C]heat\n")
    option = input("> ")
    return option


def main():
    book = Book()
    ciphertext, key = book.encrypt(FLAG)
    page_number = 1

    while True:
        option = menu()
        if option == "L":
            # ascii_print(ciphertext, key, page_number)
            print(ciphertext, key, page_number)
        elif option == "T":
            ciphertext, key = book.encrypt(FLAG)
            page_number += 2
            print()
        elif option == "C":
            print(f"\n{list(ciphertext)}\n{list(key)}\n")
        else:
            print("\nInvalid option!\n")


if __name__ == "__main__":
    try:
        main()
    except Exception as e:
        print(f"An error occurred: {e}")

Reading through the code, there are three menus that we can interact with:

L, which prints the ciphertext, key, and page_number
T, which encrypts the FLAG and stores the encryption result to ciphertext and key
C, which is the same as L, but prints it as a list format.

The encryption scheme is as follows:

Parse the FLAG to a matrix 5x5 under GF(prime).
- prime is randomized from range ($2^4$ - $2^6$)
Generate random key and parse it to matrix 5x5 under GF(P).
Do matrix multiplication between parsed FLAG and the parsed key.
Return the encryption result and the key itself.

Note that the server doesn’t return the value of prime. Therefore, the task for this challenge is to recover the flag given an encrypted flag and a key.

Solution

Because we know the key value, we actually can just simply multiple the encrypted flag with the inverse of key. Take a look on the below equations,

$$ \begin{align*} c = mk \\ mkk^{-1} = ck^{-1} \\ m = ck^{-1}\\ \end{align*} $$

where $m$ is message, $c$ is encryted message, and $k$ is the key. To do the above equation, we need to know the prime value first. Notice that the range is actually small, so we can actually just bruteforce it. The possible primes that is used in this encryption scheme is actually only [17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]. So, by bruteforcing the prime, we can recover the matrix of the parsed FLAG.

However, there is a problem with this one. Notice that the parsed matrix elements was reduced with modulo of the chosen prime. The prime is small, which means that the parsed matrix of FLAG each element’s value is actually not the original value of the FLAG char. So, we need to think on how to recover this.

The answer is we can use Chinese Remainder Theorem to recover the original FLAG. Notice that if we recover three pairs of ciphertext and key with different prime, after we recover the $m$, we actually can rearrange the value as follows,

$$ x_{i,j} = m_{1,i,j} \mod p_1 \\ x_{i,j} = m_{2,i,j} \mod p_2 \\ x_{i,j} = m_{3,i,j} \mod p_3 \\ $$

where $x_{i,j}$ is the original element of FLAG char on the matrix $m[i][j]$, $m_{1,i,j}, m_{2,i,j}, m_{3,i,j}$ is the messages recovered from the three pairs, and $p_1, p_2, p_3$ is the recovered primes. The above setup can be solved with Chinese Remainder Theorem, where the recovered $x$ will be the original char of the FLAG.

To summarize, what we need to do to solve this challenge:

Recover three reduced messages (in form of matrix) from the three pairs of (ct, key) from the server
For each element in the recovered messages, perform CRT.

Full Script

Below is my full script (sage script):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


from pwn import *

# Based on `self.prime = random_prime(2**6, False, 2**4)`
possible_primes = [17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]

while True:
    print(f'Try to bruteforce...')
    # r = remote(b'159.65.86.238', int(32021))
    r = process(['python3', 'server.py'])

    # Collect 3 pair of cts and keys with hope that all of them are unique.
    # If not unique, just reconnect.
    cts = []
    keys = []
    for i in range(3):
        r.sendlineafter(b'> ', b'C')
        r.recvline()
        ct = eval(r.recvline().strip())
        key = eval(r.recvline().strip())
        cts.append(ct)
        keys.append(key)
        r.sendlineafter(b'> ', b'T')

    # We will bruteforce the possible primes
    for p0 in possible_primes:
        for p1 in possible_primes:
            for p2 in possible_primes:
                if p0 == p1 or p0 == p2 or p1 == p2:
                    continue
                primes = [p0, p1, p2]
                msgs = []
                for i in range(3):
                    try:
                        # Try to calculate msg by doing ct*key^-1
                        mat_ct = Matrix(GF(primes[i]), cts[i])
                        mat_key = Matrix(GF(primes[i]), keys[i])
                        msgs.append(mat_ct * mat_key.inverse())
                    except:
                        # If failed, that means the inverse is failed,
                        # which mean we used the wrong prime
                        pass
                if len(msgs) < 3:
                    # Continue to bruteforce the correct primes
                    continue

                '''
                Now, we have this equations
                x = msgs[0][i][j] mod primes[0]
                x = msgs[1][i][j] mod primes[1]
                x = msgs[2][i][j] mod primes[2]
                Do CRT to retrieve x, which is the character of the flag
                '''
                test_m_arr = []
                for chr_idx in range(25):
                    test_m = []
                    for msg_idx in range(len(msgs)):
                        i = chr_idx // 5
                        j = chr_idx % 5
                        test_m.append(int(msgs[msg_idx][i][j]))
                    test_m_arr.append(test_m)
                flag = ''
                for test_m in test_m_arr:
                    flag_char = crt(test_m, primes)
                    flag += chr(flag_char)
                if 'HTB' in flag:
                    # We found the flag
                    print(flag)
                    exit()

Flag: HTB{l00k_@t_7h3_st4rs!!!}

Elliptic Labyrinth

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?

Initial Analysis

For this challenge, we were given a file called server.py. The provided code is shown below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


import os, json
from hashlib import sha256
from random import randint
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from sage.all_cmdline import *
# from secret import FLAG
FLAG = b'flag{fake_flag}'


class ECC:

    def __init__(self, bits):
        self.p = getPrime(bits)
        self.a = randint(1, self.p)
        self.b = randint(1, self.p)

    def gen_random_point(self):
        return EllipticCurve(GF(self.p), [self.a, self.b]).random_point()


def menu():
    print("1. Get parameters of path")
    print("2. Get point in path")
    print("3. Try to exit the labyrinth")
    option = input("> ")
    return option


def main():
    ec = ECC(512)
    print(f'{ec.p = }')
    print(f'{ec.a = }')
    print(f'{ec.b = }')

    while True:
        choice = menu()
        if choice == '1':
            r = randint(ec.p.bit_length() // 3, 2 * ec.p.bit_length() // 3)
            print(
                json.dumps({
                    'p': hex(ec.p),
                    'a': hex(ec.a >> r),
                    'b': hex(ec.b >> r)
                }))
        elif choice == '2':
            A = ec.gen_random_point()
            print(json.dumps({'x': hex(A[0]), 'y': hex(A[1])}))
        elif choice == '3':
            iv = os.urandom(16)
            key = sha256(long_to_bytes(pow(ec.a, ec.b, ec.p))).digest()[:16]
            cipher = AES.new(key, AES.MODE_CBC, iv)
            flag = pad(FLAG, 16)
            print(
                json.dumps({
                    'iv': iv.hex(),
                    'enc': cipher.encrypt(flag).hex()
                }))
        else:
            print('Bye.')
            exit()


if __name__ == '__main__':
    main()

Upon analyzing the given code, we can deduce that this is an ECC (Elliptic Curve) challenge. When we connect to the server, we are presented with three menus:

The first one is used to dump some information related to the ECC parameters, which includes:
- $p$
- $a_{msb}$ (a >> r) where r is a random number within the range of p.bit_length()/3 until 2*p.bit_length()/3
- $b_{msb}$ (b >> r)
The second menu allows us to generate a random point on the curve.
The third menu allows us to dump the encrypted flag (with AES), where the AES key is encrypted with the key sha256(long_to_bytes(pow(ec.a, ec.b, ec.p))).digest()[:16].

Therefore, based on our initial analysis, our objective in this challenge is to recover the ECC parameters (a, b, p).

Solution

Well, we can recover p from the first menu as it is provided. Now, we need to recover a and b. It’s important to remember that the equation for the ECC curve is as follows: $$ y^2 = x^3 + ax + b \mod p $$

Now, remember that from the second menu, we can generate many points that reside on the curve. As you can see, if we have two points, it becomes two equations with two unknown variables, which are solvable (and for this challenge, we actually don’t need the leak of a and b at all!).

So, to recover the a and b, we just need to recover two points, and then subtract it to remove a. See below equations: $$ \begin{align} y_1^2 = x_1^3 + ax_1 + b \mod p \\ y_2^2 = x_2^3 + ax_2 + b \mod p \\ \end{align} $$

If we subtract the above equations, we will get a new equation as follows $$ \begin{align} (y_1^2 - y_2^2) = (x_1^3 -x_2^3) + a(x_1-x_2) \mod p \\ ((y_1^2 - y_2^2) - (x_1^3 -x_2^3))(x_1-x_2)^{-1} = a \mod p \\ \end{align} $$

Now that we can recover a from the above equation, recovering b becomes trivial. $$ b = y^2 - x^3 - a*x $$

Once we have recovered a and b, we can retrieve the AES key and use it to decrypt the encrypted flag. The following is the solver that can be used to do that (sage script):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


from pwn import *  
import os, json
from hashlib import sha256
from random import randint
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

r = remote(b'167.71.143.44', int(31762))
r.sendlineafter(b'> ', b'1') 
out = json.loads(r.recvline().strip()) 
p = int(out['p'], 16) 
partial_a = int(out['a'], 16) 
partial_b = int(out['b'], 16) 
xy_data = [] 
for i in range(2):
    r.sendlineafter(b'> ', b'2') 
    xy_out = json.loads(r.recvline().strip()) 
    xy_data.append([int(xy_out['x'], 16), int(xy_out['y'], 16)])
r.sendlineafter(b'> ', b'3')
enc_out = json.loads(r.recvline().strip())
iv = bytes.fromhex(enc_out['iv'])
enc = bytes.fromhex(enc_out['enc'])

'''
y1^2 = x1^3 + a*x1 + b mod p
y2^2 = x2^3 + a*x2 + b mod p
----------------------------- subtract
(y1^2 - y2^2) = (x1^3 -x2^3) + a*(x1-x2) mod p
((y1^2 - y2^2) - (x1^3 -x2^3))*(x1-x2)^-1 = a mod p
'''
x1, y1 = xy_data[0]
x2, y2 = xy_data[1]
sol_a = (((y1^2 - y2^2) - (x1^3 -x2^3))*inverse_mod(x1-x2, p)) % p
sol_b = (y1^2 - x1^3 - sol_a*x1) % p
print(f'{sol_a = }')
print(f'{sol_b = }')

key = sha256(long_to_bytes(pow(int(sol_a), int(sol_b), p))).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
print(f'Flag: {cipher.decrypt(enc)}')

Flag: HTB{d3fund_s4v3s_th3_d4y!}

Elliptic Labyrinth Revenge

Description

Initial Analysis

This is the revenge of the previous challenge. The only difference is that in the previous challenge, we could retrieve multiple points, but for this challenge, we can only retrieve one point.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


import os, json
from hashlib import sha256
from random import randint
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from sage.all_cmdline import *
FLAG = b'flag{fake_flag}'


class ECC:

    def __init__(self, bits):
        self.p = getPrime(bits)
        self.a = randint(1, self.p)
        self.b = randint(1, self.p)

    def gen_random_point(self):
        return EllipticCurve(GF(self.p), [self.a, self.b]).random_point()


def menu():
    print("1. Get parameters of path")
    print("2. Try to exit the labyrinth")
    option = input("> ")
    return option


def main():
    ec = ECC(512)
    print(f'{ec.p = }')
    print(f'{ec.a = }')
    print(f'{ec.b = }')

    A = ec.gen_random_point()
    print("This is the point you calculated before:")
    print(json.dumps({'x': hex(A[0]), 'y': hex(A[1])}))

    while True:
        choice = menu()
        if choice == '1':
            r = randint(ec.p.bit_length() // 3, 2 * ec.p.bit_length() // 3)
            print(
                json.dumps({
                    'r': r,
                    'p': hex(ec.p),
                    'a': hex(ec.a >> r),
                    'b': hex(ec.b >> r)
                }))
        elif choice == '2':
            iv = os.urandom(16)
            key = sha256(long_to_bytes(pow(ec.a, ec.b, ec.p))).digest()[:16]
            cipher = AES.new(key, AES.MODE_CBC, iv)
            flag = pad(FLAG, 16)
            print(
                json.dumps({
                    'iv': iv.hex(),
                    'enc': cipher.encrypt(flag).hex()
                }))
        else:
            print('Bye.')
            exit()


if __name__ == '__main__':
    main()

However, it’s important to remember that we actually have a leak for the a and b parameters, which are their most significant bits (MSBs). Thus, we can use that leak to retrieve them.

Solution

Let’s take a look at how the leak is generated.

1
2
3
4
5
6
7
8
9


r = randint(ec.p.bit_length() // 3, 2 * ec.p.bit_length() // 3)
print(
    json.dumps({
        'r': r,
        'p': hex(ec.p),
        'a': hex(ec.a >> r),
        'b': hex(ec.b >> r)
    })
)

Notice that the p.bit_length() is 512. Therefore, the range of r is from 170 to 340, which can be bruteforced. It is important to remember that the ECC equation is as follows:

$$ y^2 = x^3 + ax + b \mod p $$

And with our leak, the equation can be rearranged as follows:

$$ y^2 = x^3 + (2^ra_{leaked} + c) + {2^rb_{leaked} + d} \mod p $$

Notice that the value of r is bruteforce-able, and the values of $c$ and $d$ are small compared to the other values ($y^2$, $x^3$, and $2^r$). In this type of challenge, we can try to retrieve the values of $c$ and $d$ value with Coppersmith.

We can reuse the defund implementation of coppersmith to perform the coppersmith attack on the equation.

After retrieving the value $c$ and $d$, we will be able to recover the values of $a$ and $b$.

Below is my solver script (sage script):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94


from pwn import *  
import os, json
from hashlib import sha256
from random import randint
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

import itertools

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 []

r = remote(b'165.232.100.46', int(31844))

# Retrieve x y
r.recvuntil(b':\n')
xy_out = json.loads(r.recvline().strip())
x, y = int(xy_out['x'], 16), int(xy_out['y'], 16)

# Retrieve partial_a and partial_b
r.sendlineafter(b'> ', b'1') 
out = json.loads(r.recvline().strip()) 
p = int(out['p'], 16) 
partial_a = int(out['a'], 16) 
partial_b = int(out['b'], 16)
r.sendlineafter(b'> ', b'2')
enc_out = json.loads(r.recvline().strip())
iv = bytes.fromhex(enc_out['iv'])
enc = bytes.fromhex(enc_out['enc'])

'''
f(x) = x^3 - y^2 + (partial_a*2^r + c)*x + (partial_b*2^r + d) mod p
c and d is small, r is bruteforceable
bounds = [2^r, 2^r]
'''
print(f'{p = }')
for guess_r in range(p.bit_length() // 3, 2*p.bit_length() // 3):
	P.<c, d> = PolynomialRing(Zmod(p))
	bound = 2^(guess_r)
	print(f'{guess_r = }')
	f = x^3 - y^2 + x*(partial_a*2^guess_r + c) + (partial_b*2^guess_r +d)
	bounds = (bound, bound)
	sols = small_roots(f, bounds, m = 7, d=3)
	if len(sols) > 0:
		for sol in sols:
			sol_a = int(sol[0]) + partial_a*2^guess_r
			sol_b = int(sol[1]) + partial_b*2^guess_r
			key = sha256(long_to_bytes(pow(int(sol_a), int(sol_b), p))).digest()[:16]
			cipher = AES.new(key, AES.MODE_CBC, iv)
			print(f'Flag: {cipher.decrypt(enc)}')
		exit()

Flag: HTB{y0u_5h0u1d_h4v3_u53d_c00p325m17h}

Colliding Heritage

Description

As you arrive at the location of the relic, you discover an ancient tomb that appears to have no visible entrance. However, a scan of the area reveals the presence of unusual RF signals coming from a specific location. With the help of your team, you manage to create an interface to communicate with the signal-emitting device. Unfortunately, the device only grants access to descendants of the pharaoh’s left hand. Can you find a way to enter the tomb?

Initial Analysis

For this challenge, we were given a file called server.py. Below is its code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88


#!/usr/bin/env python3

import signal
from secrets import randbelow
from hashlib import md5
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long

FLAG = "HTB{???????????????????????????}"


class MD5chnorr:

    def __init__(self):
        # while True:
        #     self.q = getPrime(128)
        #     self.p = 2*self.q + 1
        #     if isPrime(self.p):
        #         break
        self.p = 0x16dd987483c08aefa88f28147702e51eb
        self.q = (self.p - 1) // 2
        self.g = 3
        self.x = randbelow(self.q)
        self.y = pow(self.g, self.x, self.p)

    def H(self, msg):
        return bytes_to_long(md5(msg).digest()) % self.q

    def sign(self, msg):
        k = self.H(msg + long_to_bytes(self.x))
        print(f'{k = }')
        r = pow(self.g, k, self.p) % self.q
        e = self.H(long_to_bytes(r) + msg)
        s = (k - self.x * e) % self.q
        return (s, e)

    def verify(self, msg, sig):
        s, e = sig
        if not (0 < s < self.q):
            return False
        if not (0 < e < self.q):
            return False
        rv = pow(self.g, s, self.p) * pow(self.y, e, self.p) % self.p % self.q
        ev = self.H(long_to_bytes(rv) + msg)
        return ev == e


def menu():
    print('[S]ign a message')
    print('[V]erify a signature')
    return input('> ').upper()[0]


def main():
    md5chnorr = MD5chnorr()
    print('g:', md5chnorr.g)
    print('y:', md5chnorr.y)
    print('p:', md5chnorr.p)

    for _ in range(3):
        choice = menu()

        if choice == 'S':
            msg = bytes.fromhex(input('Enter message> '))
            if b'I am the left hand' in msg:
                print('No!')
            else:
                sig = md5chnorr.sign(msg)
                print('Signature:', sig)

        elif choice == 'V':
            msg = bytes.fromhex(input('Enter message> '))
            s = int(input('Enter s> '))
            e = int(input('Enter e> '))
            if md5chnorr.verify(msg, (s, e)):
                if msg == b'I am the left hand':
                    print(FLAG)
                else:
                    print('Valid signature!')
            else:
                print('Invalid signature!')

        else:
            print('Invalid choice...')


if __name__ == '__main__':
    signal.alarm(30)
    main()

So, we were given a server that implements a signature scheme with the Schnorr signature algorithm. The details of the algorithm can be read on Wikipedia. The challenge shares the public key of the signature scheme (g, y, and p), and gives us three chances to use the available menus:

S, which is a menu to sign any message that we provide.
- There is a restriction that disallows messages containing the string I am the left hand.
- We get the s and e values as well, which are the signature.
V, which is a menu to validate our signature of the message.
- If the signature is valid and the message is I am the left hand, it will print the flag.

Therefore, the objective of this challenge is to retrieve the private key with two signatures that we obtain from the server so that we can sign the message I am the left hand, send it to the server, and retrieve the flag.

Solution

Notice that in this kind of signature scheme, the vulnerability usually lies in the way it generates the k (nonce) value. The k generation cannot be weak because it can be used to retrieve the private key (x).

As mentioned in the Wikipedia page that I shared before, reusing a nonce is disallowed in this kind of signature scheme. The reason is that we can recover the private key (x) if we use the same k during signing two different messages. Let’s take a look at the signing equations below to understand why we can recover k if it is being reused to sign different messages:

$$ \begin{align} s_1 = (k - xe_1) \mod q \\ s_2 = (k - xe_2) \mod q \\ \end{align} $$

If we subtract the above equation, retrieving the value of $x$ becomes very easy because we know the value of $s_1$, $s_2$, $e_1$, $e_2$ and $q$. We can rearrange those two equations to retrieve $x$.

$$ \begin{align} (s_1 - s_2) = k - k - x(e_1e_2) \mod q \\ x = -(s_1 - s_2)(e_1e_2)^{-1} \mod q \\ \end{align} $$

So, if we sign two different messages with the same k, we will be able to recover x and sign the required message.

Now that we know that we need to somehow sign two different messages with the same k value, let’s take a look at how the k is generated.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


  def H(self, msg):
      return bytes_to_long(md5(msg).digest()) % self.q

  def sign(self, msg):
      k = self.H(msg + long_to_bytes(self.x))
      print(f'{k = }')
      r = pow(self.g, k, self.p) % self.q
      e = self.H(long_to_bytes(r) + msg)
      s = (k - self.x * e) % self.q
      return (s, e)

Notice that the generation of k (nonce) is basically just md5(msg || x). As mentioned in many articles, it is easy to generate a hash collision with md5. Reading through this article helped me understand why the way this challenge generates k is weak. It is easy to generate a md5 hash collision, which means we can sign two different messages with the same k value due to the collision.

After reading that article, I realized that it is pretty simple to exploit the weakness of md5. We just need to grab two strings that have md5 collisions and use that as our messages to be signed. However, we need to be careful because the msg that we send will be appended by the x as well. Therefore, we can’t send the raw msg to the server. As mentioned in the previous article, md5 pads the msg first with some bytes during hashing. Thus, we need to send the padded message to the server instead of raw msg. This ensures that before the md5 process the bytes of appended x, both of the messages that we sent will have the same md5 state. So, when the md5 algorithm tries to process the block of the appended x, the state will be the same, which means it will produce the same hash.

Once we are able to produce the md5 collision, we can retrieve the private key x based on the previous equations that I explained because the k value is reused.

Below is my full script to recover the flag (sage script):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


from pwn import *
from hashlib import md5
from Crypto.Util.number import *

# Use two strings that has md5 collisions
m1 = bytes.fromhex('4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2')
m2 = bytes.fromhex('4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2')
assert m1 != m2

'''
After we properly padding the above string to follow the specification of MD5,
(64-bytes per block), both of the string will produce the same state.
So, if you append any same string, the produced hash will still be the same.
#
In this case, k = HASH(m11 || x) == HASH(m22 || x) will be the same.
But, HASH(r || m11) != HASH(r || m22), because the 64-bytes block are different
#
So, if we sign this two message, it is basically the same case as re-used nonce k,
which is vulnerable. Notice this.
s2-s1 = k2-k1 - x(e2-e1)

If k2 == k1, that means:
x = -1 * (s2 - s1) * (e2-e1)^-1
'''
m11 = m1 + b"\x80" + b"\x00" * 55 + p64(0x200)
m22 = m2 + b"\x80" + b"\x00" * 55 + p64(0x200)

io = remote(b'142.93.35.133', int(31079))
io.recvuntil(b': ')

# Retrieve the public key
g = int(io.recvline())
io.recvuntil(b': ')
y = int(io.recvline())
io.recvuntil(b': ')
p = int(io.recvline())
q = int((p-1)//2)

# Sign the padded messages
io.sendlineafter(b'> ', b'S')
io.sendlineafter(b'> ', m11.hex().encode())
io.recvuntil(b': ')
s1, e1 = eval(io.recvline())
io.sendlineafter(b'> ', b'S')
io.sendlineafter(b'> ', m22.hex().encode())
io.recvuntil(b': ')
s2, e2 = eval(io.recvline())

# Recover x
x = (((s2-s1) * inverse_mod(e2-e1, q)) * -1) % q
print(f'recovered x = {x}')

# Sign the required message and send it to the server
msg = b'I am the left hand'
def H(msg):
    return bytes_to_long(md5(msg).digest()) % q
k = H(msg + long_to_bytes(x))
r = pow(int(g), int(k), int(p)) % q
e = H(long_to_bytes(r) + msg)
s = (k - x * e) % q

io.sendlineafter(b'> ', b'V')
io.sendlineafter(b'> ', msg.hex().encode())
io.sendlineafter(b'> ', str(s).encode())
io.sendlineafter(b'> ', str(e).encode())

io.interactive()

Flag: HTB{w3ll_y3s_bu7_4c7ual1y_n0…}

Biased Heritage

Description

You emerge from the labyrinth to find a massive door blocking your path to the relic. It has the same authentication mechanism as the entrance, but it appears to be more sophisticated and challenging to crack. Can you devise a plan to breach the door and gain access to the relic?

Initial Analysis

This is the upgraded challenge from the previous challenge (Colliding Heritage). Let’s try to see the given server.py

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87


#!/usr/bin/env python3

import signal
from secrets import randbelow
from hashlib import sha256
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long

FLAG = "HTB{???????????????????????????????????????}"


class SHA256chnorr:

    def __init__(self):
        # while True:
        #     self.q = getPrime(512)
        #     self.p = 2*self.q + 1
        #     if isPrime(self.p):
        #         break
        self.p = 0x184e26a581fca2893b2096528eb6103ac03f60b023e1284ebda3ab24ad9a9fe0e37b33eeecc4b3c3b9e50832fd856e9889f6c9a10cde54ee798a7c383d0d8d2c3
        self.q = (self.p - 1) // 2
        self.g = 3
        self.x = randbelow(self.q)
        self.y = pow(self.g, self.x, self.p)

    def H(self, msg):
        return bytes_to_long(2 * sha256(msg).digest()) % self.q

    def sign(self, msg):
        k = self.H(msg + long_to_bytes(self.x))
        r = pow(self.g, k, self.p) % self.q
        e = self.H(long_to_bytes(r) + msg)
        s = (k - self.x * e) % self.q
        return (s, e)

    def verify(self, msg, sig):
        s, e = sig
        if not (0 < s < self.q):
            return False
        if not (0 < e < self.q):
            return False
        rv = pow(self.g, s, self.p) * pow(self.y, e, self.p) % self.p % self.q
        ev = self.H(long_to_bytes(rv) + msg)
        return ev == e


def menu():
    print('[S]ign a message')
    print('[V]erify a signature')
    return input('> ').upper()[0]


def main():
    sha256chnorr = SHA256chnorr()
    print('g:', sha256chnorr.g)
    print('y:', sha256chnorr.y)
    print('p:', sha256chnorr.p)

    for _ in range(3):
        choice = menu()

        if choice == 'S':
            msg = bytes.fromhex(input('Enter message> '))
            if b'right hand' in msg:
                print('No!')
            else:
                sig = sha256chnorr.sign(msg)
                print('Signature:', sig)

        elif choice == 'V':
            msg = bytes.fromhex(input('Enter message> '))
            s = int(input('Enter s> '))
            e = int(input('Enter e> '))
            if sha256chnorr.verify(msg, (s, e)):
                if msg == b'right hand':
                    print(FLAG)
                else:
                    print('Valid signature!')
            else:
                print('Invalid signature!')

        else:
            print('Invalid choice...')


if __name__ == '__main__':
    signal.alarm(30)
    main()

As you can see, the generation of k is changed. Now, it uses sha256 instead of md5. Up until now, there isn’t any collision found for sha256, which mean we can’t use our previous approach to solve this challenge.

Solution

Reading through the Wikipedia again, it is mentioned that:

Warning

In fact, even slight biases in the value k or partial leakage of k can reveal the private key, after collecting sufficiently many signatures and solving the hidden number problem.

So, there is another method to recover the private key x which involves exploiting a weak bias in the generation of k. Let’s take another look at the new method used to generate k and see if it has any biases.

1
2
3
4
5
6
7
8
9


def H(self, msg):
    return bytes_to_long(2 * sha256(msg).digest()) % self.q

def sign(self, msg):
    k = self.H(msg + long_to_bytes(self.x))
    r = pow(self.g, k, self.p) % self.q
    e = self.H(long_to_bytes(r) + msg)
    s = (k - self.x * e) % self.q
    return (s, e)

Notice that generation of k (nonce) is now 2 * sha256(msg || x). This is actually a weak generation. Even though the size of k is around 512 bits, the repeated sequence of bits in k reduces its entropy to only 256 bits. Therefore, k can be constructed as follows:

$$ k = 2^{256}b + b \\ k = b(2^{256} + 1) \\ $$

where $b$ is the 256 bits produced by the sha256 hashing algorithm, so there are indeed biases in the generated k, and we might be able to recover it.

This paper and writeup helped me a lot in understanding how to approach this problem. Basically, notice that the way of Schnorr signature mechanism works is actually similar to a hidden number problem. By incorporating the knowledge of how k is generated into the signature mechanism, we can obtain a new equation:

$$ \begin{align} s = k - xe \mod q \\ s = b(2^{256}+1) - xe \mod q \\ s - b(2^{256}+1) + xe = 0 \mod q \\ \end{align} $$

Notice that the $b$ value is actually smaller compared to the other value.

Usually, in this kind of setup, we can construct a lattice and use LLL to recover an unknown value that we have in the above equation. I recommend reading the write-up I mentioned above to understand the details of how lattices work, but basically, I came up with this lattice after reading through the previous paper and write-up.

$$ M = \begin{bmatrix} 1 & 0 & 0 & 0 & s_2 & s_1 \\ 0 & 2/q & 0 & 0 & e_2 & e_1 \\ 0 & 0 & 1/B & 0 & (B+1) & 0 \\ 0 & 0 & 0 & 1/B & 0 & (B+1) \\ 0 & 0 & 0 & 0 & q & 0 \\ 0 & 0 & 0 & 0 & 0 & q \\ \end{bmatrix} $$

where $B = 2^{256}$ ($B$ is bound of the b value that we’re trying to recover). It is the same like previous challenge, where we can only retrieve two signatures from the server, which is why the lattice only contains signature 1 and 2.

Using that lattice, we hope that that there exist a vector in the lattice that is small, which can be expressed as follows:

$$ \begin{pmatrix} 1 & \frac{2x}{q} & \frac{-b_2}{B} & \frac{-b_1}{B} & 0 & 0 \end{pmatrix} $$

And because the bit lengths of $x$, $q$, $b_2$, $B$, and $b_1$ is pretty much the same or close, we hope that the above vector is small enough for the lattice. To find that target vector, we can assume that if we’re trying to look for a vector in the lattice that is close to the following vector,

$$ \begin{pmatrix} 1 & 1 & -1 & -1 & 0 & 0 \end{pmatrix} $$

we will find our target vector. To find the approximation of it, we can use the Babai CVP algorithm.

If we find the target vector, that means we have successfully recovered the private key x, and the rest of the steps are the same as the previous challenge.

Below is my full script (Sage script). Note that due to the lack of signatures that we can collect (only 2), the script’s success rate is not 100%, so you might need to re-run the script multiple times.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88


from secrets import randbelow
from hashlib import sha256
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long
from pwn import *
import os

'''
def H(self, msg):
    return bytes_to_long(2 * sha256(msg).digest()) % self.q

Notice that the k generation is:
- k = self.H(msg + long_to_bytes(self.x))

The Hash message is weak, because that means:
k = b + 2^256*b = b(2^256+1)
where b is the 256 bits generated by the sha256, and it is small enough compared to q

This means, we can try to recover it by constructing a lattice that
can produced a vector containing the b value after being reduced
by LLL algorithm.
'''

def Babai_closest_vector(B, target):
    # Babai's Nearest Plane algorithm
    M = B.LLL()
    G = M.gram_schmidt()[0]
    small = target
    for _ in range(1):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -= M[i] * c
    return target - small

p = 0x184e26a581fca2893b2096528eb6103ac03f60b023e1284ebda3ab24ad9a9fe0e37b33eeecc4b3c3b9e50832fd856e9889f6c9a10cde54ee798a7c383d0d8d2c3
q = (p - 1) // 2
g = 3

msg1 = os.urandom(16)
msg2 = os.urandom(16)

io = remote(b'206.189.112.129', int(30481))
io.recvuntil(b': ')
g = int(io.recvline())
io.recvuntil(b': ')
y = int(io.recvline())
io.recvuntil(b': ')
p = int(io.recvline())
q = int((p-1)//2)

io.sendlineafter(b'> ', b'S')
io.sendlineafter(b'> ', msg1.hex().encode())
io.recvuntil(b': ')
s1, e1 = eval(io.recvline())
io.sendlineafter(b'> ', b'S')
io.sendlineafter(b'> ', msg2.hex().encode())
io.recvuntil(b': ')
s2, e2 = eval(io.recvline())

B = 2**256 # b_i = (2^256 + 1)*b_i), and b_i bound is 2**256 because it is the result of sha256
M = Matrix([
    [1, 0, 0, 0, s2,   s1],
    [0, 2/q, 0, 0, e2,   e1],
    [0, 0, 1/B, 0, (B+1), 0],
    [0, 0, 0, 1/B, 0, (B+1)],
    [0, 0, 0, 0, q,     0],
    [0, 0, 0, 0, 0,     q],
])

# Try to find a vector resides in the lattice which is close to the
# target vector
res = Babai_closest_vector(M, vector([1, 1, -1, -1, 0, 0]))
x = int(res[1]*q/2) - 1 # Based on observation, if we're lucky, our recovered x is differed by 1
print(f'recovered x = {x}')

# Sign the message with our recovered private key
msg = b'right hand'
def H(msg):
    return bytes_to_long(2 * sha256(msg).digest()) % q
k = H(msg + long_to_bytes(x))
r = pow(int(g), int(k), int(p)) % q
e = H(long_to_bytes(r) + msg)
s = (k - x * e) % q

io.sendlineafter(b'> ', b'V')
io.sendlineafter(b'> ', msg.hex().encode())
io.sendlineafter(b'> ', str(s).encode())
io.sendlineafter(b'> ', str(e).encode())
io.interactive()

Flag: HTB{full_s1z3_n0nc3_l4cks_ful1_s1z3_3ntr0py}

Converging Visions

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?

Initial Analysis

On this challenge, we were given a file called server.py. Below is the contents of the code:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104


from secret import FLAG, p, a, b
from sage.all_cmdline import *


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)


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])


def menu():
    print('Options:\n')
    print('1. Setup Point')
    print('2. Receive new point')
    print('3. Find true point')
    option = input('> ')
    return option


def main():
    artifact = Relic(p, a, b)
    setup = False
    while True:
        try:
            option = menu()
            if option == '1':
                print('Enter x coordinate')
                x = int(input('x: '))
                response = artifact.setupPoints(x)
                if response[0] == 'Point confirmed on curve':
                    setup = True
                print(response)
            elif option == '2':
                if setup:
                    response = artifact.nextPoints()
                    print('Response')
                    print((response[0], response[1], response[2]))
                else:
                    print('Configure origin point first')
            elif option == '3':
                if setup:
                    print('Input x,y')
                    Px = int(input('x: '))
                    Py = int(input('y: '))
                    response = artifact.nextPoints()
                    if response[3] == Px and response[4] == Py:
                        print(
                            'You have confirmed the location. It\'s dangerous however to go alone. Take this: ',
                            FLAG)
                    else:
                        print('The vessels will never be found...')
                    exit()
                else:
                    print('Configure origin point first')
            else:
                print("Invalid option, sutting down")
                exit()
        except Exception as e:
            response = f'An error occured: {e}'
            print(response)
            exit()


if __name__ == '__main__':
    assert p.bit_length() == 256
    main()

As we can see in the code, the server is basically a combination of Elliptic Curve and PRNG. Let’s check the PRNG code first.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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)

Well, this is just a usual PRNG, with an extra that it doesn’t only return the seed, but also the encrypted seed (encrypted with scheme similar to RSA rabin, which is $enc = \text{seed}^2 \mod (p*c)$, where $c$ is the constant hard-coded in the code).

Now, let’s try to check the ECC class:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


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])

Okay, so to summarize:

The Relic class uses the PRNG class as one of its attribute
It also has two variables to store points: P and EP
There are two main method:
- setupPoints
  - This resets the Relic point to our chosen x, which is required to be a valid point.
  - It also resets both P and EP to store our chosen point.
- nextPoints
  - This generates a new random number from the PRNG, and then multiplies:
    - P with seed
    - EP with enc_seed

There are three menus that we can interact with:

1
- Reset the points that will be used by the Elliptic Curve.
- If the given x is larger than the used p, it will return the message Coordinate greater than curve modulus.
- Otherwise, it will try to generate a point (x, y) on the curve and return it to us if it is valid.
2:
- Generate new points, which are:
- P *= seed
- EP *= enc_seed
  - where EP is basically the current point set in the Elliptic Curve multiplied with the encrypted seed.
- It will then return only the EP to us.
3:
- Print the flag, but we need to be able to predict the generated point by nextPoints method.

Based on this information, our goal is to recover the seed value and use it to predict the next generated point.

Solution

Firstly, we don’t know the parameters of the curve yet (p, a, b). So, we need to recover them first. Notice that in the first menu, we can perform a binary search to find the p value, because if we provide an x value greater than p, the program will indicate that the x value is greater than the p value.

Once we have recovered the p value, it is easy to obtain the a and b values. We just need to generate two points and then subtract them, just like what we did in the Elliptic Labyrinth Challenge. Below is the script that I used to recover the parameters (I used sagemath).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


from pwn import *

r = remote('68.183.37.122', int(32073))

# Binary Search the p. I've changed the high and low value in here to speed up the process as
# I've already retrieved the value before making this writeup.
high = 91720173941422125335466921700213991383508377854521057423162397714341988797840
low = 91720173941422125335466921700213991383508377854521057423162397714341988797837

while high - low >= 0:
    print(f'high, low = {high}, {low}')
    print(f'Curr diff: {high - low}')
    if high - low == 0:
        break
    mid = (high + low) // 2
    r.sendlineafter(b'> ', b'1')
    r.sendlineafter(b'x: ', str(mid).encode())
    out = r.recvline()
    if b'greater' in out:
        # Too high
        high = mid
    else:
        low = mid + 1
p = high
print(f'recovered p = {p}')

def setup_point(x):
    r.sendlineafter(b'> ', b'1')
    r.sendlineafter(b'x: ', str(x).encode())
    _, x1, y1 = eval(r.recvline().strip())
    return x1, y1

x1, y1 = setup_point(4)
x2, y2 = setup_point(6)
a = (((y1^2 - y2^2) - (x1^3 -x2^3))*inverse_mod(x1-x2, p)) % p
b = (y1^2 - x1^3 - a*x1) % p
print(f'recovered a = {a}')
print(f'recovered b = {b}')

E = EllipticCurve(GF(p), [a, b])

After we finally recovered the curve, the next step is to figure out how to recover the PRNG seed.

In ECC, discrete logarithm is hard. So, if we have equation like $A = kB$ where $A$ and $B$ are points, $k$ is the multiplier, and we only know $A$ and $B$, we won’t be able to recover the $k$ value easily. However, for this challenge, in order to recover the seed value, we need to retrieve the enc_seed first.

Even though we can setup the point (let’s call it A) via the first menu, and we can also get the EP value, which is EP = enc_seed*A, if the ECC is not weak, it won’t be possible for us to recover the enc_seed.

However, after playing around with the curve, I noticed that the curve order is actually the same with the p used in the curve.

1
2
3
4


sage: E.order()
91720173941422125335466921700213991383508377854521057423162397714341988797837
sage: E.order() == p
True

This is a weak curve that is vulnerable to Smart Attack. Below is the script that I used to perform the Smart Attack, taken from this github:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


# Lifts a point to the p-adic numbers.
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):
    """
    Solves the discrete logarithm problem using Smart's attack.
    More information: Smart N. P., "The discrete logarithm problem on elliptic curves of trace one"
    :param G: the base point
    :param P: the point multiplication result
    :return: l such that l * 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)))

gx, gy = setup_point(4)
G = E(gx, gy)

def next_point():
    r.sendlineafter(b'> ', b'2')
    if args.LOCAL:
        print(r.recvline().strip())
    r.recvline().strip()
    _, x, y = eval(r.recvline().strip())
    return x, y

px, py = next_point()
P = E(px, py)
enc_seed = attack(G, P)
print(f'recovered enc_seed: {enc_seed}') # enc_seed = seed^2 mod p

By using the Smart attack, we will be able to recover the enc_seed, and now it’s time to move to the next part, which is recovering the seed from the known enc_seed.

To retrieve the seed, it is actually easy. SageMath has a built-in feature that can calculate the nth_root of an integer over a ring. So, we just need to use that, and there will be two roots that are recovered. One of the two roots is the seed. With 50:50 chance, I decided to always take the second root as the seed, and then use it to predict the next point in the server. After that, we will be able to get our flag.

Below is the full script that I used to solve the challenge (I use SageMath).

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111


from pwn import *

r = remote('68.183.37.122', int(32073))

p = None

if p is None:
    # Binary Search the p. I've changed the high and low value in here to speed up the process as
    # I've already retrieved the value before making this writeup.
    high = 91720173941422125335466921700213991383508377854521057423162397714341988797840
    low = 91720173941422125335466921700213991383508377854521057423162397714341988797837

    while high - low >= 0:
        print(f'high, low = {high}, {low}')
        print(f'Curr diff: {high - low}')
        if high - low == 0:
            break
        mid = (high + low) // 2
        r.sendlineafter(b'> ', b'1')
        r.sendlineafter(b'x: ', str(mid).encode())
        out = r.recvline()
        if b'greater' in out:
            # Too high
            high = mid
        else:
            low = mid + 1
    p = high
    print(f'recovered p = {p}')

a = None
b = None

def setup_point(x):
    r.sendlineafter(b'> ', b'1')
    r.sendlineafter(b'x: ', str(x).encode())
    _, x1, y1 = eval(r.recvline().strip())
    return x1, y1

if a is None or b is None:
    x1, y1 = setup_point(4)
    x2, y2 = setup_point(6)
    a = (((y1^2 - y2^2) - (x1^3 -x2^3))*inverse_mod(x1-x2, p)) % p
    b = (y1^2 - x1^3 - a*x1) % p
    print(f'recovered a = {a}')
    print(f'recovered b = {b}')

# Now that we have recovered the curves parameter build the curve
E = EllipticCurve(GF(p), [a, b])
print(f'Vulnerable to smart attack: {E.order() == p}')
assert E.order() == p # Vulnerable to Smart Attack

# Lifts a point to the p-adic numbers.
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):
    """
    Solves the discrete logarithm problem using Smart's attack.
    More information: Smart N. P., "The discrete logarithm problem on elliptic curves of trace one"
    :param G: the base point
    :param P: the point multiplication result
    :return: l such that l * 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)))

gx, gy = setup_point(4)
G = E(gx, gy)

def next_point():
    r.sendlineafter(b'> ', b'2')
    if args.LOCAL:
        print(r.recvline().strip())
    r.recvline().strip()
    _, x, y = eval(r.recvline().strip())
    return x, y

px, py = next_point()
P = E(px, py)
enc_seed = attack(G, P)
print(f'recovered enc_seed: {enc_seed}') # enc_seed = seed^2 mod p

inc = int.from_bytes(b"Coordinates lost in space", "big")
Z = IntegerModRing(p)
seeds_1 = Z(enc_seed).nth_root(2, all=True) # There will be two roots
print(f'recovered_seed: {seeds_1}')

# Calculate next_seed
next_seed = (a * pow(seeds_1[1], 3) + b * seeds_1[1] + inc) % p # Take second entry (50:50)
setup_point(4) # Reset point

# Predict
prediction_point = G*int(next_seed)
print(f'prediction: {prediction_point}')
r.sendlineafter(b'> ', b'3')
r.sendlineafter(b'x: ', str(prediction_point[0]).encode())
r.sendlineafter(b'y: ', str(prediction_point[1]).encode())
r.interactive()

Flag: HTB{0Racl3_AS_a_f3A7Ur3_0n_W3aK_CURV3_aND_PRN9??_7H3_s3cur17Y_0F_0uR_CRyP70Sys73M_w1LL_c0LLAp53!!!}

Follow me on twitter

Contents

Cyber Apocalypse 2023: Crypto

Crypto

Multipage Recyclings

Initial Analysis

Solution

Full Script

Inside the Matrix

Initial Analysis

Solution

Full Script

Elliptic Labyrinth

Initial Analysis

Solution

Elliptic Labyrinth Revenge

Initial Analysis

Solution

Colliding Heritage

Initial Analysis

Solution

Biased Heritage

Initial Analysis

Solution

Converging Visions

Initial Analysis

Solution

Social Media