This weekend was the Boston Key Party Ctf. There were a bunch of challenge, and my team did pretty well (top 10) even though we didn’t have a lot of our regulars. Two of the problems involved signing a string “There is no need to be upset” using Elgamal signing.
The TLDR version is both failed in the duplicate checks.
Both problems required “proof of work” prior to the signing test:
- Server reads 9 bytes of random data and generates a base64 encoded version
- Sever sends the base64 to client (12 bytes)
- Client adds up to 8 bytes
- Server then verifies first 12 are the ones it sent
- Server computes SHA1 hash of all 20 bytes
- Hash must end with 24 bits of 0 to pass
Once you passed the proof of work you had to send the message (“There is no need to be upset”) and signature (r and s). The format of the message and signature was json with Wood Island, and asn1 with Orient Heights. If the signature passed you were rewarded with the key.
Along with the server script and the key information, we were given a collection of valid signatures, lest we had to brute force up to a 1024 bit private key. However, even though the message that the server wanted was in the example signatures, the server checked that we weren’t sending a duplicate signature.
Here in lies the flaw we used. Wood Island used the python json library to decode the string into a dict and the duplicate check was a simple “user_dict in list” check. Adding a field to the json was enough to pass the check. Orient Heights just compared the binary ASN1 encoding; once again adding a field caused it to fail.