Two weeks ago I played 0CTF/TCTF 2021 Quals CTF with my team. As every year, it was a pretty fun CTF, though in all honesty I observed only one challenge - pypypypy. Without going into too many details, it was a Python sandbox escape challenge where the player controlled only Python bytecode (limited to 1000 bytes - that's 500 instructions). Yes - only bytecode, i.e. no constants, no local or global variable names, etc (with a minor exception, but that's besides the point). Given this, I had to come up with a way to make strings out of thin air, and before that, make integers out of thin air as well.

Making integers isn't actually that hard, since it's quite easy to get False or True on the stack (e.g. with 2 times BUILD_LIST, 0 followed by a COMPARE), and these get implicitly converted to 0 and 1 respectively when used in any math operations. Having a 1, I implemented a method that just kept left-shifting it (to get 1, 2, 4, 8, 16, 32, 64, ...) and selectively duplicating the values on the stack to add them later - this is basically how the binary system works anyway (and it's quite similar to Russian peasant multiplication method). This worked, but...

As I mentioned above, the total number of instructions was effectively limited to 500, and the above method – while it worked – generated waay too long operation sequences. So I had to figure out a new approach.

In the end I decided not to do it. Or rather, I decided to let my computer figure out what's the shortest way to create a constant number having the value 1 on the stack (technically it should have been True instead, but whatever).

To achieve this I used /dev/urandom a genetic algorithm that created sequences of instructions (limited to math/bitwise/stack operators), then run this "program" on a trivial Python bytecode VM implementation, and if it didn't crash, plus it finished with just one value on the stack, I compared the generated "program" for the given constant to the previously known one (if any). And this worked surprisingly well, allowing me to cut down the per-constant instruction sequence length by anything between 25% and 50%!

Now, the fascinating thing about programs made by genetic algorithms is how eerie they are! A few examples:

• To make the value 0 (which I already had, but I forgot to tell this to the genetic algorithm), it created this expression: 1 % 1 → 0. Is this 0? Yes! Would I have thought of that? Nope – I would just use 1 - 1 instead.
• To make the value 14 it first made the value -2 on the stack with ~1 operation, and then made the value 16 by using power and multiplication, to finally arrive at -2 % 16 → 14. While I'm well aware how negative modulo behaves in various languages, again it's not something I would come up with.

If you're curious, and would like to explore all generated the numbers, you can use this interactive widget - just put a number from 0 to 200 on the top left, and then you can click through the generated Python opcodes to see how the expression is formed (or scroll down for the full list):

I must admit that this was both a pretty fun exercise, and a pretty fun CTF challenge. Apart from automated code generation itself (almost like GitHub Copilot, ey?), writing a trivial "decompiler" that gets the bytecode and returns an expression was interesting as well – I didn't have a chance to do this before.

You can find my source code here (this is CTF-quality code, I am NOT paying for your therapist - you have been warned!):
https://github.com/gynvael/random-stuff/tree/master/pypypypy-genetic

P.S. If you like this kind of stuff, I greatly recommend checking out the Hacker's Delight book.

If you'd like to see the full list of expressions, here it is:

Till next time!