作者Editor

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

发布于:2017-06-28 18:34:41 阅读:195 回帖:1


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



  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. 初始化几个值



            // 初始化
            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即为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 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资源,为用户提供免费、稳定、安全的上网服务,以帮助更多的人上网,找到属于他们的机会,改变自己的命运。



最新回复 (1)
wjllz 12小时前
1
哇  请问比赛什么时候结束呀
返回