## HACKvent 2015: Day 12

12 Dec 2015
CTF: Hackvent 2015
Date Completed: 12 December 2015

## Challenge

The following C code is also provided:

## Solution

Clearly the issue here is that this program is very inefficient.
So what does the program do? First it sets the unsigned 64 bit integer variables  val and i  to 0. Then 0xC0DE42 iterations occur and the val is recomputed each calculation. The previous val  and i  values are used to recompute the new val  value.

After all this, it appears as if the nugget we need is printed out! The 4 missing blocks in the nugget are based on 4 groups of 16 bits which come from the final val value.
So we begin to optimize the code!

foo and bar

We start with the foo and bar  functions which are very similar to each other.
It turns out that they simplify to:

So we have just optimised these two functions slightly. The next step is go through the code and replace all calls to foo  and bar  with simply increments or decrements. I’m not going to show the changes I made to each call as that would make this post too long but you get the idea.

Optimized functions:

baz

baz  should look like this at this stage:

It is clear from the code that baz  can be optimised. First the variable r  is set to zero and then a 1 is added to r , a times. Then 1 is added to rb times.
This is simply the same as adding a  to b  and storing the result in r .

Optimized function:

spam

Spam should look like this at this stage:

This function is simply setting r  to a and then taking away 1 from rb times before returning the result in r .
This is the same as returning a - b .

Optimized function:

eggs

eggs  should look like this at this stage:

Well all that is happening here is r  is increasing by b, a times. That means we are adding a number of b’s to r .
This is the same as returning a * b .

Optimized function:

merry

merry  should look like this at this stage:

So at this stage, we are taking away b  from a  while a  is still bigger than b . The value of  i is then returned which is the number of times we took away b  from a .
This is clearly a simple division operation: a / b

Optimized function:

xmas

xmas  should look like this at this stage:

This one is a little more tough. a  is divided by b  then multiplied by b  and this result is subtracted from a . You may be tempted to think that this returns 0 all the time but it does not.
This is because the division operation that occurs is integer division and multiplying that result by b  may not result in the original a  being restored.
A small example: 10/3 = 3.33 but is stored as 3 in an integer. However, 3*3 = 9 and not 10!

In this case, a modulo operation is happening: a % b

Optimized function:

hackvent

hackvent should look like this at this stage:

This is a fun one. Notice how r is set to 1 initially, that is important. r is then multiplied by ba number of times.
This is the same as calculating b to the power of a.
However, we cannot just use the pow function defined in <math.h>.
We are dealing with uint64_t data types and must thus get a power function that can handle these larger numbers.
I decide to find one online and use it.

Optimized function ( ipow  and hackvent):

Putting it all together

At this stage you can do two things.
You can either run your program as is to find the answer or you can inline your function or convert the function calls in main so you save making all those function frames.
In this case it doesn’t really matter but this is what the calculation of val in main should look like with no function calls:

Then you run your program and within a few seconds you get the flag!

Flag:  HV15-mHPC-067e-751e-f50e-17e3