首页
论坛
课程
招聘
[原创]CTF2017 第五题 brichfire writeup
2017-11-2 22:30 4479

[原创]CTF2017 第五题 brichfire writeup

2017-11-2 22:30
4479
前一天赶paper……然后开始直接睡着了……第二天中午才醒来……总计大概花了15个小时左右……感觉是目前最有趣的一道?果然是crypto狗吗……
这题主要考察了逆向大整数库……作者自己写了个大整数库和椭圆曲线的计算函数
首先先开字符串……没找到什么有用的东西……(IDA对UTF8的识别并不是很好……)
然后开findcrypt插件

发现了base64,直接找过去,找到base64encode函数

x找reference,找到check函数

发现有个0x2d的中断,并且之后的base64 10000次怎么也不可能等于那个需求的值,推测有exception handler
退回到hexview,这里用到了exception table

看exception table,找到exception handler的函数

跳到handlerfunc,发现就在check这个hexview中,不过没有被链接上,为了能简单的看hexray的c代码……上keypatch将int 0x2d那条直接patch 成 jmp handlerfunc

重新f5刷新一下

这里有两个检测,一个是keygen之后对比的检测,一个是point_check的检测,x一下check可以看到我们的main函数 (字符串是Ctrl + A 以后编成了Unicode, IDA 7.0对unicode的支持更好一些……)

可以看出假如我们只过了keygen这个检测check会返回2,过了point_check这个检测会返回1
init_key里面由于没有任何输入,所以直接OD到call init_key这条指令dump 出 v7这个key到arr.mem (StrongOD 可以处理异常)


这里为了OD找东西好找……于是IDA edit->segments->rebase program改为了OD的base(0x1060000)

右键eax 数据窗口中跟随

f8

数据窗口中直接右键,备份->保存数据到文件(会从0x00D71000开始dump),然后删掉没用的部分
dump出来的即为我们key的原始状态存储为arr.mem

之后看keygen这个函数,第一个参数是我们的v7 (key),第二个参数是个输入的字符串,keygen会执行两次,第一次的字符串是KanXueCrackMe2017,第二次的字符串是我们的输入

下面来看compute_base18这个函数,函数有点长……


我们一个函数一个函数分析……这里怎么猜出来是大整数计算的呢……点进BigIntDiv以后发现有这么一条……

找到处错误那个地址以后发现有那么点像UTF-8,于是把他Ctrl+A了一下……就发现了这么个字符串……在他附近找,还能发现更多的字符串(这里也说明了为什么String view里面没什么有用的东西……因为基本上都是中文字符串……dt)

0 has not ni yuan (大概意思是chinglish的0没有逆元……)可见这里面应该有取模算法和模逆算法,所以推测应该是大整数运算,同时因为这句话上github和google搜都没有……判断应该是作者自己写的大整数库
同时x查找0 has not ni yuan的引用找到了sub_106570b,这个大概是大整数的模逆运算,在查找这个的引用,找到了这么个函数……

Error in PointMul 推测应该是椭圆曲线的乘法,同时点进去以后发现旁边还有这么个字符串

eccPoint可以验证这确实是一个椭圆曲线的算法,回到compute_base18
点进BigIntFrom_num_index(sub_1063641)

挺简单的一个函数……这里猜测前16个int存放大整形,第18个int存放这个整形的长度 (第17个不知道干嘛的……),于是IDA创建一个大整数的struct

把a3改成新创建的大整数type (y),于是得知a1为存储的数据,a2是大整数数组的存储的角标,a3是存储的大整数

返回到check

这里就可以看出来其实是定义了一个62和18的大整数,之后会用到

开始逆向大整数库函数……
点进BigIntMultipy (sub_10638e1)
可以看出这个函数相当复杂……逆向算法感觉比较麻烦……

于是这里采取半蒙半猜的手法……OD break到call BigIntMultiply这行(0x01068390),下个断点

从IDA和BigIntMultipy这个函数最后的返回可以看出ebx存储的是我们的计算结果,ecx是我们第一个参数,eax是我们第二个参数,OD查看ecx

od查看eax

数据窗口中跟随ebx,f8步过

可以看到结果out = a1 * a2 (这里也有可能是别的……不过看看下一轮就知道之前的猜测对不对了)

同理可以得到以下的大整数库函数(有些会连带参数也变化,需要注意)

然后我们回来看compute_base18这个函数

第一个for循换把
“0”-“9” -> 0-9
"A"-"Z" -> 10-35
"a"-"z" -> 36-61
所以可以看出这和base64很像,得到的是一个逆向的查找表,因为是62个字符,所以我们得到的其实是base62的逆向查找表,v4即为我们当前字符在base62下所代表的10进制数值,所以整个逻辑是
mult = 1
sums = 0
b62c = string.digits + string.ascii_uppercase + string.ascii_lowercase
s = <input_str>
for i in range(len(s)):
   v4 = b62c.index(i)
   v5 = mult * inputa
   sums = sums + v5
   mult *= 62
简单一看,其实就是base62decode

compute_base18下半段

每次都除18,然后将余下的字符map到"0-9" + "A-H"
所以是base18encode

这两段代码可以总结为如下,同时我们也可以简单的写出逆运算
base62c = string.digits + string.ascii_uppercase + string.ascii_lowercase
base18c = "0123456789ABCDEFGH"

def basen_e(i, n):
    assert(n <= 62)
    res = ""
    while i > 0:
        res += base62c[i % n]
        i /= n
    return res

def basen_d(s, n):
    sums = 0
    mults = 1
    for i in range(len(s)):
        num = base62c.index(s[i])
        sums += num * mults
        mults *= n
    return sums

def compute(s):
    i = basen_d(s, 62)
    return basen_e(i, 18)

def inverse_compute(s):
    i = basen_d(s, 18)
    return basen_e(i, 62) 
compute即为我们compute_base18所输出的值,我们可以OD对比一下是否一致,退回到keygen

可以看出他会把我们base18之后的string取每个在十进制中的数,然后进行mult_array_pow这个运算,我们看这个函数


这里查看每两个相邻的array_mult,可以看出差是48 * 48, 同时res1的数组下标是96 (int数组)
查看array_mult

不难看出这个计算的是一个矩阵的乘法,矩阵inp 是[a0, a1, a2,....a48], 矩阵 out是一个48*48的方阵,这里计算了out = inp * out (矩阵乘法)

IDA里面创建key这个struct,以便于我们查看hexray

然后观察mutl_arrays_pow,可以得知他计算的是res1 = res1 * arr[choose]^pownum
综合keygen来看,得知keygen所计算的是如下代码(numpy对array处理起来很容易)
def read_array():
    with open("arr.mem", "rb") as f:
        res = f.read()
    assert(len(res) == (48 * 2 + 48 * 48 * 6) * 4)
    nums = len(res) / 4
    res = struct.unpack("<%dL" % nums, res)
    result = np.array(list(res[:48]))
    iv = np.array(list(res[48:96]))
    arrs = list(res[96:])
    arrs = [np.array(arrs[i:i+48*48]).reshape(48, 48) for i in range(0, len(arrs), 48*48)]
    return result, iv, arrs

def array_pow(arrs, iv, s):
    for i in s:
        i = base18c.index(i)
        a1, a2 = i / 3, (i % 3) + 1
        for j in range(a2):
            iv = np.dot(iv, arrs[a1])
    return iv

result, iv, arrs = read_array()
assert(iv == result)
s = compute("KanXueCrackMe2017")
iv1 = array_pow(arrs, iv, s)

其中keygen的v7即为Key ressult + iv + arrs
这样我们就不难得出第一个输入判断条件

即KanXueCrackMe2017对v7的iv做了以上的变换,得到iv1,我们的输入需要做逆变换,使得iv1变回iv
同时,查看pointcheck的第二个判断条件可知输入的长度为12个字符

这里刚开始我想的是计算每个array (0-6)被乘了几次,从而暴力破解,但是这样有两个问题……首先第一个是情况太多了……我们可以得知input的最大值是zzzzzzzzzzzz, 对应的compute后的长度是18,因为每个数组都有0-3几种可能,所以每个最大值是18 * 3 = 54,以下即为暴力破解的代码
def solve_1(arrs, arr_count, max_len, arr_res):
    max_pow = max_len * 3
    for i in range(max_pow):
        for j in range(i):
            for k in range(j):
                for l in range(k):
                    for a in range(l):
                        for b in range(max_pow - i - j - k - l - a):
                            counts = [i, j, k, l, a, b]
                            for count in itertools.permutations(counts):
                                if np.array_equal(multarrs(arrs, count), arr_res):
                                    print count
        print i
    return "Huh" 
arrs不变,arr_count 是list(每个数组被乘的总次数,max_len是18, arr_res是iv1/ iv,既multarrs不乘iv)
这么做其实并不对……因为数组乘法并没有交换律……既A^3 * B^3 * A 不等于 A^4 * B^3……所以我们还是需要暴力破解总共12个字符……这显然太多了……于是我们来看point_check这个函数


这个函数前面有一堆有的没的这些乱七八糟的……其实只是在构造大整数而已……重要的函数在后面

其中前面for函数那段很像我们之前所逆过的keygen中的base62decode
eccPoint (因为有之前的字符串的暗示),我们可以用OD dump出他所有的参数
得到
a1 = 没用
modulus = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xd9d8bd32fc078af28cb318a7ae07227accf335a1a02eddff421a50b7eceb9fd7
b = 0xffffffffffffffffffffffffffffffff000000000000000000000001
x_1 = 0xfa00a8d4d5755ae92322a317c3b1895d935ed95a36b4e4589328d7b7214a5d35

查看eccPoint函数

没有标出来的大整数库还沿用上面的连蒙带猜法……

椭圆曲线函数为 y^2 = x^3 + a * x + b

由于v6是一个平方的函数,所以推测之后还会再成一遍x,既得最后一个参数是x,a2 = x
由于BigIntMod最后一个是modulus所以可知第二个参数为modulus
由于计算的是a2^3 + a2 *a  + b,可知 a是第三个参数,b是第4个参数 (这里在bigintAdd b那里下个断点,可以看出加上的值并不是b,而是 b - 0x1000000000000000000000000000000000000000000000000),不知道是什么原因……不过这里我们需要修改之前椭圆曲线的b

最终y由最后的开平方得到,结果(x,y)存入第二个参数中, sage 验证
A = 0xd9d8bd32fc078af28cb318a7ae07227accf335a1a02eddff421a50b7eceb9fd7
B = 0xfffffffeffffffffffffffffffffffff000000000000000000000001
M = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
x = 0xfa00a8d4d5755ae92322a317c3b1895d935ed95a36b4e4589328d7b7214a5d35
y = 0xaeeb0346ec45386861311d68619391181116843e51e91c7d80a17faa47792fe8

P = (x, y)
F = FiniteField(M)
E = EllipticCurve(F,[A,B])
P = E.point(P) 
可知点P为符合曲线的点
point_check 之后进行了pointMul(同样字符串中得到……),即为椭圆曲线乘法,由于函数非常复杂……所以用连蒙带猜法和OD检测该函数是否为椭圆曲线乘法

同时


这里create_point定义了另外一个点Q,

point_equals 和 create_point 函数非常简单,这里略过
我们可以看出,check_point的检查是 h*P == Q,h是我们base62_decode以后的输入
其中 P 点 为 之前eccPoint计算出来的x,y,即
P =(0xfa00a8d4d5755ae92322a317c3b1895d935ed95a36b4e4589328d7b7214a5d35, 0xaeeb0346ec45386861311d68619391181116843e51e91c7d80a17faa47792fe8)
Q点为create_point创造出的点,OD dump一下可知
Q =  (0x739ca3c42d60579b8ab304fe511eb7501343d3a951a85ec67e74cfb88fdde40b, 0x3bcc7adbf46e9ce70453644e27b6947e7382c23c315f5ea7847f6cb4f10b62a2)

验证Q点在曲线上
A = 0xd9d8bd32fc078af28cb318a7ae07227accf335a1a02eddff421a50b7eceb9fd7
B = 0xfffffffeffffffffffffffffffffffff000000000000000000000001
M = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
x = 0xfa00a8d4d5755ae92322a317c3b1895d935ed95a36b4e4589328d7b7214a5d35
y = 0xaeeb0346ec45386861311d68619391181116843e51e91c7d80a17faa47792fe8

x1 = 0x739ca3c42d60579b8ab304fe511eb7501343d3a951a85ec67e74cfb88fdde40b
y1 = 0x3bcc7adbf46e9ce70453644e27b6947e7382c23c315f5ea7847f6cb4f10b62a2


P = (x, y)
Q = (x1, y1)
F = FiniteField(M)
E = EllipticCurve(F,[A,B])
P = E.point(P)
Q = E.point(Q)
至此point_check所要做的事就很清楚了……我们需要做的就是ECDLP……找到使等式Q == h * P 成立的h,这里乘法是椭圆曲线乘法 (刚开始不长记性的又暴力破解了一次……然并卵)

然而椭圆曲线密码学的安全性就建立在ECDLP是几乎不可能的这个假设上……所以我们需要另找出路

由于A,B是作者所选,所以有可能该曲线是weak curve,查看曲线的order,发现可以被完全的分解……
>>> print factor(E.order())
2^3 * 2137 * 7649 * 63127 * 33636409 * 55866443 * 194282080159 * 269685708029 * 142466661438412398901622269
于是可以考虑和DLP一样在变成subgroup上的ECDLP,然后再用chinese remainder theorem整合

这里有几个问题,一个是最后一个因数太大,于是ECDLP会花很长时间,但这里我们就可以用以上链接所用的方法忽略掉最后一个因数(因为之前的因数积已经大于我们所需要的最大值)
还有一个问题是8这个数并没有对应的ECDLP……于是分解成了2,4,最终sageMath代码如下
A = 0xd9d8bd32fc078af28cb318a7ae07227accf335a1a02eddff421a50b7eceb9fd7
B = 0xfffffffeffffffffffffffffffffffff000000000000000000000001
M = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
x = 0xfa00a8d4d5755ae92322a317c3b1895d935ed95a36b4e4589328d7b7214a5d35
y = 0xaeeb0346ec45386861311d68619391181116843e51e91c7d80a17faa47792fe8

x1 = 0x739ca3c42d60579b8ab304fe511eb7501343d3a951a85ec67e74cfb88fdde40b
y1 = 0x3bcc7adbf46e9ce70453644e27b6947e7382c23c315f5ea7847f6cb4f10b62a2


P = (x, y)
Q = (x1, y1)
F = FiniteField(M)
E = EllipticCurve(F,[A,B])
P = E.point(P)
Q = E.point(Q)

print factor(E.order())
factors, exponents = zip(*factor(E.order()))
primes = [2, 4, 2137, 7649, 63127, 33636409, 55866443, 194282080159, 269685708029]

dlogs = []
for fac in primes:
    t = int(P.order()) / int(fac)
    dlog = discrete_log(t*Q,t*P,operation="+")
    dlogs += [dlog]
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
    
#The result after run
#dlogs = [0, 0, 1170, 3054, 3754, 19965250, 39500704, 43692311729, 107916879091]
l = crt(dlogs,primes)
print(l)
print P*l == Q
 
于是得到l = 1773497881723270350100

扔进base62decode以后就是我们的最终答案CcLaoE37J45Y

验证第一个keygen的条件
import string
import struct
import numpy as np
from pwn import *

base62c = string.digits + string.ascii_uppercase + string.ascii_lowercase
base18c = "0123456789ABCDEFGH"

def basen_e(i, n):
    assert(n <= 62)
    res = ""
    while i > 0:
        res += base62c[i % n]
        i /= n
    return res

def basen_d(s, n):
    sums = 0
    mults = 1
    for i in range(len(s)):
        num = base62c.index(s[i])
        sums += num * mults
        mults *= n
    return sums

def compute(s):
    i = basen_d(s, 62)
    return basen_e(i, 18)

def inverse_compute(s):
    i = basen_d(s, 18)
    return basen_e(i, 62)

def read_array():
    with open("arr.mem", "rb") as f:
        res = f.read()
    assert(len(res) == (48 * 2 + 48 * 48 * 6) * 4)
    nums = len(res) / 4
    res = struct.unpack("<%dL" % nums, res)
    result = np.array(list(res[:48]))
    iv = np.array(list(res[48:96]))
    arrs = list(res[96:])
    arrs = [np.array(arrs[i:i+48*48]).reshape(48, 48) for i in range(0, len(arrs), 48*48)]
    return result, iv, arrs

def array_pow(arrs, iv, s):
    #arr_count = [0 for i in range(6)]
    for i in s:
        i = base18c.index(i)
        a1, a2 = i / 3, (i % 3) + 1
        for j in range(a2):
            iv = np.dot(iv, arrs[a1])
            #arr_count[a1] += 1
    return iv#, arr_count

def dump_bignum(s):
        s = format(s, 'x')
        s = '0' * (len(s) % 2) + s
        print hexdump(s.decode('hex')[::-1])

num = 1773497881723270350100
flag = basen_e(num, 62)
print flag

result, iv, arrs = read_array()
print np.array_equal(iv, result)
s = compute("KanXueCrackMe2017")
iv1 = array_pow(arrs, iv, s)

b18_flag = compute(flag)
iv2 = array_pow(arrs, iv1, b18_flag)

assert(np.array_equal(iv2, result))

总的来说这题逆向起来还是挺费劲的……而且还有椭圆曲线密码学……是一道还不错的题……不过当初不逆第一个keygen就好了……完全没卵用……

看雪侠者千人榜,看看你上榜了吗?

收藏
点赞0
打赏
分享
最新回复 (22)
雪    币: 561
活跃值: 活跃值 (14)
能力值: ( LV12,RANK:650 )
在线值:
发帖
回帖
粉丝
brichfire 活跃值 4 2017-11-3 13:18
2
0
Very  Good!
雪    币: 8543
活跃值: 活跃值 (852)
能力值: ( LV15,RANK:1920 )
在线值:
发帖
回帖
粉丝
ccfer 活跃值 15 2017-11-3 13:19
3
0
这个方法我服气
雪    币: 5
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
wx_心隐草 活跃值 2017-11-3 14:01
4
0
厉害
雪    币: 345
活跃值: 活跃值 (12)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
Koorey 活跃值 2017-11-3 14:07
5
0
厉害
雪    币: 2720
活跃值: 活跃值 (124)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
MaYil 活跃值 2017-11-3 14:40
6
0
666666感谢分享
雪    币: 260
活跃值: 活跃值 (49)
能力值: ( LV7,RANK:111 )
在线值:
发帖
回帖
粉丝
ReeHeiHei 活跃值 1 2017-11-3 14:51
7
0
大佬大佬
雪    币: 171
活跃值: 活跃值 (101)
能力值: ( LV15,RANK:843 )
在线值:
发帖
回帖
粉丝
NearJMP 活跃值 5 2017-11-3 15:38
8
0
直接撸ECC,膜膜膜
雪    币: 6182
活跃值: 活跃值 (173)
能力值: ( LV5,RANK:71 )
在线值:
发帖
回帖
粉丝
joker陈 活跃值 2017-11-3 15:39
9
0
学习学习。
雪    币: 331
活跃值: 活跃值 (35)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
金箍棒 活跃值 2017-11-3 15:52
10
0
厉害。。。
雪    币: 260
活跃值: 活跃值 (36)
能力值: ( LV9,RANK:144 )
在线值:
发帖
回帖
粉丝
THREAD 活跃值 2017-11-3 16:19
11
0
雪    币: 11624
活跃值: 活跃值 (270)
能力值: ( LV12,RANK:779 )
在线值:
发帖
回帖
粉丝
readyu 活跃值 12 2017-11-3 19:36
12
0
佩服!
雪    币: 4
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
acsZeng 活跃值 2017-11-3 20:29
13
0
还有这操作
雪    币: 5638
活跃值: 活跃值 (460)
能力值: ( LV17,RANK:1185 )
在线值:
发帖
回帖
粉丝
holing 活跃值 15 2017-11-3 21:06
14
0
膜拜
雪    币: 4671
活跃值: 活跃值 (279)
能力值: ( LV15,RANK:1338 )
在线值:
发帖
回帖
粉丝
lelfei 活跃值 22 2017-11-3 21:18
15
0
一直在想魔方还原步骤化简再加上长度限制就直接得到答案了,那个eccCheck有什么用?原来直接逆ecc也能得到答案!
这种解法太牛!
雪    币: 923
活跃值: 活跃值 (186)
能力值: ( LV15,RANK:734 )
在线值:
发帖
回帖
粉丝
iweizime 活跃值 7 2017-11-3 22:14
16
0
佩服
雪    币: 11434
活跃值: 活跃值 (490)
能力值: ( LV9,RANK:142 )
在线值:
发帖
回帖
粉丝
orz1ruo 活跃值 2017-11-4 07:24
17
0
膜拜大佬
雪    币: 923
活跃值: 活跃值 (15)
能力值: ( LV13,RANK:760 )
在线值:
发帖
回帖
粉丝
不问年少 活跃值 15 2017-11-4 08:07
18
0
大神都服气了,我也跟服吧!
雪    币: 22584
活跃值: 活跃值 (1601)
能力值: ( LV15,RANK:3225 )
在线值:
发帖
回帖
粉丝
风间仁 活跃值 19 2017-11-5 09:01
19
0
服气
雪    币: 455
活跃值: 活跃值 (149)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
ssarg 活跃值 2017-11-14 22:18
20
0
分析的很具体,很透彻。然并卵对我来说,完全不懂。
体力好的让人羡慕。
我自己写了个穷举的脚本,现在还在算着呢,唉什么时候是个头?此时此刻才感觉到人生苦短啊。
不过,借用你的正确结果验证了一下脚本,缩小范围跑了下,可以正确弹出结果,唉,算是yiyin了一把。
什么时候可以租个超算,估计应该也是件快乐的事情了。
雪    币: 455
活跃值: 活跃值 (149)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
ssarg 活跃值 2017-11-14 22:24
21
0
不问年少 大神都服气了,我也跟服吧!
这个也字用的好
雪    币:
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
李优秀 活跃值 2018-3-15 20:40
22
0
虽然我不会,但我会喊666666。
雪    币: 1435
活跃值: 活跃值 (186)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
陈jack 活跃值 2018-7-22 23:14
23
0
写的很好
游客
登录 | 注册 方可回帖
返回