The final round of Gemastik Cyber Security division finally returned to attack-defense format with a tick system. Gemastik is an event organized by the Indonesian ministry, where all of the participants are only undergraduate students. In this format, each team must submit a flag for every tick. This format is also used in several popular international attack-defense CTFs, such as DEFCON, HITB SECCONF, ENOWARS, and so on.
For this event, I wrote a crypto challenge about predictable nonce in ECDSA named burvesigner. There are quite a lot of considerations when we try to put crypto challenges into an attack-defense format. One of them is that I have to ensure that this challenge can be exploited with an automation script in a very short time so that all teams can exploit all other teams in just one tick. So that in preparing it, the bruteforce process must be designed to be as short as possible.
Unfortunately, only one team managed to solve this challenge during the competition. I guess it’s because the competition time is so short for the high number of challenges, so the participants’ focus is divided into other challenges. Without further ado, here is a short writeup about burvesigner.
burvesigner (solved by 1/20 teams)
There is a web service where participants can log in as a guest role. When a participant logs in, the service will generate a signature that is used as a token by the user using the Elliptic Curve Digital Signature Algorithm (ECDSA) variation algorithm with the secp112r1 curve.
Quoted from Wikipedia, here’s how the ECDSA signature generation process is performed:
Attack
In point 3, the nonce $ k $ used in the signature generation process must be a secure random number. However, in this challenge, the nonce used by the service is not a secure random, so participants can take advantage of this condition to perform signature forgery with different roles. Participants must perform signature forgery with the admin role to successfully get the other team’s flag (attack).
The following challenge code has a vulnerability in the signature generation process:
def sign(self, msg):
self.set_keys()
k = (int(time() * 1337) << self.u) + self.v
R = k * self.C.G
s = (self.hash(msg) - self.x * R.x) * pow(k, -1, self.C.q) % self.C.q
sig = b"".join(map(self.to_bytes, [R.x, R.y, s]))
return urlsafe_b64encode(sig)
It can be seen that the nonce $ k $ is generated using the formula $ 2^{u} t + v $ where $ t $ allows it to be bruteforced by participants in a short time, $ u $ is a constant, and $ v $ is a random number of size $ u $ bits. By collecting at least 2 signatures (performing guest login 2 times), participants can eliminate 2 equations to get the nonce $ k $ value and the private key used by the service.
Defense
By changing the nonce $ k $ to a secure random value, participants should have successfully defended their service. As an additional point, there is a slight improper implementation in the signature generation process. In the signature generation process, the hash function used by the service is CRC32 which obviously only generates 32-bit output which is small if we compare to curve bitsize. This is also not the best practice considering that CRC is not a secure hash function. The best practice is to use a hash function that has been proven safe such as SHA.