Ghost In The Shellcode - AdventurePwn Final Riddle 2

One of staples of InfoSec conventions are Capture the Flag competitions. Fortunately, you don’t actually have to go to the convention to participate. Over the past few months I’ve been doing as many of these as I can with the RobotMafia team. Well, in reality, it’s only been a handful of people from the team which means we haven’t posted any impressive scores, but the fun is in the playing.

One of the other staples of the competitions is to write up your solutions. This one isn’t anything special, but I can think of a few particular people who might like the story. They also might like to compete with us in the future, because although these events are centered around security, a lot of them are more programming puzzles than anything else. And I know my friends love puzzles.

So our story begins with one of the three teaser round challenges of “Ghost in the Shellcode” which is the CTF competition affiliated with Schmoocon. The first challenge this year was called “AdventurePwn” and was a choose your own adventure style game with problems to solve at different steps. To give you an idea how it went, here are the first couple of screens:

  You hold in your hands a map to a vast treasure under the mountain.  Your
  desire to be rich far outweighs your desire to cooperate with others, so
  you are obviously going on this quest alone, with only your wits and your
  awesome hacker magic to aid you.

  You start your quest on a road just outside of town.

  You feel a strange forboding feeling eminating from the map, like it has
  an alien magic all of its own.

  What do you do?
  1) Follow the road toward the mountain.
  2) Turn around and ask the mage in town what is going on.
  Choice: 
  Sending 1

  You begin your journey down the road to the mountain.  About a mile into
  your journey, you see a camp of bandits.  They look to be the ruthless
  type, which would feed their own grandmother to the Ravenous Bugbladder
  Beast of Traal rather than see anyone go by with their money still with
  them.  You do not want to know what would become of the world if they
  managed to get the treasure.

  What do you do?
  1) Try to sneak around.
  2) Keep walking down the road.
  3) \ for (i = 0; i < 10; i++) cast(fireball);
  Choice: 
  Sending 1

If you choose the wrong path, for instance asking the mage what is going on, you die. Although on the second screen, if you fireball the bandits, you can continue, but it makes a future puzzle impossible. I’m tempted to just write a spider to try all the paths, but then things get more interesting.

  As you are walking down the road, you hear a faint wooshing sound, then
  you are face to face with a strange looking ninja.  He says:

  "I am the Binary Ninja!  I am here to make sure that people like
  you that say that they know hacker magic aren't just a bunch of liars.
  We all know that some are.  I am going to ask you a riddle to test your
  hacker knowledge."

  "What C function does this x86 incantation represent: 8b4424049931d029d0c3."

  "Just give me the name of the function, no symbols please."

  What is your response?

Binary analysis isn’t my strong point, but I’m learning. I start off by taking the first few characters and just googling for them. And I’m rewarded by disovering that the first command is a mov. 8b442404 = mov eax,dword ptr (esp+4) to be exact. The next one 99 is CDQ which converts a double to a quad. Not particularly helpful here. So next I use a hex editor to create a file with those contents, and msfencode to wrap it in an elf header so that IDA can analyze it (if you didn’t follow that, it’s not important) and maybe be so kind as to tell me what function that decompiles to. IDA only gives me the following assembly:

  mov     eax, [esp+arg_0]
  cdq
  xor     eax, edx
  sub     eax, edx

That still does nothing for me. I can see what it’s doing but not the point. Fortunately, another member of the team (Tilver) googles it and comes up with the “ABS” function. The elf replies with “Seems you are not a liar when you say you know hacker magic. Thank you, and enjoy your quest.” Yes, Google is a mainstay of hacker magic.

Next we face a troll. “I am thinking of number between 1 and 100, you have 7 guesses before I smash you.” The troll is kind enough to tell us if we are too high or too low when we guess. If we had blasted the bandits before, the high number would have been 500, but since we cleverly snuck around, a maximum value of 100 means that our 7 guesses are sufficient to do a binary search. By now we have scripted the interactions so it’s no challenge to guess 50, then 75, then 62, etc.

With that passed, we get a visit from a sinister mage who says: “You claim to have awesome hacker magic. If you do not, I will kill you right where you sit. I ask this of you, what x86 incantation will give you the contents of the flags without touching the stack?”

Did I mention I’m not so good at assembly yet? But teamwork comes through again and Tilver knows the incantation of “lahf” so we can move on to the final guardian of our treasure.

  "I see you have located the Treasure of the Ancients.  I congratulate you on
  getting this far.  However, I am the keeper of the treasure, and I will not
  let it go easily.  You may try your magic on me, but I warn you that it might
  not be strong enough.  I am going to present you with some riddles, and if
  you solve them I might be kind enough to give you some information that would
  be of value to a truly great practitioner of hacker magic.  Only one with
  great power may leave my treasure room with its riches."

  "I give you a choice.  Which riddle do you want to play?"
  1) A simple question.
  2) A game of colors.
  3) A game of numbers.
  You may also:
  4) Prepare your magic incantation.
  5) Use your magic.
  Choice: 

The first option spits a binary file out at you one character at a time, erasing the character as it goes. So one team member focuses on capturing that binary and doing whatever analysis they can. The third option presents a triangular shaped sudoku. If you solve it (wamsachel did it by hand) you are told:

  I have gotten rid of that pesky NX demon for you, just so you know.  Also,
  if you were there preparing an incantation I can put some zeros in it for you."
  "Give me a number and I will put a zero there.  Give me zero and I will stop."

So winning these games makes it easier to exploit the binary. Mantis and Wamsachel set about trying to automate beating the tridoku and I tackle game number 2, which is:

  "Here were are going to play a game of colors.  Get the colors in the right
  order and you will win a prize.  I will not tell you what game this is, but
  most hackers have seen it before."

  516113426 345323142 223132652 314542466 142453354 161665565
  What is your move? (1-6)

Each of the digits are colored and all the 1s are one color, 2s a different color, etc. So our first task is figuring out what game this is. It seemed most likely to find something interesting by playing the same move several times and it might be useful to be at an edge, so I played the following moves, and got the results below:

516113426 345323142 223132652 314542466 142453354 161665565
(played 6)
516113426 426323142 523432352 314545463 142453216 561666551
(played 6)
516113426 453323142 623232452 316541462 142453543 565566161
(played 6)
516113426 612323142 323532452 313544465 142453624 155666165
(played 1)
415211636 612323223 321534452 113444265 453453624 155666165
(played 1)
624311615 612323241 324535453 213244365 241453624 155666165
(played 1)
636112514 612323354 322534451 213444165 322453624 155666165

As you play, some of the digits change but most remain the same. So I went through and marked whether the digits went up or down to try and highlight a pattern. Every time I played a 6 exactly 15 characters changed, mostly in the same places but there were a couple that changed at different times. Playing a 1 resulted in 17 changes, and again, they were mostly in the same places, but once or twice it would stay the same. I also noticed that the digits seemed to be swapped around, preserving the 9 of each digit that we started with. Also, when I played a 6, nothing changed in block 1. When I played a 1 nothing changed in block 6. When I played a 2, nothing changed in block 5. Interesting, but nothing clicked yet.

My initial suspicion was that this was some sort of block encryption scheme which is something a hacker would have seen, but with the constant distribution of 1-6 that didn’t seem likely. So I resorted to Google again. The clue told us that the colors were significant and there were 54 digits, so I tried different combinations of those searches. Finally I added that there were six groups of nine numbers and that yielded a few hits for a classic puzzle game. A Rubiks cube.

Staring at it a little more confirmed it. Each of the six groups of 9 had one digit in the center that never changed. Playing a 6 moved all but the center digit on the sixth side, and nothing in side 1 which is on the opposite side of the block. The places where a digit hadn’t always changed were places where the same number/color happened to get moved in to the same spot.

I know the sequence of moves that will solve a Rubiks cube, but with the sides presented in this format, I knew that a manual solution was just about impossible. So I set out trying to find a solver that I could adapt. Imagine a time lapse here where I looked at half a dozen or more different solvers but they all wanted the starting position entered by hand using a GUI. Finally I found this one http://www.wrongway.org/work/solver.tar.gz which used input in almost exactly the format that we were being given. It wouldn’t surpise me if this was the code they used to generate the puzzle. Problem solved right? Not quite.

When I fed the starting position to the solver, it rejected it saying the configuration was invalid. Apparently the sides were being presented in a different order than the solver expected. No big deal, I already knew which sides were opposites so that should narrow down the possibilities quite a bit right? Yes, but not enough. I kept manipulating the string to try different combinations but could not find the right one.

And as I was slowly typing out all the different possible combinations in to a script to test them individualy, it dawned on me that since the test was really fast, the number of combinations was relatively trivial for a computer. This was a time to fuzz it (or in other words just send random combinations of sides at the solver and see which one succeeds). Sure enough, once the script was set up, after about 15 seconds the magic order of sides was revealed to be: 1 2 0 3 5 4 (zero based), or in solver terms top=2, left=3, front=1, right=4, back=6, bottom=5. With that solved I now had this much:

  566311511 563126334 146332226 241244553 453653452 254261641 
  200 cube solved ok.
  101 version 1.30.505 by Eric Dietz (root@wrongway.org)
  202 104 moves 7 groups 12 21 38 0 9 8 16
  220 starting diagram:
      5 6 3     2      0
      1 2 6   2 0 1 3
      3 3 4     0
   1 4 6  5 6 6  2 4 1  2 5 4
   3 3 2  3 1 1  2 4 4  2 6 1
   2 2 6  5 1 1  5 5 3  6 4 1
      4 5 3
      6 5 3
      4 5 2
  221 diagram end.
  210 sending solution:
  LD, LD, RU, RU, BA, UL, UL, DL, DL, RU, DR, DR, BC, LD, BC, LU, RD, BC, RU, UL, BC,
  UR, BA, RU, BC, RD, BA, UR, BA, UL, RD, BA, RU, BA, LD, BC, LU, BC, DL, BA, DR, RD,
  BA, RU, BA, DR, BC, DL, BC, LU, BA, LD, BA, UL, BC, UR, UR, BA, UL, BA, RU, BC, RD,
  BA, UR, BA, UL, BA, RU, BC, RD, RD, BC, BC, RU, BA, RD, BA, RU, BA, UR, BA, DR, BC,
  UL, BA, DL, BC, UL, BA, UR, BA, UL, BC, BC, UR, DL, BC, DR, BC, DL, BA, BA, DR, 
  211 completed solution.
  201 terminating successfully.

So how do those moves translate to commands to our game? Well, the first character tells us which side to rotate and the second tells us which direction. We know the mapping of sides and even though we can only rotate a side clockwise, three clockwise turns makes a counterclockwise turn so we’re covered there.

So I wrapped it all up in our auto play script and let it run. After a tense couple of minutes (it takes a while to send a hundred moves)

  I spy with my little eye that any incantation you might try to use against me
  could be addressed as 0xb81cce48, and the little game we just played could
  be addressed as 0xb77f299f."

Wahoo! Success! Of course with various other obligations during the day this teaser contest had ended about 45 minutes before I got the solution. And this is only one part of the overall challenge. That’s no good from a scoring perspective, but from the personal satisfaction side, I still did my little coders dance of joy.

Not a bad way to spend a Saturday afternoon (and part of the evening). To be honest the whole reason I like Information Security is for the puzzles and Capture the Flag competitions are pure puzzle. Sound like fun? Hit me up and I’ll get you involved in one of the upcoming events. Security experience helps but, surprisingly is not required. There are always some challenges which are simply programming puzzles and having some more people around who can work those would be a big help.