The final round of Gemastik Cyber Security division now uses the attack-defense format with a tick system. Gemastik is an event organized by the Indonesian ministry for undergraduate students. In this format, teams must submit a flag for every tick. This format is also used in popular international attack-defense CTFs like DEFCON, HITB SECCONF, and ENOWARS.
For this event, I created a crypto chall called burvesigner about predictable nonce in ECDSA. When making crypto challs for attack-defense format, we need to consider several things. The chall must be exploitable with an automation script quickly, so teams can exploit others within one tick. This means the bruteforce process needs to be fast.
burvesigner (solved by 1/20 teams)
The chall provides a web service where users can log in as a guest. When a user logs in, the service creates a signature token using the Elliptic Curve Digital Signature Algorithm (ECDSA) with the secp112r1 curve.
Here’s how ECDSA signature generation works, as explained by Wikipedia:
Attack
In step 3, the nonce $ k $ must be a secure random number. However, this chall uses an insecure nonce. This lets a team forge signatures with different roles. To get the flag, they need to forge a signature with admin role.
The chall code has a bug in the signature generation:
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)
The nonce $ k $ is created using $ 2^{u} t + v $. Here, $ t $ can be bruteforced quickly, $ u $ is a constant, and $ v $ is a random number of $ u $ bits. By getting two signatures (logging in as a guest twice), a team can solve two equations to find the nonce $ k $ and the private key.
Defense
To defend their service, a team should use a secure random value for the nonce $ k $. There’s also another issue: the service uses CRC32 as its hash function. This only produces 32-bit output, which is too small for the curve size. CRC is not a secure hash function. A better choice would be a proven secure hash function like SHA.