Google CTF | Reverse a Cellular Automata

This is a writeup for one of the challenges from the Google CTF which I participated in a few weeks ago. My friend Chris and I were finally able to get this flag after a lot of hitting our heads together. The Reverse a Cellular Automata challenge (may not be up in the future) was a lot of fun.

This crypto category flag gave us the base64 encoded flag and the encryption key after one iteration of Wolfram’s rule 126 was ran on it. Our job was to move backward one step and get the actual key.

Wolfram Rule 126

This rule is a bit similar to the Game of Life. In this case, take an n bit number, for example 101110, and run through the following rules:

  • For every bit, if the value is the SAME as each of its two neighbors, its next value is 0
  • Otherwise, its value is 1
  • The least/most significant bits are neighbors with each other

So in the example above, if we’re dealing with 101110 and run rule126 on it, our next value would be: 111011.

It’s trivial to go forward one step, it’s a bit more difficult to go backward which is what this problem requires.

Reverse Rule 126

We didn’t prove this, but pragmatically speaking, given a number N there is at least one ancestor n' where rule126(n') == N. Let’s call the set of all values of n' where rule126(n') == N‘. It seems that, in many cases |N'| is rather high. That is, the number of potential values of n' ∈ N' is large.

The most obvious way to solve this problem would be to brute force it. But since the encryption key is 64 bits this would take about 545 years so we decided to go a different route. We needed to limit our search space.

In order to do so, we thought about the rule126 rules in reverse. For instance, what does it mean if a given bit in N is a 0? Well, it means that in the previous ancestor n' that bit was the same as each of its neighbors. In other words, if we saw a 0 in bit b_1 then in n' bits {b_0,b_1,b_2} were either all 0 or all 1. The opposite is true if we encounter a 1 in b_1. That is, bits {b_0,b_1,b_2} were NOT either all 0 or all 1.

As we talked this through, it became apparent that we could use a SAT solver to limit our search space.

SAT Solvers

SAT Solvers, or satisfiability solvers, take a number of constraints and determine if the constraints are satisfiable. That is, if there is some solution which will satisfy all of the constraints.

In order to use one, we needed to write our rules above as a series of constraints. Let’s say we have three bits: A, B, and C where B is some bit b_i and A and C are B‘s left and right neighbors respectively. If the value of B is 0 then we know that in n':

In other words, either all of those bits are on or they’re all off.

Similarly if the value of B is 1 then:

Unfortunately, SAT solvers do not take logical propositions like the ones above. They need to take constraints in something called Conjunctive Normal Form (CNF). Luckily, any valid logical proposition can be written in CNF and there are lots of tools to automatically rewrite propositions in CNF.

to_cnf

We were able to use a python library called sympy which has the ability to rewrite propositional logic into CNF. This was ideal for our use case, and we were able to quickly generate our logic above into equivalent logic in CNF. This was then fed into our sat solver and we were on our way. I won’t go into all of the rewrites, but see our final solution below to get a feel for how this worked.

Getting Ancestors

Running our solver gave us gave us 10,753 different possible values for n' which was honestly much larger than I expected. Not to worry though, we saved each valid n' as a binary key and then ran our decryption script with each key using the following code:

In other words, if the decryption had an error we directed it to /dev/null, otherwise we checked to see if CTF was in the output and we had our flag. The decryption code above was given to us in the question.

And we got it! Though it’s not really incredibly helpful, I thought it was interesting:

Solution Code

Links

From another CTF Player:

A Simple ROP Exploit | poor_canary writeup

HXP 2018 has a “baby” challenge called poor_canary which was my first actual ROP exploit. If you want to follow along you’ll need to download and install the hxp 2018 vm image and install it locally. If you’re on a mac, you might need to port forward in order to get the image working properly. I have the following in my .zshrc:

That way I can just open up a new screen with my vm running and run hxp to have my vm serve the hxp site to localhost:8888 and if I want to forward one of the services I can run something like hxp 18113 and then nc localhost 18113 will work as expected. I’d like to give a huge shout out to the ENOFLAG team who’s writeup helped me comprehend this challenge. Now that that’s settled, let’s jump in.

Pwntools

I’d never used pwntools before, but it’s something that is completely necessary for this challenge. I set it up in a virtual environment and just source that anytime I want to use it.

Solution

Looking at the c code provided shows us that this is a buffer overflow exploit, but the title leads us to believe that the stack has a canary in it. Looking at the binary in binary ninja confirms this hunch.

__stack_chk_guard check the canary

We can also see that the function pointer to systemis saved after main so we can guess that this address should be somewhere in the binary.

Further analysis of the binary shows us that __libc_system is located at address 0x0016d90.

Now that we know this information, we need to start messing with payloads to send to the binary. Running the command pwn template --host 127.0.0.1 --port 18113 ./canary will generate code to connect to a remote host and send payloads to it. This is part of pwntools. Once we connect to the remote, we can send some code like this:

What does this actually do? Well looking at the c code we can see that we are allocated a 40 character buffer, but we can read in 0x60 characters. It’s also important to note that many canary’s start with 0x00 (why? because this makes it harder to get the canary because this acts like a null terminator). But, in our binary, if we just send 41 characters this will overwrite the null byte and send the remainder of the canary! Then we add back 0x00to get our canary and we’re ready to move forward.

Next comes finding the string /bin/sh, since this is what we’d ideally like to pass to system to spawn a shell. So let’s use ropper to see if there is anything in our binary.

Well that was easy; ropper rocks!

Now, where do we put this string in order to have it be run by system? Using godbold to help us we can look at the ARM assembly for system("/bin/sh");.

Great, so we push our command into register r0 and then system will use that as its argument. Now let’s find some rop gadgets that put things into r0. Keep in mind that ARM is a little weird and uses the concept of regliststo push and pop multiple registers at the same time.

pop {r0, r4, pc}looks ideal. This will take the next three words off the stack and save them into r0, r4, and pc respectively. And with this we can construct our payload! We have 40 bytes of garbage to fill up the buffer, the canary, 12 bytes of garbage (this I just took from the other writeup, if someone could explain exactly how to get this 12 byte offset for the return address that would be really helpful), our ROP gadget, the address of /bin/sh, 4 bytes of garbage (we don’t care what gets saved into r4), and finally the address of system.

To fully lay it out, this will overwrite the return address to be our ROP gadget, which will then pop the address of /bin/sh into r0 and change the PC to the system function. This is essentially calling system("/bin/sh");. Our full exploit script looks like so:

And this gives us access! When we run: