Cyber Apocalypse 2024: Crypto

Mar 14, 2024 8840 words 42 minutes

Contents

https://ctf.hackthebox.com/storage/ctf/banners/DREwio2TXADvSLScO07rux2olm6vjUoEXQPPAKBC.jpg — HackTheBox - Cyber Apocalypse 2024: Hacker Royale

I have been casually participating in the Cyber Apocalypse CTF 2024. During this time, I managed to solve all the challenges in the pwn, crypto, blockchain, and hardware categories. In this write-up, I will share my solutions for all the challenges in the crypto category that I solved. If you are interested in reading the write-up for all the blockchain & hardware challenges, check out this post. If you are interested in reading the write-up for all the pwn challenges, check out this post.

https://i.imgur.com/3Hc0cYH.png — I managed to solve all of the pwn, crypto, blockchain, and hardware challenges by myself :)

Crypto

ROT128 [insane]

Description

In the eerie stillness of the Bitting village, a dilapidated laboratory lies forgotten and forsaken, its ancient walls whispering secrets of unspeakable horrors. As you awaken within its confines, a shiver runs down your spine, the air thick with the weight of untold darkness. With no recollection of how you came to be here, you begin to explore the place. The dim glow of flickering lights casts long shadows across the worn floors, revealing rusted equipment and decaying machinery. The air is heavy with the scent of decay and abandonment, a tangible reminder of the atrocities that once transpired within these walls. Soon, you uncover the sinister truth lurking within the laboratory’s forgotten depths. This place was a chamber of horrors, a breeding ground for abominable experiments in human cloning. The realization sends chills coursing through your veins, your mind reeling at the thought of the atrocities committed in the name of science. But there is no time to dwell on the horrors of the past, because a sinister countdown echoes through the laboratory, its ominous tones a harbinger of impending doom. Racing against the ticking clock, you discover the source of the impending catastrophe—a chemical reactor primed to unleash devastation upon the village. With the weight of the world upon your shoulders, you realize that you alone possess the knowledge to defuse the deadly device. As a chemist, you understand the delicate balance of chemical reactions, and you know that triggering a specific collision multiple times is the key to averting disaster. With steady hands and a racing heart, you get to work. As the seconds tick away, you feel the weight of the world bearing down upon you, but you refuse to falter.

Initial Analysis

In this challenge, we were given a source code named 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
88
89
90
91
92
93
94
95
96


import random, os, signal
from Crypto.Util.number import long_to_bytes as l2b, bytes_to_long as b2l
from secret import FLAG

ROUNDS = 3
USED_STATES = []
_ROL_ = lambda x, i : ((x << i) | (x >> (N-i))) & (2**N - 1)
N = 128

def handler(signum, frame):
    print("\n\nToo slow, don't try to do sneaky things.")
    exit()

def validate_state(state):
    if not all(0 < s < 2**N-1 for s in user_state[-2:]) or not all(0 <= s < N for s in user_state[:4]):
        print('Please, make sure your input satisfies the upper and lower bounds.')
        return False
    
    if sorted(state[:4]) in USED_STATES:
        print('You cannot reuse the same state')
        return False
    
    if sum(user_state[:4]) < 2:
        print('We have to deal with some edge cases...')
        return False

    return True

class HashRoll:
    def __init__(self):
        self.reset_state()

    def hash_step(self, i):
        r1, r2 = self.state[2*i], self.state[2*i+1]
        return _ROL_(self.state[-2], r1) ^ _ROL_(self.state[-1], r2)

    def update_state(self, state=None):
        if not state:
            self.state = [0] * 6
            self.state[:4] = [random.randint(0, N) for _ in range(4)]
            self.state[-2:] = [random.randint(0, 2**N) for _ in range(2)]
        else:
            self.state = state
    
    def reset_state(self):
        self.update_state()

    def digest(self, buffer):
        buffer = int.from_bytes(buffer, byteorder='big')
        m1 = buffer >> N
        m2 = buffer & (2**N - 1)
        self.h = b''
        for i in range(2):
            self.h += int.to_bytes(self.hash_step(i) ^ (m1 if not i else m2), length=N//8, byteorder='big')
        return self.h


print('Can you test my hash function for second preimage resistance? You get to select the state and I get to choose the message ... Good luck!')

hashfunc = HashRoll()

for _ in range(ROUNDS):
    print(f'ROUND {_+1}/{ROUNDS}!')

    server_msg = os.urandom(32)
    hashfunc.reset_state()
    server_hash = hashfunc.digest(server_msg)
    print(f'You know H({server_msg.hex()}) = {server_hash.hex()}')

    signal.signal(signal.SIGALRM, handler)
    signal.alarm(2)

    user_state = input('Send your hash function state (format: a,b,c,d,e,f) :: ').split(',')

    try:
        user_state = list(map(int, user_state))

        if not validate_state(user_state):
            print("The state is not valid! Try again.")
            exit()

        hashfunc.update_state(user_state)

        if hashfunc.digest(server_msg) == server_hash:
            print(f'Moving on to the next round!')
            USED_STATES.append(sorted(user_state[:4]))
        else:
            print('Not today.')
            exit()
    except:
        print("The hash function's state must be all integers.")
        exit()
    finally:
       signal.alarm(0)

print(f'Uhm... how did you do that? I thought I had cryptanalyzed it enough ... {FLAG}')

The code is extensive, but essentially, the task is to create a unique hashing algorithm referred to as HashRoll. Upon checking through the HashRoll’s design, we can see that it operates with six internal states.

These states are manipulated through the update_state function. The hashing process involves the digest function, which computes the hash for the given message. To illustrate, if we consider a 32-byte message in the buffer, the digest function begins by dividing this message into two 16-byte segments, denoted as $m_{0}$ and $m_{1}$. The computation of the hash result follows this segmentation.

$$ \text{digest}(m) = m_{0} \oplus h_{0} || m_{1} \oplus h_{1} $$

Let’s see how the $h$ is made.

$$ h_{0} = \text{ROL}(s_{4}, s_{0}) \oplus \text{ROL}(s_{5}, s_{1})\\ h_{1} = \text{ROL}(s_{4}, s_{2}) \oplus \text{ROL}(s_{5}, s_{3}) $$

where $s$ stands for states.

Next, let’s find out the goal of this challenge. Looking at the for loop, the main task is to come up with new, unique states. With the same $\text{m}$ and $\text{digest}$, our input states should give us back the same $\text{digest}$.

Knowing what we need to do, let’s start thinking about how to tackle this challenge.

Solution

First, I tackled this challenge by trying to express its logic through mathematical equations. The task is to find different states that would lead to the same hash_step result for both $h_{0}$ and $h_{1}$.

To figure out the values of $h_{0}$ and $h_{1}$ our states input needs to generate, observe that given $m$ and its hash $\text{digest}(m)$ (let’s call $\text{digest}(m)$ as $d$), we can easily find the $h$ values. By dividing both $m$ (into $m_0$ and $m_1$) and $d$ (into $d_0$ and $d_1$), we notice:

$$ h_{0} = m_{0} \oplus d_{0}\\ h_1 = m_1 \oplus d_1 $$

Next, while attempting to mathematically represent the hash_step operation, I noticed that the xor operation can be represented as addition in $GF(2)$, and the ROL operation can be represented as multiplication by a special matrix in $GF(2)$ that can rotate a vector or another matrix.

For instance, if we want to calculate _ROL_(2, 2) in an 8-bit space, it is equivalent to the following equation:

$$ \text{ROL}(2,2) = \begin{pmatrix} 0&0&1&0&0&0&0&0\\ 0&0&0&1&0&0&0&0\\ 0&0&0&0&1&0&0&0\\ 0&0&0&0&0&1&0&0\\ 0&0&0&0&0&0&1&0\\ 0&0&0&0&0&0&0&1\\ 1&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0\\ \end{pmatrix} * \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ \end{pmatrix} $$

Next, calculating $2 \oplus 2$ is essentially addition in $GF(2)$.

$$ 2 \oplus 2 = \begin{pmatrix}0&0&0&0&0&0&1&0\end{pmatrix} + \begin{pmatrix}0&0&0&0&0&0&1&0\end{pmatrix} $$

So, by analyzing how the hash_step is generated, we can deduce it is equivalent to an equation involving $\text{ROL}_{i}$, the matrix I described earlier.

$$ r_0 = \text{ROL}_{s_0}\\ r_1 = \text{ROL}_{s_1}\\ r_2 = \text{ROL}_{s_2}\\ r_3 = \text{ROL}_{s_3}\\ $$

$$ h_0 = r_0s_4+r_1s_5\\ h_1 = r_2s_4+r_3s_5\\ $$

With these equations in hand, we find ourselves with only $h_0$ and $h_1$ known, leaving us with two equations and six unknowns.

To tackle this, I decided to define four of the unknowns myself: $r_0$, $r_1$, $r_2$, and $r_3$. I set the value of $r_0$ equal to $r_2$ to help eliminate variables in our equations. Assuming we set:

Both $r_0$ and $r_2$ to $\text{ROL}_a = r_a$
$r_1$ to $\text{ROL}_b = r_b$
$r_3$ to $\text{ROL}_d = r_d$

This leads us to the following equation: $$ \begin{align} h_0 = r_as_4 + r_bs_5 \\ h_1 = r_as_4 + r_ds_5 \\ \end{align} $$

If we subtract the equations we have, we will arrive at a new equation as follows: $$ \begin{align} (h_0 - h_1) = (r_b-r_d)s_5 \\ \end{align} $$

Knowing $h_0$ and $h_1$, and having defined $r_b$ and $r_d$ ourselves, we can easily solve this equation to find $s_5$ with the help of SageMath’s solve_right() function.

After determining $s_5$, and since we’ve also chosen $r_a$ ourselves, figuring out $s_4$ becomes straightforward. $$ \begin{align} h_0 = r_as_4 + r_bs_5 \\ h_0 - r_bs_5 = r_as_4 \\ \end{align} $$

To solve this equation, we can use SageMath’s solve_right() again. Now, we just need to implement this. We have three rounds, and I’ve predefined the values as follows:

ROUND_1: $a=c=1$, $b=2$, $d=3$
ROUND_2: $a=c=2$, $b=3$, $d=4$
ROUND_3: $a=c=3$, $b=4$, $d=5$

Below is the full 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


from pwn import *

ROUNDS = 3
N = 128

r = remote('83.136.249.138', int(36059))
print(r.recvline().strip())

# Convert integer to vector of 128-bits
def i2v(A, N=128):
    binary_str = bin(A)[2:]
    bits = [0 for _ in range(N)]
    for i in range(len(binary_str)):
        bits[-(i+1)] = int(binary_str[-(i+1)])
    return vector(GF(2), bits)

# Convert vector of 128-bits to integer
def v2i(v):
    result = 0
    for i in range(len(v)):
        result += (int(v[-(i+1)])) * (2^i)
    return result

# Generate ROL matrix for 128-bits space
def gen_rol_mat(rol, N=128):
    m = []
    for i in range(N):
        temp = [0 for _ in range(N)]
        temp[(i+rol) % N] = 1
        m.append(temp)
    return Matrix(GF(2), m)

for ROUND in range(ROUNDS):
    print(r.recvline().strip())
    out = r.recvline().strip()
    print(out)
    _server_msg, _server_hash = out.strip(b'You know H(').split(b') = ')
    print(_server_msg)
    print(_server_hash)
    server_msg = bytes.fromhex(_server_msg.decode())
    server_hash = bytes.fromhex(_server_hash.decode())
    print(f'{server_msg.hex() = }')
    print(f'{server_hash.hex() = }')

    buffer = int.from_bytes(server_msg, byteorder='big')
    m1 = buffer >> N
    m2 = buffer & (2**N - 1)
    print(f'{hex(m1) = }')
    print(f'{hex(m2) = }')
    out1 = int.from_bytes(server_hash[:16], byteorder='big')
    out2 = int.from_bytes(server_hash[16:], byteorder='big')
    print(f'{hex(out1) = }')
    print(f'{hex(out2) = }')

    step0 = m1 ^^ out1
    step1 = m2 ^^ out2
    print(f'{hex(step0) = }')
    print(f'{hex(step1) = }')

    h0 = i2v(step0)
    h1 = i2v(step1)
    a = c = 1+ROUND
    b = 2+ROUND
    d = 3+ROUND
    r_a = gen_rol_mat(1+ROUND)
    r_b = gen_rol_mat(2+ROUND)
    r_d = gen_rol_mat(3+ROUND)
    s0 = i2v(step0)
    s1 = i2v(step1)
    f = (r_b-r_d).solve_right(h0-h1)
    e = r_a.solve_right(h0-r_b*f)
    val_e = v2i(e)
    val_f = v2i(f)

    ans = f'{a},{b},{c},{d},{val_e},{val_f}'
    print(f'{ans = }')
    r.sendlineafter(b' :: ', ans.encode())
    print(r.recvline().strip())
    print('---')

r.interactive()

Flag: HTB{k33p_r0t4t1ng_4nd_r0t4t1ng_4nd_x0r1ng_4nd_r0t4t1ng!}

Tsayaki [hard]

Description

You find yourself in the middle of a deadly ancient maze. The maze sprawls before you, its secrets veiled in shadows, its gates locked tight against intruders. With thousands of keys shimmering under the harsh light, you steel yourself for the daunting challenge ahead. Each chamber of the maze presents a new puzzle to unravel, each gate a barrier to overcome. Armed with determination and resolve, you set forth into the labyrinth’s depths, knowing that your survival hinges on unlocking the path forward by finding the proper key. With each new chamber you enter, you are greeted with a cup of tea—a brief respite from the perilous journey that lies ahead. But the tea is not the only gift bestowed upon you in these chambers. With each cup, you receive a hint that will guide you on how to move on. NOTE: ’tea.py’ can be found in the challenge ‘Iced Tea’

Initial Analysis

In this challenge, we were provided with a file named 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


from tea import Cipher as TEA
from secret import IV, FLAG
import os

ROUNDS = 10

def show_menu():
    print("""
============================================================================================
|| I made this decryption oracle in which I let users choose their own decryption keys.   ||
|| I think that it's secure as the tea cipher doesn't produce collisions (?) ... Right?   ||
|| If you manage to prove me wrong 10 times, you get a special gift.                      ||
============================================================================================
""")

def run():
    show_menu()

    server_message = os.urandom(20)
    print(f'Here is my special message: {server_message.hex()}')
    
    used_keys = []
    ciphertexts = []
    for i in range(ROUNDS):
        print(f'Round {i+1}/10')
        try:
            ct = bytes.fromhex(input('Enter your target ciphertext (in hex) : '))
            assert ct not in ciphertexts

            for j in range(4):
                key = bytes.fromhex(input(f'[{i+1}/{j+1}] Enter your encryption key (in hex) : '))
                assert len(key) == 16 and key not in used_keys
                used_keys.append(key)
                cipher = TEA(key, IV)
                enc = cipher.encrypt(server_message)
                if enc != ct:
                    print(f'Hmm ... close enough, but {enc.hex()} does not look like {ct.hex()} at all! Bye...')
                    exit()
        except:
            print('Nope.')
            exit()
            
        ciphertexts.append(ct)

    print(f'Wait, really? {FLAG}')


if __name__ == '__main__':
    run()

Looking at this challenge, the summary is that, given 10 ROUNDS, in each round, we need to provide 4 different keys. These keys, when used as the key for the Tiny Encryption Algorithm (TEA) with the same input, should generate the same encryption result. Below is the implementation of the TEA (sourced from another challenge named Iced TEA). I’ve added the decrypt_block method to the code 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
67
68
69
70
71
72
73
74


import os
from Crypto.Util.Padding import pad
from Crypto.Util.number import bytes_to_long as b2l, long_to_bytes as l2b
from enum import Enum

class Mode(Enum):
    ECB = 0x01
    CBC = 0x02

class Cipher:
    def __init__(self, key, iv=None):
        self.BLOCK_SIZE = 64
        self.KEY = [b2l(key[i:i+self.BLOCK_SIZE//16]) for i in range(0, len(key), self.BLOCK_SIZE//16)]
        self.DELTA = 0x9e3779b9
        self.IV = iv
        if self.IV:
            self.mode = Mode.CBC
        else:
            self.mode = Mode.ECB
    
    def _xor(self, a, b):
        return b''.join(bytes([_a ^ _b]) for _a, _b in zip(a, b))

    def encrypt(self, msg):
        msg = pad(msg, self.BLOCK_SIZE//8)
        blocks = [msg[i:i+self.BLOCK_SIZE//8] for i in range(0, len(msg), self.BLOCK_SIZE//8)]
        
        ct = b''
        if self.mode == Mode.ECB:
            for pt in blocks:
                ct += self.encrypt_block(pt)
        elif self.mode == Mode.CBC:
            X = self.IV
            for pt in blocks:
                enc_block = self.encrypt_block(self._xor(X, pt))
                ct += enc_block
                X = enc_block
        return ct

    def encrypt_block(self, msg):
        m0 = b2l(msg[:4])
        m1 = b2l(msg[4:])
        K = self.KEY
        msk = (1 << (self.BLOCK_SIZE//2)) - 1

        s = 0
        for i in range(32):
            s += self.DELTA
            m0 += ((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])
            m0 &= msk
            m1 += ((m0 << 4) + K[2]) ^ (m0 + s) ^ ((m0 >> 5) + K[3])
            m1 &= msk
        
        m = ((m0 << (self.BLOCK_SIZE//2)) + m1) & ((1 << self.BLOCK_SIZE) - 1) # m = m0 || m1

        return l2b(m)

    def decrypt_block(self, msg):
        m = b2l(msg)
        m1 = m & ((1 << (self.BLOCK_SIZE//2)) - 1)
        m0 = m >> (self.BLOCK_SIZE//2)
        K = self.KEY
        msk = (1 << (self.BLOCK_SIZE//2)) - 1

        s = self.DELTA * 32
        for i in range(32):
            m1 -= ((m0 << 4) + K[2]) ^ (m0 + s) ^ ((m0 >> 5) + K[3])
            m1 &= msk
            m0 -= ((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])
            m0 &= msk
            s -= self.DELTA
        
        decrypted_block = l2b(m0) + l2b(m1)
        return decrypted_block

Now that we understand the main goal of the challenge, let’s consider how to approach it.

Solution

First, note that in server.py, a static IV is used. Recovering the IV is straightforward, because when the server provides the message and the encryption result, we also know the key since it’s provided by us. To recover the IV, we can simply connect to the server, then decrypt the given encryption result with our input key, and finally xor it with the message.

After recovering the IV, the next step is to figure out how we can find 4 different keys that produce the same encryption result for the same input. Upon searching about the TEA cipher on Google, we found a paper which explains that the key of the TEA cipher can be defined as:

$$ K = K_0 || K_1 || K_2 || K_3 $$

If we flip the most significant bits (MSBs) of both $K_0$ and $K_1$, or both $K_2$ and $K_3$, we end up with a different key that produces the same encryption result. This indicates that we can start by generating a random key and then create 4 pairs of keys as follows:

The original key.
A key with the MSBs of both $K_0$ and $K_1$ flipped.
A key with the MSBs of both $K_2$ and $K_3$ flipped.
A key where the MSBs of all $K_i$ are flipped.

Below is the full script used to implement the above strategy:

  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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140


from Crypto.Util.Padding import pad
from Crypto.Util.number import bytes_to_long as b2l, long_to_bytes as l2b
from enum import Enum

class Mode(Enum):
    ECB = 0x01
    CBC = 0x02

class TEA:
    def __init__(self, key, iv=None):
        self.BLOCK_SIZE = 64
        self.KEY = [b2l(key[i:i+self.BLOCK_SIZE//16]) for i in range(0, len(key), self.BLOCK_SIZE//16)]
        self.DELTA = 0x9e3779b9
        self.IV = iv
        if self.IV:
            self.mode = Mode.CBC
        else:
            self.mode = Mode.ECB
    
    def _xor(self, a, b):
        return b''.join(bytes([_a ^ _b]) for _a, _b in zip(a, b))

    def encrypt(self, msg):
        msg = pad(msg, self.BLOCK_SIZE//8)
        blocks = [msg[i:i+self.BLOCK_SIZE//8] for i in range(0, len(msg), self.BLOCK_SIZE//8)]
        
        ct = b''
        if self.mode == Mode.ECB:
            for pt in blocks:
                ct += self.encrypt_block(pt)
        elif self.mode == Mode.CBC:
            X = self.IV
            for pt in blocks:
                enc_block = self.encrypt_block(self._xor(X, pt))
                ct += enc_block
                X = enc_block
        return ct

    def encrypt_block(self, msg):
        m0 = b2l(msg[:4])
        m1 = b2l(msg[4:])
        K = self.KEY
        msk = (1 << (self.BLOCK_SIZE//2)) - 1
        s = 0
        for i in range(32):
            s += self.DELTA
            m0 += ((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])
            m0 &= msk
            m1 += ((m0 << 4) + K[2]) ^ (m0 + s) ^ ((m0 >> 5) + K[3])
            m1 &= msk
        
        m = ((m0 << (self.BLOCK_SIZE//2)) + m1) & ((1 << self.BLOCK_SIZE) - 1) # m = m0 || m1

        return l2b(m)

    def decrypt_block(self, msg):
        m = b2l(msg)
        m1 = m & ((1 << (self.BLOCK_SIZE//2)) - 1)
        m0 = m >> (self.BLOCK_SIZE//2)
        K = self.KEY
        msk = (1 << (self.BLOCK_SIZE//2)) - 1

        s = self.DELTA * 32
        for i in range(32):
            m1 -= ((m0 << 4) + K[2]) ^ (m0 + s) ^ ((m0 >> 5) + K[3])
            m1 &= msk
            m0 -= ((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])
            m0 &= msk
            s -= self.DELTA
        
        decrypted_block = l2b(m0) + l2b(m1)
        return decrypted_block
    
from pwn import *

def flip(x):
    return p32(u32(x) ^ 0x00000080)

def gen_keys():
    key = os.urandom(16)
    print(f'{key.hex() = }')
    keys = []
    k0 = key[:4]
    k1 = key[4:8]
    k2 = key[8:12]
    k3 = key[12:]
    keys.append(k0+k1+k2+k3)
    keys.append(flip(k0)+flip(k1)+k2+k3)
    keys.append(k0+k1+flip(k2)+flip(k3))
    keys.append(flip(k0)+flip(k1)+flip(k2)+flip(k3))
    return keys

# Recover IV
r = remote('94.237.63.83', 46862)
r.recvuntil(b': ')
msg = bytes.fromhex(r.recvline().strip().decode())
print(f'{msg.hex() = }')
keys = gen_keys()
for key in keys[:1]:
    print('key', key.hex())
    print('msg', msg.hex())
    cipher = TEA(key, b'\x00'*8)
    out = cipher.encrypt(msg)
    print(out.hex())
    print('---')
    r.sendlineafter(b': ', out.hex().encode())
    r.sendlineafter(b': ', key.hex().encode())
    r.recvuntil(b'but ')
    ct = bytes.fromhex(r.recvuntil(b' ').strip(b' ').decode())
    print(f'{ct.hex() = }')
    first_block = ct[:8]
    iv = xor(cipher.decrypt_block(first_block), msg[:8])
    print(f'{iv = }')

# assert
cipher = TEA(key, iv)
test_out = cipher.encrypt(msg)
print(f'{test_out = }')
print(f'{ct       = }')
r.close()

# Attack
r = remote('94.237.63.83', 46862)
r.recvuntil(b': ')
msg = bytes.fromhex(r.recvline().strip().decode())
print(f'{msg.hex() = }')
for i in range(10):
    keys = gen_keys()
    print('----')
    print(r.recvuntil(b'/10\n'))
    print('Round {i}...')
    print('key:', keys[0].hex())
    print('msg:', msg.hex())
    cipher = TEA(keys[0], iv)
    out = cipher.encrypt(msg)
    print('ct :', out.hex())
    r.sendlineafter(b': ', out.hex().encode())
    for key in keys:
        r.sendlineafter(b': ', key.hex().encode())
r.interactive()

Flag: HTB{th1s_4tt4ck_m4k3s_T34_1n4ppr0pr14t3_f0r_h4sh1ng!}

Permuted [hard]

Description

You drop to the ground as a voltaic mist of energy surrounds you; within it are the Aranaya, reflections of your emotions that break into the physical world from the spiritual realm. Love, hate, pain and more writhe and dance before your eyes in an endless storm. As one tears into your soul, a lightning bolt strikes your inner being and the emotion remoulds into another. Startled and wide-eyed, you recognise an undeniable truth: they are all reflections of one another, an ecosystem of your being that you could lose forever. Consciousness leaves you as the psychedelic show whirls on. To retain your self, you must brave the storm: a cyclone of patterns, an infinitude of permutations.

Initial Analysis

In this challenge, we were given two files named source.py and output.txt.

 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


from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes

from hashlib import sha256
from random import shuffle

from secret import a, b, FLAG

class Permutation:
    def __init__(self, mapping):
        self.length = len(mapping)

        assert set(mapping) == set(range(self.length))     # ensure it contains all numbers from 0 to length-1, with no repetitions
        self.mapping = list(mapping)

    def __call__(self, *args, **kwargs):
        idx, *_ = args
        assert idx in range(self.length)
        return self.mapping[idx]

    def __mul__(self, other):
        ans = []

        for i in range(self.length):
            ans.append(self(other(i)))

        return Permutation(ans)

    def __pow__(self, power, modulo=None):
        ans = Permutation.identity(self.length)
        ctr = self

        while power > 0:
            if power % 2 == 1:
                ans *= ctr
            ctr *= ctr
            power //= 2

        return ans

    def __str__(self):
        return str(self.mapping)

    def identity(length):
        return Permutation(range(length))


x = list(range(50_000))
shuffle(x)

g = Permutation(x)
print('g =', g)

A = g**a
print('A =', A)
B = g**b
print('B =', B)

C = A**b
assert C.mapping == (B**a).mapping

sec = tuple(C.mapping)
sec = hash(sec)
sec = long_to_bytes(sec)

hash = sha256()
hash.update(sec)

key = hash.digest()[16:32]
iv = b"mg'g\xce\x08\xdbYN2\x89\xad\xedlY\xb9"

cipher = AES.new(key, AES.MODE_CBC, iv)

encrypted = cipher.encrypt(pad(FLAG, 16))
print('c =', encrypted)

The challenge is akin to the Diffie-Hellman key exchange but operates within a Permutation Group instead. The output.txt file provides us with g, A, B, and c.

The task is to discover the private key, either a or b, enabling us to generate C and use it to decrypt the encrypted flag.

Solution

First, we should load the given g, A, and B, and experiment with them. I prefer using Sage for debugging in such challenges because of its convenience. Let’s start by converting the list to Permutations and PermutationGroup in Sage.

 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


from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes

from hashlib import sha256

out = open('output.txt').read()
exec(out)
print(len(g))
print(len(A))
print(len(B))

a = A
b = B

# sage permutations doesn't allow 0, so we can simply increase all of it :D
for i in range(50_000):
    g[i] += 1
    a[i] += 1
    b[i] += 1

V = Permutations(50_000)
G = V(g)
A = V(a)
B = V(b)

PG = PermutationGroup([G])

Now, this is a discrete log problem, where given g and A, we need to find a so that g**a = A. Let’s check the group order first.

1
2


order = PG.order()
print(f'{order = }')

As you can see, the order is 3311019189498977856900. Let’s check whether this can be factorize or not.

1
2


sage: factor(order)
2^2 * 3^3 * 5^2 * 7 * 11 * 13 * 23^2 * 47 * 53 * 101 * 149 * 163 * 379

Notably, the order of the group is quite smooth, allowing the potential application of the Pohlig-Hellman algorithm to deduce the private key a. For a detailed explanation, refer to this resource. In summary, this strategy involves simplifying the discrete logarithm problem to a smaller subgroup, where finding the discrete log is feasible. Subsequently, the findings from these smaller subgroups can assist in reconstructing the accurate private key using the Chinese Remainder Theorem.

Below is the script I used to solve this challenge:

 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


from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes

from hashlib import sha256

out = open('output.txt').read()
exec(out)
print(len(g))
print(len(A))
print(len(B))

a = A
b = B

# sage permutations doesn't allow 0, so we can simply increase all of it :D
for i in range(50_000):
    g[i] += 1
    a[i] += 1
    b[i] += 1

V = Permutations(50_000)
G = V(g)
A = V(a)
B = V(b)

PG = PermutationGroup([G])
order = PG.order()
print(f'{order = }')

# Order is smooth, so we can do Pohlig-Hellman :)
primes = [2^2, 3^3, 5^2, 7, 11, 13, 23^2, 47, 53, 101, 149, 163, 379]
dlogs = []
for fac in primes:
    print(f'===')
    print(f'{fac = }')
    t = int(order) // int(fac)
    GG = G**t
    AA = A**t

    # Subgroup is smaller, so we can easily bruteforce it (and do CRT later)
    print(f'Start bf...')
    for dlog in range(fac):
        print(f'Try {dlog}...')
        test = GG**dlog
        if test == AA:
            # found!
            print(f'Found!!!')
            dlogs += [dlog] 
            break
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
    print(f'===')
print(f'{dlogs = }')
priv_a = crt(dlogs, primes)
assert A == G**priv_a
C = B**priv_a

# Restore back to permutations starting from 0
list_c = [x-1 for x in list(C)]

sec = tuple(list_c)
sec = hash(sec)
sec = long_to_bytes(sec)

hash = sha256()
hash.update(sec)

key = hash.digest()[16:32]
iv = b"mg'g\xce\x08\xdbYN2\x89\xad\xedlY\xb9"

cipher = AES.new(key, AES.MODE_CBC, iv)

msg = cipher.decrypt(c)
print(msg)

Flag: HTB{w3lL_n0T_aLl_gRoUpS_aRe_eQUaL_!!}

Partial Tenacity [medium]

Description

You find yourself in a labyrinthine expanse where movement is restricted to forward paths only. Each step presents both opportunity and uncertainty, as the correct route remains shrouded in mystery. Your mission is clear: navigate the labyrinth and reach the elusive endpoint. However, there’s a twist—you have just one chance to discern the correct path. Should you falter and choose incorrectly, you’re cast back to the beginning, forced to restart your journey anew. As you embark on this daunting quest, the labyrinth unfolds before you, its twisting passages and concealed pathways presenting a formidable challenge. With each stride, you must weigh your options carefully, considering every angle and possibility. Yet, despite the daunting odds, there’s a glimmer of hope amidst the uncertainty. Hidden throughout the labyrinth are cryptic clues and hints, waiting to be uncovered by the keen-eyed. These hints offer glimpses of the correct path, providing invaluable guidance to those who dare to seek them out. But beware, for time is of the essence, and every moment spent deliberating brings you closer to the brink of failure. With determination and wit as your allies, you must press onward, braving the twists and turns of the labyrinth, in pursuit of victory and escape from the labyrinth’s confounding embrace. Are you tenacious enough for that?

Initial Analysis

In this challenge, we were given a quite simple source 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


from secret import FLAG
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

class RSACipher:
    def __init__(self, bits):
        self.key = RSA.generate(bits)
        self.cipher = PKCS1_OAEP.new(self.key)
    
    def encrypt(self, m):
        return self.cipher.encrypt(m)

    def decrypt(self, c):
        return self.cipher.decrypt(c)

cipher = RSACipher(1024)

enc_flag = cipher.encrypt(FLAG)

with open('output.txt', 'w') as f:
    f.write(f'n = {cipher.key.n}\n')
    f.write(f'ct = {enc_flag.hex()}\n')
    f.write(f'p = {str(cipher.key.p)[::2]}\n')
    f.write(f'q = {str(cipher.key.q)[1::2]}')

To summarize, we were provided with only the odd digits of p and the even digits of q. With this information, we need to find a way to recover p and q.

Solution

The approach I chose involves a sort of brute-force method combined with backtracking. To illustrate, consider the following scenario.

1
2
3
4
5


last_digit only
     3_4_1 <- p
     _9_5_ <- q
---------- x
2117357569 <- n

Upon careful observation, we can identify a relationship that can be derived. Below is the illustration if we were to perform the multiplication manually.

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


     3_4_1 <- p
     _9_5_ <- q
---------- x
    ______
   ______
  ______
 ______
______
---------- +
2117357569 <- n

i=0 | 0       + p[0]*q[0]
i=1 | carry_0 + p[1]*q[0] + p[0]*q[1]
i=2 | carry_1 + p[2]*q[0] + p[1]*q[1] + p[0]*q[2]
i=3 | carry_2 + p[3]*q[0] + p[2]*q[1] + p[1]*q[2] + p[0]*q[3]
...

From this manual multiplication exercise, we can derive that for each digit of n, the formula to calculate it is as follows:

$$ n_i = \text{carry}_{i-1} + \sum_{j=0}^{i} p_{i-j} \times q_i $$

With this equation in mind, we can code our Depth-First Search (DFS) strategy as follows:

At the current digit, generate all possible combinations of the missing digits.
Then, for each of these possible combinations,
- Insert it into the equation derived above and check:
  - If the result modulo 10 matches the known $n_i$ digit, this indicates a possible combination, so store it.
  - If the result modulo 10 does not match the known $n_i$ digit, skip it.
If the list of possible combinations has more than 0 items, we can proceed to the next digit.
If there are no possible combinations, something was wrong with our choice of digits. We need to backtrack to the previous digit and try a different combination.

Below is the implementation of the strategy described above (with detailed comments). After recovering p and q, decrypting the flag becomes straightforward.

 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


from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import *

# -1 == unknown digit
ori_p_digits = [1,-1,5,-1,1,-1,4,-1,4,-1,1,-1,4,-1,7,-1,3,-1,3,-1,5,-1,7,-1,1,-1,3,-1,6,-1,1,-1,5,-1,2,-1,9,-1,8,-1,5,-1,2,-1,1,-1,6,-1,9,-1,8,-1,0,-1,3,-1,9,-1,7,-1,5,-1,2,-1,5,-1,5,-1,9,-1,1,-1,3,-1,0,-1,5,-1,8,-1,7,-1,5,-1,0,-1,9,-1,4,-1,2,-1,8,-1,8,-1,7,-1,3,-1,8,-1,8,-1,2,-1,0,-1,6,-1,9,-1,9,-1,0,-1,6,-1,9,-1,2,-1,7,-1,1,-1,6,-1,7,-1,4,-1,0,-1,2,-1,2,-1,1,-1,6,-1,7,-1,9,-1,0,-1,2,-1,6,-1,4,-1,3]
ori_q_digits = [-1,1,-1,5,-1,6,-1,2,-1,4,-1,3,-1,4,-1,2,-1,0,-1,0,-1,5,-1,7,-1,7,-1,4,-1,1,-1,6,-1,6,-1,5,-1,2,-1,5,-1,0,-1,2,-1,4,-1,6,-1,0,-1,8,-1,0,-1,6,-1,7,-1,4,-1,2,-1,6,-1,5,-1,5,-1,7,-1,0,-1,9,-1,3,-1,5,-1,6,-1,7,-1,3,-1,9,-1,2,-1,6,-1,5,-1,2,-1,7,-1,2,-1,3,-1,1,-1,7,-1,5,-1,3,-1,0,-1,1,-1,6,-1,1,-1,5,-1,4,-1,2,-1,2,-1,3,-1,8,-1,4,-1,5,-1,0,-1,8,-1,2,-1,7,-1,4,-1,2,-1,6,-1,9,-1,3,-1,0,-1,5,-1]
assert len(ori_p_digits) == len(ori_q_digits)

# Reverse the list, so the first least significant digit will be in the start of the array
ori_p_digits = ori_p_digits[::-1]
ori_q_digits = ori_q_digits[::-1]

# This will be used to store the temporary digits that we found during doing DFS.
# There might be modification during backtracking.
p_digits = ori_p_digits
q_digits = ori_q_digits
n = 118641897764566817417551054135914458085151243893181692085585606712347004549784923154978949512746946759125187896834583143236980760760749398862405478042140850200893707709475167551056980474794729592748211827841494511437980466936302569013868048998752111754493558258605042130232239629213049847684412075111663446003
def dfs(curr_i, carry):
    # Get n_i
    target = int(str(n)[::-1][curr_i])

    # We already find all the digits
    if curr_i == len(str(n)):
        return True

    # If the curr_i is beyond the length of the p_digits and q_digits,
    # it is guaranteed that the validitiy of our digits only based on the previous carry
    if curr_i == len(p_digits) and curr_i == len(q_digits):
        return carry == target

    # Get the current digit
    possible_combi = [] # (p, q, carry)
    p_digit = p_digits[curr_i]
    q_digit = q_digits[curr_i]
    iter_p = [p_digit]
    iter_q = [q_digit]

    # If in the curr_i p digit is unknown, put all the possible digits (0..9)
    if iter_p[0] == -1:
        iter_p = [num_p for num_p in range(10)]

    # If in the curr_i p digit is unknown, put all the possible digits (0..9)
    if iter_q[0] == -1:
        iter_q = [num_q for num_q in range(10)]

    # Execute the equation of calculating n_i digit that we derive before.
    for num_p in iter_p:
        for num_q in iter_q:
            res = carry
            for iteration in range(curr_i+1):
                i = curr_i-iteration
                j = iteration
                curr_p = p_digits[i]
                if i == curr_i:
                    curr_p = num_p
                curr_q = q_digits[j]
                if j == curr_i:
                    curr_q = num_q
                res += curr_p*curr_q

            # If the last digit is same as n_i digit, that means this is a possible combination
            if res % 10 == target:
                possible_combi.append((num_p, num_q, res//10))

    # This means we failed to found at least one possible combination
    if len(possible_combi) == 0:
        return False

    # Now, for each combination that we found, employ DFS, where we will
    # use the found digit as the temporary digit, then move to the next digit
    # dfs function will backtrack if in the future it failed to find any possible combination
    for combi in possible_combi:
        p_digits[curr_i] = combi[0]
        q_digits[curr_i] = combi[1]
        is_valid = dfs(curr_i+1, combi[2])
        if not is_valid:
            p_digits[curr_i] = ori_p_digits[curr_i]
            q_digits[curr_i] = ori_q_digits[curr_i]

# Start the DFS :)
dfs(0, 0)

# DFS is finished, means that we already recover all the missing digits
p = int(''.join([str(x) for x in p_digits[::-1]]))
q = int(''.join([str(x) for x in q_digits[::-1]]))
assert p*q == n
ct = bytes.fromhex('7f33a035c6390508cee1d0277f4712bf01a01a46677233f16387fae072d07bdee4f535b0bd66efa4f2475dc8515696cbc4bc2280c20c93726212695d770b0a8295e2bacbd6b59487b329cc36a5516567b948fed368bf02c50a39e6549312dc6badfef84d4e30494e9ef0a47bd97305639c875b16306fcd91146d3d126c1ea476')
e = 65537
phi = (p-1)*(q-1)
d = inverse(e, phi)
key = RSA.construct((n, e, d))
cipher = PKCS1_OAEP.new(key)
flag = cipher.decrypt(ct)
print(f'{flag = }')

Flag: HTB{v3r1fy1ng_pr1m3s_m0dul0_p0w3rs_0f_10!}

Arranged [medium]

Description

Noiselessly turning the corner, you see before you two men. In a former life, the two were best friends; pressure and pain has reduced them to mere animals, single-minded automatons devoid of emotion or feeling. The sickening, grim reality of the competition is that it is what it is designed to do, and none escape the inevitable doom. You raise your bow and bury two arrows into their chests; given their past, it was the least you could do. Death would be kinder to them than life.

Initial Analysis

In this challenge, we were given a file named sage.py and output.txt.

 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


from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from hashlib import sha256

from secret import FLAG, p, b, priv_a, priv_b

F = GF(p)
E = EllipticCurve(F, [726, b])
G = E(926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367, 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253)

A = G * priv_a
B = G * priv_b

print(A)
print(B)

C = priv_a * B

assert C == priv_b * A

# now use it as shared secret
secret = C[0]

hash = sha256()
hash.update(long_to_bytes(secret))

key = hash.digest()[16:32]
iv = b'u\x8fo\x9aK\xc5\x17\xa7>[\x18\xa3\xc5\x11\x9en'
cipher = AES.new(key, AES.MODE_CBC, iv)

encrypted = cipher.encrypt(pad(FLAG, 16))
print(encrypted)

Looking at the challenge, our objective is to somehow recover priv_a, allowing us to compute C and use it as the AES key. This simulates the implementation of the Diffie-Hellman Key Exchange.

Understanding the task at hand, let’s think how to craft the solution.

Solution

First, note that we don’t know the values of $b$ and $p$ yet, so our initial task is to ascertain these values. We have two pairs of points, A and B.

We’ll begin by attempting to recover the $p$ value. An elliptic curve is typically represented as $y^2 = x^3 + ax + b \mod p$. Given two points, we have the following 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} $$

Knowing $a$, $y$, and $x$, subtracting one equation from the other eliminates $b$:

$$ \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) + a*(x_1-x_2)) = 0 \mod p \\ \end{align} $$

Now, we know that $(y_1^2 - y_2^2) - ((x_1^3 - x_2^3) + a \cdot (x_1-x_2))$ is a multiple of $p$. Our next step is to factor this expression and check for any prime numbers, as $p$ is prime. Below is the initial script I used to first recover that value.

1
2
3
4
5
6


x1 = 6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997
y1 = 2456156841357590320251214761807569562271603953403894230401577941817844043774935363309919542532110972731996540328492565967313383895865130190496346350907696
x2 = 4226762176873291628054959228555764767094892520498623417484902164747532571129516149589498324130156426781285021938363575037142149243496535991590582169062734
y2 = 425803237362195796450773819823046131597391930883675502922975433050925120921590881749610863732987162129269250945941632435026800264517318677407220354869865
a = 726
kp = ((x1^3 -x2^3) + a*(x1-x2)) - (y1^2 - y2^2)

The result of the $kp$ that I found is 159876543767731641091481517970757427845475606054901986278343644849685033675014920747838399719911540214497783751629486726130353637225421487102773147275840819453085461179225204956109588744706616404640700114680030501842814692877925213179751117553624678716957461607736397000873235881970428009381374977362878056793806499363109868757164944583438598058337581715444472442097008263247672258671662471244150568581060911658678179702219608062901555447642033897327594285850816

If we input this number into factordb, we can see that one of its factors is a good candidate for $p$, which is 811640204116707417092117962115673978365477767365408659433165386030330695774965849821512765233994033921595018695941912899856987893397852151975650548637533

Now that we have recovered $p$, we can easily find the $b$ value:

$$ b = y_1^2 - (x_1^3 + ax_1) \mod p $$

With the curve parameters fully recovered, let’s explore further. This is a discrete logarithm problem, so we start by checking its order.

1
2
3
4
5
6


p = 6811640204116707417092117962115673978365477767365408659433165386030330695774965849821512765233994033921595018695941912899856987893397852151975650548637533
b = (y1^2 - x1^3 - a*x1) % p
F = GF(p)
E = EllipticCurve(F, [726, b])
order = E.order()
print(order)

We find that the order is 6811640204116707417092117962115673978365477767365408659433165386030330695774842975950864518820891774127689003723319868798748651155450639754051764297493817

Next, we check if this order can be factorized (with the help of factordb again).

Indeed, the order can be factorized, and it has 4 small prime factors: $3$, $11$, $11083$, and $158891976157$. We can attempt the Pohlig-Hellman algorithm. For a detailed explanation, refer to this resource. In summary, this strategy involves reducing the discrete logarithm problem to smaller subgroups, where finding the discrete log is manageable. Then, the findings from these smaller subgroups can be combined to reconstruct the accurate private key using the Chinese Remainder Theorem.

Let’s proceed with that approach and check if we can successfully find the correct priv_a.

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


G = E(926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367, 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253)

A = E(x1, y1)
B = E(x2, y2)

primes = [3, 11, 11083, 158891976157]
dlogs = []
order = 6811640204116707417092117962115673978365477767365408659433165386030330695774842975950864518820891774127689003723319868798748651155450639754051764297493817
for fac in primes:
    t = int(order) // int(fac)
    dlog = discrete_log(t*A,t*G,operation="+")
    dlogs += [dlog]
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order


priv_a = crt(dlogs, primes)
assert A == G*priv_a

Executing the above code confirms that the assertion is True, meaning we have successfully recovered priv_a.

After obtaining priv_a, we can calculate C and use it as the AES key to decrypt the flag. Below is the full script to solve this challenge (with the assistance of 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


x1 = 6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997
y1 = 2456156841357590320251214761807569562271603953403894230401577941817844043774935363309919542532110972731996540328492565967313383895865130190496346350907696
x2 = 4226762176873291628054959228555764767094892520498623417484902164747532571129516149589498324130156426781285021938363575037142149243496535991590582169062734
y2 = 425803237362195796450773819823046131597391930883675502922975433050925120921590881749610863732987162129269250945941632435026800264517318677407220354869865
a = 726
kp = ((x1^3 -x2^3) + a*(x1-x2)) - (y1^2 - y2^2)

p = 6811640204116707417092117962115673978365477767365408659433165386030330695774965849821512765233994033921595018695941912899856987893397852151975650548637533
b = (y1^2 - x1^3 - a*x1) % p
F = GF(p)
E = EllipticCurve(F, [726, b])
order = E.order()
print(order)

G = E(926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367, 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253)

A = E(x1, y1)
B = E(x2, y2)

primes = [3, 11, 11083, 158891976157]
dlogs = []
for fac in primes:
    t = int(order) // int(fac)
    dlog = discrete_log(t*A,t*G,operation="+")
    dlogs += [dlog]
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order

priv_a = crt(dlogs, primes)
assert A == G*priv_a
C = priv_a * B
secret = C[0]

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from hashlib import sha256

hash = sha256()
hash.update(long_to_bytes(int(secret)))

key = hash.digest()[16:32]
iv = b'u\x8fo\x9aK\xc5\x17\xa7>[\x18\xa3\xc5\x11\x9en'
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = b'V\x1b\xc6&\x04Z\xb0c\xec\x1a\tn\xd9\xa6(\xc1\xe1\xc5I\xf5\x1c\xd3\xa7\xdd\xa0\x84j\x9bob\x9d"\xd8\xf7\x98?^\x9dA{\xde\x08\x8f\x84i\xbf\x1f\xab'

flag = cipher.decrypt(ct)
print(f'{flag = }')

Flag: HTB{0rD3r_mUsT_b3_prEs3RveD_!!@!}

Blunt [easy]

Description

Valuing your life, you evade the other parties as much as you can, forsaking the piles of weaponry and the vantage points in favour of the depths of the jungle. As you jump through the trees and evade the traps lining the forest floor, a glint of metal catches your eye. Cautious, you creep around, careful not to trigger any sensors. Lying there is a knife - damaged and blunt, but a knife nonetheless. You’re not helpless any more.

Initial Analysis

In this challenge, we were given a source code named source.py and output.txt.

 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


from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import getPrime, long_to_bytes
from hashlib import sha256

from secret import FLAG

import random


p = getPrime(32)
print(f'p = 0x{p:x}')

g = random.randint(1, p-1)
print(f'g = 0x{g:x}')

a = random.randint(1, p-1)
b = random.randint(1, p-1)

A, B = pow(g, a, p), pow(g, b, p)

print(f'A = 0x{A:x}')
print(f'B = 0x{B:x}')

C = pow(A, b, p)
assert C == pow(B, a, p)

# now use it as shared secret
hash = sha256()
hash.update(long_to_bytes(C))

key = hash.digest()[:16]
iv = b'\xc1V2\xe7\xed\xc7@8\xf9\\\xef\x80\xd7\x80L*'
cipher = AES.new(key, AES.MODE_CBC, iv)

encrypted = cipher.encrypt(pad(FLAG, 16))
print(f'ciphertext = {encrypted}')

Based on the above source code, seems like it try to implement Diffie-Hellman key exchange. The goal here is we need to recover the private key a, so that we can calculate C.

Solution

Observed that discrete log is hard, but the value that is used here is too small. We can easily find the discrete log with the help of sagemath, so that we can recover C (which is used as the AES key), and we can decrypt the flag. Below is the script that I use to decrypt it.

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


from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import getPrime, long_to_bytes
from hashlib import sha256

p = 0xdd6cc28d
g = 0x83e21c05
A = 0xcfabb6dd
B = 0xc4a21ba9
ciphertext = b'\x94\x99\x01\xd1\xad\x95\xe0\x13\xb3\xacZj{\x97|z\x1a(&\xe8\x01\xe4Y\x08\xc4\xbeN\xcd\xb2*\xe6{'

a = discrete_log(A, Mod(g,p))
C = pow(B, a, p)

hash = sha256()
hash.update(long_to_bytes(int(C)))
key = hash.digest()[:16]
iv = b'\xc1V2\xe7\xed\xc7@8\xf9\\\xef\x80\xd7\x80L*'
cipher = AES.new(key, AES.MODE_CBC, iv)
msg = cipher.decrypt(ciphertext)
print(f'{msg = }')

Flag: HTB{y0u_n3ed_a_b1gGeR_w3ap0n!!}

Iced TEA [easy]

Description

Locked within a cabin crafted entirely from ice, you’re enveloped in a chilling silence. Your eyes land upon an old notebook, its pages adorned with thousands of cryptic mathematical symbols. Tasked with deciphering these enigmatic glyphs to secure your escape, you set to work, your fingers tracing each intricate curve and line with determination. As you delve deeper into the mysterious symbols, you notice that patterns appear in several pages and a glimmer of hope begins to emerge. Time is flying and the temperature is dropping, will you make it before you become one with the cabin?

Initial Analysis

In this chalenge we were given a source code named source.py and output.txt.

 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
from secret import FLAG
from Crypto.Util.Padding import pad
from Crypto.Util.number import bytes_to_long as b2l, long_to_bytes as l2b
from enum import Enum

class Mode(Enum):
    ECB = 0x01
    CBC = 0x02

class Cipher:
    def __init__(self, key, iv=None):
        self.BLOCK_SIZE = 64
        self.KEY = [b2l(key[i:i+self.BLOCK_SIZE//16]) for i in range(0, len(key), self.BLOCK_SIZE//16)]
        self.DELTA = 0x9e3779b9
        self.IV = iv
        if self.IV:
            self.mode = Mode.CBC
        else:
            self.mode = Mode.ECB
    
    def _xor(self, a, b):
        return b''.join(bytes([_a ^ _b]) for _a, _b in zip(a, b))

    def encrypt(self, msg):
        msg = pad(msg, self.BLOCK_SIZE//8)
        blocks = [msg[i:i+self.BLOCK_SIZE//8] for i in range(0, len(msg), self.BLOCK_SIZE//8)]
        
        ct = b''
        if self.mode == Mode.ECB:
            for pt in blocks:
                ct += self.encrypt_block(pt)
        elif self.mode == Mode.CBC:
            X = self.IV
            for pt in blocks:
                enc_block = self.encrypt_block(self._xor(X, pt))
                ct += enc_block
                X = enc_block
        return ct

    def encrypt_block(self, msg):
        m0 = b2l(msg[:4])
        m1 = b2l(msg[4:])
        K = self.KEY
        msk = (1 << (self.BLOCK_SIZE//2)) - 1

        s = 0
        for i in range(32):
            s += self.DELTA
            m0 += ((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])
            m0 &= msk
            m1 += ((m0 << 4) + K[2]) ^ (m0 + s) ^ ((m0 >> 5) + K[3])
            m1 &= msk
        
        m = ((m0 << (self.BLOCK_SIZE//2)) + m1) & ((1 << self.BLOCK_SIZE) - 1) # m = m0 || m1

        return l2b(m)



if __name__ == '__main__':
    KEY = os.urandom(16)
    cipher = Cipher(KEY)
    ct = cipher.encrypt(FLAG)
    with open('output.txt', 'w') as f:
        f.write(f'Key : {KEY.hex()}\nCiphertext : {ct.hex()}')

Taking a look at the challenge, we were given the KEY and the ciphertext. That means the challenge here is we only need to create a decrypt function, because they gave us the KEY.

Solution

The above source code is trying to implement TEA. We can simply follow the wikipedia example (or just ask ChatGPT to made it for us :D). Below is the function that we can use to decrypt it.

 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


    def decrypt(self, ciphertext):
        blocks = [ciphertext[i:i+self.BLOCK_SIZE//8] for i in range(0, len(ciphertext), self.BLOCK_SIZE//8)]
        pt = b''

        if self.mode == Mode.ECB:
            for ct in blocks:
                pt += self.decrypt_block(ct)

        return pt

    def decrypt_block(self, msg):
        m = b2l(msg)
        m1 = m & ((1 << (self.BLOCK_SIZE//2)) - 1)
        m0 = m >> (self.BLOCK_SIZE//2)
        K = self.KEY
        msk = (1 << (self.BLOCK_SIZE//2)) - 1

        s = self.DELTA * 32
        for i in range(32):
            m1 -= ((m0 << 4) + K[2]) ^ (m0 + s) ^ ((m0 >> 5) + K[3])
            m1 &= msk
            m0 -= ((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])
            m0 &= msk
            s -= self.DELTA
        
        decrypted_block = l2b(m0) + l2b(m1)
        return decrypted_block

Using the above implementation of the decrypt, we can recover the flag.

Flag: HTB{th1s_1s_th3_t1ny_3ncryp710n_4lg0r1thm_____y0u_m1ght_h4v3_4lr34dy_s7umbl3d_up0n_1t_1f_y0u_d0_r3v3rs1ng}

Primary Knowledge [very easy]

Description

Surrounded by an untamed forest and the serene waters of the Primus river, your sole objective is surviving for 24 hours. Yet, survival is far from guaranteed as the area is full of Rattlesnakes, Spiders and Alligators and the weather fluctuates unpredictably, shifting from scorching heat to torrential downpours with each passing hour. Threat is compounded by the existence of a virtual circle which shrinks every minute that passes. Anything caught beyond its bounds, is consumed by flames, leaving only ashes in its wake. As the time sleeps away, you need to prioritise your actions secure your surviving tools. Every decision becomes a matter of life and death. Will you focus on securing a shelter to sleep, protect yourself against the dangers of the wilderness, or seek out means of navigating the Primus’ waters?

Initial Analysis

In this challenge, we were given a file named source.py and output.txt.

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


import math
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG

m = bytes_to_long(FLAG)

n = math.prod([getPrime(1024) for _ in range(2**0)])
e = 0x10001
c = pow(m, e, n)

with open('output.txt', 'w') as f:
    f.write(f'{n = }\n')
    f.write(f'{e = }\n')
    f.write(f'{c = }\n')

The problem with the above encryption is that the n is actually a prime number, not the result of multiplication two prime numbers. Due to this, the private key d recovery is quite straightforward.

Solution

To calculate the private key d, we can simply calculate it by doing inverse_mod(e, n-1). After recovering d, we can simply decrypt the c by doing pow(c,d,n).

1
2
3
4
5
6
7
8


from Crypto.Util.number import *

n = 144595784022187052238125262458232959109987136704231245881870735843030914418780422519197073054193003090872912033596512666042758783502695953159051463566278382720140120749528617388336646147072604310690631290350467553484062369903150007357049541933018919332888376075574412714397536728967816658337874664379646535347
e = 65537
c = 15114190905253542247495696649766224943647565245575793033722173362381895081574269185793855569028304967185492350704248662115269163914175084627211079781200695659317523835901228170250632843476020488370822347715086086989906717932813405479321939826364601353394090531331666739056025477042690259429336665430591623215

d = inverse(e, n-1)
print(long_to_bytes(pow(c, d, n)))

Flag: HTB{0h_d4mn_4ny7h1ng_r41s3d_t0_0_1s_1!!!}

Makeshift [very easy]

Description

Weak and starved, you struggle to plod on. Food is a commodity at this stage, but you can’t lose your alertness - to do so would spell death. You realise that to survive you will need a weapon, both to kill and to hunt, but the field is bare of stones. As you drop your body to the floor, something sharp sticks out of the undergrowth and into your thigh. As you grab a hold and pull it out, you realise it’s a long stick; not the finest of weapons, but once sharpened could be the difference between dying of hunger and dying with honour in combat.

Initial Analysis

In this challenge, we were given a file named source.py and output.txt

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


from secret import FLAG

flag = FLAG[::-1]
new_flag = ''

for i in range(0, len(flag), 3):
    new_flag += flag[i+1]
    new_flag += flag[i+2]
    new_flag += flag[i]

print(new_flag)

The encryption is quite straightforward, it just reverse the FLAG string, then scrambled it per 3 characters.

Solution

We can simply re-arranged per 3 characters, then reverse it. Below is the script that I used to solve:

1
2
3
4
5
6
7


flag = '!?}De!e3d_5n_nipaOw_3eTR3bt4{_THB'
new_flag = ''
for i in range(0, len(flag), 3):
    new_flag += flag[i+2]
    new_flag += flag[i]
    new_flag += flag[i+1]
print(new_flag[::-1])

Flag: HTB{4_b3tTeR_w3apOn_i5_n3edeD!?!}

Dynastic [very easy]

Description

You find yourself trapped inside a sealed gas chamber, and suddenly, the air is pierced by the sound of a distorted voice played through a pre-recorded tape. Through this eerie transmission, you discover that within the next 15 minutes, this very chamber will be inundated with lethal hydrogen cyanide. As the tape’s message concludes, a sudden mechanical whirring fills the chamber, followed by the ominous ticking of a clock. You realise that each beat is one step closer to death. Darkness envelops you, your right hand restrained by handcuffs, and the exit door is locked. Your situation deteriorates as you realise that both the door and the handcuffs demand the same passcode to unlock. Panic is a luxury you cannot afford; swift action is imperative. As you explore your surroundings, your trembling fingers encounter a torch. Instantly, upon flipping the switch, the chamber is bathed in a dim glow, unveiling cryptic letters etched into the walls and a disturbing image of a Roman emperor drawn in blood. Decrypting the letters will provide you the key required to unlock the locks. Use the torch wisely as its battery is almost drained out!

Initial Analysis

In this challenge, we were given a file named source.py and output.txt

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


from secret import FLAG
from random import randint

def to_identity_map(a):
    return ord(a) - 0x41

def from_identity_map(a):
    return chr(a % 26 + 0x41)

def encrypt(m):
    c = ''
    for i in range(len(m)):
        ch = m[i]
        if not ch.isalpha():
            ech = ch
        else:
            chi = to_identity_map(ch)
            ech = from_identity_map(chi + i)
        c += ech
    return c

with open('output.txt', 'w') as f:
    f.write('Make sure you wrap the decrypted text with the HTB flag format :-]\n')
    f.write(encrypt(FLAG))

The encryption here is quite straightforward, where it encrypt the text by shifting it based on the current character index.

Solution

We can easily make the decrypt method which try to shift back the encrypted character by its position. Below is the script that I used to solve this challenge:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


def to_identity_map(a):
    return ord(a) - 0x41

def from_identity_map(a):
    return chr(a % 26 + 0x41)

def decrypt(c):
    m = ''
    for i in range(len(c)):
        ch = c[i]
        if not ch.isalpha():
            dm = ch
        else:
            chi = to_identity_map(ch)
            dm = from_identity_map(chi - i)
        m += dm
    return m

flag = decrypt('DJF_CTA_SWYH_NPDKK_MBZ_QPHTIGPMZY_KRZSQE?!_ZL_CN_PGLIMCU_YU_KJODME_RYGZXL')
print(f'HTB{{{flag}}}')

Flag: HTB{DID_YOU_KNOW_ABOUT_THE_TRITHEMIUS_CIPHER?!_IT_IS_SIMILAR_TO_CAESAR_CIPHER}

Follow me on twitter

Contents

Cyber Apocalypse 2024: Crypto

Crypto

ROT128 [insane]

Initial Analysis

Solution

Tsayaki [hard]

Initial Analysis

Solution

Permuted [hard]

Initial Analysis

Solution

Partial Tenacity [medium]

Initial Analysis

Solution

Arranged [medium]

Initial Analysis

Solution

Blunt [easy]

Initial Analysis

Solution

Iced TEA [easy]

Initial Analysis

Solution

Primary Knowledge [very easy]

Initial Analysis

Solution

Makeshift [very easy]

Initial Analysis

Solution

Dynastic [very easy]

Initial Analysis

Solution

Social Media