This is a writeup for the “spkac” challenge from the CONFidence 2016 Teaser CTF. It was a cryptography challenge worth 200 points.
We’re given access to a website with an HTML form:
We are given the choice between two messages: “Welcome” and “Flag”. Sadly but predicatbly, just submitting the form with the flag selected, just returns an error.
What we see below that is an HTML keygen element. When a form with such an element is submitted, the browser creates a public key and uses the corresponding secret key to sign the public key together with an optional challenge. The public key, the challenge and the signature are then put together into a structure named SignedPublicKeyAndChallenge, which is probably what gave the exercise its name. This structure is first encoded using ASN.1 (specifically, DER), then base64-encoded, and finally sent to the server along with other form data. The form in our task uses the secret we put in the text box as the challenge. The default type of key appears to be RSA.
When we submit the form with the “Welcome” message, we’re taken to the following website:
We’re seeing an encrypted message, an “Install Key” button, and some instructions. The “Install Key” button makes our browser install the previously generated key as a personal certificate. The instructions below tell us how the export that certificate, extract the private key, and use that to decrypt the message. (The instructions didn’t work for me, I had to add the -nodes option to the first command.)
We’re also given a glimpse at some code running on the server:
In the verify function at the bottom, we can see that the server extracts the signature s and the modulus N from the structure, computes s65537 mod N and encodes that number into a big-endian string of bytes. That string is then compared to some hash value via the cmpMin function, which basically just checks if the shorter one of its arguments is a suffix of the other. The comment in verify tells us that the programmer wanted to ignore the padding this way.
The critical bug is just this: the cmpMin function. If s65537 mod N were between 1 and 255 (including both), the cmpMin function would just check if that number equals the last byte of some unknown md5 hash value. So, if we could create numbers si such that si65537 mod N = i, for all i between 1 and 255, we could just try all of them. One of them would have to match the last byte of the md5 hash, unless that byte was 0. (We’d be unlucky in this case, but not lost.)
So, how can we create such numbers? The answer is easy. Recall that with RSA signatures, in order to sign some padded message m, we interpret m as a number and compute s = md mod N, where d is the secret key. In order to verify this signature s, we compute se mod N and check if that is a valid padded message. (Here, e = 65537, a very common choice.) Critically, raising some number to the e-th power and raising it to the d-th power are two complementary operations: Each one reverses the other. So, if we want to find a number si such that sie mod N = i, we can simply compute si as id mod N. Taking that number to the e-th power simply undoes the previous exponentiation with d, so we’re back at i.
Implementing the Attack
… was probably the hardest part of this challenge. I submitted the form described above, captured my traffic using BURP, and then extracted the encoded SignedPublicKeyAndChallenge structure. After stripping three layers of encoding (url encoding, base64 and ASN.1), I faced layers of ASN.1 structures within ASN.1 structures. I tried to poke around in there using the pyasn1 module, which was quite a pain. In retrospect, I should have tried the asn1crypto module for python, which might have made this a lot easier. I’m noting that for the next challenge.
I also saved the certificate, converted it to an unencrypted .pem file using the instructions given in the challenge, and wrote some python code to extract the secret key from that file.
Once I had everything decoded, I replaced the signature in my request with a number that would trigger the bug described above (i.e. one of the si-s), added the ASN.1 and base64 encodings, and issued a request to the server using the requests python module. (This one is definitly worth a look!) I tried this for all respective si. In most cases, the server returned an error (which is okay, remember that we’re trying to brute-force the last byte of the unknown md5 hash value), but after a few seconds I got a response that actually contained an encrypted message. I decrypted that message using the openssl command suggested by the challenge authors, and got the flag:
My code is quite messy, and since the challenge is down by now, I can not test any cleaned-up version. So I didn’t want to change my code too much. With this warning being given, you can find my code in our github repository. I’m also attaching the final encrypted message, the secret key generated by my browser in an (unencrypted) .pem file, and the HTML pages returned by the server. (Apparently, the HTML keygen element was replaced by some select element during saving… But you get the idea.)