Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Encryption United Kingdom

GCHQ Challenge Solution Explained 107

Posted by timothy from the oh-well-now-that's-just-obvious dept.
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."
This discussion has been archived. No new comments can be posted.

GCHQ Challenge Solution Explained More

GCHQ Challenge Solution Explained

Comments Filter:

  • Opaque (Score:4, Interesting)

    by DarkIye ( 875062 ) on Sunday December 04, 2011 @12:57PM (#38258234) Journal

    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?

    • Re:Opaque (Score:5, Funny)

      by Robadob ( 1800074 ) on Sunday December 04, 2011 @01:02PM (#38258276)

      Because terrorists are yet to discover x64

      • X64? Weren't the Taliban still using C64s? Can GCHQ crack this Commodore 64 crypto [pagetable.com]: ; WAIT Command B82D 20 EB B7 JSR $B7EB B830 86 49 STX $49 B832 A2 00 LDX #$00 B834 20 79 00 JSR $0079 B837 F0 03 BEQ $B83C B839 20 F1 B7 JSR $B7F1 B83C 86 4A STX $4A B83E A0 00 LDY #$00 B840 B1 14 LDA ($14),Y B842 45 4A EOR $4A B844 25 49 AND $49 B846 F0 F8 BEQ $B840 B848 60 RTS
    • You can probably find some examples by doing a search for the start of the code. The problem right now is that all the hits are on the challenge itself.

    • Re:Opaque (Score:5, Insightful)

      by bWareiWare.co.uk ( 660144 ) on Sunday December 04, 2011 @01:11PM (#38258372) Homepage

      The ability to recognise codes is precisely what they were testing.
      If they had used a week cryptography code everyone would have cracked it, if they had used a strong code no one could (at least no one who didn't already work for their competition).
      Utilizing an unexpected but extremely common code seems to be a nice solution.

      • Re:Opaque (Score:4, Interesting)

        by Lumpy ( 12016 ) on Sunday December 04, 2011 @02:03PM (#38258770) Homepage

        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:5, Informative)

      by pushing-robot ( 1037830 ) on Sunday December 04, 2011 @01:11PM (#38258374)

      Well, "DEADBEEF" is a bit of a giveaway [wikipedia.org].

    • Re:Opaque (Score:5, Informative)

      by marcansoft ( 727665 ) <hector@marcansoft.UMLAUTcom minus punct> on Sunday December 04, 2011 @01:28PM (#38258520) Homepage

      Recognizing unknown architecture binaries is an important skill to have when reverse engineering, especially for embedded systems. Very often you'll get a firmware file and you have to figure out what it is. Each architecture has its peculiarities, so it doesn't take long to get a feeling for what their opcodes look like. For example, 32-bit ARM code sticks out like a sore thumb (no pun intended :) due to the condition code field, which means that every 32-bit word almost always starts with 0xEx (and whether that's the first or last byte in the word tells you the endianness). Variable length architectures like x86 look very different from RISC ISAs with a fixed instruction length like PowerPC.

    • It wasn't -- according to the Register, the mark of a good cracker was the ability to use Google. [theregister.co.uk]

    • Re: (Score:2)

      by ceoyoyo ( 59147 )

      The mark of a good code cracker is to be able to look at a bunch of numbers and/or letters and recognize patterns. This one was x86 byte code, which is, IMHO, a nice break from english language letter frequencies.

    • Re: (Score:2)

      by AHuxley ( 892839 )
      Its what they taught the freedom fighters in the 1980's?

    • Re: (Score:1)

      by jdege ( 88942 )

      I wondered that, myself. I doubt I would have recognized it.

      But just on a lark, I put the bytes into a file, and hadded it to the Unix "file" command.

      It reports that it is a "DOS executable (COM)".

  • Not a great challenge (Score:5, Interesting)

    by marcansoft ( 727665 ) <hector@marcansoft.UMLAUTcom minus punct> on Sunday December 04, 2011 @01:07PM (#38258328) Homepage

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

    • Re: (Score:1)

      by ceoyoyo ( 59147 )

      "combined with some steganography"

      Calling data contained in the comment field of a png steganography seems rather overly generous.

      • "combined with some steganography"

        Calling data contained in the comment field of a png steganography seems rather overly generous.

        He didn't say that it was GOOD stenography...

      • If you want a steganography challenge (with a twist), try this [marcansoft.com], from this year's Hack-It ;)

    • It took me about 3 hours to implement stage 2 in JavaScript (and in C++ when the JavaScript implementation seemed to run in an infinite loop). The specification was not really trivial with respect to the jump instruction and did not explain the use of the cs register, which is not obvious to people who have not worked with 8 mirco processors using segmented memory, such as the Z-80. I always played with the 6502, which doesn't use segmented memory and has a 16-bit program counter.

      • It took me about 30 minutes using Python (why would you use JavaScript? The mind boggles.), but yes, I agree, the specification wasn't terribly clear especially if you've never worked with segmented memory. The jump instructions also are confusingly described as jumping to r2:r1 in the mod=1 version (it should be imm:r1). Personally, I quite dislike this memory model (and x86 in general), but I've had the "pleasure" of working with an embedded system integrating a 80186 core so I had a fairly good idea of w

      • The Z80 is not a segmented memory model either; you might be thinking of some of the embedded versions such as the HD64180. It was the x86 architecture that was really afflicted with these segment registers.

    • Re:Not a great challenge (Score:4, Interesting)

      by b4dc0d3r ( 1268512 ) on Sunday December 04, 2011 @05:42PM (#38260530)

      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: (Score:2, Interesting)

        by marcansoft ( 727665 )

        Your experience has you quite biased towards these sorts of things. You only watched this video, I can tell, and didn't pay attention.

        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 seco

    • Re: (Score:3, Insightful)

      by dnewt ( 2457806 )
      Unless you're intimately familiar with the tasks undertaken by GCHQ analysts such as the one this test is recruiting for, I think it's hard to say for sure whether the test was, in fact, good or bad. The thinking behind why some elements of the test were designed the way they were may not be immediately obvious. Having said that, I do wonder whether GCHQ would put their best minds to task working on devising a top rate recruitment puzzle. With the current international climate, combined the the current econ

  • Why crack it when you can bypass it? (Score:4, Funny)

    by TripleP ( 525879 ) on Sunday December 04, 2011 @01:10PM (#38258352) Homepage
    So if you can't crack it, but you can bypass the challenge, do you still win?

    http://www.canyoucrackit.co.uk/soyoudidit.asp [canyoucrackit.co.uk]

    • Re: (Score:2)

      by Xugumad ( 39311 )

      If by win, you mean stand a fair chance of getting to the interview stage, probably. I suspect lacking a good answer to "How did you solve the problem?" would be a bit of an issue, until the whole thing was blown wide open anyway...

      • If by win, you mean stand a fair chance of getting to the interview stage, probably. I suspect lacking a good answer to "How did you solve the problem?" would be a bit of an issue, until the whole thing was blown wide open anyway...

        "Cheating is often more efficient." 7 of 9

        I'm no expert, but isn't showing initiative a desirable quality in candidates?

        • Yeah, but simply trying out addresses to see if you randomly reach the "Well done!" page is not really useful in this context.

        • Re: (Score:2)

          by Xugumad ( 39311 )

          Debatable; keep in mind they're recruiting for cryptanalysts and information/network security people, not spies in the traditional sense. They want strong problem solving abilities; so short-cutting to the solution I would imagine won't discount someone, but they would also need to show the core skills expected of the job...

      • Re: (Score:1)

        by Anonymous Coward

        "I crowdsourced it."

    • Re: (Score:1)

      by Rashdot ( 845549 )

      No, because your IP address wasn't registered jumping through all the hoops.

  • I've been having a go... (Score:4, Interesting)

    by shic ( 309152 ) on Sunday December 04, 2011 @01:12PM (#38258378)

    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.

    • Stage 3 isn't worth the effort. It's very little hacking/reverse engineering and mostly silly guesswork with no sensible sequence of steps to get there. Spoiler ahead:

      The primary challenge is to guess what bits of stage 1 and stage 2 to stick into a URL (or a file which the exe then formats into a URL). You have to go back to stages 1 and 2 and fish out the most likely candidates for "3 32-bit numbers that do nothing and stick out like a sore thumb".

    • It's absolutely not worth it to get through to the end.

      Salary [gchq-careers.co.uk] from their job posting:

      £25,446 (GC10) £31,152 (GC9)

      Why on earth would a top notch graduate apply for this position when s/he could make 4x that in the private sector? As the professor in the third video said: that's rather a disappointing end.

      • errrr.... what?

        I'd like to know where I could earn £120,000 as a starting salary when I graduate.

        • Top grade banks. Look to get hired as a quant, not a techie. Starting salary in the US was $160K flat, plus bonus when my college friends were doing it a few years back. Things have cooled off a bit since then, but it's still possible -- especially with a finished masters or half-finished doctorate.

          • What are the hours and stress like in that job though?

            • compared to working for the Intelligence service, knowing that your every movement, call and net is monitored?

            • In at 6:30, out by 7, with monitoring of risk jobs overnight if need be.

              • So pretty horrible then, just about enough time to work, eat and sleep.

                There's always a catch isn't there?

                • I didn't mind it too much...I managed to find a wife, start a family, have a hobby shop and write a book while I was in the system.

                  The key is to not become addicted to the fat paycheck. It's hard for some people to do, which is why they stay in and subject themselves to the stress for years on end. I saw far too many people with empty million dollar Manhattan apartments to fall into that trap, so when the wife got a teaching job in another part of the country in my sixth year, I packed up and left. We bough

            • Re: (Score:3)

              by xaxa ( 988988 )

              What are the hours and stress like in that job though?

              Rhetorical, or not?

              A couple of my friends (well, more friends-of-friends) from my year went on to do that. That was when I stopped seeing them. "Let's meet for drinks after work in central London!" They rarely turned up before 10pm, and even then sometimes went back to work after an hour or two. Got to get their bonus, you see.

              One of my closer friends -- I lived with this guy for two years! -- is working for a hedge fund. £200k, I think, probably with a bonus. He was never particularly social, bu

          • Re: (Score:3, Informative)

            by MattBecker82 ( 1686358 )

            Err ... no. There simply aren't quant jobs with grad starting salaries of that level, certainly not in London, and I would highly doubt you'd find that level in NY either. Salaries actually went up (and bonuses down in relative terms) after '08-09, but there's still no way you'll get a six-figure (GBP) base for a grad starting position.

            Also, timing is pretty bad if you want to land a quant role right now. Front-office hiring patterns tend to be very cyclical and right now they're in a downswing with most ba

        • Re: (Score:3)

          by xaxa ( 988988 )

          You might get £35k (basic) in IT in a bank in London, with anything up to 100% bonus. You get to help screw up the economy, too. Don't worry -- after 2-3 years you'll have lost your morals.

          Or similar money (and bonus) working in IT for a software company writing code for banks.

          I know someone who's making nearer (over?) £120k as a contractor for banks writing Android apps, but he spent a couple of years writing apps himself (earning a decent amount selling them) before he had the reputation to

  • I didn't realize that reversing IA-32 excutables was the modern meaning of cracking a code. I figured it would be difficult and possibly even rely on dictonary attack of a cryptographic hash, but IA-32 machine code? This sounds like they are more interested in recruiting people to analyze stuff like Stuxnet than to attract people with cryptography, information theory, and signals backgrounds. I don't claim to be crypto expert (I've took an abstract algebra class that is a requirement for all cryptography cl

    • Re: (Score:2)

      by morphage ( 62416 )

      I haven't looked at the video yet, because I still want to see how far I can get with just the spoilers in the comments.

      Grr...now I'm mad I didn't recognize the byte swapped DEADBEEF.

      • Maybe I've too recently spent too much time looking at disassemblies, but I recognized it as x86 almost immediately.

    • Re:I thought this was a crypto/cypher challange (Score:5, Insightful)

      by dachshund ( 300733 ) on Sunday December 04, 2011 @01:36PM (#38258566)

      didn't realize that reversing IA-32 excutables was the modern meaning of cracking a code. I figured it would be difficult and possibly even rely on dictonary attack of a cryptographic hash, but IA-32 machine code?

      For better or for worse, modern intelligence agencies are much more dependent on people who can RE software and develop exploits, than they are on pure cryptographers.

      This is a consequence of the rolling disaster that is software security, combined with the fact that crypto folks have (mostly) gotten their act together.

    • Re:I thought this was a crypto/cypher challange (Score:4, Interesting)

      by The Askylist ( 2488908 ) on Sunday December 04, 2011 @01:40PM (#38258584)
      GCHQ has just announced that they are to lead the UK's cybersecurity push. I guess they need some reverse engineering skills in a hurry.

    • This sounds like they are more interested in recruiting people to analyze stuff like Stuxnet

      Yes, that's probably exactly what they're after.

      • This sounds like they are more interested in recruiting people to analyze stuff like Stuxnet

        Yes, that's probably exactly what they're after.

        If they're really looking for people who can do that, they should be looking at people who crack DRM. Oh, are most of the people like that keeping their heads down and unlikely to be considering government jobs? Gee golly, I can't imagine why...

  • perhaps they want to examine packet logs? (Score:5, Insightful)

    by wierd_w ( 1375923 ) on Sunday December 04, 2011 @01:41PM (#38258592)

    This is an intelligence agency, and network intrusion programs pumping executable code in the attempt at smashing a stack and jumping execution are pretty common.

    Perhaps they want people who can quickly spot x86 assembly payloads from raw packet traces as part of a counter aggression op?

    If we assume that their network stack isn't riddled with exploitable stack variables or pointers, and that they successfully prevent the code from running, but log the unrequested network access and dump the binary packets to file for analysis, then having people that can "at a glance" determine what kind of data is in those dumps would be valuable.

    Being able to determine what it actually is supposed to do even more so.

    With the recent hysteria over scada system cyber attacks (I hate that phrase btw..),setting up a fake scada system as a honeypot and seeing what the cat drags in could also make use of this skillset.

    So, the obvious questions:

    Does the UK fear it has poorly secured scada systems, or does it fear network worm intrusion on some network segement, and if so, what segments or systems are those?

    • Re: (Score:1)

      by carvell ( 764574 )
      Why do people think this is anything other than a publicity stunt to generate internet-chatter and pimp their name about a bit?

      The details of the challenge are almost certainly irrelevant - anyone can apply for GCHQ jobs directly with them, without having to complete a challenge.

      The more their name is banded around forums and sites like slashdot the better, as they'll get more people applying for their jobs, which can only be good for them.

  • Stage 1 and 2 were really easy frankly. Especially stage 2 since aside from the small error (intentional or not) in the implementation document it was just some simple coding.

    Stage 3 was where I stopped, not because I was daunted or otherwise unable but because I didn't have the tools available to screw around with the exe. It was also at that point that I learned they were too stupid to even put up a robots.txt file and thus were not an organization I had any interest in working for.

  • My solution with full writeup (Score:5, Informative)

    by ncw ( 59013 ) on Sunday December 04, 2011 @03:12PM (#38259352) Homepage

    I was going to hold this back until the competition was finished, but it seems the cat is out of the bag!

    Here is my solution and a writeup of exactly how I got there.

    http://www.craig-wood.com/nick/articles/how-i-solved-the-gchq-challenge/ [craig-wood.com]

  • I spend about three hours writing (mostly debugging) a JavaScript implementation of the VM. (I did make a side step to C++ because at one point the JavaScript implementation seemed to run in an infinite loop.) I also discovered that the specification was not very clear and required some interpretation. So stating that stage 2 was the simplest step, and using some code that someone else developed, is not really honest. The biggest problem was with figuring out how the jmp instruction worked and the use of th

  • Thank you, participants... (Score:1)

    by Anonymous Coward

    ...for helping GCHQ crack the "Modern Warfare 3" video game copy protection! Well done, everyone!

    If you are interested in helping us get free premium television channels, cellular phone minutes, tickets to concerts, and more money from taxpayers, then join our team!

  • Use google and search for site:canyoucrackit.co.uk and select show ommited results. http://www.google.com/search?q=site:www.canyoucrackit.co.uk&hl=en&safe=off&filter=0 [google.com]

Slashdot Top Deals

Every nonzero finite dimensional inner product space has an orthonormal basis. It makes sense, when you don't think about it.

Close