2017腾讯游戏安全技术竞赛 Round 2 第一题详细题解
本帖最后由 Ericky 于 2017-12-1 20:49 编辑前言
从第一题题目来看，感觉这次的题目都出得很灵活，主要考的是密码学这一块的东西。这道题目也不例外，由于不是科班出身，根本没有接触过密码学，那只能现学现卖，其中踩了不少坑，但是不要怕，我们可以慢慢爬出来再继续踩。初一看这道题后面的“双重保镖”很是霸气，很容易被吓跑，但是仔细认真做了之后会发现，Oh，hash碰撞也不是那么难的。好了，废话扯多了估计要被拉黑，我选择的依旧是安卓的题目，下面进入正题，我将此题分成两大部分，主要阐述这两大部分。
0x1 拉开帷幕
官方具体表演如下：
v17 = 0;
v15 = "aLSG";
v16 = "71b";
v19 = 0;
v20 = 0;
v21 = 0;
v22 = 0;
v18 = getpid();
v0 = dlopen("/data/local/tmp/libZapus.so", 0);
v1 = v0;
if ( !v0 )
goto LABEL_18;
v2 = (void (__fastcall *)(int *))dlsym(v0, "zapus_get");
if ( !v2 )
goto LABEL_18;
v2(&v19);
dlclose(v1);
((void (__fastcall *)(int *))sub_F90)(&v19);
v3 = memcmp(&v19, &v15, 0x10u);
if ( v3 )
goto LABEL_18;
v4 = fopen("/data/local/tmp/libZapus.so", "rb");
v5 = v4;
if ( !v4 )
goto LABEL_18;
fseek(v4, 0, 2);
v6 = ftell(v5);
fseek(v5, 0, 0);
v7 = malloc(v6);
v8 = v7;
if ( !v7 )
1.判断指定路径有没有so，没有或者是打开失败就跪。
2.找zapus_get符号，符号表里没有就跪。
3.有了的话，把该函数初始化的指针带进到图中的sub_F90函数，然后开始计算。
4.小插曲，这里说一下这个题目第一次发的有一个bug，解密后的代码与固定两个字符串的指针进行了比较，导致每次对比的值是变的，我做到这里的时候怀疑了一下人生。what？比较的值还是变的？还不能改程序内存？在心中无限崩溃循环中还好官网出来及时修补了bug。
计算过程如下:
unsigned char input[] = "1234567890abcdef";
unsigned char tmp;
for ( j = 0; (unsigned int) j < 0x80; j++ )
{
tmp = 0;
for ( k = 0; (unsigned int) k < 0x80; ++k )
{
tmp = ((((signed int)(unsigned char)buffer >> k % 8) & ((signed int)*( (unsigned char *) input + k / 8) >> (7 - k % 8) ) ) ^ tmp) & 1;
}
s |= tmp << (7 - j % 8);
}
实际上第一步要找出这段算法的逆运算。程序中有一个buffer，简算过后如下：
unsigned char buffer[] ={0x44,0x88,0x7d,0x38,0x6d,0x08,0xae,0xba,0xbc,0x0e,0xf0,0xbf,0xd1,0xda,0x27,0x1e,0x21,0x8f,0x49,0xcb,0x4d,0x5d,0x3c,0x39,0x45,0x85,0x3e,0xdd,0x40,0x07,0x85,0x6c,0x51,0x67,0x78,0xb9,0xad,0xc8,0xa6,0xaf,0x97,0x5f,0xcd,0xb5,0xe1,0x35,0xc2,0x48,0x3f,0xad,0x6c,0x04,0x50,0xec,0xe3,0x2c,0x66,0xc1,0x04,0xf9,0x9c,0x43,0x02,0xd4,0x8e,0x09,0x41,0xb6,0x3c,0x75,0xce,0xec,0x1b,0x03,0xc6,0xb9,0x17,0x7f,0x38,0x0d,0x19,0xd9,0xa2,0x42,0xc8,0x6b,0x19,0xaa,0x2f,0x6a,0xae,0xfa,0xe0,0x6e,0x29,0x4c,0x8c,0x1e,0x1b,0x7d,0x9a,0x4c,0xb5,0x23,0x6b,0xcf,0x65,0x6c,0xe3,0x25,0xd4,0x67,0x08,0xf1,0x62,0x7b,0x10,0x8d,0xeb,0xd8,0x24,0xc9,0xc5,0x4f,0x04,0x75,0xcb,0xb5,0xb3,0xa4,0xd3,0x01,0xb4,0x78,0x70,0x82,0xad,0x52,0x72,0x59,0x95,0x30,0x47,0x0c,0x0b,0xf7,0xf4,0xde,0x3c,0xcc,0x82,0xf7,0x9f,0x6d,0x6b,0xe8,0x6c,0x07,0xaf,0x0c,0xe5,0xd3,0x09,0xb5,0xc5,0x4f,0xd6,0xee,0x0e,0x51,0x31,0xa5,0xbe,0x3c,0x52,0x45,0x31,0x97,0xa0,0xc2,0x0e,0xce,0xf5,0x7b,0xaa,0x21,0xbb,0xf9,0x2c,0x2b,0x37,0x1b,0x32,0x91,0xad,0xe8,0xd0,0xe3,0xbb,0xe2,0x2b,0xb9,0x37,0xc3,0xa8,0xec,0x6a,0xa7,0x13,0xbe,0xd5,0x62,0xa8,0x32,0x78,0xd0,0x82,0x08,0x2c,0xe4,0xf7,0xbf,0x92,0x87,0x2a,0x05,0xa6,0x05,0x4b,0x44,0x24,0xea,0xcf,0xf2,0x4b,0x49,0x54,0x2d,0x20,0xda,0x4d,0x28,0xe0,0x9c,0x26,0x1a,0xcd,0x26,0x97,0xf3,0x9f,0x9e,0xe6,0xdc,0xf1,0xd5,0x6e,0x64,0xb6,0x6f,0x57,0xff,0x10,0xc3,0x30,0x73,0xb7,0x91,0x77,0x46,0x22,0x5b,0x6d,0x6d,0xd1,0xef,0x0f,0xd3,0xee,0x73,0x71,0x99,0x2a,0xbf,0x77,0x92,0x78,0xf2,0xb0,0x31,0xb5,0x53,0x01,0x43,0xe5,0xcd,0x8e,0x88,0x3e,0x8d,0x46,0xa3,0x8d,0x82,0x1d,0x93,0x4f,0x49,0x4e,0xac,0x1f,0xde,0xb3,0xec,0x45,0x79,0x8e,0x7c,0xb6,0x40,0x8c,0x42,0x7b,0xee,0xc7,0x27,0x62,0x34,0xbb,0x54,0xd9,0x8e,0x67,0xeb,0x16,0x62,0x4a,0xa7,0x16,0xfd,0xe8,0x6e,0x2a,0x0c,0x93,0x4d,0x17,0xe0,0x45,0x8e,0x5f,0x5f,0x34,0x5d,0x72,0x28,0x24,0xc8,0x7d,0x9c,0x68,0x42,0x50,0x40,0x62,0x5b,0x8c,0x2c,0xd6,0x17,0x2a,0x34,0x75,0xd6,0x92,0xe6,0xfe,0xa7,0x81,0xc8,0x38,0x94,0x36,0xee,0x30,0x14,0x29,0x7c,0x21,0x45,0x8d,0xcb,0x3f,0x94,0xee,0x60,0x67,0x26,0xcb,0xa1,0x57,0x1d,0xd3,0xe5,0x93,0x15,0xae,0x7a,0xf1,0xe4,0x79,0x93,0x01,0x58,0x90,0xcd,0x42,0xb7,0xf4,0x3c,0xf3,0x09,0x57,0x3b,0xda,0x7a,0xe7,0xb8,0xae,0x87,0x34,0xc7,0xf2,0xe8,0xb6,0x4f,0xf7,0x5d,0x43,0xdd,0x7f,0xd2,0x11,0x29,0x5c,0xf0,0xdd,0x0f,0xe0,0xef,0xad,0x14,0x46,0x44,0x4f,0xb8,0x67,0x28,0xa2,0xb1,0x79,0x5c,0xd4,0xa0,0x76,0x21,0x67,0x8a,0x91,0x7c,0x69,0xf1,0x22,0x22,0x8e,0x14,0xa1,0x41,0x2c,0x54,0x1f,0x39,0x65,0x11,0xcd,0x60,0xff,0x8a,0x44,0x7d,0xc9,0x03,0x01,0xab,0xe2,0x1c,0xed,0x9e,0x2f,0xec,0xe0,0xee,0x92,0xdb,0x38,0xb8,0x9d,0xbb,0x5f,0x35,0x84,0x95,0x06,0xe6,0x2e,0x2a,0x99,0x52,0xcf,0x72,0xdb,0xf8,0x88,0x1f,0xd8,0x1f,0x41,0x63,0xa7,0xb7,0x65,0x3d,0x87,0x57,0x72,0x21,0x77,0xcd,0x7e,0xc8,0x05,0xf5,0xeb,0xc8,0xb7,0x1b,0x20,0x27,0x50,0x67,0xd8,0xed,0x07,0x00,0x87,0xa9,0x52,0x47,0x92,0x57,0x54,0x9f,0x29,0x84,0x69,0xe2,0xc9,0x91,0xf1,0x78,0xe7,0xc8,0xd3,0xaa,0x17,0x75,0xed,0xde,0x1f,0xc8,0x98,0xba,0xf8,0x8b,0x53,0x01,0x47,0x49,0x67,0xde,0xbf,0xb8,0xd6,0xa9,0xe9,0x1e,0xd3,0x05,0xa7,0xfa,0xa8,0x79,0x4a,0xb7,0x68,0x53,0xb2,0x60,0x05,0xbe,0x79,0xf6,0x44,0xd7,0x93,0xbb,0x8b,0xa2,0x1a,0xcd,0x46,0x23,0xdb,0xa2,0xf7,0xbd,0x48,0x52,0x1f,0x35,0xd2,0x23,0x8f,0x05,0x0b,0x94,0xc6,0x27,0xab,0xee,0x38,0x33,0x9f,0x9a,0xa5,0x6f,0x65,0x58,0xba,0xa2,0xe6,0x06,0x0f,0xb1,0x6f,0x39,0xdf,0x96,0x4f,0x4d,0x30,0xe0,0x78,0x5f,0x9c,0x87,0x88,0x11,0xe0,0x43,0x73,0x1d,0x71,0xb7,0xcc,0x0d,0xf9,0x47,0x62,0xb8,0xb5,0x94,0x27,0x08,0x77,0x8f,0xe4,0x03,0xb5,0xb2,0x0d,0xd8,0x13,0x10,0x69,0x34,0x4f,0xc8,0x87,0x7b,0x87,0xec,0x41,0x7c,0x06,0x62,0xd2,0xf7,0xc0,0x0f,0x65,0x44,0x28,0xd0,0xfb,0x93,0x16,0xb4,0x35,0x71,0x9d,0xa2,0xba,0x27,0x91,0x5f,0xd7,0x59,0x1b,0xd0,0x46,0xf2,0x7e,0x04,0x81,0x8a,0x56,0x71,0xc8,0x74,0x68,0xe9,0x2b,0x3f,0x2a,0x40,0xde,0x12,0xe4,0x62,0x06,0x81,0xe2,0xd3,0x00,0xa0,0xea,0xed,0xcb,0xd9,0x82,0xd8,0xc3,0x38,0xac,0x27,0x29,0xc8,0x62,0xad,0xaf,0xb6,0x4d,0xd9,0x01,0xae,0x26,0xc3,0x36,0x41,0xad,0x2d,0x6f,0xd4,0x3b,0xc8,0x70,0x1f,0x32,0x38,0x87,0xa4,0xea,0x48,0x66,0xf3,0x1e,0x22,0xaf,0x93,0xb5,0x34,0x3b,0xaa,0x41,0xbc,0x44,0x84,0x2c,0xd4,0xf2,0xa0,0x7c,0x60,0xad,0x64,0xe1,0x6f,0xb3,0xfe,0xc4,0xd3,0x4e,0x5f,0x73,0x7d,0xc9,0x72,0x9d,0xfc,0x00,0x60,0xec,0xe0,0x79,0xd0,0x04,0x1a,0x51,0xaa,0x40,0xc1,0x90,0x8e,0xbe,0xc2,0x65,0x25,0x57,0xd4,0x46,0x2f,0xfa,0x6f,0xc9,0xa5,0xa7,0x33,0x1a,0xe7,0x17,0x79,0xcf,0x18,0x2e,0x13,0x19,0x95,0x07,0x6a,0x45,0x51,0xa6,0x9c,0xf9,0x61,0xa0,0x63,0xc3,0x37,0x6e,0x5f,0x97,0xcb,0xea,0xa9,0x4b,0xac,0xab,0x17,0xcb,0x6f,0xfc,0xb8,0xc7,0xb3,0x8c,0x2b,0x09,0xef,0x57,0xac,0x03,0x6c,0x8f,0xd4,0x9f,0x65,0x34,0x5f,0xcd,0x6f,0x7d,0x37,0x1e,0x66,0x01,0xda,0x22,0x89,0x55,0x4e,0xf2,0xc9,0xf2,0x44,0x4b,0x23,0x3e,0x7c,0x3d,0xc8,0x32,0x5f,0xec,0xee,0x17,0x1a,0xfa,0xe6,0x97,0x82,0x0e,0xfe,0x35,0x4c,0x3c,0xc8,0x21,0x1e,0xa0,0x4b,0x26,0xdd,0x5a,0x39,0xce,0x6a,0xbc,0x7e,0x9f,0xd5,0x03,0xfb,0x6f,0x98,0x97,0xce,0x8b,0xec,0x60,0x93,0x33,0x27,0x19,0xbf,0xba,0xfb,0x3f,0xb8,0x04,0x92,0xec,0x5e,0xec,0x82,0x00,0x7e,0x1e,0xe6,0xae,0xac,0x51,0x5e,0x55,0x72,0x85,0x04,0xdd,0xeb,0x1c,0xe5,0x64,0x38,0xc4,0x24,0x51,0xaf,0xbe,0x47,0x16,0xfc,0xc2,0x97,0x84,0x11,0x24,0x5b,0x2f,0xaf,0xe6,0x89,0x32,0xe7,0xa4,0xda,0x1f,0x24,0x8b,0x6f,0xc6,0xc2,0x5d,0xa1,0x96,0x4f,0x04,0xb8,0xb2,0x97,0x17,0xf9,0x2e,0x4f,0x71,0x6d,0xd9,0x0c,0x3c,0xe5,0x7f,0xd0,0x62,0x91,0x35,0x84,0xc9,0x07,0xa3,0xfc,0xfc,0x46,0x2c,0x4a,0x02,0x6a,0x4c,0xe0,0xf3,0x32,0xe7,0xf7,0x0a,0x1a,0x4d,0x87,0xfe,0xc9,0xd9,0x89,0x74,0xf7,0x47,0xe3,0x93,0x6b,0x7b,0xfe,0x3a,0xd4,0x50,0x3a,0x3d,0x9f,0x32,0x1c,0x1d,0x2e,0x73,0x62,0x4e,0x49,0x55,0xe3,0x8a,0x2f,0xe9,0x1e,0x3b,0x6f,0xb2,0x15,0x40,0x1d,0xe9,0x29,0x7c,0x16,0x7c,0x49,0x5e,0x18,0xa2,0xbd,0x11,0x3a,0xc4,0x17,0xa2,0xc4,0xe7,0x8b,0x60,0x5a,0x0e,0x52,0x1a,0xc4,0x49,0xf9,0x83,0x41,0x6e,0x22,0x3f,0xf8,0x9a,0x38,0x64,0xe4,0xcc,0x9b,0xf9,0x67,0xf1,0x3b,0x63,0x4f,0x2e,0xe5,0x1e,0x77,0xb9,0x78,0xa2,0x7e,0x4f,0x31,0x47,0x79,0xe4,0x92,0x71,0x41,0xcd,0x3d,0x60,0x02,0x85,0x3d,0x63,0xd1,0xd5,0xb5,0x51,0xbe,0xaa,0xf8,0x38,0xdc,0xda,0xe5,0x29,0x3d,0x58,0x0d,0xd1,0xa2,0x61,0x83,0x89,0xfd,0x24,0x56,0x1b,0x39,0xc2,0x01,0x47,0xaf,0x34,0x66,0x57,0x4d,0x8d,0x85,0x7a,0x90,0x4b,0x2f,0xaf,0xd5,0x92,0x1c,0xcc,0x7e,0xdf,0xc4,0x7f,0xc1,0x9b,0x4f,0x90,0xf1,0x08,0x66,0x5c,0xec,0x85,0x48,0xbd,0x17,0xcd,0x5a,0x24,0x80,0xe7,0x57,0x29,0x4b,0x74,0x52,0xce,0xc5,0x31,0xd0,0xf3,0x22,0xfe,0x75,0x5c,0x5e,0x55,0xd7,0xed,0x11,0xd8,0xae,0x52,0x53,0x66,0x58,0xe1,0x2a,0x24,0xf8,0x51,0x48,0x9d,0x6e,0x24,0x94,0x6b,0xaa,0x80,0xd6,0x0d,0xe2,0x3a,0x12,0x83,0xa2,0x53,0x74,0x2b,0x64,0x27,0x2b,0x53,0xbf,0x1d,0x50,0x3d,0x51,0xf0,0x99,0x9a,0xc4,0xbd,0xd2,0x38,0x40,0xa6,0x38,0x30,0xcb,0xd5,0x03,0x99,0xa0,0x89,0x6d,0x52,0x70,0x5c,0x5a,0xb0,0x66,0xce,0x0c,0xa9,0xfb,0xd7,0xf0,0x86,0xc6,0x46,0xb7,0xcc,0x72,0x3d,0xcc,0xaf,0xdd,0x3c,0x2f,0xc6,0x77,0x6b,0x3e,0xfc,0x1d,0xb7,0x6d,0x9b,0x75,0x0c,0xea,0x6f,0x1b,0x96,0xf3,0xfd,0x36,0x46,0x77,0x09,0x10,0xef,0xf3,0x8d,0x54,0x51,0x92,0x33,0x67,0xc4,0x02,0xf5,0x40,0xed,0xfd,0x36,0x97,0x15,0x5b,0xec,0xb8,0xfc,0x29,0x4b,0x02,0x78,0x85,0x60,0x29,0x12,0x0e,0xe8,0x43,0x2b,0x23,0xca,0x5c,0x3f,0xb0,0x03,0x3d,0x56,0xba,0x1d,0x34,0x7c,0xbd,0x11,0x55,0x06,0xfa,0xd5,0xc5,0x80,0x28,0x2b,0x92,0x66,0x28,0x36,0xba,0xc6,0x3b,0x99,0x4e,0x82,0xd2,0xfe,0x44,0x6e,0x35,0x8a,0x3d,0xf9,0xd1,0xd1,0x8f,0x13,0x08,0xc1,0xfb,0xd8,0xc3,0x32,0x9b,0xc6,0x95,0xdd,0xef,0x5d,0xd2,0x0d,0xc4,0x7a,0xf7,0x1b,0xf2,0x69,0x7d,0x04,0x69,0x8f,0x04,0x83,0x79,0xd9,0x15,0x19,0x3c,0xae,0x0c,0xdd,0xc4,0x0d,0x81,0xed,0xef,0xfa,0x43,0x67,0xff,0xc8,0xa9,0x5f,0xfb,0xa5,0xb3,0xa0,0x64,0x03,0xe0,0x71,0x99,0x69,0xab,0x6d,0x46,0x65,0xc2,0xc2,0x58,0x43,0xc7,0x9c,0x4a,0x3a,0x8a,0x1a,0x1a,0xcb,0x6b,0x34,0x16,0x4f,0xdb,0xc4,0x5f,0xc4,0x2f,0x5e,0x06,0x03,0xaf,0xd2,0xe8,0x2b,0x56,0x23,0x8d,0xd3,0xf6,0xb5,0x71,0x00,0x8e,0x15,0x8d,0xbb,0xd3,0xbe,0x90,0x5c,0xee,0x9b,0xa7,0xfc,0x4d,0xa0,0x0d,0x71,0xb0,0x16,0xfa,0x03,0x36,0x14,0x4e,0xd2,0x4e,0xfb,0xed,0xd2,0x60,0x6d,0xaf,0xb0,0x7a,0x2c,0xf3,0x3f,0x87,0xf4,0xf7,0xc6,0xaa,0x6b,0xcf,0x95,0xca,0x47,0x8d,0x4d,0x9c,0xd6,0xc4,0x1c,0x62,0x18,0x77,0x1a,0x38,0xd4,0x37,0x95,0x45,0xcd,0xeb,0x08,0xc3,0xd7,0x29,0x31,0x25,0xc0,0x74,0xaf,0x2b,0x43,0x4c,0x50,0xf9,0x4b,0x75,0x2e,0x52,0xa8,0xbf,0x2f,0xa3,0xc2,0xc2,0x61,0xc7,0x11,0x7a,0xc4,0x32,0x04,0xcf,0x47,0x07,0xe8,0xa2,0x63,0x04,0xec,0x97,0x46,0xc1,0xd0,0x64,0x42,0xe6,0x52,0x22,0x44,0x14,0xe1,0x79,0xda,0x23,0xe0,0xbe,0x35,0x54,0x2c,0x95,0x6a,0x4c,0x0d,0x07,0xb4,0x42,0xbc,0x80,0xa1,0x11,0xde,0xbd,0x23,0x17,0x17,0x06,0xf0,0xd0,0x63,0x17,0xe5,0x9f,0x19,0x8f,0x32,0xf1,0x32,0x8f,0x8a,0x13,0xe3,0xf5,0xa0,0x26,0x2d,0x79,0x2a,0x57,0x02,0x85,0x20,0x63,0x21,0xa7,0xd1,0x8e,0x41,0x95,0xeb,0x99,0x3a,0x85,0x8a,0x4e,0x2a,0x4f,0xbf,0x9b,0xe1,0x85,0xda,0xa5,0x2e,0x1c,0x4f,0x15,0x37,0xae,0xdf,0x7f,0x8f,0x5b,0x6a,0x1a,0xd6,0xf3,0xb1,0xfc,0x34,0x14,0xa5,0x26,0x3a,0xad,0x45,0xca,0x94,0x62,0xdf,0x04,0xc2,0xab,0x6e,0x9b,0xe6,0x36,0x37,0xdc,0x17,0x11,0x69,0x88,0x75,0xe8,0x59,0x70,0x63,0x7b,0x8c,0x60,0x01,0x79,0x72,0x20,0xa0,0x4b,0x53,0x49,0xf9,0x71,0xe5,0x5f,0x7a,0x90,0xa6,0x1d,0xb8,0xab,0x23,0xf7,0xac,0x53,0x35,0x3a,0x00,0x31,0x0e,0x40,0x14,0x91,0x96,0x11,0xbf,0x93,0x5d,0x59,0x7c,0x73,0xe4,0xcc,0xa3,0xa9,0x4e,0x07,0x27,0xca,0xa1,0xc2,0x14,0x9f,0x1b,0xbe,0x06,0x72,0x5f,0x34,0x04,0x7e,0x1f,0x45,0x74,0x1a,0x02,0x94,0xde,0xf7,0x73,0x61,0x3a,0x59,0x22,0x67,0x8e,0xe5,0xd5,0x91,0xcd,0x03,0x22,0xd6,0x52,0xc8,0x3c,0xdc,0xf5,0x26,0x12,0xd0,0x32,0x3c,0x33,0xe7,0xdb,0x3e,0x8d,0xb6,0x06,0x1b,0x24,0x22,0xec,0x2a,0xcb,0xa8,0x07,0x39,0x31,0xfa,0x55,0x20,0x43,0x5d,0x30,0x4f,0x14,0xc9,0x8f,0x29,0x31,0xcf,0x47,0x90,0xd8,0xe2,0x90,0x5b,0x58,0x1a,0x04,0xfa,0xd0,0xf5,0xb5,0xa4,0x9a,0xc5,0x44,0x9f,0xad,0x65,0xbc,0x09,0xfd,0xcb,0xb6,0xc1,0xb8,0xe9,0x90,0xba,0x40,0xc7,0x46,0x1a,0x56,0x2e,0x4c,0x65,0x11,0xb9,0x91,0xab,0x08,0xff,0x3e,0x1a,0xc3,0x5a,0xc2,0x91,0xc0,0x2a,0xee,0x09,0xc5,0x81,0x26,0x30,0xc6,0xe4,0x5a,0x62,0x33,0xb3,0xd8,0xd4,0x22,0x98,0xaf,0x51,0x7c,0xc4,0x75,0x88,0x7a,0xf0,0xb1,0x19,0xd4,0x72,0x10,0x94,0x16,0x41,0x51,0xa9,0xab,0x9e,0x45,0xbe,0x59,0x65,0xb8,0xf0,0x60,0xec,0xe9,0xae,0x61,0xde,0xbb,0x29,0x35,0x3c,0xb4,0x01,0xa4,0x30,0xe5,0x7f,0x7b,0xe0,0x67,0xcc,0x06,0x8c,0xd9,0x77,0xed,0x2e,0x71,0x79,0x7b,0x1e,0x51,0x47,0x26,0x71,0xa9,0x3d,0xcc,0xa3,0x36,0x3c,0xf2,0xb9,0x74,0x39,0xbb,0x91,0x4a,0x8f,0x96,0x83,0xee,0xd7,0x63,0x8f,0xac,0x25,0x39,0x7e,0x6f,0xab};
程序将输入的16bytes(也就是128bit)，记为input，buffer的大小是2048bytes，分成了128个128bit，记为x到x，根据之前的运算，input将和x数组进行128次运算，每一次运算生成1bit，一共生成128个bit，即16字节，这16字节就是最后算出来的结果，也是需要比较的结果。
其实是一个128元1次的异或方程组，采用高数中的高斯消元法来求解，这个就算没有学过密码学也会，因为这就是高数中的内容啊，看到这个名字是不是很熟悉？对，就是矩阵化简！对于高数课逃课的同学，关于高斯消元法，给个链接：
https://en.wikipedia.org/wiki/Gaussian_elimination
这里已经非常详细
然后根据本题目的特征google一下就能搜到不少解该类方程组的模板，选取一个，代码如下：
int Gauss(){
int max_r,col,k;
free_num=0;
for(k=0,col=0;k<equ&&col<var;k++,col++){
max_r=k;
for(int i=k+1;i<equ;i++){
if(abs(a)>abs(a))
max_r=i;
}
if(a==0){
k--;
free_x=col;
continue;
}
if(max_r!=k){
for(int j=col;j<var+1;j++)
swap(a,a);
}
for(int i=k+1;i<equ;i++){
if(a!=0){
for(int j=col;j<var+1;j++)
a^=a;
}
}
}
for(int i=k;i<equ;i++)
if(a!=0)
return -1;//无解
printf("you jie k:%d var :%d \n",k,var);
if(k<var) return var-k;//解不唯一，返回解个数
//解唯一，生成解集
for(int i=var-1;i>=0;i--){
x=a;
for(int j=i+1;j<var;j++)
x^=(a&&x);
printf("%d",x );
}
return 0;
}
再根据IDA中看到的信息，确认正确答案的前面7字节是"GSLab17"，最后四字节是pid，编写代码如下：
void * zapus_get(void *abc)
{ int j,k,i;
int pid = getpid();
LOGI("pid:%d\n",pid );
unsigned char key= "GSLab17";
unsigned char s = {0};
key = 0;
*((int *)key+2)= 0;
*((int *)key+3)= pid;
memset(a,0,sizeof(a));
memset(x,0,sizeof(x));
//***initialzeng guang ju zhen
for ( j = 0; (unsigned int) j < 0x80; j++ )
{
for ( k = 0; (unsigned int) k < 0x80; ++k )
{
a =(((signed int)(unsigned char)buffer >> k % 8) & 1);
}
}
for ( k = 0; (unsigned int) k < 0x80; ++k )
{
a =((signed int)*( (unsigned char *) key + k / 8) >> (7 - k % 8) ) & 1;
}
k = Gauss();
for(int i=0;i<128;i++){
s |= x << (7 - i % 8);
}
LOGI("HELLO I'm here.");
memcpy(abc, s, 16);
}
再调试看看结果，自己挖了什么坑自己填填坑，即可过第一关，进入下一关。
0x2 孪生兄弟
接下来来到孪生兄弟把守的最后大关，只要越过这道防线，就可以飞向光明顶。
之所以说它是孪生兄弟，是因为它对程序进行了hash值的校验，而且是两种校验，两个校验值都必须值为0x614C5347，其实就是“GSLa”。
什么是hash函数？
Hash函数H将可变长度的数据M作为输入，产生固定长度的Hash值h。
Hash函数，哈希函数，散列函数，杂凑函数它们说的都是同一个含义，后续我们都称之为Hash函数。
定义
Hash函数H将可变长度的数据M作为输入，产生固定长度的Hash值h。
Hash函数，哈希函数，散列函数，杂凑函数它们说的都是同一个含义，后续我们都称之为Hash函数。
h=H(M)
单向性
给定输入M，通过函数H可以很容易计算出输出h；但如果给定h，则找到M在计算上不可行。
数据完整性
输入数据M中任何1个bit发生变化，都将导致输出M发生很大的变化。
Hash冲突（突破本题的关键）
在Hash函数中，M称之为h原像,，因为H函数是一个多对一的映射,，对于任意给定的Hash数值h,，可能会有多个原像,，如果满足如下条件, 则称之为发生了哈希碰撞，也就是哈希冲突。
x!=yandH(x)==H(y)
一个优良的Hash函数必须满足如下几个性质:
任意y，找x，使得H(x) = y，非常困难
给定x1, 找x2, 使得H(x1) == H(x2), 非常困难
找任意的x1, x2, 使得H(x1) == H(x2), 非常困难
这里感觉本题是第一条或者第二条，如果是第三条的话（可惜本题并不是），可以参考生日定理来解题，这里放个链接：
https://en.wikipedia.org/wiki/Birthday_problem
介绍完基本概念，言归正传，本题用的两个校验是crc32校验和fnvhash函数校验，这里再给两个链接：
crc32：http://blog.csdn.net/zhaodm/article/details/3711034
fnvhash：http://blog.csdn.net/taochenchang/article/details/7319739
通过分析代码可以得到：
1.crc32 校验
标准算法没改动过：
unsigned long calc_crc(unsigned char *p, unsigned int len)
{
register unsigned long crc;
unsigned int count=0;
crc = 0xFFFFFFFF;
while (count < len){
crc = (crc>>8) ^ crc_table[ (crc^p) & 0xFF ];
}
return( crc^0xFFFFFFFF );
}
单独改crc32是没问题的.
2.fnv_hash
标准算法没改动过
unsigned long calc_fnvhash(unsigned char *p, unsigned int len)
{
register unsigned long hash;
unsigned int count=0;
hash = 0x811C9DC5;
while (count < len){
hash = 0x1000193 * (p ^ hash);
}
return hash;
}
因为crc32的值是可以求出来的，再给个链接，其实这篇文章最早在看雪：
http://www.cnblogs.com/thinksea/articles/2024199.html
所以思路就变成了暴力碰撞fnvhash的值即可。
分析完了，写代码进行碰撞，关键代码：
//8字节碰撞
unsigned char byte ;
unsigned char byte2 ;
srand( (unsigned) time(NULL) * getpid());
long i =0;
while(1)
{
byte=rand()%256 + byte ;
byte=rand()%256 + byte;
byte=rand()%256 + byte; ;
byte=rand()%256 + byte2; ;
byte2=rand()%256 + byte2;
byte2=rand()%256 + byte2;
byte2=rand()%256 + byte2;
byte2=rand()%256 + byte ;
*(unsigned int*)(filemap+offset -4) = *(unsigned int*)byte;
*(unsigned int*)(filemap+offset -8) = *(unsigned int*)byte2;
tweakcrc(filemap, filestat.st_size, crc, offset); //修改crc32 值为固定值
fnvhash=calc_fnvhash_op(filemap+filestat.st_size -12, 12);
if (fnvhash>= 0x614C5340 && fnvhash <= 0x614C5349)
{
printf("$$$$$$$$$$$$$$near success $$$$$$$$$$$$$\n");
printf("%x %x %x %x\n", byte,byte,byte,byte);
printf("%x %x %x %x\n", byte2,byte2,byte2,byte2);
printf("calc_fnvhash_op: 0x%X\n", fnvhash);
printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");
if (fnvhash == 0x614C5347)
{
printf("********************************\n");
printf("**************success***********\n");
printf("********************************\n");
printf("%x %x %x %x\n", byte,byte,byte,byte);
printf("%x %x %x %x\n", byte2,byte2,byte2,byte2);
printf("calc_fnvhash_op: 0x%X\n", fnvhash);
break;
}
}
i++;
if (i % 100000000 == 0)
{
printf("已经碰撞%ld次 继续努力\n", i);
}
}
优化后的crc32和fnvhash函数的计算，代码对比如下，这里的值只针对我自己的so进行的优化：
//crc
unsigned long calc_crc(char *p, unsigned int len)
{
register unsigned long crc;
unsigned int count=0;
crc = 0xFFFFFFFF;
while (count < len){
crc = (crc>>8) ^ crc_table[ (crc^p) & 0xFF ];
}
return( crc^0xFFFFFFFF );
}
unsigned long calc_crc_op(char *p, unsigned int len)
{
register unsigned long crc;
unsigned int count=0;
crc = 0x81820a5b;
while (count < len){
crc = (crc>>8) ^ crc_table[ (crc^p) & 0xFF ];
}
return( crc^0xFFFFFFFF );
}
//fnvhash
unsigned long calc_fnvhash(unsigned char *p, unsigned int len)
{
register unsigned long hash;
unsigned int count=0;
hash = 0x811C9DC5;
while (count < len){
hash = 0x1000193 * (p ^ hash);
}
return hash;
}
unsigned long calc_fnvhash_op(unsigned char *p, unsigned int len)
{
register unsigned long hash;
unsigned int count=0;
hash = 0x799362BC;
while (count < len){
hash = 0x1000193 * (p ^ hash);
}
return hash;
}
这里再说明一下，一开始没有优化算法，导致计算缓慢（被卡了一波，标记，其实也不是没做出来的主要原因，自己挖了个坑，周末一直在挂机，没注意到错误，以为hash碰撞很难，但是过了很久没跑出结果就感觉不太对了，于是我就跟了一下，解决掉大坑，到达胜利光明顶），优化算法后效率提升了大概2100倍，大概1秒钟碰撞1E次，瞬间得出解。跑了大概半分钟，得出4个解（感觉任意指定hash都可以算，然后再感觉一天给任意hash1-2W个解也是没有压力的），如下给出四组附加bytes：
1.
9a 14 7 99
56 8c 8 1f
calc_fnvhash_op: 0x614C5347
2.
84 1e 16 23
92 18 3c 34
calc_fnvhash_op: 0x614C5347
3.
5a f5 69 0
a0 d1 39 29
calc_fnvhash_op: 0x614C5347
4.
28 f0 98 98
a1 82 b0 e7
calc_fnvhash_op: 0x614C5347
经过此役，发现hash碰撞很有趣，做题使人快速学习新东西，复习老东西。
谢谢观看，不足之处请看官斧正！
2017.7.15
By Ericky Ericky 发表于 2017-12-4 17:33
我记得我们上学的时候叫线性代数
有些学校学的是高等代数，对应线性代数，然后学的不是高等数学，而是对应的数学分析。 lelandyang 发表于 2017-12-3 19:54
其实高斯消原是在高等代数里面学的～
我记得我们上学的时候叫线性代数 膜拜大神{:301_975:} 表示看不懂，头疼。 膜拜大神 不是科班还这么厉害，那大佬你是什么专业的 牛牛牛牛牛牛 膜拜大佬 膜拜大佬 挺不错的比赛题目分析，感谢分享，来学习了。。{:17_1070:} 完全看不懂，，，， {:301_993:}大牛