CONFidence 2016 Teaser 'spkac' writeup

This is a writeup for the “spkac” challenge from the CONFidence 2016 Teaser CTF. It was a cryptography challenge worth 200 points.

The Challenge

We’re given access to a website with an HTML form:

Form presented by the challenge

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:

After submittung the Form

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:

def dataToVerify(der, secret):
	# We can't trust secret sent by browser, user can modify it !
	der[0][1] = pyasn1.type.char.IA5String(secret)
	return pyasn1.codec.der.encoder.encode(der[0])

def cmpMin(a,b):
	minLen = min(len(a),len(b))
	if minLen < 1:
	# empty string ? !
	return False
	
	for i in range(minLen):
		if a[::-1][i] <> b[::-1][i]:
			return False
	
	return True

def verify(der, secret):
	md5rsa = pow(getSignature(der), 65537, getN(der))
	md5cmp = ''
	while md5rsa:
		md5cmp = chr(md5rsa % 256) + md5cmp
		md5rsa /= 256
	# md5cmp is with padding, so compare only up to hash length
	return cmpMin(md5cmp, md5.new(dataToVerify(der, secret)).digest())

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 s⁶⁵⁵³⁷ 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 Attack

The critical bug is just this: the cmpMin function. If s⁶⁵⁵³⁷ 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 s_i such that s_i⁶⁵⁵³⁷ 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 = m^d mod N, where d is the secret key. In order to verify this signature s, we compute s^e 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 s_i such that s_i^e mod N = i, we can simply compute s_i as i^d 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 s_i-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 s_i. 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:

DrgnS{7H1s_FL49_91V3s_PO1N72}

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.)