# Frog Fractions 2 WriteupBoston Key Party CTF 2016

`Turns out Frog Fractions 2 is not battletoads.`

When you run this challenge, it gets input and prints: `Nope! You need to practice your fractions!` To find the logic for final input checking, I used IDA to search for cross references to the failed output. Weirdly, the binary has no strings pertaining to success or failure. Still, we need to find a way to print some way to print something else.

Throughout the binary, we see references to GMP functions. GMP is an arbitrary precision arithmetic library with bindings for many languages. We’re probably dealing with big numbers…

At the beginning of the program, there are several calls to `__gmpz_init`. The “z” refers to the mathematical notation for the set of all integers. `gmpz_init` takes one argument, an `mpz_t`, which is actually a pointer to a special struct as evidenced by the `lea` instruction, and returns a new `mpz_t`. The `__gmpz_set_ui` function sets an `mpz_t` to an unsigned integer. Below, we see two integers initialized with one, `int1`, set to 1019. After initializing these two integers, the program creates a number by raising each prime to the power of the ASCII value of corresponding input characters and multiplying it with `int1`. For instance, if the input is `AB` the first prime, 2, is raised to 0x41 and the second prime, 3, is raised to 0x42. Thus, the resulting number is 1019 * 2^0x41 * 3^0x42.

`__gmpz_pow_ui` takes three arguments: an `mpz_t` to store the value, an `mpz_t` to be the base, and an `unsiged int` for the exponent. `__gmpz_mul` has a similar signature: an `mpz_t` to store the value and 2 operands of type `mpz_t`. The following pseudocode is equivalent:

Following the creation of `int1`, the program reads in a series of numerical pairs, which I called x’s and y’s, from `program`. `__gmp_sscanf` functions the same as `sscanf` taking a string pointer, a format string, and pointers to store the scanned values. Number strings in `program` (there’s ~250 pairs total): Next, the program checks that each x/y pair satisfies the relationship that x * int1 is evenly divisible by y. If it doesn’t, bad things happen and the program output remains the same.

`__gmpz_set` sets the first `mpz_t` equal to the second. `__gmpz_mul` multiplies the last two `mpz_t`’s and stores the result in the first. Finally, `__gmpz_divisible_p` checks if the second `mpz_t` evenly divides the first. To create a number that satisfies this relationship, I initially tried messing around with iteratively setting n to the lcm of y and x * n and dividing the result by x to cancel out its factors. Unfortunately, this number didn’t work and printed out the same message.

I realized that if I represent each number as a mapping of its factors to their corresponding exponent, I can simplify the process. This time, I iteratively set n using the following expression:

Note that the OR, AND, and subtraction signs stand for set operations in python. Since I am using a multiset (`Counter` in python) to represent the mapping, these operations differ slightly from normal set operations. The OR, or union, operation creates a new set with the values from both sets; if there are two instances of the same factor, it keeps the greater exponent. Likewise, the AND, or intersection, operation creates a new set with only factors that show up in both; if there are two instances of the same factor, it keeps the smaller exponent. The subtraction operation sets each exponent equal to exponent(left) - exponent(right).

Examining the above expression, `x & n` is equivalent to asking what factors do x and n together have. Then `y - (x | n)` asks what factors does y have that x and n do not share, or what factors does n need to make itself times x divisible by y. Finally, we add those factors to n with `n | (y - (x | n))`.

Now that we have a prime factorization of the number needed to solve the challenge, we just need to write it to the challenge input format. Recall that the program generated an input number by raising each prime to the ASCII value of the corresponding input. The following code generates the input from the multiset we used to represent n:

The resulting string is: `KEY{(By the way, this challenge would be much easier with a cybernetic frog brain)}` – a.k.a. the flag.