William Snavely

William Snavely

We are the boat, we are the sea.

Radools Realm, Part 3: Hash Extraction

This is the third of four CTF problems I made while studying at Carnegie Mellon University. To try the problem, go to this repository. You will need a recent version of Java installed. More detailed instructions can be found in the repository. The problem can be found in the level2 directory.

Solution

The hash code from the previous level has been upgraded to an HMAC, as we can see from the provided server code:

private String secret = "REDACTED";

private static String computeHmac(String json, String secret) {
	String sha1 = null;
	try {
		MessageDigest crypt = MessageDigest.getInstance("SHA-1");
		crypt.reset();
		crypt.update((secret + json).getBytes("UTF-8"));
		sha1 = byteToHex(crypt.digest(), 4);
	} catch (NoSuchAlgorithmException e) {
		e.printStackTrace();
	} catch (UnsupportedEncodingException e) {
		e.printStackTrace();
	}
	return sha1;
}

In brief: the checksum is computed by taking the SHA-1 hash of the save file contents concatenated with a server-side secret. At this point, some players might be tempted to try and exploit this HMAC scheme by using some kind of length extension attack, since the HMAC has the known-vulnerable form of SHA-1(secret + key). It might be possible to somehow take advantage of this flaw, but it seems tricky; first of all, you don’t know the length of the secret key, which is generally a requirement in these kinds of attacks. Second of all, you are extending a JSON document, which has a well-defined ending, thus it might be difficult to get the server to parse anything you place at the end. Perhaps there is a simpler approach.

Observe how the server behaves when it receives an illegal save file (where the checksum doesn’t match):

expectedHmac = computeHmac(noChecksumStr, secret);
rc = expectedHmac.compareTo(actualHmac);
if (rc != 0) {
	response = "BIG BIRD ERROR CODE " + rc;
}

The server returns an error code when the checksum fails, and this error code happens to be the return value from the compareTo method on the HMAC string. If we read the documentation for this method, we learn that if two Strings have their first difference at index k, then the method returns:

 this.charAt(k)-anotherString.charAt(k)

For example, if we compare “heap” with “head”, the result will be ('p' - 'd'), the difference between the first two characters that don’t match (after converting those characters to their underlying numerical representation). The character ‘p’ has ASCII value 112, and ‘d’ 100, so in this case we will get 112 - 100 = 12.

This means that when the server detects an invalid save file, it leaks a little bit of information about precisely how the save file is invalid, in particular the difference between the first mismatched characters. We can abuse this to leak the expected HMAC of an arbitary save file, as follows:

1) Update the save file achievements to the desired state.

2) Set the checksum field in the save file to a string the same length as an SHA-1 hash, but using characters that don’t occur in an SHA-1 hash. This is pretty easy, because the hash in the save file uses a hexadecimal representation, which only uses digits and 'abcdef'. So for example, we could submit a bogus SHA-1 hash filled with the character 'g'.

3) Send the save file to the server, and note the error code. Subtract the error code from the first character in the bogus hash code to determine the actual first character.

4) Repeat step 3, but for the second, third, fourth, etc. characters of the hash code, until you have leaked the entire string.

In brief: we determine the hash code character by character, by exploiting the information leaked by the server error message. This is best done by writing a script that automates the repeated submission of the save file to the server endpoint; manually extracting the hash will take a while.

Teaching Goal

This problem was meant to give players a more authentic sense of what CTF problems are like. You have to identify a weakness in the system and exploit it to get a result. You have to think outside the box to do this efficiently, e.g. by automating some part of the process. Players also learn about HMACs, and the dangers of leaking internal program details, e.g. by returning server-side error codes to a client.

The problem was partly inspired by the classic TENEX password vulnerability, which allowed an adversary to find a password character by character by measuring virtual memory page faults.

Updated: