第十三题

check在 0x407f30
看到了熟悉的大整数计算
拆 partA KXCTFXXXX partB

partB 十六进制数 0-9A-F 长度大于8
partA 就是username这个字符串
对partB + cdeae8b5b9e9d5d4 + deadbeefcafec0de + cdeae8b5b9e9d5d4cdeae8b5b9e9d5d4做了一个sha1
这里的+是连接

sha1字符串后面又放了一个KXCTF19Q3

对几个东西都sha1了一下，都是固定的，可以提出来

sha1s = [0x9071232e6b170092668255303e5d824f2879ad56, 0x249ba36000029bbe97499c03db5a9001f6b734ec, 0xc4b73cb0dd1d750c69e1755b06bbaffff44d2600, 0x6dc844c73b34d6e6b8de48da64ef92ab2b11f461]

其中下标为1的是username这个字符串的sha1，看出来作者是想做一队一密的
还有几个常数，提取一下

a = 0xcdeae8b5b9e9d5d4
b = 0xcdeae8b5b9e9d5d4cdeae8b5b9e9d5d4
c = 0xdeadbeefcafec0de
d = 0x3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01
e = Flag_num

逆向过程有点痛苦
整理一下算法
其中有一个F函数比较迷，单独拿出来看

xx = []
yy = []
zz = []

f = lambda x, y: (x+y) / 2 if x % 2 else x / 2


def G(x, d):
    return 1

def F(e, x, sha, d):
    bit = lambda x, n: (x >> n) & 1
    gg = (e * e + d - x * 4) % d
    ff = 1
    hh = 0
    jj = 2
    ee = e
    j = sha.bit_length() - 1
    while(j > 0):
        j -= 1
        hh = ff * ee
        jj = gg * ff * ff + ee * ee
        ff = hh % d
        ee = f(jj % d, d)
        if (bit(sha, j)):
            hh = e * ff + ee
            jj = gg * ff + e * ee
            ff = f(hh % d, d)
            ee = f(jj % d, d)
    xx.append(ff)
    yy.append(ee)
    zz.append(f((e * ee - ff * gg) * G(x, d) % d, d))

整体流程大概这样

from Crypto.Util.number import *
from hashlib import sha1
import gmpy2


flag = 'AAAAA11111'

xx = []
yy = []
zz = []

f = lambda x, y: (x+y) / 2 if x % 2 else x / 2


def G(x, d):
    return 1


def F(e, x, sha, d):
    bit = lambda x, n: (x >> n) & 1
    gg = (e * e + d - x * 4) % d
    ff = 1
    hh = 0
    jj = 2
    ee = e
    j = sha.bit_length() - 1
    while(j > 0):
        j -= 1
        hh = ff * ee
        jj = gg * ff * ff + ee * ee
        ff = hh % d
        ee = f(jj % d, d)
        if (bit(sha, j)):
            hh = e * ff + ee
            jj = gg * ff + e * ee
            ff = f(hh % d, d)
            ee = f(jj % d, d)
    xx.append(ff)
    yy.append(ee)
    zz.append(f((e * ee - ff * gg) * G(x, d) % d, d))


converted_flag = flag + 'cdeae8b5b9e9d5d4deadbeefcafec0decdeae8b5b9e9d5d4cdeae8b5b9e9d5d4'.decode('hex') 
flag_num = int(flag, 16)
sha1s = [0x9071232e6b170092668255303e5d824f2879ad56, 0x249ba36000029bbe97499c03db5a9001f6b734ec, 0xc4b73cb0dd1d750c69e1755b06bbaffff44d2600, 0x6dc844c73b34d6e6b8de48da64ef92ab2b11f461]


flag_sha1s = [bytes_to_long(sha1(converted_flag).digest() + 'KXCTF19Q3'), bytes_to_long(''.join(map(chr, [(~ord(x)) & 0xff for x in sha1(converted_flag).digest()])))]


a = 0xcdeae8b5b9e9d5d4
b = 0xcdeae8b5b9e9d5d4cdeae8b5b9e9d5d4
c = 0xdeadbeefcafec0de
d = 0x3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01
e = flag_num


ps = []


x = d + 1 
e = e + d + sha1s[0] # e + sha1s[0]
y = (e * e - x * 4) % d
for i in xrange(2):
    F(e, x, flag_sha1s[i], d)
    ps.append(1) # always 1

'''
print map(hex, xx)
print map(hex, yy)
print map(hex, zz)
print map(hex, ps)
'''

for j in xrange(9): 
    for i in xrange(8):
        xx[1] = (xx[1] * yy[1]) % d  
        yy[1] = (yy[1] * yy[1] - ps[1] - ps[1] + d + d) % d 
        ps[1] = (ps[1] * ps[1]) % d # 1

z = (yy[0] * yy[1] + y * xx[0] * xx[1]) % d

#print hex(z)
# f(z, d) = 0x2878036a7ee3fb039684c3046200f4cd5b564999bd5286955d0c9b2d57c4d9f5

z = f(z, d)  
print hex(z)
z = z + sha1s[1] # sha1(username)

w = x % d + d 
F(z, x, w, d)


t = zz + d + sha1s[3] + 3 * d 
print hex(t)


for i in xrange(9):
    t = t - d
    if (t == sha1s[2]):
        print "ok"
        #print flag
        #print "ok"

# print "gg"
# cmp t, shas[2]

https://github.com/aleaxit/gmpy/blob/master/src/gmpy_mpz_lucas.c
翻了一整篇gmp的文档，经过一些运算性质的判定和测试，确定F函数求的是Lucas序列
https://en.wikipedia.org/wiki/Lucas_sequence
返回值是(Ux, Vx, V(x-1))

然后要处理一下，化简一下这个里面的那些神奇的运算
现在已经知道

F(P, Q, k, n) => (U(k), V(k), V(k-1))

其中P和Q是Lucas序列的参数，k是需要求第k项，n是模数，U(k)和V(k)是Lucas U序列和V序列的第k项
首先，因为在模n的有限域里面，所以所有大于n的数都可以等价为模n

x = d + 1  # x => 1
y = (e * e - x * 4) % d

显然x等价于1
设flag=e，等价于flag_num+sha1s[0]
那么后面涉及的Lucas序列就都是P=flag Q=1的
F函数操作一下之后，获得了两个K=shas的序列值
设sha1(flag) = 0xSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
设取反是0xRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
显然对于每一个十六进制位，Si+Ri=0xF
那么得到了k1，k2是

k1 = 0xSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS4b5843544631395133
k2 = 0xRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR

那么xx，yy可以得到

xx = [U(k1), U(k2)]
yy = [V(k1), V(k2)]

下面看这一波运算

for j in xrange(9): 
    for i in xrange(8):
        xx[1] = (xx[1] * yy[1]) % d  
        yy[1] = (yy[1] * yy[1] - ps[1] - ps[1] + d + d) % d 
        ps[1] = (ps[1] * ps[1]) % d # 1

ps数组里面都是1，暂时不管
看一下前两个式子
U序列和V序列都有一些运算性质的
根据性质

U(k) * V(k) = U(2k)

可得第一个式子在算U(2k)
然后根据

V(k) ** 2 - 2 * Q = V(2k)

这里Q刚好是个1，所以就是第二个式子
所以这一个循环就是把U和V的k值乘了2
一共循环了72次，就是乘了2的72次方，也就是左移72位，就是9个字节
跑完了以后，现在k1和k2相当于

k1 = 0xSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS4b5843544631395133
k2 = 0xRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR000000000000000000

看上去有趣了起来
然后继续看下面的运算

z = (yy[0] * yy[1] + y * xx[0] * xx[1]) % d 
z = f(z, d)

根据之前的式子可以看出来f是一个模d的除2操作
所以实际上是

z = (yy[0] * yy[1] + y * xx[0] * xx[1]) / 2

然后Lucas序列又有如下性质

2V(m+n) = V(m)V(n) + DU(m)U(n)

其中

D = P ** 2 - 4 * Q

显然，就是上面那个式子的形式
那么这时候z就是V(k1+k2)
k1和k2之前知道了

k1 = 0xSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS4b5843544631395133
k2 = 0xRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR000000000000000000

然后又因为两个sha1是按位取反的关系，所以任意Si+Ri=0xF
这一加起来就是

0xffffffffffffffffffffffffffffffffffffffff4b5843544631395133

SHA1消掉了！
算了这么多，到现在就是一个式子

z = V(0xffffffffffffffffffffffffffffffffffffffff4b5843544631395133)，其中参数P=flag，Q=1，模数n=0x3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01

继续往下算
给z加了一个sha1s[1]

w = x % d + d 
F(z, x, w, d)
取了zz

这里x=d+1，所以w可以算，也是d+1
然后算了P=z Q=1 模数为d的lucas序列的第w-1项，就是第d项
实际上就是

zz = V(n)，
其中参数P=z，Q=1，模数n=0x3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01

最后加上一个sha1s[3]，模d看是否等于sha1s[2]

所以总结一下，流程是这样

from Crypto.Util.number import *
from hashlib import sha1
import gmpy2


flag = 'AAAAA11111' # test flag

converted_flag = flag + 'cdeae8b5b9e9d5d4deadbeefcafec0decdeae8b5b9e9d5d4cdeae8b5b9e9d5d4'.decode('hex') 
flag_num = int(flag, 16)
sha1s = [0x9071232e6b170092668255303e5d824f2879ad56, 0x249ba36000029bbe97499c03db5a9001f6b734ec, 0xc4b73cb0dd1d750c69e1755b06bbaffff44d2600, 0x6dc844c73b34d6e6b8de48da64ef92ab2b11f461]


flag_sha1s = [bytes_to_long(sha1(converted_flag).digest() + 'KXCTF19Q3'), bytes_to_long(''.join(map(chr, [(~ord(x)) & 0xff for x in sha1(converted_flag).digest()])))]


a = 0xcdeae8b5b9e9d5d4
b = 0xcdeae8b5b9e9d5d4cdeae8b5b9e9d5d4
c = 0xdeadbeefcafec0de
d = 0x3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01
e = flag_num


e = e + d + sha1s[0] 


z = gmpy2.lucasv_mod(e, 1, 0xffffffffffffffffffffffffffffffffffffffff4b5843544631395133, d)

# print hex(z)
z = z + sha1s[1] # sha1(username)

zz = gmpy2.lucasv_mod(z, 1, d, d)


t = zz + d + sha1s[3] + 3 * d 
print hex(t)


for i in xrange(9):
    t = t - d
    if (t == sha1s[2]):
        print "ok"
        #print flag
        #print "ok"

# print "gg"
# cmp t, shas[2]

可以看到实际上就是算了两个式子，真实
那么问题就转化为
已知Q=1，k，n，以及V(k)，求P

是Q=1的Lucas序列，可能有一些特殊性质，去找一找资料

读论文
http://informatika.stei.itb.ac.id/~rinaldi.munir/Kriptografi/2012-2013/Makalah2-2013/Makalah2Kripto2013-015.pdf
这个是一种基于Lucas序列的公钥加密体制
完全分解N的情况下可以求私钥

这个题N不大，可以分解
逆！

from Crypto.Util.number import *
from hashlib import sha1
import gmpy2


def recover_d(cipher, e):
    # n = 128959 * 277879388132275220363 * 804543020813130593505380215293268595059305396789149
    D = cipher ** 2 - 4
    x = 128959 - gmpy2.legendre(D, 128959)
    y = 277879388132275220363 - gmpy2.legendre(D, 277879388132275220363)
    z = 804543020813130593505380215293268595059305396789149 - gmpy2.legendre(D, 804543020813130593505380215293268595059305396789149)
    r = gmpy2.lcm(gmpy2.lcm(x, y), z)
    d = gmpy2.invert(e, r)
    return d


a = 0xcdeae8b5b9e9d5d4
b = 0xcdeae8b5b9e9d5d4cdeae8b5b9e9d5d4
c = 0xdeadbeefcafec0de
n = 0x3fbdad083dbc11a52fa2af1a0829c522c1492907f1b9523a17b7a8e65679bb01
sha1s = [0x9071232e6b170092668255303e5d824f2879ad56, 0x249ba36000029bbe97499c03db5a9001f6b734ec, 0xc4b73cb0dd1d750c69e1755b06bbaffff44d2600, 0x6dc844c73b34d6e6b8de48da64ef92ab2b11f461]


cipher = sha1s[2] - sha1s[3]

d = recover_d(cipher, n)

# cipher = gmpy2.lucasv_mod(cipher, 1, e, n)
plain = gmpy2.lucasv_mod(cipher, 1, d, n)
#print plain1
cipher = plain - sha1s[1] # sha1(username)

e = 0xffffffffffffffffffffffffffffffffffffffff4b5843544631395133
d = recover_d(cipher, e)

# cipher = gmpy2.lucasv_mod(plain, 1, 0xffffffffffffffffffffffffffffffffffffffff4b5843544631395133, n)
plain = gmpy2.lucasv_mod(cipher, 1, d, n)


flag = plain - sha1s[0]
print hex(flag).upper()

# usernameKXCTFXXXX753350C5A24300015025083AFBAE5D206A7D83E2C7F98D09ADB6EF51ACFDC83

第三题（没做出来）

32字符flag 字母数字
读进去转成64进制数字
作为opcode

arr = [29, 76, 10, 59, 66, 1, 94, 48, 6, 74, 40, 17, 81, 119, 3, 28, 2, 45, 75, 122, 126, 105, 107, 96, 36, 115, 71, 125, 64, 0, 41, 70, 9, 117, 92, 121, 7, 27, 95, 111, 78, 26, 16, 85, 104, 58, 8, 82, 124, 113, 18, 79, 99, 97, 88, 11, 24, 109, 108, 52, 46, 110, 93, 43, 30, 86, 37, 87, 31, 118, 62, 35, 38, 77, 14, 51, 47, 55, 57, 20, 89, 69, 65, 39, 101, 103, 15, 60, 44, 102, 73, 23, 90, 22, 91, 13, 98, 120, 25, 19, 50, 112, 56, 42, 5, 123, 53, 127, 80, 32, 49, 34, 54, 61, 84, 83, 100, 33, 12, 114, 4, 21, 72, 116, 63, 68, 106, 67]
correct = [73, 82, 117, 3, 123, 56, 24, 71, 26, 92, 86, 109, 113, 120, 8, 37, 75, 67, 90, 59, 10, 34, 4, 101, 79, 125, 1, 2, 51, 74, 98, 0, 61, 69, 19, 53, 107, 30, 88, 35, 70, 103, 54, 121, 41, 23, 27, 119, 65, 5, 32, 52, 64, 49, 22, 115, 116, 83, 20, 9, 99, 89, 91, 21, 84, 38, 93, 112, 95, 78, 17, 42, 6, 105, 55, 102, 15, 13, 122, 47, 60, 111, 33, 66, 43, 48, 63, 7, 29, 50, 97, 57, 16, 68, 18, 114, 44, 72, 45, 39, 106, 124, 100, 108, 58, 104, 80, 11, 28, 76, 62, 36, 12, 110, 87, 25, 46, 94, 77, 96, 81, 126, 118, 14, 31, 40, 127, 85]
wtf = [64, 58, 59, 7, 49, 95, 141, 175, 31, 115, 45, 215, 226, 154, 250, 149, 182, 135, 187, 70, 114, 120, 105, 88, 15, 234, 18, 89, 216, 176, 75, 251, 97, 166, 46, 78, 225, 35, 124, 203, 252, 86, 138, 169, 196, 199, 238, 158, 171, 102, 177, 60, 100, 72, 82, 143, 13, 181, 210, 43, 159, 65, 222, 173, 101, 93, 168, 39, 185, 69, 79, 17, 198, 2, 61, 37, 218, 243, 133, 52, 213, 245, 4, 111, 121, 255, 20, 233, 76, 117, 40, 118, 19, 128, 241, 132, 244, 178, 62, 116, 206, 51, 148, 80, 211, 142, 204, 74, 209, 21, 230, 162, 130, 25, 190, 106, 108, 5, 249, 92, 29, 83, 155, 11, 205, 57, 248, 253]

整理一下VM功能表

0 r0++
1 r0-- 
2 pos1 = r2
3 pos2 = r2
4 r2 = r0
5 r2 = target[r2]
6 r2 = wtf[r2]
7 再读一个字符存到寄存器r1
8 flag = 1
9 if (flag == 1) switch r1
  0 target[pos1] += target[pos2]
  1 target[pos1] -= target[pos2]
  2 target[pos1] &= target[pos2]
  3 target[pos1] |= target[pos2]
  4 target[pos1] ^= target[pos2]
  5 if pos1>=pos2 flag=0 else flag=1

不断的循环跑这32字节的bytecode，直到r0=128算跑一遍
一共跑128遍

这能逆？

猜一下，源数组和目标数组里面都是0-127全来了一遍，一般的运算凑不出来，可能是代换/置换盒，这几个运算里面能简单做代换的就异或
14524627489 4624527489 452462749 00
但是好像不对
作为置换盒的话，连续置换几次是会回去的，感觉可能是个突破口

第九题 （没做出来）

带混淆的安卓
https://bbs.pediy.com/thread-253533.htm
https://github.com/GeT1t/deollvm/blob/master/cfg.py

是控制流平坦化+指令替换+虚假控制流

发现了NISLFILE，根据特征找到这个文章
http://www.xjishu.com/zhuanli/55/201810446991.html

第十题（没做出来）

两个virtualprotect,更改前后如下

.text 00401000 00565000 R W X . L para 0001 public CODE 32 0000 0000 0003 FFFFFFFF FFFFFFFF
.text 00401000 00565000 R W X . L para 0001 public CODE 32 0000 0000 0003 FFFFFFFF FFFFFFFF

CrakeMe.exe 00400000 00401000 R . . D . byte 0000 public CONST 32 0000 0000 0000 0000 0000
CrakeMe.exe 00400000 00401000 R W X D . byte 0000 public CODE 32 0000 0000 0000 0000 0000

文件头被改了,文件头:

事先把保留字给改成了一个地址,然后执行fld,将这个地址放入st0,不知道在干什么,先拿出来备用

 7.9380306991563653492e-39

+0x000 ExceptionList: Ptr32 _EXCEPTION_REGISTRATION_RECORD
+0x004 StackBase        : Ptr32 Void
+0x008 StackLimit       : Ptr32 Void
+0x00c SubSystemTib     : Ptr32 Void
+0x010 FiberData        : Ptr32 Void
+0x010 Version          : Uint4B
+0x014 ArbitraryUserPointer : Ptr32 Void
+0x018 Self              : Ptr32 _NT_TIB

又把这玩意拿出来了,stackbase和stacklimit,两个地址,做差,算了一个size,地址以4(Dword对齐),放回dos头里,就是算了线程栈的大小然后把线程栈里面的东西复制到wtf中,备份esp,ebp.

前面就是因为start没什么内存,先是用没用的dos头存数据,然后把栈迁移到另外的一个地址,备份esp,ebp,开始脱壳.试一下esp定律,下了个硬件断点,好像ida炸了

过了一个指令异常,前一堆rdtsc,后面下断,找到一个call eax,东西在这里面

有地址随机化

跟进eax,还是壳的部分,按照脱壳的套路来,有上跳就下断,然后好几处call eax,估计在循环解码,有常量加密

.ctf:00567000 000 jmp     short loc_567025
.ctf:03658ECA     jmp     short loc_3658EEF
.ctf:00567000 000 jmp     short loc_567025
.ctf:01F19DD0     jmp     short near ptr unk_1F19DF5
.ctf:00567000 000 jmp     short loc_567025
.ctf:057690FA     jmp     short loc_576911F

一次567000一次其他的地址,运算全部带有常量混淆,以及所有的指令都是jmp这种,正好和控制流平坦化相反了,这玩意流程是一个纵向的

一堆rdtsc好像没什么影响,OD可以直接过反调试,rdtsc对OD无效
下了个puts(好像是)的断点,在最后打印的时候,看到了结尾左右的逻辑,popad后进行判断然后跳转,最后打印后执行Terminal

调吧 = =,好像并没有发现什么指令集的转换,都是一些很无聊的跳转加上循环

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