首页
论坛
课程
招聘
[原创] CTF2019 Q3 readyu crackme 第十三题:大圣归来 题目与设计思路
2019-8-27 00:00 6585

[原创] CTF2019 Q3 readyu crackme 第十三题:大圣归来 题目与设计思路

2019-8-27 00:00
6585
[原创] CTF2019 Q3 readyu crackme 设计思路

密码学题目, VC++6编译的Win32程序。取名“完璧归赵”。

(1) 序列号
这个程序默认只有一个SN,用户名内置为username。输入正确的SN提示good,错误的SN提示bad。

本题唯一序列号SN为:
usernameKXCTFXXXX753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83

就方程本身而言,每个name有1个key。格式为 ( || 表示字符串相加 ):
key = name || KXCTFXXXX || M0

彩蛋(额外赠送的)进入方式:
(a) SN验证通过,再点击2下,可进入解锁模式,可针对不同的用户名验证SN。
(b) 输入11个字符,点击check: ////debugme

(2) 方程缘由

某一段时间,我在考虑一个问题, 一个msg分成几段, 每段取hash,然后经过某种运算,能否和整体的hash相等?
也就是 F(hash(a) ,hash(b)) = hash(a|b) , F是某种抽象运算。

经过分析,答案是肯定的,这样的模型存在。本题“完璧归赵”就是这个意思,也可以叫 “合二为一”。

本题方程是一个高度抽象的模同余方程, 题目验证:
{ V_e2 [ V_e1(M0 + h1) + h2 ]  +  h4 } = h3   mod N   ... (a)

解法:对方程a 做逆运算即可得到M0 , 即 方程b :
M0 = { V_d1 [ V_d2 (h3 - h4) - h2 ]  - h1  }  mod N   ... (b)

给定 h1,h2,h3,h4,e1,e2 。 h是hash, e是公钥指数, N是模。
求M0, 1 < M0 < N, 使得此方程成立,且M0唯一。

在本题中, V_e(m) mod N是Lucas序列函数的V序列, 或者简写为 Lucas V_e(m,1) mod N 。
参考luc公钥系统, 对公钥e有非对称解d, 可以求逆 (V可类比RSA的幂模运算)。
从而,这道题就可以求解了。具体求解代码,参见附件keygen的cpp源代码。 

说明: 公开的论文认为luc强度与RSA相当,至少不弱于RSA。
但是luc计算速度要慢于RSA。 Lucas序列采用迭代算法,比RSA的快速幂模运算步骤要多,速度慢了不止一倍。所以实际上应用并不多。

Lucas序列有一些有趣的性质。参见(5)参考文档,或者wiki:
https://en.wikipedia.org/wiki/Lucas_sequence 

(3) 题目的参数设置:
3.1 参数
luc(m,e,N) = V_e(m, 1) mod N
head = "PEDIY_CTF2019_Q3_完璧归赵_Crackme_Readyu_"
name = "username"
body = head || name = "PEDIY_CTF2019_Q3_完璧归赵_Crackme_Readyu_username"
tail = "完璧归赵"

h1 = hash(head)
h2 = hash(name)
h3 = hash(body)
h4 = hash(tail)
hash取sha160,

h1 = 9071232e6b170092668255303e5d824f2879ad56
h2 = 249ba36000029bbe97499c03db5a9001f6b734ec
h3 = c4b73cb0dd1d750c69e1755b06bbaffff44d2600
h4 = 6dc844c73b34d6e6b8de48da64ef92ab2b11f461

N = sha-256("完璧归赵完璧归赵") = sha256(CDEAE8B5B9E9D5D4CDEAE8B5B9E9D5D4)
3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01

N只有256bit,因子分解大概1到2分钟,N=P1*P2*P3, 有三个不同的素因子:
P1:1F7BF
P2:F1059E73CFB296F8B
P3:2267D9CC91A552E23D284260B563CE490B0F7475F9D

e1 = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133
也就是 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF (20 bytes)  ||  4B5843544631395133 ("KXCTF19Q3" the HEX mode, 9 bytes)
e2 = N

3.2 验证过程

第1步,计算
m2 = luc(m0+h1, e1, N) , luc是lucas函数。

程序里采用了先分割,然后合并的算法, 使得分析的难度加大了。

e1被切分为H,K, e1=H+K , H是某个hash,其实就是相当于一个伪随机数,H的值不重要。
因为后面会合并得到e1。

V_m1h, U_m1h = lucas u,v (m0+h1, H, N)
V_m1k, U_m1k = lucas u,v (m0+h1, K, N)
 
利用公式合并 e1,  
V_i+j = (V_i * V_j + D * U_i * U_j ) / 2, 其中 D = (m^2 - 4) mod N 是 lucas(m,1) mod N的判别式。

m1 = luc(m0 + h1, e1, N) =  (Vm1h * Vm1k + D *Um1h * Um1k) /2

第2步, 计算
m2 = luc(m1+h2, e2, N)  ,程序里实际计算 luc_vp(m1+h2, e2+1, N) , 等价于  luc(m1+h2, e2, N)  。

第3步, 计算
m3 = (m2 + h4)  mod N
验证下式,成立则m0正确。
m3  ==  h3  ,

3.3 求解方法:

以下lcm是最小公倍数。

参照RSA, RSA的最小phi函数 为卡迈克尔函数 lcm(p-1,q-1) , 计算方便可取的phi函数为 欧拉函数(p-1)*(q-1) ,
后者是前者的整数倍。

lucas的phi函数可以写作
lcm(P-(Dp/P), Q-(Dq/Q)) 
(Dp/P) , (Dq/Q) ,  "()"是勒让德符号, 取值0, -1,+1。
Dp = (m^2 - 4) mod P ,   Dq = (m^2 - 4) mod Q  是 lucas(m,1) , 分别 mod P , mod Q 的判别式。 
一般地, 加密消息一则消息m, 由于 p, q 是较大素数,   (m^2 - 4) 与p互素, 与q互素, 
要么是二次剩余,要么是非二次剩余, 符号 只取到-1,+1。

简单地,可直接取最大集合:
phi = (p-1)*(p+1)*(q-1)*(q+1)

N有3个素因子, N=p*q*r,即推广为
phi = lcm(p - 1,p + 1, q - 1, q + 1, r - 1, r + 1)
或者简单地
phi = (p-1)*(p+1)*(q-1)*(q+1)*(r-1)*(r+1)

比如:
phi = lcm(p1 - 1,p1 + 1,p2 - 1, p2 + 1,p3 - 1,p3 + 1)
phi = B492D4C14E9A74E225EC3FB39BD17C830072E04732255C87C350F579D51C03F8C130961AAD6C619EE804787627F4F2A31D71C1FA69474C51F1A1889DC8C0

e1= FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133
e2= N = 3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01
d1 = 1/e1 mod phi
d2 = 1/e2  mod phi

d1=
39027AEBF5B3D358B0075506CC37DF00393C5F191AA71B216F6F716A952206A55D9D3F81430FAE5E69E35AC4A58A98C51F472F18F347FBC300E0376DDBFB

d2=
8C7A26B58368185B65B10D3C6E9C0A6DEDAB758D3895F618A884127DCD5390470F2686B7F1771AFBE373E05DA70E382EE5DD75E71FFE1EE5BB1D63CC3CC1

按如下方程计算M0:
M0 = { V_d1 [ V_d2 (h3 - h4) - h2 ]  - h1  }   mod N

最后得到
M0=753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83

从而
key=
usernameKXCTFXXXX753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83

(4)彩蛋:

如果进入彩蛋模式,额外赠送 ,可解锁用户名。
比如用户名:
name:
蔺相如
key:
蔺相如KXCTFXXXX19058E03B6FB04AAF15BD316B42B03D6D0769296F215E6604362CAA1F55036C2

(5)参考文档, 见附件打包下载。

文档:
lucas_paper.rar
代码:
keygenme2019q3_keygen.rar

lucas_paper.rar  包含如下部分文档:
wiki:
https://en.wikipedia.org/wiki/Lucas_sequence
LUC is a public-key cryptosystem based on Lucas sequences that
implements the analogs of ElGamal (LUCELG), Diffie-Hellman (LUCDIF), and RSA (LUCRSA).

cryptopp:
https://www.cryptopp.com/wiki/LUC_Cryptography

paper:
https://www.semanticscholar.org/paper/LUC%3A-A-New-Public-Key-System-Smith-Lennon/0ecfdb388bffbd623e536de70aee9ff811317cbc
LUC: A New Public Key System
Peter J. Smith, Michael J. J. LennonPublished in SEC 1993

中文文档:
Lucas公钥密码体制及其安全性.pdf
Lucas公钥密码体制及其性能公析.pdf



[公告]春风十里不如你,看雪团队诚邀你的加入!

最后于 2019-9-25 14:18 被readyu编辑 ,原因:
上传的附件:
收藏
点赞1
打赏
分享
最新回复 (7)
雪    币: 11624
活跃值: 活跃值 (270)
能力值: ( LV12,RANK:779 )
在线值:
发帖
回帖
粉丝
readyu 活跃值 12 2019-8-27 09:41
2
0
crackme_CTF19Q3_132K.exe

Size: 135168 bytes

MD5: 47A01296CF25832D67B43256DDC88B40
SHA1: 996B335E5EACFE381A53C252F8E3C5B499A51829
CRC32: 7B9CE11F

最后于 2019-8-31 23:11 被readyu编辑 ,原因:
雪    币: 11624
活跃值: 活跃值 (270)
能力值: ( LV12,RANK:779 )
在线值:
发帖
回帖
粉丝
readyu 活跃值 12 2019-9-1 08:10
3
0
keygen和crackme都更新了。
雪    币: 11624
活跃值: 活跃值 (270)
能力值: ( LV12,RANK:779 )
在线值:
发帖
回帖
粉丝
readyu 活跃值 12 2019-9-25 10:44
4
0
/*
KANXUE/PEDIY KCTF2019Q3  crackme's keygen
by Readyu @201908

based on: Lucas pubkey system
*/
#include <Windows.h>
#include "big.h"
#include "sha1.h"

#ifdef __cplusplus
extern "C" {
#endif    
#include "miracl.h"
#pragma comment( lib, "miracl531.lib" )
#ifdef __cplusplus
}
#endif

using namespace std;

Big lcm( const Big &X , const Big &Y )
{
  Big g = X/gcd(X, Y);
  g *= Y;
  return g;
}

string  calc_sn(string head, string name, string kxctf, bool uselcm)
{
    Miracl precision(1024, 2);     /* include MIRACL system */
    mr_mip->IOBASE=16;

    unsigned char hash[5][20] = {0};
    char key[1024] = {0}, buf[4096] = {0},  sm0[1024] = {0};
    Big h[5], m[4], n, d[3], bnkey, phi, p, q, r, e[3];
 
    string body = head, tail="完璧归赵";  
    body.append(name);
    
    sha160_hash(head.data(), head.size(), hash[1]);
    sha160_hash(name.data(), name.size(), hash[2]);
    sha160_hash(body.data(), body.size(), hash[3]);
    sha160_hash(tail.data(), tail.size(), hash[4]);
    
    for(int i = 1; i <= 4; i++)
        h[i] = from_binary(20, (char *)hash[i]);

    // sha256 固定的,无需动态计算。
    // n = sha-256("完璧归赵完璧归赵") = sha256(CDEAE8B5B9E9D5D4CDEAE8B5B9E9D5D4)
    // 3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01
   // factor(n),  n= p*q*r
    n = "3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01";
    p = "1F7BF";
    q = "F1059E73CFB296F8B";
    r = "2267D9CC91A552E23D284260B563CE490B0F7475F9D";
    phi = (p-1)*(p+1)*(q-1)*(q+1)*(r-1)*(r+1);

    if(uselcm == 1)
        phi = lcm(p-1, lcm(p+1, lcm(q-1, lcm(q+1, lcm(r-1, r+1)))));

    // 20 bytes FF  |  KXCTF19Q3
    // "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF4B5843544631395133" ;
    string s_e1(20, (unsigned char)0xFF);
    s_e1.append(kxctf);
    e[1] = from_binary(s_e1.size(), (char *)s_e1.data());;
    e[2] = n;

    // get d[1], d[2]
    d[1] = inverse(e[1], phi) ;
    d[2] = inverse(e[2], phi) ;
    
/*   对方程1 做逆运算即可得到M0 , 即 方程2
(1) verify:   { V_e2 [ V_e1(M0 + h1) + h2 ]  +  h4 } = h3   mod N

(2) sign:    M0 = { V_d1 [ V_d2 (h3 - h4) - h2 ]  - h1  }   mod N
*/
    // lucas round 1
    m[3] = (n + h[3] - h[4]) % n;
    m[2] = luc(m[3], d[2], n, NULL);

    // lucas round 2
    m[1] = (n + m[2] - h[2]) % n;
    m[0] = luc(m[1] , d[1], n, NULL);

    // ok, get key
    bnkey = (n + m[0] - h[1]) % n;
    key << bnkey;
    sm0 << m[0];
    sprintf(buf, "head=%s\nname=%s\nm[0]=%s\nkey=\n%sKXCTFXXXX%s", head.c_str(), name.c_str(), sm0, name.c_str(), key);
    return string(buf);
}

int main(int argc, char ** argv)
{
    string head = "PEDIY_CTF2019_Q3_完璧归赵_Crackme_Readyu_";
    string name = "username";
    string kxctf = "KXCTF19Q3";

    printf("%s\n\n",  calc_sn(head, "username", kxctf, 0).c_str());
    printf("%s\n\n",  calc_sn(head, "KCTF", kxctf, 0).c_str());
    printf("%s\n\n",  calc_sn(head, "蔺相如", kxctf, 0).c_str());
    printf("%s\n\n",  calc_sn(head, "廉颇", kxctf, 0).c_str());

    printf("%s\n\n",  calc_sn(head, "username", kxctf, 1).c_str());
    printf("%s\n\n",  calc_sn(head, "KCTF", kxctf, 1).c_str());
    printf("%s\n\n",  calc_sn(head, "蔺相如", kxctf, 1).c_str());
    printf("%s\n\n",  calc_sn(head, "廉颇", kxctf, 1).c_str());
    getchar();
    return 0;
}

雪    币: 10537
活跃值: 活跃值 (258)
能力值: (RANK:190 )
在线值:
发帖
回帖
粉丝
看场雪 活跃值 3 2019-9-25 12:43
5
0
佩服
雪    币: 3365
活跃值: 活跃值 (88)
能力值: ( LV12,RANK:694 )
在线值:
发帖
回帖
粉丝
xym 活跃值 2 2019-9-26 01:44
6
0
楼主,我能说我很想和你认识一下吗?Q2和Q3都是卡在你的题目上面,让别人绝地翻盘,欲哭无泪啊。
雪    币: 11624
活跃值: 活跃值 (270)
能力值: ( LV12,RANK:779 )
在线值:
发帖
回帖
粉丝
readyu 活跃值 12 2019-9-26 13:17
7
0
looklook队 半夜攻题,实在太猛了啊
最后于 2019-9-26 13:19 被readyu编辑 ,原因:
雪    币: 11624
活跃值: 活跃值 (270)
能力值: ( LV12,RANK:779 )
在线值:
发帖
回帖
粉丝
readyu 活跃值 12 2019-12-23 17:01
8
0
xym 楼主,我能说我很想和你认识一下吗?Q2和Q3都是卡在你的题目上面,让别人绝地翻盘,欲哭无泪啊。
@xym,   Q4 你一举成功,tql
游客
登录 | 注册 方可回帖
返回