Firebird Internal CTF 2022 Writeup
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.
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 and an encrypted flag :
Note that the prime factors of (namely and ) are generated such that:
where . The objective is to recover the flag.
Solution⌗

One important fact that we could observe is increases as increases (Refer to the above figure). That said, also increases as increases. In that way, we can simply perform binary search on and check if the corresponding satisfying:
- (which imply that ), or
- (which imply that ), or
- (which imply that ).
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 that is used to authenticates between a client and a server. Suppose that they have a pre-shared password password
:
- Client generates a 16-byte
challenge_client
and sends it to the server. - Server computes the response
response_server
(specified below) and generates a 16-bytechallenge_server
. - Server sends
response_server
andchallenge_server
to the client. - Client verifies
response_server
and aborts if it is incorrect. Otherwise, it computes the responseresponse_client
(specified below). - Client sends
response_client
to the server. - Server verifies
response_client
and aborts if it is incorrect. Otherwise, it is said that the authentication is completed.
When connected to the remote service, a 6-character password (that matches the regex /^[0-9a-zA-Z]{6}$/
) is generated. The player and the remote service respectively act as the client and the server. The objective is to complete the authentication within 10 seconds (while the player does not know the password).
Solution⌗
Walkthrough for rich person only⌗
Let's cater only the rich guys. You can simply connect to the server and send an arbitrary challenge_client
(I will use CHALLENGE_CLIENT
for simplicity). Upon receiving the response_server
, you can exhaust passwords in ten seconds using a 5680-core machine by checking whether:
You can proceed the authentication. Done! Easy?
What if I am not that rich?⌗
I guess most of us could not find a 5680-core machine easily. Instead of computing everything online, we can precompute the outputs of response_server
given that the client's challenge being CHALLENGE_CLIENT
. Below is the expected time and space taken for precompution.
- Estimated time taken: 15 hours
- Estimated space taken: 1800 GB
You can proceed the authentication. Done! Easy?
...Of course not! Precomputing for 15 hours is time-consuming, and taking up 1800 GB is absurd. Luckily there are two ways to reduce the time and space complexities by sacrificing a third factor.
Optimization 1: Precompute part of the password space⌗
This is still very resource-intensive with the above optimization. Can we precompute only of the password space? The answer is certain. However, the probability of recovering a password is decreased to .
Does it hurt? Not really. If we set , it is expected that we can recover one password every 64 times we connect to the server. This largely decrease the required resources.
- Estimated time taken: 15 minutes (⬇ 98.4%)
- Estimated space taken: 28.4 GB (⬇ 98.4%)
- Estimated service connections: 64 (⬆ 6400.0%)
Optimization 2: Store part of the BLAKE3 digest⌗
We can further reduce the space taken by storing 8 bytes of the digest (instead of the whole digest, which is 32 bytes).
As , it is unlikely that collision exists. We can reduce the space by 75% sacrificing a little bit of accuracy.
- Estimated time taken: 15 minutes (-)
- Estimated space taken: 7.1 GB (⬇ 75%)
- Estimated service connections: 64 (⬆ %)
You can proceed the authentication. Done! Easy?
Collider (Crypto)⌗
Zero (out of six) teams solved this during the CTF.
Challenge Summary⌗
Find a collision for my hash algorithm! It is basically military-graded: The output is 256-bit long, and discrete log is hard! I even made it harder such that you don't even have the public parameters!
nc HOST PORT
Attachments: chall.py
Define a hash algorithm below:
Suppose that the server is running the oracle that takes a message (with only lowercase English letters):
- Computes and sends to us.
- If but , sends the flag to us.
When connected to the server, a 256-bit prime and a 256-bit number is generated (and not given to us). We are allowed to call the oracle for five times. The goal is to obtain the flag.
Solution⌗
Recovering and ⌗
Since we are given only five calls of and we need one for getting the flag, it is expected that we could use at most four calls to recover the parameters and .
To do so, we can obtain , , and via . Thus
where is the prefix SECUREHASH_
. Since
we see that is a small multiple of . This allows us to obtain easily. Now we can effectively recover by
By the way, although we have recovered and , we will not use .
Finding a preimage⌗
Fermat's little theorem stated that for . Equivalently, if and are two padded messages (i.e., in the format SECUREHASH_...
), then
The goal is to find a padded message such that , with being the padded message SECUREHASH_pleasegivemetheflag
.
Let's present the message mathematically. If we write the unpadded message being , then
Therefore we need to find such that
We can solve the modular congruence with Lenstra–Lenstra–Lovász algorithm. LLL tries to find small roots (i.e., each variable is close to zero) so we need to "adjust the center". If we let for all 's, then which is smaller in magnitude. Now we have
Let (i.e., the right hand side), we know that there is an integer such that:
At this stage, we can construct the matrix below:
We can see that is a linear combination of the row vectors of , since
More importantly, the coefficients are integers. If is small (i.e., is short), then we can use LLL to recover such a vector. After all, LLL is an lattice reduction algorithm which is intended to find a set spanned by integer coefficients and short vectors. I suggest reading Cousin's blog post on lattice-based cryptography for an in-depth mathematical context.
We have introduced without any explanation. What is that? It is just a big number to encourage the first entry of the resulting vectors in the basis to be zero. When the first entry of a vector is non-zero, then the length of would be inevitably big. Since LLL tries to find a set of short vectors, is usually not included in the output. Finally, we can increase until a vector (where ) is found. It is suggested to try because , an average magnitude of the elements in the vector.