Tags: arm64 algebra math
Rating:
**Description**
> Wooble CEO's baby is learning computers. Help him with math.
**Files provided**
- [re1](https://github.com/Aurel300/empirectf/blob/master/writeups/2018-09-08-HackIT-CTF/files/re1)
**Solution** (by [Mem2019](https://github.com/Mem2019))
use IDA to open it, and the program is 64 bit ARM. There are many functions, so let's look at string first.
Then we can find the string `"oh noes! you no haz flag!"`, xref it, the function seems to be the verification function.
By inspecting the code, we can find that this is a matrix multiplication using nested loop to access data and compare the result with given data, we can take the matrix by the following C code. (modified from decompiled code)
`DATA2_NUM` from IDA analysis is incorrect, so I obtained it manually
```c
#include <stdio.h>
#include <stdint.h>
#define DATA1_OFF 0x7d010
#define DATA2_OFF 0x110a90
#define DATA1_NUM 151200
#define DATA2_NUM 7564
uint32_t data1[DATA1_NUM];
uint32_t data2[DATA2_NUM];
void load1()
{
FILE* f = fopen("./re1", "rb");
fseek(f, DATA1_OFF, SEEK_SET);
fread(data1, sizeof(uint32_t), DATA1_NUM, f);
fclose(f);
}
void load2()
{
FILE* f = fopen("./re1", "rb");
fseek(f, DATA2_OFF, SEEK_SET);
fread(data2, sizeof(uint32_t), DATA2_NUM, f);
fclose(f);
}
void show_matrix()
{
signed int i;
signed int j;
signed int k;
signed int l;
signed int m;
signed int n;
signed int ii;
for ( i = 0; i <= 6; ++i )
{
for ( j = 0; j <= 8; ++j )
{
for ( k = 0; k <= 2; ++k )
{
for ( l = 0; l <= 4; ++l )
{
for ( m = 0; m <= 1; ++m )
{
for ( n = 0; n <= 3; ++n )
{
printf("[");
for ( ii = 0; ii <= 19; ++ii )
{
int idx = 0x50LL * m + 0x5460LL * i +
0x960LL * j + 0x14LL * n + 0xA0LL * l +
0x320LL * k + ii;
if (idx >= DATA1_NUM)
{
printf("out of bound\n");
}
printf("%u, ", data1[idx]);
}
printf("],");
int idx = 4 * (2 * (15LL * j +
135LL * i + 5LL * k + l) + m) + n;
if (idx >= DATA2_NUM)
{
printf("out of bound\n");
}
printf(" %u\n", data2[idx]);
}
}
}
}
}
}
}
int main()
{
load1();
load2();
show_matrix();
return 0;
}
```
However, the result is huge with around 7560 lines, but for linear equation solving with 20 dimension vector, we only need a 20x20 matrix, so just take the first 20 data
```python
from numpy import *
mat = [[62, 23, 49, 47, 63, 36, 91, 6, 31, 16, 11, 91, 2, 49, 73, 19, 77, 76, 67, 86],
[89, 37, 34, 76, 30, 14, 73, 32, 20, 84, 85, 67, 3, 62, 54, 20, 78, 100, 36, 64],
[100, 71, 39, 26, 74, 73, 83, 95, 62, 90, 8, 11, 77, 32, 19, 9, 23, 76, 62, 88],
[6, 61, 69, 72, 84, 27, 18, 69, 14, 99, 20, 21, 13, 23, 42, 15, 32, 17, 73, 23],
[20, 74, 49, 43, 63, 96, 4, 88, 84, 95, 36, 51, 89, 39, 2, 41, 77, 11, 22, 20],
[41, 51, 11, 80, 0, 40, 26, 5, 11, 78, 60, 35, 53, 33, 69, 67, 0, 100, 39, 25],
[28, 27, 3, 57, 64, 23, 68, 49, 26, 16, 20, 66, 58, 3, 51, 28, 39, 5, 56, 52],
[41, 60, 51, 98, 40, 36, 50, 56, 79, 50, 57, 48, 52, 43, 66, 64, 8, 38, 65, 26],
[65, 88, 53, 36, 29, 84, 21, 98, 92, 14, 94, 29, 42, 83, 45, 34, 44, 78, 44, 77],
[78, 64, 92, 18, 39, 98, 46, 7, 60, 48, 31, 74, 40, 26, 70, 29, 23, 13, 100, 33],
[38, 63, 66, 53, 7, 87, 70, 77, 51, 98, 100, 83, 75, 67, 7, 41, 63, 80, 45, 93],
[18, 68, 76, 85, 6, 36, 24, 52, 57, 0, 4, 95, 88, 72, 46, 9, 84, 31, 22, 94],
[99, 58, 9, 72, 28, 95, 11, 74, 2, 46, 45, 62, 10, 19, 97, 30, 91, 73, 83, 55],
[100, 33, 92, 7, 60, 75, 30, 85, 62, 100, 47, 89, 14, 47, 73, 79, 92, 99, 52, 27],
[25, 19, 3, 89, 29, 2, 14, 29, 42, 23, 88, 95, 76, 54, 1, 47, 77, 50, 50, 23],
[100, 69, 71, 97, 72, 34, 41, 8, 35, 40, 91, 49, 54, 8, 20, 2, 15, 73, 77, 84],
[46, 81, 51, 9, 98, 99, 47, 61, 38, 97, 60, 88, 63, 54, 30, 15, 57, 72, 60, 44],
[32, 42, 30, 20, 56, 4, 35, 73, 13, 42, 64, 90, 81, 31, 82, 43, 91, 93, 4, 1],
[55, 32, 51, 3, 32, 59, 84, 20, 96, 7, 99, 38, 3, 21, 80, 88, 50, 46, 34, 68],
[70, 30, 76, 29, 33, 50, 95, 47, 11, 4, 96, 82, 91, 52, 68, 83, 28, 27, 89, 30],
[25, 50, 25, 95, 78, 28, 1, 77, 62, 89, 0, 72, 38, 38, 33, 34, 75, 59, 18, 50],
[6, 3, 59, 2, 15, 26, 93, 94, 2, 10, 44, 84, 41, 26, 90, 38, 30, 91, 18, 81],
[73, 10, 81, 56, 75, 67, 17, 85, 77, 95, 0, 64, 68, 96, 100, 78, 76, 26, 2, 40],
[95, 6, 77, 46, 9, 64, 77, 70, 98, 97, 55, 64, 35, 33, 75, 69, 42, 47, 4, 54],
[3, 84, 94, 24, 59, 31, 69, 79, 80, 98, 84, 69, 77, 83, 96, 92, 25, 30, 7, 100],
[80, 50, 2, 98, 22, 65, 36, 47, 81, 88, 20, 93, 12, 93, 69, 60, 41, 82, 17, 98],
[27, 37, 4, 15, 29, 28, 49, 58, 81, 3, 71, 57, 87, 94, 59, 94, 41, 79, 28, 100],
[39, 96, 87, 43, 21, 4, 27, 83, 73, 23, 90, 48, 92, 31, 7, 35, 50, 82, 94, 61],
[78, 51, 45, 15, 55, 12, 19, 30, 16, 50, 4, 30, 39, 37, 54, 21, 72, 34, 45, 43],
[72, 84, 91, 13, 68, 9, 41, 72, 75, 35, 32, 61, 43, 4, 63, 78, 52, 38, 17, 51],
[20, 50, 87, 89, 15, 69, 95, 43, 38, 24, 96, 23, 62, 25, 0, 46, 14, 56, 63, 11],
[68, 20, 74, 94, 54, 29, 99, 65, 23, 97, 10, 7, 49, 37, 87, 6, 57, 32, 73, 23],
[40, 23, 89, 60, 39, 7, 69, 15, 13, 57, 65, 49, 8, 21, 70, 45, 9, 21, 32, 40]]
res = [85050,91195,104053,74886,96859,78247,69704,93536,99410,91294,109711,85114,104598,118115,76597,91860,108325,86408,79996,92996,93246,71132,109941,99177,108060,107507,89876,95925,70342,90748,76100,90138,62864]
a = array(mat[:20])
b = array(res[:20])
x = linalg.solve(a, b)
print x
print ''.join(map(chr,[ 109,101, 32, 99, 97,110, 32,104, 97,122, 32,117,114, 32,102,108, 97,103,122, 63]))
```
`me can haz ur flagz?`
