# X-MAS CTF - Catana

## zangobot - zxgio

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}`

.