X-MAS CTF - Catana

tags: ctf challenge write-up reverse
by 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):
	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}.