Points: 150 Solves: 7 Category: Reverse Engineering, PPC Description:
Get the flag!
nc milkyway.chal.mmactf.link 6310
Write-up
ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, stripped
I really liked this problem, the general reversing of it is not much and not really complicated. But knowing what needs to be done and actually doing it are two complitely different things :). Truth is, I didn’t solve it during the competition. With the help of some friends and someone from irc (sorry I forgot your name…) we got to the solution. I’m doing this write-up only because I like the problem and nobody else has posted a solution for it yet.
In the beginning we just have a loop that takes up to 19 integers using scanf(“%d”), places each integer into an int array.
Each number is checked if it’s larger than 1 and less than 1 000 000.
Also each number needs to be larger than the previous number. In the next stage we have another loop that proceses our array of input integers.
In the above screenshot we see our integers being added together and multiplied together. Four local variables are being created here. One for the sum of the integers, one for the product of the integers, one for the number of times the sum overflew 0xFFFFFFFF and one for the number of times the multiplication of the integers overflew 0xFFFFFFFF.
Ok, so far so good, here though we see the actual decision making.
I’ve named the four variables ‘sum’, ‘product’, ‘overflows_of_sum’ and ‘overflows_of_product’ respectively. In order to get to the GoodBoy, we need EAX to be 0. To get EAX to be 0, we need the ‘sum’ to be equal to the ‘product’ and ‘overflows_of_sum’ to be equal to ‘overflows_of_product’. But how do you make that equation (a + b + c + d + …. + n) == (a * b * c * d * …. n) , really ? Well here comes the PPC problem I guess :). With the following C++ program we tried to solve this first problem.
#include <iostream>
using namespace std;
int main()
{
unsigned int x = 0;
unsigned int y = 0;
unsigned int z1 = 0;
unsigned int z2 = 0;
for (x = 0; x < 1000000 ; x++) {
for (y = 0; y < 1000000 ; y++) {
z1 = x*y;
z2 = x+y;
if (z1 == z2) {
cout << x << " " << y << " " << z1 << " " << z2 << endl;
}
}
}
return EXIT_SUCCESS;
}The program produced some of the following values:
x y sum prod
20858 411850 432708 432708
26318 652806 679124 679124
34742 618142 652884 652884
36250 947882 984132 984132
45762 187714 233476 233476
60540 922292 982832 982832
62572 137284 199856 199856
75066 801034 876100 876100 As we can see the (sum == product), however the second part of the equation is not satisfiable yet. The variables that keep track of the number of overflows for the sum and the product does not match. This is because the variable ‘overflow_of_sum’ will always contain 0 (since 19 * 1000000 < 0xFFFFFFFF) and the variable ‘overflow_of_product’ will always contain non-zero value since the sum will never be equal the product if it doesn’t overflow it’s 32bit size.
As probably you have already thought of, to satisfy this second condition we need to overflow the actual variable that keep track of the number of overflows of the product of our integers :). Since we need to overflow two 32bit integers we need to find prime factors of at least 2^64 or hex 0x10000000000000000. Ok, that’s easy we can find prime factorization of 2^64 however, just doing this our first condition is now wrong, the sum does not equal the product…
Here is where my poor math skills left me in the dust :(…
The way to solve this is not to actually use prime factors of 2^64 and overflow the ‘overflow_of_product’ just once but instead overflow it multiple, multiple times. Let’s make a test and use some prime factors of 2**64.
>>> hex((2 * 4 * 8 * 16 * 32 * 64 * 128 * 256 * 512 * 1024 * 2048))
'0x40000000000000000L'
>>> hex((2 * 4 * 8 * 16 * 32 * 64 * 128 * 256 * 512 * 1024 * 2048) / 2**64)
'0x4L'
>>> hex((2 * 4 * 8 * 16 * 32 * 64 * 128 * 256 * 512 * 1024 * 2048) % 2**64)
'0x0L'
>>> hex((2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1024 + 2048))
'0xffe'
>>>This tells us that using these prime factorials we will get sum = 0xffe, product = 0 and overflow_of_product = 0. If we play around to get the product to equal the sum or the sum to be equal the product we see that we fail miserably because the above prime factorization will always be equal 0000000000000000 in the low order 64bits.
>>> hex((2 * 4 * 8 * 16 * 32 * 64 * 128 * 256 * 512 * 1024 * 2048 * 0xffe))
'0x3ff80000000000000000L'
>>> hex((2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1024 + 2048 + 0xffe))
'0x1ffc'
>>> hex((2 * 4 * 8 * 16 * 32 * 64 * 128 * 256 * 512 * 1024 * 2048 * 0xffe) % 2**64)
'0x0L'The key to the solution came from somebody on irc after the challenge has ended, and it was to use a prime factorization of (2^64)+2. So we went to www.wolframalpha.com and looked up some prime factors of it.
However, we can’t use 77158673929 because it’s larger than 1 000 000 and it breaks the integer requirements. So instead we started multiplying this product as “2(2^64)+2”, “3(2^64)+2”, “4*(2^64)+2”… until we saw prime factors within the 1 000 000 range that we can use.
Using the “15*(2^64)+2” game us prime factors within the correct range.
Using the above prime factors we can see that the sum will be 368553, the product will be 2 and the ‘overflow_of_product’ will be 0 (we can determine that by looking at the bits 32-64 in the hex representation).
>>> (2 + 11 + 17 + 23 + 113 + 10487 + 109103 + 248797)
368553
>>> ((2 * 11 * 17 * 23 * 113 * 10487 * 109103 * 248797) % 2**64)
2L
>>> hex((2 * 11 * 17 * 23 * 113 * 10487 * 109103 * 248797))
'0xf0000000000000002L'
>>>Great, so now if we add another factor and our product will reflect that.
>>> hex((2 * 11 * 17 * 23 * 113 * 10487 * 109103 * 248797 * 368553))
'0x545ae700000000000b3f52L'
>>> (2 + 11 + 17 + 23 + 113 + 10487 + 109103 + 248797 + 368553)
737106
>>> ((2 * 11 * 17 * 23 * 113 * 10487 * 109103 * 248797 * 368553) % 2**64)
737106L
>>>Awesome ! Let’s try it while the server is still up :).
Home:~$nc milkyway.chal.mmactf.link 6310
2
11
17
23
113
10487
109103
248797
368553
1
Correct!
The Flagword: MMA{0Verflow64bit}
Home:~$