hitcon-2017-seccomp-sol.cpp

#include <iostream>
#include <cassert>

using namespace std;

int invMod[0x10001];

template<typename T>
T exgcd(T a,T b, T& x, T& y)
{
	if (b==0)
	{
		x = 1; y= 0;
		return a;
	}
	T nx, ny;
	T ret = exgcd(b,a%b, nx, ny);
	x = ny, y = nx - (a/b)*ny;
	return ret;
}

unsigned long long CHK0(unsigned long long x) {
	return !x ? 0x10000 : x;
}

void initial_fw(unsigned long long mem[4], unsigned long long n1, unsigned long long n2, unsigned long long n3, unsigned long long n4) {
	mem[0] = ((CHK0(mem[0]) * n1) %0x10001) & 0xFFFF;
	mem[1] = (mem[1] + n2) & 0xFFFF;
	mem[2] = (mem[2] + n3) & 0xFFFF;
	mem[3] = ((CHK0(mem[3]) * n4) %0x10001) & 0xFFFF;
}

void initial_bw(unsigned long long mem[4], unsigned long long n1, unsigned long long n2, unsigned long long n3, unsigned long long n4) {
	mem[0] = ((CHK0(mem[0]) * invMod[n1]) %0x10001) & 0xFFFF;
	mem[1] = (mem[1] - n2) & 0xFFFF;
	mem[2] = (mem[2] - n3) & 0xFFFF;
	mem[3] = ((CHK0(mem[3]) * invMod[n4]) %0x10001) & 0xFFFF;
}

void block_fw(unsigned long long mem[4], unsigned long long $num1, unsigned long long $num2, unsigned long long $num3, unsigned long long $num4, unsigned long long $num5, unsigned long long $num6) {
	initial_fw(mem, $num1, $num2, $num3, $num4);

	unsigned long long mem4 = mem[0] ^ mem[2];
	unsigned long long mem5 = mem[1] ^ mem[3];
	mem4 = ((CHK0(mem4) * $num5) %0x10001) & 0xFFFF;
	mem5 = (mem4 + mem5) & 0xFFFF;
	mem5 = ((CHK0(mem5) * $num6) %0x10001) & 0xFFFF;
	mem4 = (mem4 + mem5) & 0xFFFF;
	
	mem[0] = mem[0] ^ mem5;
	mem[1] = mem[1] ^ mem4;
	mem[2] = mem[2] ^ mem5;
	mem[3] = mem[3] ^ mem4;
}

void block_bw(unsigned long long mem[4], unsigned long long $num1, unsigned long long $num2, unsigned long long $num3, unsigned long long $num4, unsigned long long $num5, unsigned long long $num6) {
	unsigned long long mem4 = mem[0] ^ mem[2];
	unsigned long long mem5 = mem[1] ^ mem[3];
	
	mem4 = ((CHK0(mem4) * $num5) %0x10001) & 0xFFFF;
	mem5 = (mem4 + mem5) & 0xFFFF;
	mem5 = ((CHK0(mem5) * $num6) %0x10001) & 0xFFFF;
	mem4 = (mem4 + mem5) & 0xFFFF;
	
	mem[0] = mem[0] ^ mem5;
	mem[1] = mem[1] ^ mem4;
	mem[2] = mem[2] ^ mem5;
	mem[3] = mem[3] ^ mem4;
	
	initial_bw(mem, $num1, $num2, $num3, $num4);
}


int main(int argc, char *argv[]) {
	for(int i=1;i<0x10001;i++) {
		int a, b;
		exgcd(i, 0x10001, a, b);
		invMod[i] = ((a + 0x10001) % 0x10001) & 0xFFFF;
	}
	
	for(int t=0;t<1000;t++) {
		unsigned long long mem[4], xmem[4];
		for(int i=0;i<4;i++) mem[i] = xmem[i] = rand() & 0xFFFF;
		block_fw(mem, 0x7b1b, 0x1b2b, 0x9afb, 0x390b, 0x9b2b, 0x63ab);
//		for(int i=0;i<4;i++) printf("[%d] %04x -> %04x\n", t, xmem[i], mem[i]);
		block_bw(mem, 0x7b1b, 0x1b2b, 0x9afb, 0x390b, 0x9b2b, 0x63ab);
		for(int i=0;i<4;i++) assert(mem[i] == xmem[i]);
	}
	
	unsigned long long mem[4];
	
	unsigned long long args[5];
	
	#define REQUIREMEM(a, b, c, d, x) mem[0] = a ^ x, mem[1] = b ^ x, mem[2] = c ^ x, mem[3] = d ^ x;
	#define INITIAL(a, b, c, d) initial_bw(mem, a,b,c,d);
	#define BLOCK(a, b, c, d, e, f) block_bw(mem, a,b,c,d,e,f);
	#define LOADMEM(xf) {unsigned long long x=((unsigned long long)mem[0]<<48)|((unsigned long long)mem[1]<<32)|((unsigned long long)mem[2]<<16)|((unsigned long long)mem[3]); printf("%s: %016llu\n", #xf, x); xf = x;};
	#define SWAP(a,b) swap(a,b);
	
	REQUIREMEM(40175, 26311, 54488, 23870, 4919)
	INITIAL(0x1997, 0xd95a, 0xd859, 0x97d8)
	BLOCK(0xcbec, 0xad6c, 0x2ccb, 0xec2b, 0xedac, 0x2be9)
	SWAP(mem[1], mem[2])
	BLOCK(0xf656, 0xb616, 0x65f6, 0x15f6, 0x2cec, 0x2d8c)
	SWAP(mem[1], mem[2])
	BLOCK(0x2b5b, 0xb32, 0xd615, 0xf496, 0x7616, 0xc665)
	SWAP(mem[1], mem[2])
	BLOCK(0xfb0a, 0xfb6b, 0xafa, 0x4b3b, 0xb63, 0x32fb)
	SWAP(mem[1], mem[2])
	BLOCK(0x857d, 0xb585, 0x7d25, 0x9d85, 0xb199, 0x7d95)
	SWAP(mem[1], mem[2])
	BLOCK(0xbeda, 0xc2be, 0x92ce, 0xc2d8, 0xad85, 0x997d)
	SWAP(mem[1], mem[2])
	BLOCK(0x6d61, 0x5f49, 0xccbe, 0xcad6, 0xc2cc, 0xbec2)
	SWAP(mem[1], mem[2])
	BLOCK(0x6761, 0x6c66, 0x5f65, 0x6b61, 0x665f, 0x615f)
	LOADMEM(args[4])
	REQUIREMEM(52416, 34922, 5033, 1967, 4919)
	INITIAL(0x5b1d, 0x5c97, 0xdc1b, 0x5bd8)
	BLOCK(0x8eae, 0x4bee, 0xdad, 0xec6c, 0x6cae, 0x6bec)
	SWAP(mem[1], mem[2])
	BLOCK(0x5725, 0xf706, 0xd6f6, 0x3636, 0xe42e, 0x6cad)
	SWAP(mem[1], mem[2])
	BLOCK(0x92fb, 0x836b, 0x5735, 0xf672, 0x1736, 0x56c7)
	SWAP(mem[1], mem[2])
	BLOCK(0x7b1b, 0x1b2b, 0x9afb, 0x390b, 0x9b2b, 0x63ab)
	SWAP(mem[1], mem[2])
	BLOCK(0x8d8d, 0x95cd, 0x7d9c, 0x85cd, 0x95b1, 0xd5c9)
	SWAP(mem[1], mem[2])
	BLOCK(0xc6ca, 0xe6be, 0xce42, 0xe6ca, 0x7dc1, 0xb5bd)
	SWAP(mem[1], mem[2])
	BLOCK(0x6573, 0x5f67, 0xd8ea, 0xe4be, 0xe0da, 0xdec6)
	SWAP(mem[1], mem[2])
	BLOCK(0x2173, 0x656c, 0x7572, 0x5f70, 0x6d6f, 0x6363)
	LOADMEM(args[3])
	REQUIREMEM(45968, 47503, 4914, 18106, 4919)
	INITIAL(0xde1e, 0x1997, 0xdcda, 0x5a1d)
	BLOCK(0xf0c, 0xcbee, 0x6d2d, 0xe8b, 0xecae, 0x6e4c)
	SWAP(mem[1], mem[2])
	BLOCK(0x8665, 0xf736, 0x9687, 0x45f6, 0xadcd, 0x2d6f)
	SWAP(mem[1], mem[2])
	BLOCK(0x32fb, 0x9b4b, 0x5737, 0x2656, 0xe696, 0xb787)
	SWAP(mem[1], mem[2])
	BLOCK(0x43a2, 0xfb2b, 0x9b93, 0x2b73, 0x4b5b, 0xc3c3)
	SWAP(mem[1], mem[2])
	BLOCK(0xd17d, 0x95cd, 0xc995, 0xb9a5, 0xade1, 0xe199)
	SWAP(mem[1], mem[2])
	BLOCK(0xbeca, 0xe6e4, 0xcadc, 0xd2d6, 0x7dcd, 0xa5a1)
	SWAP(mem[1], mem[2])
	BLOCK(0x6573, 0x7265, 0xf0f0, 0xccbe, 0xe6d2, 0xd0e8)
	SWAP(mem[1], mem[2])
	BLOCK(0x6e69, 0x6b78, 0x7866, 0x5f73, 0x6968, 0x745f)
	LOADMEM(args[2])
	REQUIREMEM(39867, 15917, 15970, 37882, 4919)
	INITIAL(0x97de, 0x5c8d, 0xd7db, 0x8c17)
	BLOCK(0xef2e, 0x46eb, 0xedc6, 0xbec, 0xadad, 0xe86b)
	SWAP(mem[1], mem[2])
	BLOCK(0x9723, 0x75f6, 0xe305, 0xf656, 0xeecc, 0xae4b)
	SWAP(mem[1], mem[2])
	BLOCK(0x91ba, 0xfb71, 0xd6f4, 0x35f7, 0x6657, 0x25f7)
	SWAP(mem[1], mem[2])
	BLOCK(0x82fb, 0x2b6b, 0x7a1a, 0xfbb3, 0x2b92, 0xfbcb)
	SWAP(mem[1], mem[2])
	BLOCK(0x7d95, 0xb5bd, 0xd7d, 0xd995, 0xc97d, 0xe5c8)
	SWAP(mem[1], mem[2])
	BLOCK(0xcada, 0xde86, 0xbeec, 0xcae4, 0xdd7d, 0xb8c1)
	SWAP(mem[1], mem[2])
	BLOCK(0x6d6f, 0x435f, 0xbef2, 0xe46e, 0xbedc, 0x60be)
	SWAP(mem[1], mem[2])
	BLOCK(0x7665, 0x725f, 0x7972, 0x375f, 0x6e30, 0x5f65)
	LOADMEM(args[1])
	REQUIREMEM(44702, 45409, 6003, 2695, 4919)
	INITIAL(0x1997, 0xd95a, 0xd859, 0x97d8)
	BLOCK(0xcbec, 0xad6c, 0x2ccb, 0xec2b, 0xedac, 0x2be9)
	SWAP(mem[1], mem[2])
	BLOCK(0xf656, 0xb616, 0x65f6, 0x15f6, 0x2cec, 0x2d8c)
	SWAP(mem[1], mem[2])
	BLOCK(0x2b5b, 0xb32, 0xd615, 0xf496, 0x7616, 0xc665)
	SWAP(mem[1], mem[2])
	BLOCK(0xfb0a, 0xfb6b, 0xafa, 0x4b3b, 0xb63, 0x32fb)
	SWAP(mem[1], mem[2])
	BLOCK(0x857d, 0xb585, 0x7d25, 0x9d85, 0xb199, 0x7d95)
	SWAP(mem[1], mem[2])
	BLOCK(0xbeda, 0xc2be, 0x92ce, 0xc2d8, 0xad85, 0x997d)
	SWAP(mem[1], mem[2])
	BLOCK(0x6d61, 0x5f49, 0xccbe, 0xcad6, 0xc2cc, 0xbec2)
	SWAP(mem[1], mem[2])
	BLOCK(0x6761, 0x6c66, 0x5f65, 0x6b61, 0x665f, 0x615f)
	LOADMEM(args[0])
	
	for(int i=0;i<5;i++) printf("%llu\n", args[i]);
}