This is the time that Firebird Internal CTF happens. I made three crypto challenges this year - Lack of Entropy (⭐), Authenticator (⭐⭐) and Collider (⭐⭐). I will discuss the solution for all of them in the blog post.

What are the stars? They are the difficulties I estimated when comparing to global CTFs (where I documented them here since Q3 last year).

Lack of Entropy (Crypto)⌗

Three (out of six) teams solved this during the CTF.

Challenge Summary⌗

Mystiz's computer is lack of entropy. He needs to reuse randomness to generate the primes for RSA...

Attachments: chall.py, output.txt

We are given a RSA public key $(n, e)$ and an encrypted flag $c$:

n = 12189464288007059657184858632825479990912616419482466046617619319388181010121359489739982536798361842485210016303524715395474637570227926791570158634811951043352789232959763417380155972853016696908995809240738171081946517881643416715486249
e = 65537
c = 10093874086170276546167955043813453195412484673031739173390677430603113063707524122014352886564777373620029541666833142412009063988439640569778321681605225404251519582850624600712844557011512775502356036366115295154408488005375252950048742

Note that the prime factors of $n$ (namely $p$ and $q$) are generated such that:

$\begin{cases} p = a_0 + 3 a_1 + 3^2 a_2 + ... \\ q = a_0 + 10 a_1 + 10^2 a_2 + ... \end{cases},$

where $a_i \in \{0, 1, 2\}$. The objective is to recover the flag.

Solution⌗

One important fact that we could observe is $q$ increases as $p$ increases (Refer to the above figure). That said, $n = p \cdot q$ also increases as $p$ increases. In that way, we can simply perform binary search on $\tilde{p}$ and check if the corresponding $\tilde{n}$ satisfying:

1. $\tilde{n} < n$ (which imply that $\tilde{p} < p$), or
2. $\tilde{n} > n$ (which imply that $\tilde{p} > p$), or
3. $\tilde{n} = n$ (which imply that $\tilde{p} = p$).

Authenticator (Crypto)⌗

One (out of six) team solved this during the CTF.

Challenge Summary⌗

Hash-based authentication is great and I have invented one. Can you prove that my system is secure?

nc HOST PORT

Attachments: chall.py

Define a protocol $\mathcal{P}$ that is used to authenticates between a client and a server. Suppose that they have a pre-shared password password:

1. Client generates a 16-byte challenge_client and sends it to the server.
2. Server computes the response response_server (specified below) and generates a 16-byte challenge_server.
3. Server sends response_server and challenge_server to the client.
4. Client verifies response_server and aborts if it is incorrect. Otherwise, it computes the response response_client (specified below).
5. Client sends response_client to the server.
6. Server verifies response_client and aborts if it is incorrect. Otherwise, it is said that the authentication is completed.
response_server = blake3(password + "HANDSHAKE_FROM_SERVER" + challenge_client)
response_client = blake3(password + "HANDSHAKE_FROM_CLIENT" + challenge_server)

Solution script⌗

p = int(input('p = '))
g = 1337

def hash(m):
m = int.from_bytes(b'SECUREHASH_' + m, 'big')
return int(pow(g, m, p)).to_bytes(256//8, 'big')

# (x0 + 109) + 256 * (x1 + 109) + 256^2 * (x2 + 109) + ... + 256^(k-1) * (x(k-1) + 109) + 256^k * m0 = v (mod p-1)
m0 = int.from_bytes(b'SECUREHASH_', 'big')

for l in range(100, 200):
print(f'[ ] Trying {l = }...')
s = int((sum(256**i * 109 for i in range(l)) + 256**l * m0 - v) % (p-1))
'''
[s          1      0      0     ... 0] <-- 1
[256^(k-1)  0      1      0     ... 0] <-- x(k-1)
[256^(k-2)  0      0      1     ... 0] <-- x(k-2)
[                       ...          ]     ...
[256^0      0      0      0     ... 1] <-- x0
[p-1        0      0      0     ... 0] <-- *
↓          ↓      ↓      ↓         ↓
0          1      x(k-1) x(k-2)    x0
'''
weights = [256] + [1 for _ in range(l+1)]

A = Matrix(l+2, l+2)
Q = diagonal_matrix(weights)

# First column
A[0, 0] = s
A[l+1, 0] = p-1
for i in range(l): A[i+1, 0] = 256^(l-1-i)

# The remaining columns
for i in range(l+1): A[i, i+1] = 1

A *= Q
A = A.LLL()
A /= Q

for row in A:
if row[0] != 0: continue
if row[1] < 0: row = -row
if row[1] != 1: continue
m = row[2:] # centered by 109

if min(m) < -12: continue
if max(m) > 12: continue

m = bytes(109 + mc for mc in row[2:]).decode()
print(f"[*] '{m}' has the same hash with 'pleasegivemetheflag'")
assert False, "Collision found!"