首页
社区
课程
招聘
[原创]看雪.Wifi万能钥匙 CTF 2017 第10题Writeup
2017-6-20 21:38 3430

[原创]看雪.Wifi万能钥匙 CTF 2017 第10题Writeup

2017-6-20 21:38
3430


程序是静态编译的,全是黑函数。看了下入口call,jmp应该是VC写的,但是多了个push pop的过程。

查看字符串,发现了ctf2017,附近还有注册成功之类的,定位到关键算法所在,在字符串中还发现了GNU MP: Cannot allocate memory之类,经查为gmp计算库。

 其实本来由于前面精力用太多,感觉很累,想放了这题的,看了个开头就没看了。准备试试ida的符号加载,去掉一些黑函数,下载编译了个gmp,试了一晚上也没有成功。 

后来又想看题了,就对照gmp的源码,把部分函数比对了下,如下

printf_140006EA0("=========================================================================\n");  
printf_140006EA0("                     看雪CTF2017 CrackMe by 海风月影\n\n");  
printf_140006EA0("    请输入序列号:");  
scanf_140006F00("%s", &input_140051F20);  
printf_140006EA0("\n\n");
  v0 = -1i64;  
  do
    ++v0;  
  while ( *((_BYTE *)&input_140051F20 + v0) );  
  if ( (_DWORD)v0 == 70 )
  {
    v1 = 0i64;
    v2 = 0i64;    while ( 1 )
    {
      v3 = *((_BYTE *)&input_140051F20 + v2);      
      if ( (unsigned __int8)(v3 - 0x30) > 9u && (unsigned __int8)(v3 - 0x41) > 0x19u )// >9 >Z
        break;      
      if ( ++v2 >= 70 )
      {
        dword_140052F98 = input_140051F20;
        word_140052F9C = word_140051F24;        
        do
        {
          v4 = *((_BYTE *)&input_140051F20 + v1 + 6);
          Src[v1++] = v4;                       // 输入的后64位
        }while ( v4 );        
        mpz_set_str_140007990(&stru_140051F10, &dword_140052F98, 0x10ui64);// 输入前6以16进制转成数字
        mpz_set_str_140007990(&stru_140052F20, Src, 0x10ui64);// 输入后64 以16进制转成数字
        if ( mpz_prime_140007350((__int64)&stru_140052F20, 0x1F4u) )
        {          
        if ( mpz_prime_140007350((__int64)&stru_140051F10, 0x1F4u) )
          {            
              mpz_init_140007AD0(&stru_140051EF0, 0i64);            
              mpz_set_str_140007990(
              &stru_140051EE0,  "6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE"
              "2E313E6218A57F9CCC8189",
              0x10ui64);            
              mpz_set_str_140007990(
              &stru_140051F00, "2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69"
              "B26CB0320105A29651CB4B",
              0x10ui64);            
              mpz_init_140007AD0(&a2, 0i64);            
              mpz_mod_140007B10(&a2, &stru_140051EE0, &stru_140052F20);            
              if ( !(unsigned int)mpz_cmp_ui_____1400075D0(&a2, 0i64) )
              {              
                 mpz_div_1400071E0(&stru_140051EF0, &stru_140051EE0, &stru_140052F20);              
                 if ( (signed int)mpz_cmp_140007560(&stru_140052F20, &stru_140051EF0) <= 0 )// a1<=a2
                  {                
                     mpz_sub_1400079F0(&stru_140052F20, &stru_140052F20, 1ui64);                
                     mpz_sub_1400079F0(&stru_140051EF0, &stru_140051EF0, 1ui64);                
                     mpz_mul_140007610(&a2, &stru_140052F20, &stru_140051EF0);                
                     mpz_invert_1400073B0(&a2, &stru_140051F10, &a2);
                     v5 = mpz_cmp_140007560(&stru_140051F00, &a2);// 校验
                     v6 = "注册成功!!!\n\n";                
                     if ( !v5 )
                      goto LABEL_16;
              }
            }
          }
        }        
        break;
      }
    }
  }
  v6 = "注册失败\n\n";
LABEL_16:  
  printf_140006EA0(v6);  
  sub_14002D1B4("pause");  
  return 0i64;

先检查输入长度为70,再检查大于`Z``的字符为70。

然后把输入分别6byte和64byte两部分,按16进制字符转成数字,并检查其为素数,再进行一些算术运算,最近与常量数字比较。 

从整体看是RSA的密钥生成过程。计输入的两部分分别为e,p,记代码中的常量分别为n,d。则计算过得是这样的:

q=n/p
N = (p-1)*(q-1)
d1 = invert(e,N)
d1 == d?

其中的invert是求模反元素的函数调用。

看完到这,直接将n去数据库里查,没有结果。又拿出yafu分解了两个小时没有结果。果断停了,开始想办法爆破,试了几次都不理想。又整理下公式及思路。

n = pq
N = (p-1)(q-1)
ed = 1(mod N)

那么,

ed -1 = kN (k为整数) 
kN = k(p-1)(q-1) 
kN/n = k(p-1)(q-1)/n = k(pq-p-q+1)/(pq) 
kN/n = k(1-1/p-1/q+1/(pq))

上面两条/为带小数的除法

由于p,q很大,1-1/p-1/q+1/(pq)无限接近于1,kN/n无限接近于k,那么,

(ed-1)/n = k1 此处为整除

则k1 = k-1 ,所以

(ed-1)/(k1+1) = N = pq-p-q+1
(ed-1)/(k1+1)-n = 1-p-q 
p+q = 1-(ed-1)/(k1+1)+n

再结合pq=n,就可以由这个二元一次方程求出p,q。所以解题思路就出来了,爆破e,如果(ed-1)%(k1+1)==0,则e为可能解,再由于n为512bit,p和q应该比较接近(p为256bit,q也应该为256bit左右),限制p+q 为264bit以下,代码如下:

# -*- condig = utf-8 -*-
# author: poyoten @ ChaMd5安全团队
import gmpy2
n = gmpy2.mpz(0x6248BC3AB92A33B000FDB88568F19727F92F79EB68FF6AD73203EFD20A3E331BE941C7AA288095F33BC4B255FD983114D480EFFBEE2E313E6218A57F9CCC8189)
d = gmpy2.mpz(0x2476A7F02588913F228923E1F36F963F29708C07B117396817A6B94C336FC77FF7D381925EB40CFED8FBE894570155E41569B4EC69B26CB0320105A29651CB4B)
e = gmpy2.mpz(0x100000)
while True:
    e = gmpy2.next_prime(e) 
    m = gmpy2.mul(e,d)-1
    count = gmpy2.div(m,n)
    if m%(count+1) == 0:        
        r = 1-m/(count+1)+n
        if r<0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff:
             print 'e = '+hex(e)+' ; p+q = '+hex(r)

不到一分钟出了一个结果:

e = 0xf552b3 
p+q = 0x13f40bc9da5c21ae87dd77a150d9feca2b17b4a84db1108fe9d4dda6a9c7d9086

用matlab解算出p,q,因为题目中限制了p<=q,取小值为p:

p = 64111581030502014729907148975807553274150008894301323553363399183151805372611
q = 80290597658186981463023471970341877717671071586519890660723213036500314978243

转成16进制,与e拼接,再转成大写(题目中有字符检查),结果为:

F552B38DBDDE72E2E693B2AED5C769C0DCB3DA83534480A80E652FFE53544CD91A18C3



[培训]科锐软件逆向50期预科班报名即将截止,速来!!! 50期正式班报名火爆招生中!!!

收藏
免费 1
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回