首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. CTF对抗
    3. 发新帖
[比赛]看雪.WiFi万能钥匙 CTF 2017第十题 点评及解题思路
发表于: 2017-6-28 18:29 2565

[比赛]看雪.WiFi万能钥匙 CTF 2017第十题 点评及解题思路

CCkicker 活跃值
2017-6-28 18:29
2565

看雪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 运行流程：

  1.  输入全大写 70 个字符，前 6 个，后 64 个，分别为两个 16 进制大数:e, p

  2.  e、p 都是质数（Miller Rabin 测试算法）

  3.  初始化 N、D 两个大数，N 为 512 位
    N=6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE94
    1C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189
    D=2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D3
    81925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B
  4. p == 0 (mod N)，则设 q = N / p，p < q
  5. 验证D = ( - 1)( - 1)
  6. 上面全通过，完毕。

解题思路

  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字节


1
2
3
4
5
6
7
8
  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_t
struct __mpz_struct
{
int _mp_alloc;     //申请的大小  _mp_alloc=申请字节数/8
int _mp_size;      //当前占用的大小  _mp_size=使用字节数/8
mp_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. 初始化几个值


1
2
3
4
5
6
7
8
9
10
11
12
13
            // 初始化
            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)

1
2
3
4
5
6
7
8
9
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即为N
big_2可能是D
N=0x6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189L
D=0x2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B

在线分解N，达到P，Q：

可知：

1
2
p =64111581030502014729907148975807553274150008894301323553363399183151805372611
q =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资源，为用户提供免费、稳定、安全的上网服务，以帮助更多的人上网，找到属于他们的机会，改变自己的命运。





[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

收藏
免费 ・0
支持
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//