PowerPlay

This post is a challenge Writeup for Nullcon CTF '25

nullcon/misc/powerplay

Let’s look at what’s inside chall.py shall we?

The first thing of note is the bizarre definition of prizes. It is a super list of strings, the last 24 of which repeat the flag, our point of interest.Python allows negative indexing, reading iterables like lists backward rather than conventionally forward. On line 25, if power[i] is negative and greater than or equal to -24, it should leak the flag.The issue with inputting in a negative value is that the program expects us to ‘pump up’ at least once before ‘cashing in’. Pumping involves squaring said input, and since only real integers are accepted, that restricts the capabilities of our exploit.Fret not, however! When theoretical math fails, we rely on implementational weirdness to answer our prayers. In many lower-level memory-restricted programming, a concept called overflows exists.

What are overflows?

Although theoretically flexible in terms of size for any form of data, implementation restricts the size of storage based on the data type, the architecture, and the language.For the sake of brevity, let’s stick to signed integers since that’s what we are working with. Let’s assume integers take one byte of memory space. That’s 8 bits (or 2 nibbles for you old folk).Let’s take the number 127. In binary that should be 1111111. When storing this data in a byte of memory, it’ll be as such:

Alright! Now let’s add 2 to this value and watch what happens.

The resulting value is 10000001. Hold on a minute! You were gonna convert this to 129, weren’t you? In the case of unsigned integers, you would be on point. However, whenever it comes to signed integers, the last bit is reserved to indicate the sign of the number (0 for non-negative and 1 for non-positive).Given that fact, our resulting arithmetic resolves to -0000001 or -1. Wait how did that happen? Summing two positive integers resulted in a negative one? Such are the consequences of containing the powers of math onto puny chips and transistors. This my dear friend is an overflow. Now back to the challenge.

We’ve found the vault, now to crack the lock!

Let’s see what we have so far: Your input is stored and squared at least once. The flag is only reachable if we move backward by at most 24 indices, and the input is stored as an int32 type (i.e., 32 bits or 4 bytes of memory). Hence, overflowing 31 bytes such that the resulting value is a negative number whose magnitude is no greater than 24 should yield the flag. Simple enough? Well if you plan to do this by hand, not so much (unless you are a polyglot in the 17th century with 5 years to spare).

Making the lockpick

In times like these kids, we code. So let’s get scripting!

Before we get into what this little scribble over here cooks up, a few irrelevant or subjective decisions in this code need to be mentioned, lest I confuse you, dear reader. Tqdm is a purely aesthetic library that lets you print out a cool dynamic “progress bar” of sorts via tqdm.tqdm, passing in an iterable that serves as the “progressie".The custom function definitions are not entirely necessary and it would be ideal if we used numpy’s int32 data type. This implementation was how it naturally occurred to me and can be altered to give the same solution. To find the solution to an algorithmic problem, one can either reverse engineer (in the non-hacker sense) the algorithm to produce the inverse algorithm or simply emulate all of its necessary functionalities and run it as a simulation. We’ll be following the second method since it’ll be quicker.trueStore() simply represents how unsigned int32s are stored in memory. Any data that crosses the 32nd bit will not be read as a part of the value of the current variable, sufficiently replaceable with a modulo 2^32 (the highest value possible)

proj(), a shorthand for projection, is a combination of ‘pump up’’s squaring functionality applied to a conversion of unsigned int32s to signed int32s (note that 1 bit is reserved for sign representation, resulting in 31 bits of “magnitude” space).

To skip the first few trivial values that fall under the valid non-overflow range, the initial value is set to ceil(sqrt(231)) = ceil(215.5)=46341

The highest value would naturally be 231, represented by HALFWIDTH.

Now all that’s left is to dig this astronomical range for a match, namely satisfying the condition prj < 0 & -prj<= 24. Since one match is all we need, we can end it there.

Let’s break in!

Let this guy loose and feel free to grab a cup of coffee or something while he rummages his head for a number.

A really big number that when squared gives us a negative number that falls within the bounds of 24: 34716455, resulting in -15. Let’s give this a try:

And sure enough, the flag is ours. Thank the loop gods!