看雪.WiFi万能钥匙 CTF 2017第十题 点评及解题思路
看雪CTF 2017 比赛进行至第十题
截止至今天中午12点，第十题破解人数为 13 人！
防守方 hsadkhk 依然位居首位~，第十题作者位居第五位。
、
此题过后，风间仁依然处于第一位，lacoucou再次进入前十。
期待ing......
接下来我们来回顾一下第十题
看看 看雪评委和出题者是怎么说的ヾ(๑╹◡╹)ﾉ"。
看雪评委 netwind 点评
此题是一道算法为主的题目，需要攻方熟练掌握大数运算以及RSA算法。要解此题，首先要枚举e，然后再根据e、d、n求得p、q。
作者简介
看雪ID：海风月影
职业：老牌打酱油人员
联系方式：无
兴趣爱好：逛逛论坛，吹吹牛
特长：忽悠
研究方向：人工智能
看雪 CTF2017 第十题设计思路
参赛内容：Windows 64位系统 CrackMe
文件名：cm.exe
CRC32：13F73C04
MD5：31A4B4FF1ABFE9F0C9A11CF4E37C2B86
SHA-1：F38DE836BE531F436ACFD04100FFA52848FEFF15
设计思路
题目：RSA 密码学算法，穷举 e，快速分解 N
cm 运行流程：
输入全大写 70 个字符，前 6 个，后 64 个，分别为两个 16 进制大数:e, p
e、p 都是质数（Miller Rabin 测试算法）
初始化 N、D 两个大数，N 为 512 位
N=6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE94
1C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189
D=2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D3
81925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4Bp == 0 (mod N)，则设 q = N / p，p < q 验证D = ( - 1)( - 1) 上面全通过，完毕。
解题思路
N 是 512 位，分解 N = pq，e = D ( - 1)( - 1)，拼接 ep 完毕（如果是 768
以上的，目前就不能用这种方法了，为了放水。。。所以 N 设计成 512 位）
分解方法，使用 ggnfs 和 msieve 工具即可，这里不多说了。2 天内分解完，可能有点难度。
下面选取攻击者 lacoucou 的破解分析
1. PEID 扫描
又是大数运算，IDA打开：
F5，好直观：
查找字符串：
有 PEID 和上边的字符串信息可知，是用GMP实现的大数运算，接着就是猜每个函数的意义了。
由 MPN 的官方文档可知：
1. 所有对象使用前要初始化，通过调用函数 mpz_init来完成
2. 一般的函数，第一个参数为输出函数，后边的为输入参数
刚开始，使用的默认值来计算，进展缓慢，后来把mpn_set_str_140007990 处的大数改成0x10之后，进展飞快。
__int64 sub_140006F50(){ signed __int64 v0; // rax@1 __int64 v1; // r8@4 __int64 v2; // rdx@4 char v3; // cl@5 char v4; // al@9 int v5; // eax@14 const char *v6; // rcx@14 char v8; // [sp+20h] [bp-18h]@12 printf_140006EA0("=========================================================================\n"); printf_140006EA0(" 看雪CTF2017 CrackMe by 海风月影\n\n"); printf_140006EA0(" 请输入序列号："); scanf_140006F00("%s", &g_dwInput_140051F20); printf_140006EA0(&unk_14004BF30); v0 = -1i64; do ++v0; while ( *((_BYTE *)&g_dwInput_140051F20 + v0) ); if ( (_DWORD)v0 == 70 ) { v1 = 0i64; v2 = 0i64; while ( 1 ) { v3 = *((_BYTE *)&g_dwInput_140051F20 + v2); // 大写字母加数字 if ( (unsigned __int8)(v3 - 48) > 9u && (unsigned __int8)(v3 - 65) > 0x19u ) break; if ( ++v2 >= 70 ) { dword_140052F98 = g_dwInput_140051F20; word_140052F9C = word_140051F24; do { v4 = *((_BYTE *)&g_dwInput_140051F20 + v1 + 6); byte_140052F30[v1++] = v4; } while ( v4 ); // 初始化 mpn_set_str_140007990(&mpn_str_left_6_140051F10, &dword_140052F98, 16i64); mpn_set_str_140007990(&mpn_str_right_64_140052F20, byte_140052F30, 16i64); // 判断是否为质数 if ( mpz_probab_prime_p_140007350((__int64)&mpn_str_right_64_140052F20, 500u) ) { if ( mpz_probab_prime_p_140007350((__int64)&mpn_str_left_6_140051F10, 500u) ) { // 初始化 mpz_set_si_140007AD0(&unk_140051EF0, 0i64); mpn_set_str_140007990( &big_1, "6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE" "2E313E6218A57F9CCC8189", 16i64); mpn_set_str_140007990( &big_2, "2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69" "B26CB0320105A29651CB4B", |
完整函数如上，流程如下：
1.假设输入的字符串为szInput
2.首先判断szInput的长度是否为70个字节
1 2 3 4 5 | v0 = -1i64; do ++v0; while ( *((_BYTE *)&g_dwInput_140051F20 + v0) ); if ( (_DWORD)v0 == 70 ) |
3.接着判断这些字符是否由 0-9 和A-Z的字符组成：
1 2 3 4 | v3 = *((_BYTE *)&g_dwInput_140051F20 + v2); // 大写字母加数字 if ( (unsigned __int8)(v3 - 48) > 9u && (unsigned __int8)(v3 - 65) > 0x19u ) break; |
4.将输入字符串分成两段，第一段为原字符串的0-6自己，第二段为后64字节
dword_140052F98 = g_dwInput_140051F20; word_140052F9C = word_140051F24; do { v4 = *((_BYTE *)&g_dwInput_140051F20 + v1 + 6); byte_140052F30[v1++] = v4; } while ( v4 ); |
5.用这两个字符串来初始化两个mpz结构题：
1 2 3 | // 初始化 mpn_set_str_140007990(&mpn_str_left_6_140051F10, &dword_140052F98, 16i64); mpn_set_str_140007990(&mpn_str_right_64_140052F20, byte_140052F30, 16i64); |
结构体定义：
1 2 3 4 5 6 7 | typedef unsigned long mp_limb_tstruct __mpz_struct{int _mp_alloc; //申请的大小 _mp_alloc=申请字节数/8int _mp_size; //当前占用的大小 _mp_size=使用字节数/8mp_limb_t * _mp_d; //数据指针}; |
初始化前6个字符的例子：
内存中，rcx地址的值：
运行之后：
6. 判断是否为素数
1 2 3 | if ( mpz_probab_prime_p_140007350((__int64)&mpn_str_right_64_140052F20, 500u) ) { if ( mpz_probab_prime_p_140007350((__int64)&mpn_str_left_6_140051F10, 500u) ) |
这里花了点时间，后来通过连续测试0-0x10基本可以确定是判断素数。
跟官方文档似乎不太一样。
7. 初始化几个值
// 初始化 mpz_set_si_140007AD0(&unk_140051EF0, 0i64); mpn_set_str_140007990( &big_1, "6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE" "2E313E6218A57F9CCC8189", 16i64); mpn_set_str_140007990( &big_2, "2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69" "B26CB0320105A29651CB4B", 16i64); mpz_set_si_140007AD0(&v8, 0i64); |
8.用大数0x62..... 模上我们输入的64位然后与0比较：
1 2 | mpz_mod_140007B10((__int64)&v8, (__int64)&big_1, (__int64)&mpn_str_right_64_140052F20);if ( !mpz_cmp_si_1400075D0(&v8, 0i64) ) |
9.用大数0x62..... 除以我们输入的64位然后与商做比较，商大于我们输入的数：
1 2 | mpz_div_1400071E0(&unk_140051EF0, &big_1, &mpn_str_right_64_140052F20);if ( mpz_cmp_140007560(&mpn_str_right_64_140052F20, &unk_140051EF0) <= 0 ) |
10.最后一段，p=input[6:64] 商q=big_1/p v8=(p-1)(q-1)
mpn_sub_1400079F0(&mpn_str_right_64_140052F20, &mpn_str_right_64_140052F20, 1i64);mpn_sub_1400079F0(&unk_140051EF0, &unk_140051EF0, 1i64);mpn_mul_140007610(&v8, &mpn_str_right_64_140052F20, &unk_140051EF0);// 猜不出来sub_1400073B0((__int64)&v8, (__int64)&mpn_str_left_6_140051F10, (__int64)&v8); v5 = mpz_cmp_140007560(&big_2, &v8); v6 = "注册成功!!!\n\n"; if ( !v5 ) goto LABEL_16; |
有了以上信息，结合上一题的坑，基本猜到是RSA，不然还能有啥。。。。。。。。
RSA 算法：
RSA密钥生成步骤：
根据以上信息，以及计算过程：
1 2 3 4 5 6 7 8 | mpz_mod_140007B10((__int64)&v8, (__int64)&big_1, (__int64)&mpn_str_right_64_140052F20);if ( !mpz_cmp_si_1400075D0(&v8, 0i64) )mpz_div_1400071E0(&unk_140051EF0, &big_1, &mpn_str_right_64_140052F20);if ( mpz_cmp_140007560(&mpn_str_right_64_140052F20, &unk_140051EF0) <= 0 ){ mpn_sub_1400079F0(&mpn_str_right_64_140052F20, &mpn_str_right_64_140052F20, 1i64);mpn_sub_1400079F0(&unk_140051EF0, &unk_140051EF0, 1i64);mpn_mul_140007610(&v8, &mpn_str_right_64_140052F20, &unk_140051EF0); |
猜测：
1 2 3 4 | big_1即为Nbig_2可能是DN=0x6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189LD=0x2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B |
在线分解N，达到P，Q：
可知：
1 2 | p =64111581030502014729907148975807553274150008894301323553363399183151805372611q =80290597658186981463023471970341877717671071586519890660723213036500314978243 |
把P转成十六进制作为后64位，果然可以直接运行到：
1 2 3 | // 猜不出来 sub_1400073B0((__int64)&v8, (__int64)&mpn_str_left_6_140051F10, (__int64)&v8); v5 = mpz_cmp_140007560(&big_2, &v8); |
那么肯定是要根据以下公式求解E
1 2 3 4 5 | ed - 1 = kφ(n)e：不知道，待求d:私钥，似乎是big_2 0x 2476.....K：为整数φ(n)=(p-1)*(q-1) |
根据以上条件,写python，计算：
1 2 3 4 5 6 7 8 9 | def calc_e() ola_n=(p-1)*(q-1 for x in range(1,10000000): e=(ola_n*x+1)/big_num_2 if ola_n*x+1==big_num_2*e: #验证e是否为整数(是否舍弃了小数部分 10/3=3 3×3！=10) print e,hex(e)输出：16077491 0xf552b3L |
完整注册码：
F552B38DBDDE72E2E693B2AED5C769C0DCB3DA83534480A80E652FFE53544CD91A18C3
最后感谢 WiFi 万能钥匙安全应急响应中心的赞助支持，
接下来的比赛大家一定要使出洪荒之力哦！↖(^ω^)↗
比心 ❤
上海连尚网络科技有限公司成立于 2013 年，是一家专注于提供免费上网和内容服务的移动互联网企业。连尚网络自主研发的核心产品 WiFi 万能钥匙，以分享经济的模式，通过云计算和大数据技术，利用热点主人分享的闲置WiFi资源，为用户提供免费、稳定、安全的上网服务，以帮助更多的人上网，找到属于他们的机会，改变自己的命运。