"Hello fibonacci?" was a 100 point programming challenge in the AceBear Security Contest 2018. While all in all not very complicated, I struggled a lot to solve it due to numerous insufficient approaches. These failed approaches as well as the one that worked will be presented below.

Challenge description

Description: Yesterday, my friend shows me some math sequence. And now, it's your turn to showed me your skill. No vuln, just math, raw math :3
Service: nc 35.200.176.244 8856

The problem

We connect to the service using nc and are met with the following output:

~$ nc 35.200.176.244 8856
Programming/ACM challenge!
Sequence: 3 2 1 4 6 7 11 17 24 35 52 76 111 163 239
Send me: number nth % N
Good luck! <3
Author: kad96
n=892905
N=380956559856027373126956504768
~$

The socket closes almost immediately, which means that the results will have to be sent really fast.

It appears that we have to reply with the nth element of the sequence provided. We connect to the service once more, in order to verify whether the sequence stays the same.

~$ nc 35.200.176.244 8856
Programming/ACM challenge!
Sequence: 3 2 1 4 6 7 11 17 24 35 52 76 111 163 239
Send me: number nth % N
Good luck! <3
Author: kad96
n=714289
N=653565208569715160595426147251
~$

As we can see, only the values of n and N changed, so we can go ahead and analyze the sequence.

Analyzing the sequence

The title of the challenge is a big hint, and we quickly realize that the sequence follows the following equation:

While we will use this sequence for our calculations, we should keep in mind that the server probably considers that the first member of the sequence is 3.

A naive solution

We'll call our function fibo2mod in the following implementations. Since I am definitely not a fan of premature optimization, we implement the following very naive solution:

def fibo2mod(n, N):
    if n <= 1:
        return -1
    running = [-1, -1, 3]
    for i in range(1, n):
        running.append((running[0] + running[2]) % N)
        running = running[1:]
    return running[2]

The code needed to parse the input and communicate with the service is fairly straightforward, so it won't be discussed here.

As is often the case in such challenges, solving the first problem is not sufficient to get the flag, and the service issues other values of n and N for which we have to provide the solution.

This naive method fails to produce a fast enough result around the 20th iteration, at which point the n grows by one order of magnitude.

It seems that we have to build faster code.

A better naive solution

Since I still believe that my solution could be sufficient given a bit of cleaning, we implement the following function:

def fibo2mod(n, N):
    a, b, c = -1, -1, 3
    for _ in range(1, n):
        a, b, c = b, c, (a + c) % N
    return c

This function is a bit neater, and it manages to plow through a few more problems. Alas, there's no flag in sight yet.

Since we're obviously lazy and would really like to avoid thinking too much (and also to avoid having to code socket-handling code in C), we try to compile the previous function using cython and by adding furious optimization flags to gcc.

Sadly, without any typing information, cython is not able to produce a better result. Since the number we manipulate are so big, adding typing information sounds like a pain. Also, many teams have solved the challenge at this point in the CTF. Hard to believe that they would go through this trouble.

We decide to let it go and to find a smarter approach.

Using the analytic function

An analytic function is a function that is locally given by a convergent power series (Wikipedia).

For example, the nth member of the Fibonacci sequence can be calculated using the following function:

In order to find a similar functions, we must find the eigenvectors and eigenvalues of the matrix A used in the following set of equations:

In our case, it's pretty easy to figure out that the system is the following:

.

We can already implement the following function in sage:

def fibo2mod(n, N):
    n = n - 1
    return mod((u * (lambda1 ** n) + v * (lambda2 ** n) + w * (lambda3 ** n)).abs().round(), N)

where lambda1, lambda2 and lambda3 are the eigenvalues of the matrices, and u, v and w the coefficients for which the linear combination of the sequence correspond to the first terms of the sequence.

We execute the following lines in sage:

A = matrix([[1, 0, 1], [1, 0, 0], [0, 1, 0]])
eigen = A.eigenvectors_right()

lambda1 = eigen[0][0]
lambda2 = eigen[1][0]
lambda3 = eigen[2][0]

var('u v w')

eq1 = eigen[0][1][0][0] * u + eigen[1][1][0][0] * v + eigen[2][1][0][0] * w == 3
eq2 = eigen[0][1][0][1] * u + eigen[1][1][0][1] * v + eigen[2][1][0][1] * w == -1
eq3 = eigen[0][1][0][2] * u + eigen[1][1][0][2] * v + eigen[2][1][0][2] * w == -1

solve([eq1, eq2, eq3], u, v, w)

Sadly, due to a weird error from sage, the system is not solvable on my configuration if eq1, eq2 and eq3 use the exact values provided by eigenvectors_right().

By copying approximative values for each element in the eigenvectors up to 16 decimals, I obtain consistent values for u, v, and w.

At this point, I am able to check that fibo2mod can and does find the exact values of the first few members of the sequence.

Unfortunately, the members requested by the service can contain more than 10000 digits. The approximations used to build our function are therefore too imprecise to provide a function that works for our use case.

Exact analytic function

We can try to execute the previous code once again, but this time using symbolic representation in order to get exact values another way. This only requires that we replace

A = matrix([[1, 0, 1], [1, 0, 0], [0, 1, 0]])

by

A = matrix(SR, [[1, 0, 1], [1, 0, 0], [0, 1, 0]])

That still doesn't work, but for another reason: now, sage is unable to find any eigenvector…

By changing our approach, it is still possible to find a symbolic representation of the values we want by finding the roots u, v and w of the following polynomial:

and then solving our linear system for lambda1, lambda2 and lambda3.

We find the roots by executing the following code:

K.<X> = SR[]
P = X**3-X**2-1
P.roots()

With that, and after solving the system, we have a symbolic representation of the analytic function. However, when we try to execute it… the program just hangs.

Guess we're going to have to find another way.

C libraries in Python

We're going to have to write in C, this time. But writing all the code to communicate with the service sounds like a pain. Fortunately, we stumble upon the ctypes library.

ctypes is a foreign function library in Python that allows calling functions in shared libraries.

Using the GNU MP Bignum Library in order to handle very large numbers, we write the following C code:

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

char *fibo2mod(unsigned long long n, char *mod) {
    mpz_t a, b, c, N, tmp;
    mpz_init_set_str(a, "-1", 10);
    mpz_init_set_str(b, "-1", 10);
    mpz_init_set_str(c, "3", 10);
    mpz_init_set_str(N, mod, 10);

    mpz_init(tmp);

    for (unsigned long long i = 1; i < n; ++i) {
        mpz_set(tmp, a);
        mpz_set(a, b);
        mpz_set(b, c);
        mpz_add(c, c, tmp);
        mpz_mod(c, c, N);
    }

    char *result = NULL;
    result = mpz_get_str(result, 10, c);
    return result;
}

and compile it to a shared object using the following compilation instructions:

~$ gcc -c -fPIC solve.c
~$ gcc solve.o -shared -o libsolve.so -lgmp

In order to hook it to our python code, we add the following lines there:

import ctypes
import ctypes.util

solve = ctypes.cdll.LoadLibrary('/home/siben/CTF/2018/AceBear/Hello_fibonacci/C/libsolve.so')

fibo2mod = solve.fibo2mod
fibo2mod.restype = ctypes.c_char_p

This DOES provide better performance. Unfortunately, we only manage to solve problems up to step 40. After asking the admins about it, I learn that there are 100 levels to complete.

At this point, I realize I have to rethink my approach to the problem, and come up with…

Modular exponentiation

I don't know why I didn't think of that before. This is quite easy to implement. We start by efficiently exponentiating the matrix we defined before, and then multiply it with the vector containing our start elements. Using numpy, we obtain the following recursive code:

import numpy as np

def fibo2mod_aux(matrix, count, mod):
    if count == 0:
        return np.matrix([[1, 0, 0], [0, 1, 0], [0, 0, 1]])
    if count % 2 == 1:
        return (matrix * fibo2mod_aux(matrix, count - 1, mod)) % mod
    return (fibo2mod_aux(matrix, count / 2, mod)**2) % mod

def fibo2mod(n, N):
    mx = np.matrix([[1, 0, 1], [1, 0, 0], [0, 1, 0]])
    return (fibo2mod_aux(mx, n - 1, N) * np.matrix([[3], [-1], [-1]])) % N

We stare at our screen in awe while this very basic solution solves the 100 challenges without breaking a sweat.

And… we get the flag: AceBear{Math_is_always_fun!s0me_icedoll_said!}!

Conclusion

I have been able to rediscover a lot of things during this challenge, so I'm pretty happy with the result. However, the time it's taken me to actually get the flag leaves me quite salty.

Folks, don't try this at home.