The program tries to compute a sequence of very big numbers and it uses them to decode the flag. The function at address `0x00400556` contains the generator of that sequence (it is not PIE, hence the functions are loaded always at the same addresses). We translated it into python code:

``````def catalan(a1,a2,a3):
result=0
if a1 ==a2 and a2==a3: return 1
if a1 > a2: result= catalan(a1, a2+1,a3)
if a1 > a3 and a2>a3: result += catalan(a1,a2,a3+1)
return result
``````

By googling the first results of the sequence, we understood that it is a famous mathematical series called Catalan Numbers.

The program tries to compute this sequence for numbers from 1 to 36, and it is computationally unbearable. Moreover, not all the computations are necessary because the program multiplies the computed value with an entry of a matrix, which hardcoded into the program. Only few entries are different from zero, so it’s a waste of CPU!

To overcome this issue, we dumped the matrix using radare2 and we precomputed the first 36 catalan numbers. Then, we used frida to re-write the catalan function to avoid any computation, and we replaced it with a lookup table.

``````'use strict';
Interceptor.replace(ptr('0x00400556'), new NativeCallback(function(j,a,b) {
var CATALANS = ['1', '1', '2', '5', '14', '42', '132', '429', '1430', '4862', '16796', '58786', '208012', '742900', '2674440', '9694845', '35357670', '129644790', '477638700', '1767263190', '6564120420', '24466267020', '91482563640', '343059613650', '1289904147324', '4861946401452', '18367353072152', '69533550916004', '263747951750360', '1002242216651368', '3814986502092304', '14544636039226909', '55534064877048198', '212336130412243110', '812944042149730764', '3116285494907301262', '11959798385860453492'];
var x = new Int64(CATALANS[j]);
return x;
},'int64', ['int64','int64','int64']));
``````

And we are done! Here you can find the file of the challenge. The flag is `X-MAS{c474l4n_4nd_54n74_w3r3_600d_fr13nd5_1_7h1nk}`.