GCHQ Challenge Solution Explained 107
First time accepted submitter DrDevil writes "The British spy agency GCHQ recently published a puzzle at canyoucrackit.co.uk (as featured on Slashdot), now just a few days later an academic at the University of Greenwich in England has posted a full video explanation of the puzzle. The puzzle has three stages and is not at all simple — likely to challenge even the best computer science graduates."
Opaque (Score:4, Interesting)
I didn't give the challenge a serious go, but stage 1 just seems convoluted - why is it the mark of a good code cracker to recognise x86 bytecode?
Not a great challenge (Score:5, Interesting)
My opinion, as someone who has both solved and organized several challenges of this sort, is that the challenge is neither hard (at least by the standards of the ones I've dealt with) nor well designed. In fact, it kind of degenerates: it starts out OK but the ending is terrible.
Stage 1 is interesting: it combines recognizing executable code (the first thing I thought when I stared at that hex dump is "this looks like x86 code", but being able to recognize binary architectures is a valuable skill) combined with some steganography (fishing out the rest of the required data from the PNG. Fair enough, and OK for a first round.
Stage 2 starts out well: virtual machines are used for obfuscation and make fun challenges. However, the execution is backwards. Being given VM bytecode and a specificiation to implement a VM isn't a hacking or reverse engineering challenge; it's just work ("go implement this for me"). A much better challenge would be to be given either the spec or (preferably) code that implements it, and then have to reverse engineer the bytecode itself to solve the puzzle. That involves writing a custom disassembler, which is a much more interesting task.
Stage 3 is a clusterfuck. It's just an executable that checks for a few constants in a file and then builds a URL out of the rest of it. There's a hash (old-school DES crypt() salted password) that the input has to match, but even though it's crackable using a dictionary, you don't even have to do that because the URL includes the hash (which is in the executable), not the plaintext! The rest of the URL isn't checked, and it's basically a guessing game where you have to fish out constants from previous levels. It's just a glorified way of saying "okay, now take a wild guess as to what numbers to stick in the URL". It's not realistic in the slightest.
Anyone interested in a "better stage 2" might want to check out a level [marcansoft.com] that I put together for the Hack-It competition at the 18th Euskal Encounter (2010). Your goal is to figure out the 64-bit input key that works (if you don't know what "works" means, compile and run the code and it should be obvious). The full set of challenges can be found here: 2010 [marcansoft.com] 2011 [marcansoft.com] (unfortunately, the website / problem statements are in Spanish, but I'm sure you can work it out with a bit of copy/pasting into Google Translate - if there's enough interest I'll translate them to English).
I've been having a go... (Score:4, Interesting)
I'm aware that the solution has been leaking out onto the net...
Starting later than most, in spare time, I've trudged through stages One and Two... I've been playing with the stage-3 executable and have disassembled it... though there remains further tedious trudging for me to demonstrate by sensible sequential steps how to go about solving stage-3.
I'm finding it difficult to convince myself that it's worth the effort... I'm sure I can fathom any remaining steps - based upon the fact that there has been little about stages one and two that was actually 'challenging'. It seems silly to plod onwards without 'cheating'.
I was interested principally to try and find out what sort of skills GCHQ actually want... I never assumed I'd be (one of the) first to solve it. The experience has left me wondering what sort of job this sort of tom-foolery would suit one for. Sure debugging and OS-level skills can be valuable - but the challenge is most time consuming as one is required to guess the objective - identifying the intentions of the challenge setter rather than to address real-world issues.
Re:I thought this was a crypto/cypher challange (Score:4, Interesting)
Re:Opaque (Score:4, Interesting)
Not really.
You can make a simple cipher that is obfuscated in such a way that many people will not get it.
Heck a simply letter substitution ciper used on a dead language will pretty much cull the number of people trying to crack it by a significant amount. I completely fooled my CS instructor by doing just that. Aramaic phrase that had a simple letter substitution applied and a xor of a passphrase that was 1/10th the length of the cipher.
Mine was un-cracked for a full semester with him, his undergrads and all the CS students crakcing at it. Nowhere in the challenge did he say we HAD to use english as the content of the message.
Re:Opaque (Score:3, Interesting)
Let's assume for the sake of this discussion that you are a USian.
As a result of political infighting you have heads of state that are reviled in a vitriolic manner by about half the population.
Lets take a list of your heads of state:
Nixon (out due to Watergate)
Ford (ok, but reviled for Nixon pardon)
Carter (amiable bloke, but seemed to let America go to sleep on his watch)
Reagan (surprisingly effective, considering he was slowly losing his marbles)
H.W.Bush (had the bad luck to say "No new taxes" when ambush adverting was getting going)
Clinton (also effective, but American expectation of clean personal life when married to Hillary?? pleasse)
George Bush (endless disputes about chads)
Obama (has the bad luck to be black, leading to morons disputing his legitimacy to be President)
In the UK, Queen Lizzie enjoys the support of a large majority of the population, and most of the political shenanigans gets directed, not at the Head of State, but at the (semi) elected Prime Minister, thus keeping the head of state out of most of the sh1t. I'd say the UK system works better in that regard.
As for the tv cameras, I strongly suspect that most US shopping malls have the same coverage as our city centres, and your heavily robbed 7-11s probably have their own personal systems etc. Most states have surveillance of one sort or another; the only question is where and how much.
And we've (nearly) all been British Citizens and not British Subjects since the Nationality Act 1981 (subject is used but is normally incorrect)
Re:Screen recorder - here (Score:2, Interesting)
http://recordmydesktop.sourceforge.net/about.php
Re:Opaque (Score:5, Interesting)
It looked interesting, but I lost interest when I saw the salary -- slightly less than what I have already, working for a different bit of government. And GCHQ is in Cheltenham.
But have you visited the UK? I live here, so it's what I'm used to, but when visiting a couple of cities in the US recently I felt more "watched" and regulated. There were many signs with lists of local laws, with violations incurring big fines. There were *more* public (government/city/whatever) CCTV cameras. (I don't know about private ones, in shops and so on -- they didn't catch my eye.) The government buildings were built like fortresses, and I had my ID scanned and bag x-rayed when visiting museums. When I tried to leave, a government employee handled my genitals.
I don't want an argument about which country is better -- they both need improvements in this respect. But I'd like to know how you felt watched (or similar) when you visited the UK.
Re:Not a great challenge (Score:4, Interesting)
Your experience has you quite biased towards these sorts of things. You only watched this video, I can tell, and didn't pay attention.
In the disassembly for stage 3, the messages "loading stage x license key", when they clearly said you were on "stage 2 of 3", were good hints. The unused firmware bits were fairly obvious because they had the right size and served no other purpose, and the unused bytes from stage 1 were obvious after you get your mind on the "unused bits from each stage" track.
And the VM part wasn't trivial. This guy did it in python, but it was intended to be done in javascript. The implementation doesn't really matter, but understanding the bit fiddling needed to implement it is a valuable skill. If you have the skills to disassemble, but not write anything more complicated than hello world, you're probably not useful to them. Not a difficult challenge, but one where you can easily make a mistake and grind your gears for hours. Remember the intent, to find viable candidates for cybersecurity who are interested in doing this sort of thing. Sometimes cyber security is boring but you do what's necessary to solve the problem.
And they never advertised it as a hack-it contest or programming challenge, just a puzzle. So it didn't have to even be fun or entertaining to do - just something to solve. Note as well, they didn't ask for contact information or offer a resume upload - just "Please consider applying with us". So it doesn't even get you an interview.
If you spent the time and are curious enough, you're probably someone they want. If not, you're probably not.
Re:Not a great challenge (Score:2, Interesting)
I solved stage 2 entirely on my own and reverse engineered enough of stage 3 to realize exactly what it was doing. I had glossed over stage 1 (after I realized it was x86 I just googled it and saw that others had solved it already) so I didn't immediately know about the unused instructions, but I did correctly guess that the "firmware" stuff from stage 2 was used for the second two 32-bit words in the URL.
Basically, I had no interest in playing the guessing game portions of the challenge, especially since I found out about it late and plenty of people had solved all of it already. I have no incentive to beat it entirely on my own: this isn't a contest and I already have a full-time job so I am not interested in applying; I was just curious to see what kind of problems they were and whether any of them were interesting to me.
Of course it was obvious, but that doesn't make it interesting. This is the kind of problem that is testing no useful skill other than whether the player has been on the lookout for unused stuff that may or may not be useful later. That's not really how real life problems work. If something is used, there will be pointers to it in real applications. Reverse engineering isn't about pulling numbers from strange places and "trying to see if they work".
Mind you, some people enjoy this kind of puzzle. I'm just saying it's the wrong kind of puzzle.
Why, because the file happened to end in .js? The only information in it was a memory array, a few constants, and comments. If, as a reverse engineer, you pick the language that you're "supposed to use" instead of the language that you prefer or which is most practical or useful in a given situation, you're doing it wrong. I played in a CTF once where we were given a Linux box running a few services, including one written in shell with a bunch of shell injection and path traversal vulnerabilities. I just rewrote it in Python: it was faster than trying to wrap my head around the existing shell code and its bugs, and I could easily guarantee that all of those holes were gone (and the service was simple enough that I knew there wouldn't be any unexpected exploitable problems). Fixing the original would've taken longer.
So they had people implement a VM in order to prove that they know how to shift and mask bits? The are a myriad other ways of doing that that don't involve a VM. If you're going to have a challenge based on a VM, it should be because you want the player to be able to understand a program written in a novel architecture and write their own disassembler, or something similar. The whole point of a VM in a security system is to obfuscate the code running on it - if you don't have to disassemble or understand that code to achieve your goal, then the VM has failed its purpose.
If the intent is to test that the player can program, then it's still a much better challenge to provide the VM code and a description of the architecture, but still require th