GCHQ Challenge - Stage 3

Stage 3 is at http://www.thisisgloucestershire.co.uk/bletchley.html and reveals a new code:

2910404C21CF8BF4CC93B7D4A518BABF34B42A8AB0047627998D633E653AF63A873C\
8FABBE8D095ED125D4539706932425E78C261E2AB9273D177578F20E38AFEF124E06\
8D230BA64AEB8FF80256EA015AA3BFF102FE652A4CBD33B4036F519E5899316A6250\
840D141B8535AB560BDCBDE8A67A09B7C97CB2FA308DFFBAD9F9

I wonder what it is! No time now… need to rescue the kids from the bath!

[Later that evening…] Well no answer yet, but some thoughts/updates:

1. it looks like it’s hex, it’s 256 bytes long (assuming the trailing slashes follow convention and simply denote a line-continuation)
2. it’s not a simple base64 encoding… :(
3. by observation there are byte values ranging from low (e.g. 10) to high (FF) so if this is a substitution cipher it’s clearly more complex than a vanilla letters-of-the-alphabet thing, or a simply rotation across a larger “alphabet” (think 256-bit extended ASCII).
4. I tried pluging it into a UTF-8 decoder but that got nowhere

So I am left with the “obvious” - which is that the private key from stage 2 was used to encrypt this, and I need to decrypt it using that. I’ve spent a good portion of the evening so far reading up on the openssl toolkit, and RSA encryption in particular.

Sadly the private key is “corrupt” (the GCHQ folks mangled it deliberately to insert the stage 2 solution into the “prime2” field) - however my reading about RSA has proved interesting in that you don’t NEED the Prime2 value to use the private key in principle - it is basically there as a “pre-computed value” to improve performance only. The critical values are some of the other values which remain intact. So that’s the good news. The bad news is that despite extensive googling I have yet to find a tool that can “repair” a broken RSA private key file for me (e.g. openssl doesn’t seem to be able to).

Related to the above I looked again at the private key file and remembered something I noticed, but passed over in stage 2: there is extensive duplication of data between the modulus field and the prime1 field, specifically exactly the first half of both fields (64 bytes out of 128) is the same!

Now I can’t say I understand this intimately, but from my reading about RSA, modulus = p1 * p2, so very roughly you would expect the modulus field to be double the length of the p1 and p2 fields, so that suggests to me that the p1 field has been extended artificially. I’m not sure what that means - does it mean the extra data in p1 (the second 64 bytes) was copied from the original p2, before p2 was used to encode the stage2 answer? Also if the left hand 64 bytes of the modulus are the same as p1 (minus those second 64 bytes) then surely that means that p2 = 2^512 (basically to shift all those bits 512 bits to the left) ?

Perhaps that’s all irrelevant… I think the best form of attack is simply to use the information available from the private key and either: 1) find a tool that can manually decrypt an RSA encoded message using the information available within the private key or 2) write a tool that can re-create the private key so that I can use openssl to do it. I couldn’t find any node.js libraries for this that didn’t appear to depend on openssl, so I’m gonna start looking at java libraries (tomorrow!)

It’s amazing what a good night’s sleep and a bit of luck can do…

So after much unsuccessful googling for easy to use RSA manipualtion libraries, I thought I’d simply implement implement the RSA calculations myself in java using BigInteger. A google for “RSA calculation” however conveniently yielded an online tool http://nmichaels.org/rsa.py that worked (all the tools I looked for yesterday were limited precision, small primes, etc, which wouldn’t work for the 1024 bit encryption here).

Simply typing in the public modulus, the public exponent and the private exponent, plus of course the hex string from challenge 3 itself and hitting the decrypt button worked a treat (note: you have to specify all of the elements in hex, including the public exponent, e.g. 0x 10001 rather than 65537).

The tool produced the following output:

0x20 0x20 0x20 0x20 0x20 0x20 0x20 0x20 0x77 0x77 0x2e 0x77 0x68 0x74 0x72 0x65 0x67 0x65 0x73 0x69 0x65 0x74 0x2e 0x72 0x6f 0x63 0x75 0x2e 0x2f 0x6b 0x6e 0x65 0x67 0x69 0x61 0x6d 0x30 0x32 0x33 0x31 0x20 0x20 0x20 0x20 0x20 0x20 0x20 0x20

Even by observation I knew that this was likely to be the answer - all of the numbers are in the “printable ASCII range”, so it is back to the tool from the previous challenge to convert Hex back to ASCII to confirm my suspicion http://tomeko.net/online_tools/hex_to_ascii.php?lang=en.

Entering the deciphered Hex string here (and requesting it to automatically remove the 0x hex identifiers first, or doing that manually) reveals the following:

ww.whtregesiet.rocu./knegiam0231

Now I recognise this as per the previous challenge - the letters are swapped in pairs, kind of a big/little-endian transposition. Simply going through and swapping the order of each pair of letters reveals the answer:

http://www.theregister.co.uk/enigma2013

A quick check on the canyoufindit website confirms that the final part of the URL is indeed the answer to question 3 (enigma2013)

Onto stage 4….