首页
论坛
专栏
课程

看雪.纽盾 KCTF 2019 Q2 | 第十题点评及解题思路

Editor 发布于 看雪学院 2019-07-05 18:15


“池塘边的榕树上,知了在声声叫着夏天~”伴着窗外绿叶间的蝉鸣,我们迎来周五的夕阳,于此同时,我们看雪纽盾KCTF的Q2赛题解析也到达尾声。


此刻,小伙伴们有没有一丢丢不舍和眷恋呢?没关系,我们的KCTF第三赛段在九月火热开启,等你来战!


今天我们来看下第十题,观英雄斗智斗勇,开启时间之轮,逆转乾坤~


题目简介


题目背景:


历经千辛万苦,集齐所有的能量宝石,但成功开启时间之轮,开启进入另一个平行时空的入口,还差一步。


你需要将这八颗宝石按照正确的顺序排列出来,才能够成功开启时间之轮,否则能量宝石也只是八块石头……


快来寻找宝石排列的秘密吧!人类的命运如今就掌握在你的手中。



本题共有1990人围观,截至比赛结束只有5人攻破此题。纵观全局,十道题目中难度排名前三,难倒了不少英雄好汉。


攻破此题的战队一览:



接下来我们来对题目进行详细解析。


看雪评委crownless点评



本题算法基于二次剩余与离散对数,主要涉及公钥密码学的知识。解决此题的关键在于,不仅要掌握扎实的密码学、数学知识,而且还要懂逆向分析、程序分析。



出题团队简介



本题出题战队 ReadPage :



论坛ID为readyu,毕业于中国科学技术大学自动控制专业,从事软件开发多年。在软件保护技术、加密算法方面有一些体验。曾在北京多看科技从事电子阅读加密技术的研究,以及在MIUI从事系统安全方面工作。



设计思路



本题算法主要涉及公钥密码学的基础知识。Win32程序, 无壳, 无Anti。暂定取名 “一石二鸟”。



一、序列号

本题唯一序列号SN为:


KCTFREADYKXXXX1548396171915056368526513804948765619094392315806578461796159505215278288254



二、方程

算法基于二次剩余与离散对数, 建立了2个方程 (1) (2)  见下文,并且模同一个素数,所以暂定取名 “一石二鸟”。


P=2^255-19 是一个素数,base16 或者base10如下:


P(hex)=7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED


P(dec)=57896044618658097711785492504343953926634992332820282019728792003956564819949

序列号格式为两段字符, + 表示字符串合并:


SN = “s1” + “XXXX” + “s2”

s1是大写字母串, s2是十进制数字串。数值上, 1 < s1,  s2 < P

其中,s1,s2 是未知量, d是s1变换而来的未知量。

s1逆序变换,加上最小位调整, 然后base25解码得到d. (Y,G)内置于程序之中。

64*(s2-s1)^4 + (s2-s1)^2 + 3 = s1 mod P    ... (1)

G^d = Y  mod P      ... (2) 


G,Y 是已知数, 范围 [ 1, P-1]:

Y = 100

G = 9230197858975018299629857977411527954550899478307510809210520967346958600039 



三、解法


解法:首先解方程2,得到d,转换为s1 ;然后再解方程1,得到s2。


3.1 解方程(2)


方程(2)解释如下:
d = base25.reverse(s1) ....(3)

随机验证任何一对,结果都是一样的。


(Y,G) =

        "100,9230197858975018299629857977411527954550899478307510809210520967346958600039",
        "101,50414221767352083765613498524674590844333823720255656432490557866777248860034",
        "102,38377684164112914669201831650756813551072223314592288217929947158283532270268",
        "103,13436195533519778671648120865743178010431697022400670384909515001970400645091",

比如 Y=100,
     G=9230197858975018299629857977411527954550899478307510809210520967346958600039

G^d = Y mod P ,  P是256bit的大素数。

表面一看,需要解256 bit的离散对数, 需要解离散对数工具,比如gdlog。


GDLOG
Implementation of the GNFS for discrete logarithm problem in GF(p) 
https://sourceforge.net/projects/gdlog/

但本题,程序里给出了条件,d 转化为base25字符时,最长为10个字节。 


所以数量级极大地缩小,只有47bits。也就是d < limit, limit = 25^10 = 95367431640625 。


因此,用pollard kangaroo 算法求解d,范围为band = (1, 95367431640625) 只有47 bits。


kangaroo算法是解决区间band = (a, b)上离散对数问题很有效的方法,在平均意义下需要进行2 * √|a-b|次群操作。


期望步数 2 *(limit^0.5)= 2* 9765625, 也就是大概2000万次。经测试, 大概30-60秒之间。

我们得到:

d(dec) = 79821823136933
d(hex)= 4898F769D4A5 
base25table=ABCDEFGHKJILMNOPQRSTUVWYZ  


是26个大写字母表,(扣除X, 并且K,I互换位置),得到 d.base25 = UYDAERFTCK

逆序后得到:s = d.base25.reverse = KCTFREADYU


为了防止被猜测到s1, 低位做了修正,修正值 diff = 'U' - 'K' = 10:


注册码里的采用KCTFREADYK, 
s1 = KCTFREADYK + diff = KCTFREADYU
s1(hex) = 4B435446524541445955

3.2 解方程(1)


1

首先,根据一般的二次剩余方程, 可以配方以后求解:
a*x^2 + bx + c = 0  mod p


两边乘以4a配方:
4a^2*x^2 + 4a*bx + 4ac = 0  mod p

方程变为
(2a*x + b)^2 = b^2 - 4ac


令delta = b^2 - 4ac, 就可以归结为求  sqroot(delta) mod p:

x1 = (-b - sqroot(delta))/(2a)   mod p

x2 = (-b + sqroot(delta))/(2a)   mod p


注意,这里的除法是模P的逆。

2

方程(1)解释如下:

64*(s2 - s1)^4 +  (s2-s1)^2 + 3 - s1 = 0 mod P

F(x)是一个4次多项式:F(x) = a4*x^4 + a2*x^2 + a0

这里取x = s2 - s1, a4 = 64, a2 = 1, a0 = 3

F(x) 可以简化为一个二次剩余方程,


64*(s2 - s1)^4 +  (s2-s1)^2 + 3 = s1  mod P  ... (4)

64*r^2 + r + 3 = s1 mod p , 
=> 64*r^2 + r  = (s1 - 3) mod p 

两边乘以4a,加上1:
4*64*64*r^2 + 256*r + 1 = 256*(s1-3) + 1 mod p

(128r + 1)^2 = 256*(s1-3) + 1  mod p

s1 = 4B435446524541445955, s1-3 = 4B435446524541445952


乘以256就是左移一个字节。


3


方程简化为:

(128r + 1)^2 = 4B43544652454144595201  mod p  ...(5)
r =  (sqroot(4B43544652454144595201, P) - 1)/128

第一步,方程(5)求解首先求得两个解r1,r2。

Y = 4B43544652454144595201
sqroot(Y, P), RDLP 求解。

Two sqroots of Y (mod P), in HEX BASE.


G1-258B783A22015B08A6C64FB55644BAACCDA201473D4B6786821056707C680B58
G2-5A7487C5DDFEA4F75939B04AA9BB4553325DFEB8C2B498797DEFA98F8397F495

再求得:
r1=2D4B16F0744402B6114D8C9F6AAC8975599B44028E7A96CF0D0420ACE0F8D010
r2=1CB4E90F8BBBFD49EEB273609553768AA664BBFD71856930F2FBDF531F072FE5  

然后r1,r2分别求解二次剩余,各有两个解,所以一共有4个解。

第二步,解出 x^2 = r mod p,可用RDLP求解。


root(r1)=  
x2-3CCA260F45B79993C67F35F7A716B28BBA591BA35593C8DEB9B959C2CE43AE21
x3-4335D9F0BA48666C3980CA0858E94D7445A6E45CAA6C37214646A63D31BC51CC

root(r2)=
x4-7C93A389F44E31BC25D90165624292389B47C2C27F60286FF627A6FC3DB84BC4
x1-036C5C760BB1CE43DA26FE9A9DBD6DC764B83D3D809FD79009D85903C247B429

这4个解记作x1,x2,x3,x4, 恰好每一个都分布在(1, P)的4个区间之一。
(0-1/4), (1/4-1/2), (1/2 - 3/4), (3/4, 1)

然后:s2 = s1 + X  , 也有4个s2, 并转为10进制表示。


最后合并:
SN = "s2" + "XXXX" + "s1"

4个解为:

SN_X1=KCTFREADYKXXXX1548396171915056368526513804948765619094392315806578461796159505215278288254


SN_X2=KCTFREADYKXXXX27495936700183671733408543181646240981077460232127048216208422649817010276214


SN_X3=KCTFREADYKXXXX30400107918474425978376949322697712945557532100693234514359350753673330338593


SN_X4=KCTFREADYKXXXX56347648446743041343258978699395188307540600017013704268771613898275062326553

题目取最小的解:

x < P/4,SN_X1 为有效答案。



解题思路



本题解题思路由看雪论坛ODPan提供:



这是一道数论高配题。整数要用大整数,方程要用模方程,模方程要用二次模方程,二次模方程要用二次模合数方程,求逆要选离散对数。


该题选用了mbedtls大数库,可以对应着源代码查看分析。



程序的初步分析


作者一如既往的对话框程序,我们需要关心两个程序。sub_403B00 输入字符处理函数和sub_404270校验函数。校验函数做了抗F5小处理。将此处Nop掉即可F5分析。


.text:00404B1E    pop     ebp



输入字符处理


简单查看了一下。合法字符串使用“XXXX”进行分割,分为前后两个部分,并转化为string类型。


char__cdeclstrProcess(char*key, ctf10_Str *strRetKeyBefore, ctf10_Str *strRetKeyAfter)
{
char*pchar;// eax
unsigned__int64 XXXXlen;// ST04_8
char*index;// eax
char*index_1;// esi
ctf10_Str *strKeyBefore;// eax
ctf10_Str *strTemp;// eax
unsignedintkeyAfterLen;// ecx
_BYTE *pchar_keyAfter;// eax
intv11;// edi
char*pchar_keyAfter_1;// eax
charv13;// al
charv14;// al
charv15;// al
charresult;// al
charv17;// al
ctf10_Str strXXXX;// [esp+Ch] [ebp-3Ch]
ctf10_Str strKey;// [esp+1Ch] [ebp-2Ch]
ctf10_Str strKeyAfter;// [esp+2Ch] [ebp-1Ch]
intv21;// [esp+44h] [ebp-4h]

LOBYTE(strKey.field_0) = (_BYTE)key;
StrInitByFalg(&strKey,0);
strLoad(&strKey, key,strlen(key));
LOBYTE(strXXXX.field_0) = (_BYTE)key;
v21 =0;
StrInitByFalg(&strXXXX,0);
strLoadByInput(&strXXXX,0,4u,'X');
pchar = (char*)strXXXX.pchar;
LOBYTE(v21) =1;
if( !strXXXX.pchar )
pchar = (char*)&unk_4100FC;
HIDWORD(XXXXlen) = strXXXX.len;
LODWORD(XXXXlen) =0;
index = str_find(&strKey, pchar, XXXXlen);// find XXXX
index_1 = index;
if( index == (char*)-1)
gotoLABEL_39;
strKeyBefore = str_substr(&strKey, &strKeyAfter,0, (unsignedint)index);
LOBYTE(v21) =2;
strCpy(strRetKeyBefore, strKeyBefore,0,0xFFFFFFFF);
LOBYTE(v21) =1;
StrInitByFalg(&strKeyAfter,1);
strTemp = str_substr(&strKey, &strKeyAfter, (unsignedint)&index_1[strXXXX.len],0xFFFFFFFF);
LOBYTE(v21) =3;
strCpy(strRetKeyAfter, strTemp,0,0xFFFFFFFF);
LOBYTE(v21) =1;
StrInitByFalg(&strKeyAfter,1);
if( !strRetKeyBefore->len )
gotoLABEL_39;
keyAfterLen = strRetKeyAfter->len;
if( !keyAfterLen )
gotoLABEL_39;
pchar_keyAfter = (_BYTE *)strRetKeyAfter->pchar;
if( !pchar_keyAfter )
pchar_keyAfter = &unk_4100FC;
if( *pchar_keyAfter =='0')
{
LABEL_39:
LOBYTE(v21) =0;
StrInitByFalg(&strXXXX,1);
v21 =-1;
StrInitByFalg(&strKey,1);
return0;
}
v11 =0;
if( keyAfterLen >0)
{
while(1)
{
pchar_keyAfter_1 = (char*)strRetKeyAfter->pchar;
if( !pchar_keyAfter_1 )
pchar_keyAfter_1 = (char*)&unk_4100FC;
if( !isdigit(pchar_keyAfter_1[v11]) )// 数字
break;
if( (unsignedint)++v11 >= strRetKeyAfter->len )
gotoLABEL_14;
}
if( strXXXX.pchar )
{
v14 = *(_BYTE *)(strXXXX.pchar -1);
if( v14 && v14 !=-1)
*(_BYTE *)(strXXXX.pchar -1) = v14 -1;
else
strFree((LPVOID)(strXXXX.pchar -1));
}
strXXXX.pchar =0;
strXXXX.len =0;
strXXXX.field_C =0;
if( strKey.pchar )
{
v15 = *(_BYTE *)(strKey.pchar -1);
if( v15 && v15 !=-1)
{
*(_BYTE *)(strKey.pchar -1) = v15 -1;
result =0;
}
else
{
strFree((LPVOID)(strKey.pchar -1));
result =0;
}
returnresult;
}
return0;
}
LABEL_14:
if( strXXXX.pchar )// 全是数字的处理
{
v13 = *(_BYTE *)(strXXXX.pchar -1);
if( v13 && v13 !=-1)
*(_BYTE *)(strXXXX.pchar -1) = v13 -1;
else
strFree((LPVOID)(strXXXX.pchar -1));
}
strXXXX.pchar =0;
strXXXX.len =0;
strXXXX.field_C =0;
if( strKey.pchar )
{
v17 = *(_BYTE *)(strKey.pchar -1);
if( v17 && v17 !=-1)
{
*(_BYTE *)(strKey.pchar -1) = v17 -1;
return1;
}
strFree((LPVOID)(strKey.pchar -1));
}
return1;
}



校验函数


该函数要满足3个条件,才能返回正确结果。下面分别分析这三个条件。


函数初始化部分


大整数初始化


mbedtls_mpi_lset(&power0xff, v91);
BigInt_pow(&ret, &power0xff, v7);// 2^0xff
mbedtls_mpi_add_int(&power0xff, &ret, v8);// 2^0XFF - 0X13
mbedtls_mpi_sub_int(&powerSbu1, &power0xff,1);// /2^0XFF - 0X13 - 1
mbedtls_mpi_lset(&A, a4);


将输入字串的两部分转化为大整数,我们假设a=keyBefore,b= keyAfter 


mbedtls_mpi_copy(&keyBefore, &mytarget);
mbedtls_mpi_copy(&keyAfter, &srcNode);


第一个条件:4b < power0xff


mbedtls_mpi_add_mpi(&doubleAfter, &keyAfter, &keyAfter);
mbedtls_mpi_add_mpi(&node4b, &doubleAfter, &doubleAfter);
v12 = mbedtls_mpi_cmp_mpi(&node4b, &power0xff);// 4b < power0xff


第一个条件是个限制条件,4*b < 2^0xff – 0x13。


第二个条件:模方程


mbedtls_mpi_lset(&sum, v12 >=0);// v90 = 0
v13 =0;
v63 =0;
v14 = v50;
while( v13 < v14 )// v14= 6
{
mbedtls_mpi_sub_mpi(&afterSunBefor, &keyAfter, &keyBefore); r=b-a
powern(&desNode[v13], &afterSunBefor, *(&n + v13), &power0xff);// n=0,1,2,3,4,5
addNum(&v58, *(&num + v13), &desNode[v13], &sum, &power0xff);// a*num+v90 num = 3,0,1,0,0x40,0,1
mbedtls_mpi_copy(&sum, &v58);
v63 = ++v13;
}
mbedtls_mpi_sub_mpi(&a1a, &keyBefore, &sum);


这里我们另r=b-a,循环6次的过程如下:

sum0 =  r^0/N                 *3 =3

sum1 =  r^1*0/N              +sum0/N = 3

sum2 =  r^2*1/N              +sum1/N = (r^2+3)/N

sum3 =  r^3*0/N              +sum2/N = (r^2+3)/N

sum4 =  r^4*0x40/N +sum3/N = 0X40r^4/N + (r^2+3)/N

sum5 =  r^5*0/N +sum4


最后得到的方程:

(64r^4/N + (r^2 +3)/N)/n = a


这里我们另x=r^2,这里往回逆的时候要逆两次。化简后可得一个二次模方程:

64x^2 + x a = 0(mod N)


从方程可知,求出a即可反推x,r最后求得b。那么我们继续分析,看如何求a值。


第三个条件:离散对数


mbedtls_mpi_lset(&E,0);
maxTableData = getDataFormTable((char*)'X');// v15 = 0x19
maxTableData_1 = maxTableData;
maxTableData_2 = maxTableData;
index =0;
index_1 =0;
const0xA = *((_DWORD *)checkData +4);
buf =0;
memset(&v39,0,252u);
v40 =0;
v41 =0;
size = *((_DWORD *)checkData +1);
pcharend = (char*)(size + *(_DWORD *)checkData -1);
v36 = (char*)(size + *(_DWORD *)checkData -1);
pbuf = &buf;
v42 = &buf;
while( (unsignedint)pcharend >= *(_DWORD *)checkData )
{
*pbuf++ = *pcharend;
v42 = pbuf;
v36 = --pcharend;
}
buf += checkData[12];// 输入字符串前半部分keyBefore,最后一个字符+0xA
while( index <strlen(&buf) )
{
keyChar1 = (char*)*(&buf + index++);
index_1 = index;
numFromTableByKey = getDataFormTable(keyChar1);
numFromTableByKey_1 = numFromTableByKey;
v43 = numFromTableByKey;
if( numFromTableByKey >= maxTableData_1 )
{
errorFlag =1;
break;
}
mbedtls_mpi_mul_int(&E, &E, maxTableData_1);
mbedtls_mpi_add_int(&E, &E, numFromTableByKey_1);// 将keyBfore内容转换为0x19进制数
}
if( index <= const0xA && !errorFlag )// KEY 前半部分长度小于10
{
sushuCnt = createSuShuByRand(randNum, &buf2);// 产生素数列表和随机检测个数
randNum = sushuCnt;
for( j =0; ; ++j )// 米勒罗宾素性测试
{
v63 = j;
if( j >= sushuCnt || !*(&buf2 + j) )
break;
sub_4025A0(&ret_1, &E, *(&buf2 + j));
if( !ret_1 )
gotoLABEL_35;
}
get_gccd(&v58, &powerSbu1, &E);// gcd
if( node_getBitNum_0(&v58) <=1)
{
mbedtls_mpi_inv_mod(&D, &E, &powerSbu1);// D = E^-1 mod (N-1)
mbedtls_mpi_exp_mod(&final, &A, &D, &power0xff, &a5);// X = A^D mod N
mbedtls_mpi_sub_mpi(&v71, &nodeCheck, &final);
v25 = node_getData(&v71);
result3 = v25;
mbedtls_mpi_exp_mod(&a2, &nodeCheck, &E, &power0xff, &a5);// A = X^E mode N
mbedtls_mpi_sub_mpi(&v69, &a2, &A);
if( v25 )
result3 = node_getData(&v69);
}


代码几个关键步骤说明:

1、 将keyBefore(输入字符串得前半部分)最后一位+0x0A;

2、 将keyBfore内容转换为0x19进制数,记作E;

3、 米勒罗宾素性测试,确保E为素数;

4、 E与(N-1)最大公约数为1

5、 检测计算

D = E^-1 mod (N-1)

X = A^D mod N

A = X^E mode N


N=0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED


这里我们已知A和X得四组数据,求D,求离散对数。利用作者dlp工具可以跑出D。这样我们可以一路反推D->E->keyBefore->a,将a带回二次模方程,这里简单提一下方程化简过程:

64r^4 + r^2 + 3-0x4B435446524541445955 = 0 mod N

64x^2 + x + 3-0x4B435446524541445955 = 0 mod N


转换为一般模方程:

x^2 = A mode M      

A是奇数非素数,M是个合数  GCD(A,M)==1


其中

a = 64

b = 1

c =-0x4B435446524541445952


所以

A = b^2 - 4ac

M = 4aN


这样经过两次二次模方程求解可以解的r(b-a,b<4N。最终求得a,b。


aXXXXb= KCTFREADYKXXXX1548396171915056368526513804948765619094392315806578461796159505215278288254



END


主办方


看雪学院(www.kanxue.com)是一个专注于PC、移动、智能设备安全研究及逆向工程的开发者社区!创建于2000年,历经19年的发展,受到业内的广泛认同,在行业中树立了令人尊敬的专业形象。平台为会员提供安全知识的在线课程教学,同时为企业提供智能设备安全相关产品和服务。 



合作伙伴



上海纽盾科技股份有限公司(www.newdon.net)成立于2009年,是一家以“网络安全”为主轴,以“科技源自生活,纽盾服务社会”为核心经营理念,以网络安全产品的研发、生产、销售、售后服务与相关安全服务为一体的专业安全公司,致力于为数字化时代背景下的用户提供安全产品、安全服务以及等级保护等安全解决方案。


天上真的掉馅饼啦!     

面试跳槽没有拿得出手的证书?

升职加薪能力不够?

公司申请安全资质,但员工要求达不到?

一张CISP的证书,帮您解决全部问题。


预算不够又想找靠谱的机构?

纽盾帮您解决全部问题,全新的上课机制,丰富的课程安排,超多大型项目供你累积经验,通过率高达99%。

现报名还有优惠补贴,快来了解下吧。






10大议题正式公布!第三届看雪安全开发者峰会重磅来袭!


小手一戳,了解更多




分享到:
最新评论 (0)
登录后即可评论