2017腾讯游戏安全技术竞赛 Round 2 第一题详细题解

Ericky

前言

从第一题题目来看，感觉这次的题目都出得很灵活，主要考的是密码学这一块的东西。这道题目也不例外，由于不是科班出身，根本没有接触过密码学，那只能现学现卖，其中踩了不少坑，但是不要怕，我们可以慢慢爬出来再继续踩。初一看这道题后面的“双重保镖”很是霸气，很容易被吓跑，但是仔细认真做了之后会发现，Oh，hash碰撞也不是那么难的。好了，废话扯多了估计要被拉黑，我选择的依旧是安卓的题目，下面进入正题，我将此题分成两大部分，主要阐述这两大部分。
0x1 拉开帷幕

官方具体表演如下：

[Asm] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

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。
计算过程如下:

[Asm] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11

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[16 * j + k / 8] >> k % 8) & ((signed int)*( (unsigned char *) input + k / 8) >> (7 - k % 8) ) ) ^ tmp) & 1;     }     s[j/8] |= tmp << (7 - j % 8); }

实际上第一步要找出这段算法的逆运算。程序中有一个buffer，简算过后如下：

[Asm] 纯文本查看 复制代码

?

1

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[0]到x[127]，根据之前的运算，input将和x数组进行128次运算，每一次运算生成1bit，一共生成128个bit，即16字节，这16字节就是最后算出来的结果，也是需要比较的结果。

其实是一个128元1次的异或方程组，采用高数中的高斯消元法来求解，这个就算没有学过密码学也会，因为这就是高数中的内容啊，看到这个名字是不是很熟悉？对，就是矩阵化简！对于高数课逃课的同学，关于高斯消元法，给个链接：
https://en.wikipedia.org/wiki/Gaussian_elimination
这里已经非常详细

然后根据本题目的特征google一下就能搜到不少解该类方程组的模板，选取一个，代码如下：

[Asm] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

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[i][col])>abs(a[max_r][col]))                  max_r=i;          }          if(a[max_r][col]==0){              k--;              free_x[free_num++]=col;              continue;          }          if(max_r!=k){              for(int j=col;j<var+1;j++)                  swap(a[k][j],a[max_r][j]);          }          for(int i=k+1;i<equ;i++){              if(a[i][col]!=0){                  for(int j=col;j<var+1;j++)                      a[i][j]^=a[k][j];              }          }      }      for(int i=k;i<equ;i++)          if(a[i][col]!=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[i]=a[i][var];          for(int j=i+1;j<var;j++)              x[i]^=(a[i][j]&&x[j]);          printf("%d",x[i] );     }      return 0;  }

再根据IDA中看到的信息，确认正确答案的前面7字节是"GSLab17"，最后四字节是pid，编写代码如下：

[Asm] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

void * zapus_get(void *abc) {   int j,k,i;     int pid = getpid();     LOGI("pid:%d\n",pid );     unsigned char key[16]= "GSLab17";     unsigned char s[16] = {0};     key[7] = 0;     *((int *)key+2)  = 0;     *((int *)key+3)  = pid;     memset(a,0,sizeof(a));      memset(x,0,sizeof(x));      //***initial  zeng guang ju zhen     for ( j = 0; (unsigned int) j < 0x80; j++ )     {         for ( k = 0; (unsigned int) k < 0x80; ++k )         {             a[j][k] =  (((signed int)(unsigned char)buffer[16 * j + k / 8] >> k % 8) & 1);              }     }     for ( k = 0; (unsigned int) k < 0x80; ++k )     {         a[k][128] =((signed int)*( (unsigned char *) key + k / 8) >> (7 - k % 8) ) & 1;     }     k = Gauss();           for(int i=0;i<128;i++){              s[i/8] |= x[i] << (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 校验
标准算法没改动过：

[Asm] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10

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[count++]) & 0xFF ];     }     return( crc^0xFFFFFFFF ); }

单独改crc32是没问题的.
2.fnv_hash
标准算法没改动过

[Asm] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10

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[count++] ^ hash);     }     return hash; }

因为crc32的值是可以求出来的，再给个链接，其实这篇文章最早在看雪：
http://www.cnblogs.com/thinksea/articles/2024199.html
所以思路就变成了暴力碰撞fnvhash的值即可。
分析完了，写代码进行碰撞，关键代码：

[Asm] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

//8字节碰撞            unsigned char byte[4] ;     unsigned char byte2[4] ;     srand( (unsigned) time(NULL) * getpid());     long i =0;     while(1)     {                    byte[0]=rand()%256 + byte[1] ;         byte[1]=rand()%256 + byte[2];         byte[2]=rand()%256 + byte[3]; ;         byte[3]=rand()%256 + byte2[0]; ;         byte2[0]=rand()%256 + byte2[1];          byte2[1]=rand()%256 + byte2[2];          byte2[2]=rand()%256 + byte2[3] ;         byte2[3]=rand()%256 + byte[0] ;         *(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[0],byte[1],byte[2],byte[3]);             printf("%x %x %x %x\n", byte2[0],byte2[1],byte2[2],byte2[3]);             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[0],byte[1],byte[2],byte[3]);                 printf("%x %x %x %x\n", byte2[0],byte2[1],byte2[2],byte2[3]);                 printf("calc_fnvhash_op: 0x%X\n", fnvhash);                 break;             }                        }         i++;         if (i % 100000000 == 0)         {             printf("已经碰撞%ld次 继续努力\n", i);         }     }

优化后的crc32和fnvhash函数的计算，代码对比如下，这里的值只针对我自己的so进行的优化：

[Asm] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

//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[count++]) & 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[count++]) & 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[count++] ^ 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[count++] ^ hash);     }     return hash; }

这里再说明一下，一开始没有优化算法，导致计算缓慢（被卡了一波，标记，其实也不是没做出来的主要原因，自己挖了个坑，周末一直在挂机，没注意到错误，以为hash碰撞很难，但是过了很久没跑出结果就感觉不太对了，于是我就跟了一下，解决掉大坑，到达胜利光明顶），优化算法后效率提升了大概2100倍，大概1秒钟碰撞1E次，瞬间得出解。跑了大概半分钟，得出4个解（感觉任意指定hash都可以算，然后再感觉一天给任意hash1-2W个解也是没有压力的），如下给出四组附加bytes：

[Asm] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16

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

lelandyang

Ericky 发表于 2017-12-4 17:33
我记得我们上学的时候叫线性代数

有些学校学的是高等代数，对应线性代数，然后学的不是高等数学，而是对应的数学分析。

Ericky

lelandyang 发表于 2017-12-3 19:54
其实高斯消原是在高等代数里面学的～

我记得我们上学的时候叫线性代数

龍龖龘

膜拜大神

宁采成

表示看不懂，头疼。 膜拜大神

A-_虚伪_！

不是科班还这么厉害，那大佬你是什么专业的

ftmovie

牛牛牛牛牛牛

WellDingel

膜拜大佬

先有我后有天

膜拜大佬

shian1988

挺不错的比赛题目分析，感谢分享，来学习了。。

zjm0616

完全看不懂，，，，

无查灬

大牛