Boston Key Party - Frog Fractions 2 Writeup

In this reversing exercise we are given with an unstripped 64-bit ELF file. Reversing the binary is fairly simple just load it in IDA or hopper and you pretty much have the source code. Before I started working on the task my team mate @sghctoma has already rewritten the program in C and extracted the “constants” array. The source code of the program:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gmp.h>

#include "defs.h"

void factor_print(mpz_t a1)
{
    mpz_t v5;
    char c;

    mpz_init_set(v5, a1);

    for (int i = 0; i <= 171; ++i) {
        c = 0;
        while (mpz_divisible_ui_p(v5, primes[i])) {
            mpz_tdiv_q_ui(v5, v5, primes[i]);
            ++c;
        }
        if (!c) break;
        putchar(c); of the 
    }
    putchar('\n');
}

int main(int argc, char* argv[])
{
    mpz_t v10, v11, v14, v15;
    size_t size = 172;

    mpz_init(v10);
    mpz_init(v11);
    mpz_init(v14);
    mpz_init(v15);

    mpz_set_ui(v15, 1019);

    char* line = (char*)malloc(size);
    size_t s = getline(&line, &size, stdin);
    line[s - 1] = 0;

    // v15 = 1019 * primes[0]^line[0] * primes[1]^line[1] .. primes[limit]^line[limit]
    double limit = fmin((double)s, 84.0);
    for (int i = 0; (double)i < limit; ++i) {
        mpz_set_ui(v14, primes[i]);
        mpz_pow_ui(v14, v14, line[i]);
        mpz_mul(v15, v15, v14);
    }
    // if v15 = fractions[338], or v15 == fractions[339] at this point
    // we get the congratz message.
    int cont;
    int i = 0;
    do {
        cont = 0;
        for (int j = 0; j < 423; ++j) {
            gmp_sscanf(fractions[2 * j], "%Zi", v11);
            gmp_sscanf(fractions[2 * j + 1], "%Zi", v10);
            mpz_set(v14, v15);
            mpz_mul(v14, v14, v11);
            if (mpz_divisible_p(v14, v10)) {
                mpz_tdiv_q(v15, v14, v10);
                cont = 1;
                break;
            }
        }
        i++;
    } while(cont);

    factor_print(v15);
}

The defs.h contains the definition of the primes array which contains the first 172 prime number. The fractions array contain a set of integers that can be factorized with the given prime numbers.

If we go through the code we can see that we have to insert a number by providing the exponents of its prime fractions, however we can only use the first 83 prime numbers. Then the program multiplies this number with 1019 (which is the 171st prime) and runs it through a series of transformation and prints the result. If the result of the transformation is fractions[339] than we get the Congratulations message.

The transformation is the following, it iterates every second number in the fractions array and multiplies the input with it and stores the result in a temporary variable. If the result can be divided with the next number in the fractions[] array than the result is stored as the next input and the cycle goes on. If no division happens the cycle ends and the result is printed.

At this point it is clear that we are looking at a VM that stores its state in an integer with its prime fractions. We can look at this state as the sum of 172 unique bins, each of these bins holding zero or more tokens. The bins are identified by the corresponding prime fraction and the tokens are represented as the exponent of that fraction. The “instructions” try to push some tokens into given bins than try to pop some other tokens, if the pop is successful the instruction is executed otherwise nothing happens (the push is reverted). If no instruction can be executed the final state is printed.

Printing all the states in the fractions array shows that we want the inner state to be fractions[338] or fractions[339], because state 338 is directly transformed into 339 in the next cycle. Unfortunately none of these can be factorized using only the first 83 primes, so we have to take a closer look at the actual instructions. I have written a small python snippet that factorizes all the number pairs in the fractions array and prints which bins and tokens are affected, in the following format:

index inst  count/address
.
.
.
346   pop:  75/0 1/170
      push:  1/171 1/84

352   pop:  69/1 1/170
      push:  1/171 1/85

358   pop:  89/2 1/170
      push:  1/86 1/171

364   pop:  123/3 1/170
      push:  1/87 1/171

370   pop:  40/4 1/170
      push:  1/88 1/171

376   pop:  66/5 1/170
      push:  1/89 1/171

382   pop:  1/170 121/6
      push:  1/90 1/171
.
.
.

By examining the instructions we can see that the 167+ bins are used for control tokens and that the first 165 instructions is pretty much only used to get an arbitrary state into the “wrong solution” state. The really interesting part is the 170th instruction and above every third instruction is used to pop tokens from the first 83 bins and push tokens into each 84-166 bins. This is exactly what is required to reach state “fractions[338]” and get the win message. I have written the following little python script to calculate the correct input:

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def get_solution(num):
    fact = prime_factors(num)
    res = dict()
    for p in fact:
        i = primes.index(p)
        if str(i) in res:
            res[str(i)] += 1
        else:
            res[str(i)] = 1
    ret = ""
    for k in res:
        if k != "170":
           return res[str(k)]
    return ret
    
with open("solution.txt", "wb") as f:
    for i in range(346, len(frac)-2, 6):
        f.write(chr(get_solution(int(frac[i+1]))))
    f.write('\n')

And the result was KEY{(By the way, this challenge would be much easier with a cybernetic frog brain)} those are the correct initial token values for the first 83 bins. At this point we just had to calculate the md5 sum of the string and get the real flag BKPCTF{db7365f3ff8887aa315d79361651627f}.

I think this challenge wasn’t one particularly hard to solve, however it was real fun. I really liked the idea of storing program state as prime fractions, thanks for the organizers for the challenge.