-
-
[原创]CTF2017 第五题 brichfire writeup
-
发表于: 2017-11-2 22:30
-
前一天赶paper……然后开始直接睡着了……第二天中午才醒来……总计大概花了15个小时左右……感觉是目前最有趣的一道？果然是crypto狗吗……
这里为了OD找东西好找……于是IDA edit->segments->rebase program改为了OD的base(0x1060000)
这题主要考察了逆向大整数库……作者自己写了个大整数库和椭圆曲线的计算函数
首先先开字符串……没找到什么有用的东西……（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)
可以看出他会把我们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)
这样我们就不难得出第一个输入判断条件
即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"
这么做其实并不对……因为数组乘法并没有交换律……既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)
point_check 之后进行了pointMul（同样字符串中得到……），即为椭圆曲线乘法，由于函数非常复杂……所以用连蒙带猜法和OD检测该函数是否为椭圆曲线乘法
同时
这里create_point定义了另外一个点Q，
这题主要考察了逆向大整数库……作者自己写了个大整数库和椭圆曲线的计算函数
首先先开字符串……没找到什么有用的东西……（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)
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)
可以看出他会把我们base18之后的string取每个在十进制中的数，然后进行mult_array_pow这个运算，我们看这个函数
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
|
|
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
直接撸ECC，膜膜膜
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
 还有这操作
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
这个也字用的好 
|
|
|
|
|
|
|
