[原创]2019看雪CTF > 总决赛 > 第九题：四季之歌 WP-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

[原创]2019看雪CTF > 总决赛 > 第九题：四季之歌 WP

2019-12-24 15:19 6375

[原创]2019看雪CTF > 总决赛 > 第九题：四季之歌 WP

xym

2019-12-24 15:19

6375

首先进行逆向分析，这次题目和Q3的结构很像，基本是一个框架写的，因此前面的分析过程可以参考上次题目的。

最终输入要求答案具有 test_KXCTF_flag{key1-key2-key3} 的形式，其中key1可以算是key2和key3的校验，所以真正要求解的是key2和key3。

判断key2和key3是否符合条件的具体运算过程可以提炼成以下python代码。

v162_P = 0x4EA28B61F4C3B12B0B544814578629410ECCF55A7

def Add_Rol(a1):
    P = v162_P
    a1 = a1 % P
    if a1 < 0:
        a1 += P
    if a1 % 2:
        a1 += P
    a1 = a1 / 2
    return a1 % P

def sub_404860(a1, a2, a3, a4, a5, a6):
    P = v162_P
    # v61 = a1 * a5
    # v60 = a2 * a4
    # v59 = a3 * a6
    # v58 = a1 * a4 + a2 * a5 #(a1 + a2) * (a4 + a5) - v60 - v61
    # v57 = v60 - 0x7E3 * v61
    # v56 = v60 * v61
    # v55 = 0xBD9 * v59 * v59
    # v64 = v59 * v57 * v58
    v64 = (0x7E3 + 0xBD9) * a3 * a6 * (a2 * a4 - 0x7E3 * a1 * a5) * (a1 * a4 + a2 * a5) #(0x7E3 * v64 + 0xBD9 * v64)
    out3 = ((v64 % P + P) % P) * 2
    #v63 = (v56 - v55) * v58
    v63 = (0x7E3 + 0xBD9) * (a2 * a4 * a1 * a5 - 0xBD9 * a3 * a6 * a3 * a6) * (a1 * a4 + a2 * a5)#(0x7E3 * v63 + 0xBD9 * v63)
    out2 = ((v63 % P + P) % P) * 2
    #v62 = (v55 + v56) * v57
    v62 = (0x7E3 + 0xBD9) * (0xBD9 * a3 * a6 * a3 * a6 + a2 * a4 * a1 * a5) * (a2 * a4 - 0x7E3 * a1 * a5) #(0x7E3 * v62 + 0xBD9 * v62)
    out1 = ((v62 % P + P) % P) * 2
    return out1, out2, out3

def sub_404E90(sha3,sha1,sha2,k3,k2,const0x13D00,inputadd):
    v163 = [0 for i in range(4)]
    v167 = [0 for i in range(4)]
    v168 = [0 for i in range(4)]
    v164 = [0 for i in range(4)]
    v165 = [0 for i in range(4)]
    v166 = [0 for i in range(4)]

    v163[0] = 0x0294F20E7B5DC2D408E4D05A35FACEB13D3DCF5C69 * 2 * 1 * inputadd * sha1
    v163[1] = 0x006458A8D5AEEE40A2C95B667FC705F19112E17397 * 2 * 2 * inputadd * sha1
    v163[2] = 0x0330A0818BC327794D974BA7AA8070AB6917482491 * 2 * 3 * inputadd * sha1
    v163[3] = 0x02F5AE3DEC2A4D95E9E01A2B6D9F226162BBE2B3AD * 2 * 4 * inputadd * sha1

    v167[0] = 0x20190204 * 2 * 1 * inputadd * sha1
    v167[1] = 0x20190506 * 2 * 2 * inputadd * sha1
    v167[2] = 0x20190808 * 2 * 3 * inputadd * sha1
    v167[3] = 0x20191108 * 2 * 4 * inputadd * sha1

    v168[0] = 1 * 2 * 1 * inputadd * sha1
    v168[1] = 1 * 2 * 2 * inputadd * sha1
    v168[2] = 1 * 2 * 3 * inputadd * sha1
    v168[3] = 1 * 2 * 4 * inputadd * sha1

    v164[0] = 0x1DB0A6222242978D383FAC95B7CB3573F628D0FDA * inputadd * sha2
    v164[1] = 0x7C283613ABF06C423F887035C1FCA8BBDDADB548 * inputadd * sha2
    v164[2] = 0x29500DBA9ECAB405C9D11DC067E01590BB5E1F514 * inputadd * sha2
    v164[3] = 0x52653AAA31FE29A8C9209ED5FB3E164255C366900 * inputadd * sha2

    v165[0] = 0x4E559F46B4ADF60BAC0BA565EB681C758955D1BB6 * inputadd * sha2
    v165[1] = 0x96992ADA68A7FCCA696FA29EBFE066580AE2436AC * inputadd * sha2
    v165[2] = 0x13B396F4F22FDB14876E0405C02628E518BDA7161A * inputadd * sha2
    v165[3] = 0x84FA600452F0DE8E1A13BCB444918391525620758 * inputadd * sha2

    v166[0] = 2 * 1 * inputadd * sha2
    v166[1] = 2 * 2 * inputadd * sha2
    v166[2] = 2 * 3 * inputadd * sha2
    v166[3] = 2 * 4 * inputadd * sha2

    v139 = sha3 * k3
    v136 = sha3 * k2
    v135 = sha3 * const0x13D00
    v158 = sha1 * k3
    v157 = sha1 * k2
    v160 = sha1 * const0x13D00
    v150 = sha2 * k3
    v149 = sha2 * k2
    v152 = sha2 * const0x13D00

    P = v162_P

    # v128 = sha1 % (sha1%0x7E3 + 0x16D)
    v43 = 0x439
    v44 = 0x4B7

    for i in range(v43):
        (v158, v157, v160) = sub_404860(v136, v139, v135, v158, v157, v160)
        v139 = Add_Rol(v139)
        v136 = Add_Rol(v136)
        v135 = Add_Rol(v135)

    for i in range(v44):
        (v150, v149, v152) = sub_404860(v136, v139, v135, v150, v149, v152)
        v139 = Add_Rol(v139)
        v136 = Add_Rol(v136)
        v135 = Add_Rol(v135)

    for i in range(12):
        v167[i % 4] = (v167[i % 4] * v43) % P
        v163[i % 4] = (v163[i % 4] * v43) % P
        v168[i % 4] = (v168[i % 4] * v43) % P
        v158 = v158 * 0x7E3
        v157 = v157 * 0x7E3
        v160 = v160 * 0x7E3
        (v158, v157, v160) = sub_404860(v163[0], v167[0], v168[0], v158, v157, v160)
        (v158, v157, v160) = sub_404860(v163[1], v167[1], v168[1], v158, v157, v160)
        (v158, v157, v160) = sub_404860(v163[2], v167[2], v168[2], v158, v157, v160)
        (v158, v157, v160) = sub_404860(v163[3], v167[3], v168[3], v158, v157, v160)

    for i in range(4):
        v164[i] = (v164[i] * v44) % P
        v165[i] = (v165[i] * v44) % P
        v166[i] = (v166[i] * v44) % P
        v150 = v150 * 0xBD9
        v149 = v149 * 0xBD9
        v152 = v152 * 0xBD9
        (v150, v149, v152) = sub_404860(v165[0], v164[0], v166[0], v150, v149, v152)
        (v150, v149, v152) = sub_404860(v165[1], v164[1], v166[1], v150, v149, v152)
        (v150, v149, v152) = sub_404860(v165[2], v164[2], v166[2], v150, v149, v152)
        (v150, v149, v152) = sub_404860(v165[3], v164[3], v166[3], v150, v149, v152)

    for i in range(365):
        (v134, v133, v132) = sub_404860(v157, v158, v160, v158, v157, v160)
        v158 = Add_Rol(v158)
        v157 = Add_Rol(v157)
        v160 = Add_Rol(v160)
        (v158, v157, v160) = sub_404860(v133, v134, v132, v158, v157, v160)
        v158 = Add_Rol(v158)
        v157 = Add_Rol(v157)
        v160 = Add_Rol(v160)
        (v150, v149, v152) = sub_404860(v149, v150, v152, v150, v149, v152)
        v150 = Add_Rol(v150)
        v149 = Add_Rol(v149)
        v152 = Add_Rol(v152)

    v157 = v157 * 0x7E3
    v158 = v158 * 0x7E3
    v160 = v160 * 0x7E3
    v137 = ((v158**2 + v157**2*0x7E3) * v160**2) % P
    v138 = (v158**2 * v157**2 + v160**2*0xBD9*v160**2) % P
    print "assret(v137 == v138) ",Hex(v137 - v138)
    print Hex(v137)
    print Hex(v138)

    v150 = v150 * 0xBD9
    v149 = v149 * 0xBD9
    v152 = v152 * 0xBD9
    v137 = ((v150**2 + v149**2*0x7E3) * v152**2) % P
    v138 = (v150**2 * v149**2 + v152**2*0xBD9*v152**2) % P
    print "assret(v137 == v138) ",Hex(v137 - v138)
    print Hex(v137)
    print Hex(v138)


    v134 = v139*0x7E3 * (v158+v157+v160)
    v133 = v136*0x7E3 * (v158+v157+v160)
    v132 = v135*0x7E3 * (v158+v157+v160)
    v134 = Add_Rol(v134)
    v133 = Add_Rol(v133)
    v132 = Add_Rol(v132)
    (v158, v157, v160) = sub_404860(v133, v134, v132, v158, v157, v160)
    v158 = Add_Rol(v158)
    v157 = Add_Rol(v157)
    v160 = Add_Rol(v160)
    v137 = ((v158*v152 - (v150*v160)%P)*0x7E3)%P    #(v158*v152)%P == (v150*v160)%P
    v138 = ((v157*v152 - (v149*v160)%P)*0xBD9)%P    #(v157*v152)%P == (v149*v160)%P
    print "assret(v137 == 0) ",Hex(v137)
    print "assret(v138 == 0) ",Hex(v138)

sha1 = 0xac7fc2865d908c75fc6698c3b0aaa9cb89515185
sha2 = 0xa94a8fe5ccb19ba61c4c0873d391e987982fbbd3
sha3 = 0x047e8e0068522d9d32c36b28279759d657072e0d
key1 = 0x6789
key2 = 0xABCDEF223456789
key3 = 0xABCDE
sub_404E90(sha3, sha1, sha2, key3, key2, 0x13D00, 0x2507A)

根据sub_404860里面的运算，发现可以对每组数的公因子进行消除而不影响最后结果，因此可以对题目进行化简，

最后发现Add_Rol应该也不会影响结果，所以得到化简版的代码如下：

v162_P = 0x4EA28B61F4C3B12B0B544814578629410ECCF55A7
Const_0x7e3 = 0x7e3
Const_0xBD9 = 0xbd9

v163 = [0 for i in range(4)]
v167 = [0 for i in range(4)]
v168 = [0 for i in range(4)]
v164 = [0 for i in range(4)]
v165 = [0 for i in range(4)]
v166 = [0 for i in range(4)]
v163[0] = 0x0294F20E7B5DC2D408E4D05A35FACEB13D3DCF5C69
v163[1] = 0x006458A8D5AEEE40A2C95B667FC705F19112E17397
v163[2] = 0x0330A0818BC327794D974BA7AA8070AB6917482491
v163[3] = 0x02F5AE3DEC2A4D95E9E01A2B6D9F226162BBE2B3AD
v167[0] = 0x20190204
v167[1] = 0x20190506
v167[2] = 0x20190808
v167[3] = 0x20191108
v168[0] = 1
v168[1] = 1
v168[2] = 1
v168[3] = 1
v164[0] = 0x1DB0A6222242978D383FAC95B7CB3573F628D0FDA
v164[1] = 0x7C283613ABF06C423F887035C1FCA8BBDDADB548
v164[2] = 0x29500DBA9ECAB405C9D11DC067E01590BB5E1F514
v164[3] = 0x52653AAA31FE29A8C9209ED5FB3E164255C366900
v165[0] = 0x4E559F46B4ADF60BAC0BA565EB681C758955D1BB6
v165[1] = 0x96992ADA68A7FCCA696FA29EBFE066580AE2436AC
v165[2] = 0x13B396F4F22FDB14876E0405C02628E518BDA7161A
v165[3] = 0x84FA600452F0DE8E1A13BCB444918391525620758
v166[0] = 2 * 1
v166[1] = 2 * 2
v166[2] = 2 * 3
v166[3] = 2 * 4

def sub_404860(a1, a2, a3, a4, a5, a6):
    P = v162_P
    v64 = a3 * a6 * (a2 * a4 - Const_0x7e3 * a1 * a5) * (a1 * a4 + a2 * a5)
    out3 = v64 % P
    v63 = (a2 * a4 * a1 * a5 - Const_0xBD9 * a3 * a6 * a3 * a6) * (a1 * a4 + a2 * a5)
    out2 = v63 % P
    v62 = (Const_0xBD9 * a3 * a6 * a3 * a6 + a2 * a4 * a1 * a5) * (a2 * a4 - Const_0x7e3 * a1 * a5)
    out1 = v62 % P
    return out1, out2, out3

def sub_404E90(sha3, sha1, sha2, k3, k2, const0x13D00):
    v139 = k3
    v136 = k2
    v135 = const0x13D00
    v158 = k3
    v157 = k2
    v160 = const0x13D00
    v150 = k3
    v149 = k2
    v152 = const0x13D00

    P = v162_P

    for i in range(0x439):
        (v158, v157, v160) = sub_404860(v136, v139, v135, v158, v157, v160)

    for i in range(0x4B7):
        (v150, v149, v152) = sub_404860(v136, v139, v135, v150, v149, v152)

    for i in range(12):
        (v158, v157, v160) = sub_404860(v163[0], v167[0], v168[0], v158, v157, v160)
        (v158, v157, v160) = sub_404860(v163[1], v167[1], v168[1], v158, v157, v160)
        (v158, v157, v160) = sub_404860(v163[2], v167[2], v168[2], v158, v157, v160)
        (v158, v157, v160) = sub_404860(v163[3], v167[3], v168[3], v158, v157, v160)

    for i in range(4):
        (v150, v149, v152) = sub_404860(v165[0], v164[0], v166[0], v150, v149, v152)
        (v150, v149, v152) = sub_404860(v165[1], v164[1], v166[1], v150, v149, v152)
        (v150, v149, v152) = sub_404860(v165[2], v164[2], v166[2], v150, v149, v152)
        (v150, v149, v152) = sub_404860(v165[3], v164[3], v166[3], v150, v149, v152)

    for i in range(365):
        (tmpv134, tmpv133, tmpv132) = sub_404860(v157, v158, v160, v158, v157, v160)
        (v158, v157, v160) = sub_404860(tmpv133, tmpv134, tmpv132, v158, v157, v160)
        (v150, v149, v152) = sub_404860(v149, v150, v152, v150, v149, v152)

    print 'v150', Hex(v150)
    print 'v149', Hex(v149)
    print 'v152', Hex(v152)
    tmp1 = ((v158 ** 2 + v157 ** 2 * Const_0x7e3) * v160 ** 2) % P
    tmp2 = (v158 ** 2 * v157 ** 2 + v160 ** 2 * Const_0xBD9 * v160 ** 2) % P
    print "assret(tmp1 == tmp2) ", Hex(tmp1 - tmp2)
    print Hex(tmp1)
    print Hex(tmp2)
    tmp1 = ((v150 ** 2 + v149 ** 2 * Const_0x7e3) * v152 ** 2) % P
    tmp2 = (v150 ** 2 * v149 ** 2 + v152 ** 2 * Const_0xBD9 * v152 ** 2) % P
    print "assret(tmp1 == tmp2) ", Hex(tmp1 - tmp2)
    print Hex(tmp1)
    print Hex(tmp2)

    tmp1 = ((v158 * v152 - (v150 * v160) % P) * Const_0x7e3) % P  # (v158*v152)%P == (v150*v160)%P
    tmp2 = ((v157 * v152 - (v149 * v160) % P) * Const_0xBD9) % P  # (v157*v152)%P == (v149*v160)%P
    print "assret(tmp1 == 0) ", Hex(tmp1)
    print "assret(tmp2 == 0) ", Hex(tmp2)

sub_404E90(sha3, sha1, sha2, key3, key2, 0x13D00)

对代码初步分析可以知道这可能是一道椭圆曲线相关的题目。
在00406839位置有一个判断，经过化简形式如下：

((v158**2 + v157**2*0x7E3) * v160**2) % v162和(v158**2 * v157**2 + v160**2*0xBD9*v160**2) % v162是否相等。

在00406AEA位置有一个判断：

((v150**2 + v149**2*0x7E3) * v152**2) % v162和(v150**2 * v149**2 + v152**2*0xBD9*v152**2) % v162是否相等。

已知v162=0x4EA28B61F4C3B12B0B544814578629410ECCF55A7。

对v162进行素性检测，发现v162是一个素数，记为Prime。由此，可以推测这是一个FiniteField(Prime)有限域上的问题。
又总结上面两个判断的特点，使用变量xyz表示的话，形式如下：
x^2*z^2+0x7E3*y^2*z^2=x^2*y^2+0xBD9*z^4
令x'=x/z,y'=y/z，上面的方程可以改为
x'^2+0x7E3*y'^2=x'^2*y'^2+0xBD9
也就是
x^2+0x7E3*y^2=x^2*y^2+0xBD9
猜测这是一个椭圆曲线的问题，查看维基百科英文版elliptic curve的介绍，发现twisted edwards curve跟该方程曲线比较像，在twisted edwards curve的维基百科的英文版上查看http://www.hyperelliptic.org/EFD/g1p/index.html，查看Twisted Edwards curves: a*x2+y2=1+d*x2*y2下的Projective coordinates: x=X/Z, y=Y/Z，可以看到有各种椭圆曲线上点的加法实现方式，并且与sub_404E90函数调用的sub_404860函数具有非常高的相似性。由此推测sub_404860函数是椭圆曲线的加法实现方式。使用python实现的等价函数，在后期验证各种猜想时起到了重要作用。因为是射影坐标下的表示方式，在验证两个点在只有xy的直角坐标系上是否为同一个点时，需要考虑到z对xy大小的影响，具体判断方式就容易实现了。根据以上分析，选取x^2+0x7E3*y^2=x^2*y^2+0xBD9曲线上的整数点P，对P点进行倍加2次更新，这样能得到4P点，再通过递增更新也能得到4P点，验证这两种方式得到的为同一个点（xy直角坐标系下的同一个点）就可以确定sub_404860函数就是椭圆曲线的加法实现。更进一步，令射影坐标下的点P=(x,y,z)乘以或除以相同的数，不会影响点P在xy直角坐标系上的位置，据此可以简化sub_404E90函数且不影响对输入的判断。

经过对函数的详细分析总结，发现有3个关键判断，上面已经提到的2个判断（00406839位置和00406AEA位置的判断）为点是否在椭圆曲线上，第3个判断是两个点是否为同一个点。

问题最后变成了(0x43A*x+c1)*3^365+x=(0x4B8*x+c2)*2^365，其中c1和c2是v163和v164等数据决定的固定的点，需要求取z为0x13D00的点x。

问题归结为，对于已知整数k、点Q，求点P，使得kP=Q。该问题可以转为求取椭圆曲线的阶。

为此，需要下面3个条件。
1.
sagemath中给出了Weierstrass形式的椭圆曲线的阶的求取函数，使用方法是
K =GF(Prime)
R.<x,y,z>=K[]
EC=EllipticCurve(x^3+c1*x^2+c2*x-y^2)
print(EC.order())
2.
记不起来怎么搜索到了论文《Edwards Elliptic Curves》，http://fse.studenttheses.ub.rug.nl/10478/，发现论文第4章提到了从Edwards曲线到Weierstrass曲线的一种映射方式。
3.

通过求取发现0x7E3是模Prime的二次剩余，也就是存在整数c使得c^2=0x7E3(mod Prime)。使用sagemath实现，命令是

F=FiniteField(Prime);print(F(0x710bbc3150967cdd76c3915d3afda635d3ad7206).sqrt())。那么x^2+0x7E3*y^2=x^2*y^2+0xBD9方程可以通过利用0x7E3是模Prime的二次剩余这个性质来进行变换，可以通过几步简单变换得到从本题的曲线到Edwards曲线的一种映射方式。

根据以上3点就可以利用sagemath求取得到该题中的椭圆曲线的阶，记为ord。求取k关于ord的逆，记为d，则P=dQ，到此问题解决。
这次的解题说明是总结性质的，解题过程碰到的问题比这里更复杂，在探索阶段进行了很多猜测，这里给出的结果已经把不正确的猜测都去掉了，所以显得解题过程比较顺利。

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界

收藏・1

点赞・4

打赏

最新回复 (1)
榆钱雪币： 1394 活跃值： (58) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 15 粉丝 0 关注私信	榆钱 2019-12-31 10:06 2 楼 0 解释的清楚，就像四季沐歌太阳能热水器，洗的酣畅淋漓……
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复