Escape from Minecraft was one of the most surprising tasks at the PHDays CTF 4 Qualifications. In this task you were greeted by a tarball of a Minecraft world which, upon loading, presented you with the following scenario:
 |
| The door. |
 |
| The keypad. |
 |
| The logic. Oh gods. |
At the heart of the puzzle was a 9-digit keypad, backed by a breathtaking amount of “redstone” logic. For those unfamiliar with the game mechanics, redstone is an ore, available in the game, used to create digital logic based on the core principle of NOR gates. Redstone ore can either be deposited on blocks to create “traces” or can be combined into torches, also placeable on blocks. Torches, at the most basic level, drive all neighbouring traces to a high level - if not driven by anything, traces remain at a low state. Additionally, when a torch is placed on a block, it will be te turned off (ie. stop powering adjacent traces) if any powered trace touches the block it is placed on. Can you see where this is going..? ;)
 |
| A torch powering some traces. |
 |
| Two NOR gates, the upper with a single active input, the other with two inputs (one active). |
 |
| A more compact NOR gate with an active output and two inactive inputs. |
Based on these very simple rules (ie. a whole bunch of NOR gates) one can recreate nearly all forms of digital logic - logic gates, flip-flops, counters, even simple ALUs (arithmetic processing units) and processors!
 |
| An AND gate with two active inputs and, therefore, an active output. |
 |
| RS Latch with inactive output. |
 |
| RS Latch with active output. |
Furthermore, a wide variety of game objects can interact with redstrone. There are levers which turn on traces but are flippable in game, buttons that power traces for a short amount of time when pushed, doors which open when a powered trace touches them, et caetera. Recent Minecraft updates also supplemented the arsenal of items with some more integrated redstone circuit elements, the most important one being the repeater. This device allows the signal to propagate past a limit of 7 blocks and also doubles as a diode, letting signals pass only in one direction.
 |
| Door and repeater activated by lever. |
Let's get back to our puzzle. The player was free to navigate amongst the maze of traces, blocks and torches that made up the keypad logic. There were two main parts of the circuit, separated by a wall. The first one, which received nine inputs from the keypad and outputted four unknown signals into further parts of the lock, contained some relatively irregular-looking logic, thwarting efforts to analyze it statically . However, after some experiments with providing different input values manually (by placing torches in-line) it was clearly visible that the resulting signals contained a 4-bit encoding of the keypad value, with the lowest bit... lowest.
 |
| Decoding logic when 5 is pressed on the keypad. |
 |
| Output of decoding logic when 5 is pressed on the keypad. |
The next block of logic looks a lot more daunting, however it also seems very regular. After some basic examination, we can see that the 4-bit input forks off into two paths: one leads via a series of ORs and a pulse generator to a long, periodically repeated signal; the other path goes straight into a jungle of gates, which seem to treat each bit in parallel.
While observing carefully the first fork of the signal (the long, single line), we can observe that it goes straight into the end of the circuit, then goes back along to the 4-bit input - activating some sub-blocks of logic one-by-one, starting the farthest away from our input. Additionally, right after that signal is triggered, even before it hits the blocks farthest away, it triggers a bunch of flip-flops labelled by the creator of the level as “input register”, which latch the input from our keypad into them, and keep that data until the next digit entry. Based on all of this information, we will from now on refer to this signal as “clock”, as that's what it is - on each rising edge, it latches our keypad input into the input register, then proceeds into activating other part of the circuits.
 |
| Our “1010” (five) latched into the input register. Here, the visible traces are the inverse of the latched data. |
 |
| A register in more detail. Clock input hidden behind. |
 |
| Long clock signal, crude datapath of input bits. |
Before continuing on with the rest of this part of the logic, let's look at the output stage for a second. Obviously, we can see here a hierarchy of and gates, that take four inputs and return one output, which is then used to open the door (and lets us escape). A good guess here is that we need to meet four conditions in order to open the door - and these four conditions come from four different blocks of the logic we discussed previously.
 |
| Output AND gates. |
Let's take a closer look at these four conditions to be met. All modules looks very similar - they take data from a register from the other side of the logic, and output, via an AND gate, a result into the output stage.
 |
| Our condition-checking blackbox. Four inputs from the previous stage, and an output. |
Let's take, again, a closer look at the logic that feeds input data into these four modules. After noticing that it is made up of four RS latch registers separated by AND gates which are triggered by the clock, we can now obviously see this as a four stage, 4-bit shift register, where each stage has its output connected to a condition checking stage.
 |
| Our 4-stage, 4-bit shift register. |
What this means, is that we have to enter a four-digit code, so that it fills up the shift register and so that each digit meets a certain condition. Hopefully, if we do so, we will be able to open the door. What is left to do now is just to understand how to satisfy these per-digit conditions.
If we keep walking or flying around a condition-checking stage, we can see it is made out of four layers, each presumably checking one bit of the the digit. All of these layer-based conditions get ANDed together into the main output. Each layer has two torches visible - a left one, which seems to be just the output of the shift register for that digit, and the right one which seems to be hardwired on or off. What if we feed such a digit so that the pairs of torches match?
 |
| Feeding “9” into the first stage of the shift register. The binary representation matches the hardwired torches, and we get a positive output. |
Success! We were able to decode a digit of the target code. Now we just need to read out the rest of the hardwired torches from the output stages:
And enter our newly found code (3549) into the PIN pad!
 |
| Freedom! |
No comments:
Post a Comment